Metaheurystyki - algorytm genetyczny

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
Rozmiar populacji potomnej
Inicjalizacja
Selekcja następnego pokolenia
 
Warunek zatrzymania
lista (ciąg) n miast
20; 50; 100
2*rozmiar pokolenia rodzicielskiego
populacja początkowa wyznaczona w sposób losowy
pokolenie rodziców w całości zastępowane przez najlepszych potomków
po wykonaniu [10000; 25000; 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
0,9; 0,7; 0,5
Mutacja
Operator mutacji

Pm
zamiana lub wstawianie wylosowanych miast , inwersja (z równym prawdopodobieństwem)
0,1; 0,3; 0,5

Zadania

  1. Projekt obejmuje opracowanie programu rozwiązującego problem TSP oraz wykonanie testów w celu dostrojenia GA.
  2. Opracować program, w którym parametrami decyzyjnymi są:
    • rozmiar populacji rodziców [20, 50, 100],
    • prawdopodobieństwo krzyżowania i mutacji,
    • liczba iteracji.
  3. W badaniach symulacyjnych wybrać najlepszą wersję algorytmu dla problemu TSP75.
  4. Porównać działanie GA z algorytmem zachłannym NN oraz prostym hillclimbing.
  5. Sprawdzić działanie algorytmów dla problemów TSP30 i TSP50.

Arkusz z algorytmami NN i GA dla TSP75 do ściągnięcia tutaj.