O algorytmach ewolucyjnych

Oto krótki wstęp w którym opisane są najważniejsze elementy algorytmów ewolucyjnych. Dodatkowo pobieżnie przedstawiony jest przykład praktycznego wykorzystania tych algorytmów.

Jeśli chcesz zyskać pogłębioną widzę na temat całej rodziny algorytmów ewolucyjnych, znajdziesz uporządkowane wykłady na playliście Algorytmy ewolucyjne.

Czym są 'algorytmy ewolucyjne'? Najprościej rzecz ujmując jest to próba zasymulowania w pamięci komputera populacji jakiegoś gatunku. Na taką populację składają się dziesiątki, setki, tysiące... pojedynczych osobników. Osobniki te między sobą mogą się krzyżować, mogą również następować jakieś samoistne zmiany w strukturze pojedynczego osobnika (tzw. mutacja). W wyniku krzyżowania i mutacji powstają nowe osobniki. Ze względu na fakt, że populacja ma swój z góry narzucony maksymalny rozmiar część osobników należy z niej usunąć (ten krok nazywany jest selekcją). Oczywiście usuwane są te najmniej przystosowane... Cały ten proces (krzyżowanie, mutacja, selekcja) powtarzany jest w nieskończoność...

Powyższy opis dotyczył komputerowych algorytmów, ale na pierwszy rzut oka widać ogromną analogię do matki natury (krzyżowania chyba nie muszą tłumaczyć, mutacja może być spowodowana np. Czarnobylem, a selekcji może dokonywać wilk, który szybciej dogoni słabszą sarenkę...). I to chyba ona była wzorem dla twórców algorytmów ewolucyjnych...

Cóż z algorytmów ewolucyjnych jest dobrego dla kodera, a tym bardziej dla sztucznej inteligencji? Przyjmijmy, że mamy do rozwiązania 'problem komiwojażera' (krótka definicja tego zagadnienia: komiwojażer ma do odwiedzenia n miast, wszystkie są ze sobą połączone (oznacza to że z każdego komiwojażer może dojechać do wszystkich pozostałych). Należy znaleźć najkrótszą drogę jaką musi pokonać komiwojażer). W przypadku małej ilości miast problem wydaje się być łatwy. Wystarczy zestawić wszystkie permutacje miast, obliczyć otrzymane w ten sposób odległości i wybrać najkrótszą. Jednak problem komiwojażera jest NP-trudny (oznacza to że przy wzroście rozmiaru instancji (liczby miast) czas potrzeby na obliczenia rośnie wykładniczo (w przypadku problemu komiwojażera dodanie jednego, kolejnego miasta powoduje wielokrotne zwiększenie czasu obliczeń)) dlatego ten sposób rozwiązania na dłuższą metę jest niefajny...

Zaprzęgnijmy więc do roboty algorytmy ewolucyjne. Jako 'gatunek' możemy przyjąć trasę komiwojażera. Każdy osobnik będzie pamiętał jedną trasę. Takich osobników może być dowolna ilość (im więcej tym bardziej zróżnicowana populacja jednak kosztem dłuższych obliczeń). Na początku do każdego osobnika wpisujemy trasę zupełnie losową... I rozpoczynamy algorytm ewolucyjny. Krzyżowanie polega na wymianie pomiędzy dwoma osobnikami pewnych elementów tras (czyli podtras), natomiast mutacja może oznaczać wymianę w pojedynczym osobniku dwóch miast między sobą. Jeśli dodamy do tego krok selekcji, czyli wybór do następnej populacji osobników najlepiej przystosowanych (to znaczy takich które reprezentują trasy o najmniejszym koszcie) otrzymamy algorytm, który po pewnej liczbie kroków znajdzie nam całkiem niezłą trasę przez wszystkie miasta...

Niestety algorytmy ewolucyjne są tylko heurystyką. Oznacza to, że otrzymane rozwiązania nie zawsze będą najlepszymi możliwymi. W zamian za to otrzymujemy rozwiązania bardzo dobre w rozsądnym czasie.