Jak rozwiązać problem komiwojażera? Implementacja algorytmu genetycznego

Czas czytania: 4 minut

W poprzednim artykule omówiliśmy, jak powinien działać algorytm genetyczny rozwiązujący problem komiwojażera. Skoro posiadamy podstawy teoretyczne, pora zabrać się za praktykę. Spróbujemy zaimplementować rozwiązanie problemu komiwojażera za pomocą algorytmu genetycznego w języku TypeScript z użyciem frameworka Angular. Do dzieła!
Jeśli chcesz przetestować aplikację, która została tu omówiona, wejdź pod ten adres.

Definicja podstawowych klas

Osobnik – będzie to jedna z możliwych tras, odwiedzających wszystkie miasta. Połączenia pomiędzy poszczególnymi miastami w trasie będą zarazem jego genomem. Np.: takim osobnikiem (i jego genomem) może być trasa Ostrowiec->Kraków->Kielce->Warszawa.

Aby zdefiniować osobnika, potrzebujemy miast i tras.

Miasto

Nasza klasa „Miasto” jest bardzo prosta. Definiujemy sobie w niej tylko metodę pomocniczą getDistance która pozwala nam obliczyć w prosty sposób odległość do innego miasta. Korzystamy w tym miejscu ze wzoru Pitagorasa, który pewnie wszyscy doskonale znacie 🙂 Zdefiniowane atrybuty to pozycja miasta (x, y) oraz jego identyfikator (id). Identyfikatorem nie zaprzątaj sobie głowy – nie będzie nam potrzebny w rozwiązywaniu tego problemu 🙂

Trasa

Powyżej znajduje się definicja klasy Tour, która reprezentuje naszą trasę, przechodzącą przez wszystkie miasta. W linijce drugiej definiujemy sobie tablicę miast, które będziemy odwiedzali.Linijka 4 to getter pozwalający pobrać długość całej trasy. Będziemy używali tej metody do obliczenia funkcji przystosowania.

Funkcję przystosowania liczymy w linijce 19. Jak widzisz, mój drogi czytelniku, nie jest to nic skomplikowanego. Po prostu dzielimy 1 przez długość całej trasy. Zwykle będzie to bardzo mała liczba, ale najważniejsze aby rosła wraz z poprawą jakości trasy.

Powyżej znajduje się kolejny zbiór metod pomocniczych znajdujących się w klasie Tour. setCity pozwala nam podmienić miasto znajdujące się na konkretnej pozycji w trasie na inne. Metoda shuffle pozwala na wymieszanie miast znajdujących się w trasie. Wykorzystywana jest ona do generowania nowych tras w metodzie generate.

Populacja

Mamy już zdefiniowane miasta i trasy. Możemy więc zająć się populacją!

Podobnie jak trasa posiada listę miast, tak populacja posiada listę tras zdefiniowaną w linijce 2. Dalej mamy standardowe gettery. W konstruktorze tworzymy populację złożoną z określonej ilości tras. Metoda init generuje tę populację. Metoda saveTour natomiast pozwala podmienić trasę w populacji na inną. Za pomocą metody getFittiest możemy wybrać trasę (czyli osobnika) który jest najlepiej przystosowany w danej populacji.

Algorytm genetyczny

Omówiliśmy już wszystkie klasy pomocnicze. Pora zająć się wisienką na torcie, czyli implementacją samego algorytmu genetycznego :). Ze względu na wielkość tej klasy, będziemy ją omawiali fragmentami.

Na początku powyższego listingu, jak zwykle, mamy zadeklarowane prywatne atrybuty klasy. _mutationRate jest to domyślne prawdopodobieństwo zajścia mutacji (0,015*100%=1.5%). _tournamentSize jest to ilość tras, jaką będziemy poddawali „turniejowi”. (Jeśli nie pamiętasz, o co chodzi, przypomnij sobie poprzedni artykuł, w którym omawialiśmy selekcję turniejową.

Gwoli wyjaśnienia wymaga zmienna selectedStrategy typu CrossoverStrategy. Cóż to takiego jest? Otóż, jak doskonale wiemy, istnieje wiele różnych sposobów przeprowadzania krzyżowania. Wobec tego, wykorzystaliśmy w tym miejscu wzorzec projektowy Strategia.Zastosowanie wzorca pozwala nam w prosty sposób rozszerzyć aplikację o inne algorytmy krzyżowania. W konstruktorze do wspieranych strategii dodajemy strategię PMX. Aby dodać wsparcie nowej strategii, wystarczy stworzyć klasę rozszerzającą CrossoverStrategy i stworzyć obiekt tej klasy w konstruktorze Genetic.

Następnie mamy metodę evolvePopulation, która jako argumenty przyjmuje: populację, wielkość pojedynczego turnieju oraz współczynnik mutacji. Wartości tych zmiennych są przypisywane do prywatnych atrybutów. Następnie tworzona jest nowa, pusta populacja.

Pętla for w linijce 17 przechodzi po wszystkich elementach populacji i wykonuje selekcję oraz krzyżowanie. Po krzyżowaniu wykonywana jest mutacja.

Metoda zwraca nową lepszą ewolucyjnie populację.

Selekcja i krzyżowanie

Metoda performSelectionAndCrossover przyjmuje trzy argumenty: populacja, nowa populacja oraz index potomka, którego aktualnie przetwarzamy.

Najpierw tworzymy rodziców. Przeprowadzamy dwa razy selekcję turniejową aby wyznaczyć każdego z rodziców.

W kolejnym kroku wykonujemy krzyżowanie. Służą do tego dwie metody pochodzące od omówionej wcześniej zmiennej selectedStrategy.
prepareStrategyData – przygotowuje wszystkie dane, które są potrzebne do wykonania krzyżowania potomków. W przypadku strategii PMX jest to wylosowanie fragmentu genomu, który zostanie wycięty.
generateTourFromParents – wykonuje właściwe krzyżowanie.

Na samym końcu lepszy potomek staje się częścią nowej populacji. Gorszy niestety musi zostać unicestwiony …

Selekcja turniejowa

Zastosowany algorytm selekcji turniejowej jest niezwykle prosty. Najpierw tworzymy nową populację o rozmiarze turnieju. Następnie losujemy osobników, którzy wezmą udział w turnieju. Jako wynik selekcji zwracamy najlepszego osobnika tej populacji.

Krzyżowanie PMX

Pora zająć się jedną z najważniejszych części algorytmu genetycznego, czyli krzyżowaniem :).

Atrybuty klasy x1 i x2 to punkty: początkowy i końcowy w ramach których będziemy „wycinali” genom.

W metodzie prepareStrategyData dokonujemy wyboru tych punktów.

Kolejną metodą którą omówimy jest generateTourFromParents. Przyjmuje ona jako argument osobników, którzy staną się rodzicami dla nowych potomków. Wewnątrz tej metody uruchamiamy metodę performCrossoverForChildren. Generujemy dwóch potomków.

performCrossoverForChildren zawiera praktycznie całą logikę algorytmu PMX. Najpierw tworzymy sobie kopię tablicy z rodzica pierwszego, za pomocą Array.from. Następnie wykonujemy pierwszą część algorytmu krzyżowania PMX, czyli kopiujemy fragment znajdujący się pomiędzy wylosowanymi wcześniej punktami x1 i x2 z jednego rodzica do drugiego. Jednocześnie uzupełniamy sobie tablicę mappingForChildren, w której zapiszemy jakie elementy przeszły w jakie podczas zamiany.

Pojawia się problem:
Rozważmy następujące genomy:

Rodzic 1: * * * 4 6 5 * * *
Rodzic 2: * * * 6 5 4 * * *

Zostaną utworzone następujące mapowania: (dla dziecka nr 1. Dla dziecka nr 2 będą one analogiczne, tyle że odwrotne)
4->6
6->5
5->4

Zauważyłeś pewną ciekawą rzecz? Wykonując zamiany wg tych mapowań, dokonujemy odkrycia dwóch bardzo nieciekawych zależności:
a) zależność przechodnia – skoro czwórka przechodzi w szóstkę i szóstka w piątkę, a piątka w czwórkę to czwórka przechodzi w czwórkę.
b) cykl – wynikający z tej zależności -> czwórka przechodzi w czwórkę.
Obydwie zależności są niedopuszczalne. Dlaczego? Ponieważ doprowadzą one do „zakleszczenia się” naszego algorytmu. (spójrz na pętle while w linijkach 48/54) Właśnie dlatego używamy dwóch metod pomocniczych: eliminateTransitives – która eliminuje zależności tranzytywne ( oraz eliminateCycles – która eliminuje cykle z mapowań.

Po wyeliminowaniu wszystkich niepożądanych cech mapowania możemy go użyć. Służą do tego dwie kolejne pętle for. Znajdująca się w nich pętla while szuka takich elementów w dziecku, które znajdują się w mapowaniu. Następnie dokonywana jest wymiana. Wymian dokonujemy dopóty, dopóki w dziecku znajdują się takie elementy, które podlegają wymianie.

Algorytmem służącym do eliminacji cykli oraz zależności przechodnich zajmiemy się w innym artykule.

Mutacja

Mutacja w niniejszym algorytmie jest bardzo prostym operatorem. Jako argument przyjmujemy trasę. dla każdego elementu tej trasy losujemy liczbę (z zakresu od 0 do 1) i sprawdzamy czy jest ona mniejsza niż współczynnik mutacji. Jesli tak – losowo dokonujemy zamiany dwóch elementów trasy ze sobą (dokładny opis algorytmu znajduje się w artykule wprowadzającym do tego tematu).

Stworzyliśmy pierwszy działający algorytm genetyczny!

Sukces 🙂 Stworzyliśmy algorytm genetyczny, który z dużą dozą prawdopodobieństwa wyznaczy w miarę optymalną trasę rozwiązującą problem komiwojażera. Kompletna aplikacja dostępna jest na Githubie. (Wersja omówiona w tym artykule znajduje się na branchu artykul_1. Na branchu master może znajdować się nieco odmienna wersja).

Przypominam, że możesz przetestować omówiony powyżej program bez instalowania kompletnego środowiska. Jest on dostępny pod tym adresem.

Masz jakieś pytania, wątpliwości? Może popełniłem gdzieś błąd? Śmiało – napisz komentarz 🙂

Pozdrawiam i do następnego razu 🙂

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.