Algorytmy genetyczne – wyjaśnienie
Ewolucja stworzyła oczy, skrzydła i mózgi bez projektanta, po prostu zachowując to, co działa, i wprowadzając zmiany. Algorytm genetyczny pożycza ten pomysł, by rozwiązywać problemy na komputerze. Nie musi rozumieć problemu, wystarczy, że odróżni lepszą odpowiedź od gorszej, i dlatego jest potężnym narzędziem, gdy przestrzeń możliwych odpowiedzi jest zbyt duża i zbyt dziwna, by przeszukać ją w jakikolwiek inny sposób.
Idea
W latach sześćdziesiątych i siedemdziesiątych John Holland z Uniwersytetu Michigan przekształcił teorię Darwina w algorytm, opisany w jego książce Adaptation in Natural and Artificial Systems z 1975 roku. Mniej więcej w tym samym czasie Ingo Rechenberg i Hans-Paul Schwefel w Niemczech opracowali strategie ewolucyjne do projektowania inżynierskiego. Wspólny przepis: utrzymuj populację rozwiązań kandydujących, oceniaj je, pozwól lepszym rozmnażać się ze zmiennością i powtarzaj przez wiele pokoleń.
Geny i populacja
Każdego kandydata opisuje chromosom, czyli lista genów. Na placu zabaw genami rakiety są jej pchnięcia, po jednym na każdą chwilę lotu; w innych problemach mogą to być bity liczby, kolejność miast na trasie albo rozmiary części w projekcie. Pierwsze pokolenie jest losowe, co oznacza, że szeroko bada przestrzeń odpowiedzi, ale prawie nie zawiera dobrych.
Funkcja przystosowania
Przystosowanie to jedna liczba, która mówi, jak dobry jest kandydat, i jedyna rzecz, jaką algorytm wie o problemie. W przypadku rakiet najbardziej nagradza ono wczesne dotarcie do celu, potem zakończenie lotu blisko celu, a karze rozbicie się. Dobrze dobrana funkcja przystosowania płynnie prowadzi poszukiwania ku dobrym odpowiedziom; niedbała nagradza nie to, co trzeba, a algorytm wykorzysta każdą furtkę, jaką pozostawi.
Selekcja
Rodziców wybiera się tak, by lepiej przystosowani kandydaci mieli więcej dzieci, ale słabsi nadal mają szansę, bo ich geny mogą zawierać przydatne fragmenty. Selekcja ruletkowa daje każdemu kandydatowi wycinek koła proporcjonalny do jego przystosowania; selekcja turniejowa losuje kilku i wybiera najlepszego z nich. Silniejsza selekcja przyspiesza postęp, ale też upodabnia populację, co może zbyt wcześnie zakończyć poszukiwania.
Krzyżowanie i mutacja
Krzyżowanie łączy dwoje rodziców: tutaj dziecko bierze pierwszą część genów od jednego rodzica, a resztę od drugiego, więc wczesne manewry jednej rakiety mogą spotkać się z późnymi manewrami innej. Mutacja losowo zastępuje kilka genów. Krzyżowanie na nowo łączy to, co populacja już ma; mutacja wnosi to, czego nigdy nie miała. Twierdzenie Hollanda o schematach opisuje, jak krótkie cegiełki dobrych genów rozprzestrzeniają się w populacji pod wpływem tego połączenia selekcji i rekombinacji.
Elitaryzm, eksploracja i eksploatacja
Kopiowanie kilku najlepszych kandydatów bez zmian do następnego pokolenia, czyli elitaryzm, gwarantuje, że najlepsza odpowiedź nigdy nie zginie. Każdy algorytm genetyczny musi równoważyć eksplorację, czyli próbowanie nowych obszarów przestrzeni poszukiwań, i eksploatację, czyli dopracowywanie tego, co już jest dobre. Przy zbyt małej zmienności populacja zbiega do jednej przeciętnej odpowiedzi; przy zbyt dużej nigdy się nie ustala. Wielkość populacji, współczynnik mutacji i presja selekcyjna to pokrętła, którymi ustawia się tę równowagę.
Optima lokalne
Algorytm genetyczny kieruje się wyłącznie przystosowaniem, więc można go zwieść. Gdy droga do najlepszej odpowiedzi prowadzi najpierw przez gorsze, populacja wspina się na najbliższe wzniesienie i na nim zostaje: to optimum lokalne. Za przesuniętymi ścianami na placu zabaw rakiety, które rozbijają się pod celem, dostają lepszą ocenę niż te, które skręcają, by znaleźć przejście, więc populacja gromadzi się przy ścianie. Pomagają większe populacje, silniejsza mutacja, utrzymywanie różnorodności populacji, a przede wszystkim lepsza funkcja przystosowania.
Wypróbuj sam
Otwórz plac zabaw algorytmu genetycznego, aby rakiety ewoluowały wokół jednej ściany, szczeliny, filarów, przesuniętych ścian albo ścian narysowanych przez ciebie. Zmieniaj populację, współczynnik mutacji, czas życia i metodę selekcji, włączaj i wyłączaj elitaryzm i śledź na wykresie, jak szybko rośnie odsetek rakiet docierających do celu, albo dlaczego nie rośnie.
Często zadawane pytania
Czy algorytm genetyczny to rodzaj sztucznej inteligencji?
Należy do szerszej dziedziny SI i uczenia maszynowego jako metoda przeszukiwania i optymalizacji. Nie uczy się na przykładach jak sieć neuronowa; ulepsza rozwiązania kandydujące metodą prób i selekcji. Obie metody często się łączy, na przykład ewoluując strukturę lub wagi sieci neuronowych; takie podejście nazywa się neuroewolucją.
Czy algorytm genetyczny zawsze znajduje najlepszą odpowiedź?
Nie. To heurystyka: zwykle znajduje dobre odpowiedzi na trudne problemy, ale nie gwarantuje znalezienia najlepszej ani nie dowodzi, jak blisko niej jest. W problemach, dla których metoda dokładna jest wystarczająco szybka, lepsza jest ta metoda.
Czym różni się algorytm genetyczny od strategii ewolucyjnych?
Jedno i drugie to algorytmy ewolucyjne. Klasyczne algorytmy genetyczne kładą nacisk na krzyżowanie chromosomów przypominających ciągi znaków; strategie ewolucyjne działają głównie przez mutację liczb rzeczywistych i często same dostosowują rozmiar mutacji w trakcie działania. Nowoczesne metody łączą pomysły z obu.
Dlaczego rakiety są na początku takie niezdarne?
Ich pierwsze geny to całkowicie losowe pchnięcia, które średnio się znoszą, więc rakiety dryfują. Dopiero gdy selekcja zachowa rzadkie rakiety, które przypadkiem pchały się mniej więcej we właściwą stronę, a krzyżowanie połączy ich dobre odcinki, pojawiają się skoordynowane loty.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz plac zabaw algorytmu genetycznego