🚚 Optymalizator tras łańcucha dostaw — algorytm genetyczny w akcji

Algorytm genetyczny (GA) to heurystyka przeszukiwania inspirowana doborem naturalnym. Zamiast wyprowadzać rozwiązanie analitycznie, GA utrzymuje populację kandydujących rozwiązań — tutaj kompletnych tras dostaw — i wielokrotnie stosuje selekcję, krzyżowanie i mutację, by wyhodować nowych kandydatów. Osobniki lepiej przystosowane (krótsze trasy) mają większą szansę przekazać swoją strukturę kolejnemu pokoleniu. Przez wiele pokoleń średnia jakość populacji rośnie, mimo że żadna pojedyncza trasa nigdy nie została rozwiązana bezpośrednio, ponieważ przeszukiwanie eksploruje wiele regionów przestrzeni rozwiązań równolegle i wciąż rekombinuje to, co działa.

Każda trasa jest permutacją przystanków klientów, więc zwykłe krzyżowanie produkowałoby nieprawidłowe trasy z powtórzonymi lub brakującymi klientami. Ta symulacja używa krzyżowania porządkowego (OX): ciągły fragment przystanków jest kopiowany z rodzica A na tych samych pozycjach, a pozostałe przystanki są wypełniane z rodzica B w kolejności, w jakiej się pojawiają, pomijając te już umieszczone. Gwarantuje to prawidłową permutację. Mutacja to mutacja zamiany: z prawdopodobieństwem równym współczynnikowi mutacji dwa losowo wybrane przystanki w trasie zamieniają się miejscami, odchylając trasę od jej obecnego kształtu, nigdy nie tworząc nieprawidłowej trasy.

Selekcja, krzyżowanie i mutacja są wszystkie stochastyczne, więc pokolenie może przypadkiem wyprodukować populację, która jest średnio gorsza niż poprzednia — krzyżowanie może rozbić dobrą trasę, a mutacja może uszkodzić niemal optymalną. Elitaryzm kopiuje pojedynczą najlepszą trasę z bieżącego pokolenia bezpośrednio do następnego pokolenia, całkowicie niezmienioną. Gwarantuje to, że najlepsza dotąd znaleziona odległość nigdy nie może się pogorszyć z pokolenia na pokolenie, dlatego krzywa „najlepszej odległości” na wykresie jest zawsze płaska lub opadająca, nigdy rosnąca.

To mały wariant trasowania pojazdów problemu komiwojażera (TSP): znajdź najkrótszą zamkniętą trasę zaczynającą i kończącą się w magazynie, która odwiedza każdego klienta dokładnie raz. TSP jest NP-trudny — liczba możliwych tras dla N klientów wynosi (N−1)!/2, co dla zaledwie 16 klientów przekracza 650 miliardów. Algorytmy dokładne (branch-and-bound, programowanie dynamiczne) mogą rozwiązać skromne przypadki, ale słabo się skalują. Algorytmy genetyczne, wraz z innymi metaheurystykami, jak symulowane wyżarzanie i optymalizacja mrowiskowa, wymieniają gwarancję optymalności na trasę, która jest zwykle bardzo dobra i znaleziona w ułamku czasu — dokładnie taki kompromis stosuje prawdziwe oprogramowanie logistyczne dla flot z dziesiątkami lub setkami przystanków.

Jeśli cała populacja zbiega ku trasom dzielącym tę samą podstawową strukturę, krzyżowanie między dwoma podobnymi rodzicami głównie odtwarza tę samą strukturę, a małe mutacje zamiany rzadko wystarczają, by uciec z lokalnie dobrej, ale globalnie nieoptymalnej pętli — na przykład trasy z jedną krawędzią krzyżującą się, której można by uniknąć. Nazywa się to przedwczesną zbieżnością: różnorodność w populacji zapada się, zanim zostanie znaleziona najlepsza możliwa trasa. Podniesienie współczynnika mutacji, zwiększenie rozmiaru populacji lub użycie nowej mapy do porównania przebiegów to sposoby, by zobaczyć ten kompromis między eksploracją (różnorodnością) a eksploatacją (udoskonalaniem tego, co już działa).

Selekcja turniejowa wybiera mały losowy podzbiór populacji (turniej, tutaj o rozmiarze 3) i wybiera najlepiej przystosowanego członka tego podzbioru jako rodzica. Jest prosta, szybka, a jej presja selekcyjna jest łatwa do dostrojenia poprzez rozmiar turnieju: większy turniej sprawia, że bardziej prawdopodobne jest, że pojedynczy najlepszy osobnik zdominuje reprodukcję (szybsza zbieżność, wyższe ryzyko przedwczesnej zbieżności), podczas gdy mniejszy turniej utrzymuje więcej różnorodności. Unika to niektórych pułapek selekcji proporcjonalnej do przystosowania (koło ruletki), gdzie jedna trasa o nietypowo krótkiej odległości może natychmiast zdominować całą populację.

Większa populacja eksploruje więcej przestrzeni permutacji tras na pokolenie i jest mniej narażona na utratę użytecznej różnorodności przez losowy dryf, ale każde pokolenie kosztuje więcej ocen odległości. Wyższy współczynnik mutacji wprowadza więcej losowości, pomagając uciec z optimów lokalnych, ale też częściej zaburzając dobre trasy, co może spowolnić zbieżność lub nawet tymczasowo pogorszyć średnią populacji (elitaryzm chroni pojedynczą najlepszą trasę niezależnie). W praktyce istnieje słodki punkt — mniej więcej rozmiary populacji rzędu dziesiątek do niskich setek i współczynniki mutacji rzędu kilku procent na gen zwykle zbiegają najszybciej dla problemów tej wielkości.