Pokolenie
Dotarło do celu
Najszybsze dotarcie
Najmniejsza odległość
  • Lot trwa
  • Dotarło do celu
  • Rozbite
  • Najlepszy lot ostatniego pokolenia
  • Dotarło do celu
  • Rozbite

Więcej o algorytmach genetycznych

Plac zabaw algorytmu genetycznego

Algorytm genetyczny rozwiązuje problem tak, jak ewolucja kształtuje żywe istoty: wypróbuj wiele losowych odpowiedzi, zachowaj lepsze, wymieszaj je, losowo zmień kilka fragmentów i powtarzaj. Tutaj odpowiedziami są rakiety. Każda wykonuje listę losowych pchnięć i nic więcej, więc na początku miotają się bez celu. Naciśnij Start i obserwuj, jak populacja poprawia się z pokolenia na pokolenie, aż większość rakiet zgrabnym łukiem omija ściany i dolatuje do celu, choć nikt nie mówi im, dokąd mają lecieć. Naciśnij Start i obserwuj, jak populacja rakiet próbuje dotrzeć do zielonego celu. Każda rakieta wykonuje tylko to, co zapisano w jej genach: listę małych pchnięć, po jednym na każdą chwilę lotu. Po każdym locie rakiety, które podleciały najbliżej, a przede wszystkim te, które dotarły do celu, mają największą szansę zostać rodzicami następnego pokolenia; ich geny są mieszane, a kilka zmienia się losowo. Następne pokolenie pomija resztę lotu. Przeciągnij po polu, aby narysować ścianę, i kliknij ścianę, aby ją usunąć.

Jak to działa

  1. Wybierz przeszkody albo przeciągnij po polu, aby narysować własne ściany, i ustaw populację, współczynnik mutacji oraz czas życia.
  2. Naciśnij Start i obserwuj lot każdego pokolenia; Następne pokolenie pomija resztę lotu.
  3. Śledź na kafelkach i wykresie odsetek rakiet docierających do celu i wypróbuj inne współczynniki mutacji oraz metody selekcji.

Jak ewoluują rakiety

Każda rakieta nosi geny: jedno małe pchnięcie na każdą chwilę lotu. Geny pierwszego pokolenia są losowe. Po locie każda rakieta otrzymuje ocenę przystosowania: najwyższą za wczesne dotarcie do celu, w pozostałych przypadkach tym wyższą, im bliżej celu skończyła, a po rozbiciu się dzieloną przez dziesięć. Rodzice następnego pokolenia są wybierani losowo, ale lepiej przystosowane rakiety mają większą szansę na wybór. Każde dziecko bierze pierwszą część genów od jednego rodzica, a resztę od drugiego, a kilka genów zostaje zastąpionych losowymi pchnięciami: to mutacje. Z pokolenia na pokolenie dobre plany lotu rozprzestrzeniają się i ulepszają.

Co zmieniają ustawienia

Większa populacja bada naraz więcej planów lotu i rzadziej utyka, ale każde pokolenie trwa dłużej. Współczynnik mutacji równoważy eksplorację i zachowywanie tego, co działa: bez mutacji populacji szybko kończą się nowe pomysły, a przy zbyt dużej zapomina ona dobre loty szybciej, niż potrafi je znaleźć. Selekcja ruletkowa wybiera rodziców proporcjonalnie do przystosowania, a turniej bierze najlepszą z trzech losowych rakiet, co jest mniej wrażliwe na to, jak przeskalowano przystosowanie. Elitaryzm kopiuje najlepszą rakietę bez zmian do następnego pokolenia, więc najlepszy wynik nigdy się nie pogarsza.

Często zadawane pytania

Dlaczego rakiety utykają za przesuniętymi ścianami?

Ich przystosowanie mierzy odległość w linii prostej do celu, więc rakieta, która wlatuje w ścianę pod celem, dostaje lepszą ocenę niż taka, która odlatuje, by znaleźć przejście. Populacja gromadzi się w tym ślepym zaułku, czyli w optimum lokalnym. Większa populacja, więcej mutacji lub selekcja turniejowa pomagają się z niego wydostać, a przystosowanie mierzące rzeczywistą drogę wokół ścian pozwoliłoby uniknąć pułapki. Wybór dobrej funkcji przystosowania to najtrudniejsza część stosowania algorytmu genetycznego.

Czy tak działa ewolucja w przyrodzie?

W zarysie tak: zmienność wynikająca z mutacji i rekombinacji, dziedziczenie genów i selekcja najlepiej przystosowanych to składniki teorii Darwina. Różnice są jednak duże. Przyroda nie ma celu ani wzoru na przystosowanie, tylko przetrwanie i rozmnażanie, a prawdziwe genomy budują ciała w procesie rozwoju, zamiast wyliczać czynności.

Do czego używa się algorytmów genetycznych?

Do problemów z ogromną przestrzenią możliwych odpowiedzi i łatwym sposobem oceny kandydata: kształtowania anten, skrzydeł i części samochodowych, układania harmonogramów, dostrajania ustawień innych algorytmów, projektowania sieci neuronowych oraz tworzenia sztuki i strategii gier. Słynnym przykładem jest wyewoluowana antena NASA na satelitach ST5 z 2006 roku.

Dlaczego najlepsza rakieta czasem leci gorzej w następnym pokoleniu?

Bez elitaryzmu najlepsza rakieta nie jest kopiowana: jej geny przetrwają tylko zmieszane z innymi i być może zmutowane, więc następne pokolenie może utracić dokładnie ten lot. Przy włączonym elitaryzmie najlepsza rakieta zostaje zachowana bez zmian, a najlepszy wynik nigdy się nie pogarsza.

Czy coś jest wysyłane na serwer?

Nie. Rakiety latają i ewoluują w twojej przeglądarce, a narysowane przez ciebie ściany pozostają w pamięci lokalnej tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora