Algorytmy genetyczne

Symetryczny problem komiwojażera (TSP)

Cel

Celem ćwiczenia jest opanowanie umiejętności doboru zaawansowanych elementów GA.

Opis problemu

Mamy n miast o współrzędnych (xi,yi), położonych w kwadracie o boku 100 jednostek. Należy tak ustalić kolejność odwiedzin miast przez komiwojażera, by odległość przezeń przebyta była minimalna przy założeniu, że miasto można odwiedzić tylko jeden raz oraz że wracamy do miasta początkowego

Obliczenie odległości między miastami
Odl(i,j)=int(sqrt((xi- xj)2+(yi- yj )2)+0.51)

Struktura zbioru testowego
Mamy 3 zbiory testowe TSP30.TXT, TSP50.TXT, TSP75.TXT zawierające dane o problemach odpowiednio dla 30, 50 i 75 miast. Każdy zbiór zorganizowany jest następująco:

liczba miast
najlepszy wynik osiągnięty przez znane algorytmy (tutaj - wynik optymalny),
współrzędne pierwszego miasta
...
współrzędne i-tego miasta
...
współrzędne ostatniego miasta

Algorytm rozwiązujący - algorytm genetyczny

Funkcja dopasowania
Postać

długość trasy komiwojażera lub wartość wyliczona na jej podstawie
Schemat i populacja
Reprezentacja
Rozmiar populacji rodziców
Inicjalizacja
Selekcja następnego pokolenia
Warunek zatrzymania
lista (ciąg) n miast
10 - 200
populacja początkowa wyznaczona w sposób losowy
pokolenie rodziców w całości zastępowane przez potomków
po wykonaniu [1000 - 50000]/ileDzieci iteracji
Reprodukcja
Sposób wyboru rodziców do krzyżowania
Operator krzyżowania
Pc
metoda proporcjonalna (ruletki) lub turniejowa
operator losowy z uzupełnianiem
1,0 - 0,5
Mutacja
Operator mutacji
Pm
zamiana (można spróbować wstawianie) wylosowanych miast oraz inwersja z równym prawdopodobieństwem (czyli po 0,5)
0,05 - 0,80 (to całościowe prawd. - dotyczy razem obu operatorów)

Zadania

  1. Zarządzajacy projektem sporządza specyfikację, rozdziela zadania między członków zespołu i koordynuje wykonanie projektu, który obejmuje opracowanie programu rozwiązującego TSP oraz wykonanie testów w celu dostrojenia GA.
  2. Opracować program, w którym parametrami decyzyjnymi są:
    • rozmiar populacji rodziców [10, 25, 50, 100, 200],
    • prawdopodobieństwo krzyżowania i mutacji,
    • sposób selekcji do krzyżowania: ruletka lub turniej dwuelementowy (jeśli prowadzący zajęcia nie wskaże inaczej, stosujemy tylko turniej. (czyli nie badamy, który sposób jest lepszy),
    • liczba iteracji: [1000, 5000, 10000, 25000, 50000]/ileDzieci.
  3. W badaniach symulacyjnych wybrać najlepszą wersję algorytmu dla problemu TSP30 (I zespół) albo TSP50 (II zespół) albo TSP75 (III zespół) albo TSP60 (IV zespół - o ile potrzebny, ze względu na liczbe studentów w grupie projektowej)..
  4. Sprawdzić działanie opracowanego algorytmu dla pozostałych dwóch (trzech) problemów (sprawdzamy tylko - nie dopieramy parametrów), wyniki konfrontujemy z wynikami otrzymanymi z grup, którre opracowują pozostałe problemy..
  5. Porównać działanie GA z algorytmem zachłannym NN.
  6. Poszczególne zespoły piszą sprawozdanie z wykonania swoich zadań/zadania.
  7. Zarządzajacy projektem przedstawia końcowe sprawozdanie wraz z propozycją ocen zespołów.