🧬 Algorytm genetyczny

Algorytm genetyczny to technika przeszukiwania i optymalizacji naśladująca dobór naturalny. Utrzymuje populację rozwiązań kandydujących, ocenia każde z nich funkcją przystosowania i wielokrotnie krzyżuje najlepsze osobniki, stosując krzyżowanie i mutację. Przez wiele pokoleń populacja dąży do rozwiązań o wysokim przystosowaniu.

Ewoluuje losowy ciąg liter w stronę frazy docelowej, domyślnie METHINKS IT IS LIKE A WEASEL. Przystosowanie to po prostu odsetek pozycji znaków zgodnych z celem. Odtwarza to słynny program Weasel Richarda Dawkinsa, który pokazuje, jak selekcja kumulatywna osiąga cel znacznie szybciej niż ślepe losowe tasowanie.

Funkcja Rastrigina to standardowy test optymalizacyjny zdefiniowany na siatce 2D od minus pięciu do pięciu na każdej osi. Ma jedno globalne optimum w punkcie zerowym, otoczone wieloma zwodniczymi optimami lokalnymi ułożonymi w regularną kratę. Jej pofałdowana powierzchnia czyni ją trudnym testem pokazującym, jak populacja unika utknięcia.

Aby wybrać rodzica, algorytm losowo wybiera pięć osobników z populacji i zatrzymuje tego o najwyższym przystosowaniu. Powtarzanie tego procesu faworyzuje lepiej przystosowane osobniki, wciąż dając słabszym okazjonalną szansę, co pomaga utrzymać różnorodność. Presja selekcyjna rośnie wraz z rozmiarem turnieju, ustalonym w tej symulacji na pięć.

Krzyżowanie łączy dwoje rodziców w potomka. W trybie napisu używa jednego losowego punktu cięcia, biorąc początek od jednego rodzica, a resztę od drugiego. Mutacja następnie losowo zamienia znaki z prawdopodobieństwem równym współczynnikowi mutacji. W trybie krajobrazu potomek to ważona mieszanka współrzędnych rodziców plus niewielkie losowe drgania skalowane współczynnikiem mutacji.

Współczynnik mutacji, regulowany od 1 do 30 procent, określa, jak często każdy gen jest losowo zmieniany przy tworzeniu potomstwa. Niskie wartości powodują szybką zbieżność populacji, ale grożą utknięciem w optimum lokalnym. Wysokie wartości wprowadzają więcej różnorodności i pomagają uciec z pułapek, ale nadmierna mutacja zamienia przeszukiwanie w nieefektywne błądzenie losowe.

Nazywa się to elitaryzmem. Dwa osobniki o najwyższym przystosowaniu są kopiowane bezpośrednio do następnego pokolenia bez krzyżowania i mutacji. Elitaryzm gwarantuje, że najlepsze dotąd znalezione rozwiązanie nigdy nie zostanie utracone, więc krzywa najlepszego przystosowania nigdy nie maleje. Pozostałe miejsca wypełniają selekcja, krzyżowanie i mutacja.

W trybie napisu różnorodność mierzy się jako średnią liczbę odrębnych znaków występujących na każdej pozycji w całej populacji. Wysoka różnorodność na początku oznacza, że populacja wciąż szeroko eksploruje; gdy zbiega do celu, różnorodność spada w stronę jedynki, co oznacza, że większość osobników ma już te same litery.

To wierny model kluczowego mechanizmu — selekcji działającej na dziedziczną zmienność — ale celowo uproszczony. Prawdziwa ewolucja nie ma stałego celu, globalnej funkcji przystosowania ani tak bogatej genetyki. Zadanie Weasel jest w szczególności ilustracją dydaktyczną selekcji kumulatywnej, a nie twierdzeniem o tym, jak ewoluują organizmy.

Stosuje się je wszędzie tam, gdzie przestrzeń przeszukiwania jest ogromna, a gradienty niedostępne lub niewiarygodne, w tym w projektowaniu samolotów i anten, planowaniu fabryk i harmonogramów, układach scalonych, dostrajaniu hiperparametrów uczenia maszynowego i optymalizacji strategii finansowych. NASA słynnie wykorzystała wyewoluowane projekty anten kosmicznych o niekonwencjonalnych, lecz bardzo skutecznych kształtach.