Algorytm genetyczny

Co to jest

Naturalna ewolucja może być modelowana jako gra, w której nagrodą dla organizmu, który dobrze gra w życie, jest przekazanie jego materiału genetycznego następcom i jego dalsze przetrwanie. ^[2] W naturalnej ewolucji to, jak dobrze radzi sobie osobnik, zależy od tego, z kim współpracuje i z kim konkuruje, a także od środowiska. Algorytmy genetyczne są symulacją naturalnej selekcji na populacji kandydatów na rozwiązanie problemu optymalizacyjnego (chromosomów, osobników, istot lub fenotypów).

Kandydaci są oceniani i krzyżowani w celu uzyskania dobrych rozwiązań. Takie rozwiązania mogą zająć dużo czasu i nie są oczywiste dla człowieka. Faza ewolucji jest rozpoczynana z populacją losowo wygenerowanych istot. W każdym pokoleniu oceniana jest kondycja każdego osobnika w populacji. Niektóre z nich są losowo wybierane z bieżącej populacji (na podstawie ich kondycji) i modyfikowane (rekombinowane i ewentualnie losowo mutowane), aby utworzyć nową populację. Cykl powtarza się z tą nową populacją. Algorytm kończy się albo po przejściu określonej liczby pokoleń, albo po osiągnięciu dobrego poziomu kondycji dla populacji. Jeśli algorytm zakończył się z powodu osiągnięcia maksymalnej liczby pokoleń, nie musi to oznaczać, że osiągnięto dobry poziom kondycji.

Zaprogramuj to na komputerze

Pseudokod to:

1. Inicjalizacja: Tworzone są pewne możliwe rozwiązania; bardzo często będą one miały losowe wartości
2. Ocena: Funkcja fitness punktuje każde rozwiązanie; wynik będzie liczbą, która mówi, jak dobrze dane rozwiązanie rozwiązuje problem.
3. Kolejne kroki są wykonywane do momentu spełnienia wymogu zatrzymania:
1. Selekcja: Wybierz rozwiązania/indywidualności do następnej iteracji
2. Rekombinacja: Połącz wybrane rozwiązania
3. Mutacja: Losowo zmieniaj nowo utworzone rozwiązania
4. Ocena: Zastosuj funkcję fitness, patrz krok 2.
5. Jeśli wymóg zatrzymania nie jest spełniony, należy ponownie rozpocząć od kroku wyboru.

Przykład

Powyższy opis jest abstrakcyjny. Pomoże w tym konkretny przykład.

Aplikacje

Ogólnie rzecz biorąc

Algorytmy genetyczne są dobre w rozwiązywaniu problemów, które obejmują planowanie i układanie harmonogramów. Znalazły one również zastosowanie w inżynierii. Są one często używane do rozwiązywania globalnych problemów optymalizacyjnych.

Jako ogólna zasada, algorytmy genetyczne mogą być użyteczne w domenach problemowych, które mają złożony krajobraz kondycji, ponieważ mieszanie jest zaprojektowane tak, aby odsunąć populację od lokalnych optimów, w których tradycyjny algorytm wspinaczkowy mógłby utknąć. Powszechnie stosowane operatory krzyżowania nie mogą zmienić żadnej jednolitej populacji. Sama mutacja może zapewnić ergodyczność całego procesu algorytmu genetycznego (postrzeganego jako łańcuch Markowa).

Przykłady problemów rozwiązywanych przez algorytmy genetyczne to: lustra zaprojektowane do kierowania światła słonecznego do kolektora słonecznego, anteny zaprojektowane do odbierania sygnałów radiowych w przestrzeni kosmicznej, metody chodzenia dla figur komputerowych, optymalne projektowanie ciał aerodynamicznych w złożonych polach przepływu.

W swoim podręczniku projektowania algorytmów, Skiena odradza algorytmy genetyczne dla jakichkolwiek zadań: "Jest dość nienaturalne modelowanie aplikacji w kategoriach operatorów genetycznych, takich jak mutacja i krzyżowanie na łańcuchach bitowych. Pseudobiologia dodaje kolejny poziom złożoności pomiędzy tobą a twoim problemem. Po drugie, algorytmy genetyczne zajmują bardzo dużo czasu na nietrywialnych problemach. [...] Analogia z ewolucją - gdzie znaczący postęp wymaga [sic] milionów lat - może być całkiem trafna. [...] Nigdy nie spotkałem się z żadnym problemem, w którym algorytmy genetyczne wydawałyby mi się właściwym sposobem jego rozwiązania. Co więcej, nigdy nie widziałem żadnych wyników obliczeń zgłoszonych przy użyciu algorytmów genetycznych, które zrobiły na mnie pozytywne wrażenie. Trzymaj się symulowanego wyżarzania dla swoich potrzeb heurystycznego wyszukiwania voodoo."

Gry planszowe

Gry planszowe stanowią bardzo istotną część dziedziny algorytmów genetycznych w zastosowaniu do problemów teorii gier. Wiele z wczesnych prac nad inteligencją obliczeniową i grami było skierowanych na klasyczne gry planszowe, takie jak tic-tac-toe,^[3] szachy i warcaby. ^[4] Gry planszowe mogą być obecnie, w większości przypadków, grane przez komputer na wyższym poziomie niż najlepsi ludzie, nawet przy użyciu technik ślepego wyczerpującego wyszukiwania. Go jest wyjątkiem od tej tendencji i do tej pory opiera się atakom maszyn. Najlepsi komputerowi gracze Go grają obecnie na poziomie dobrego nowicjusza. ^[5][6] Mówi się, że strategia Go polega w dużej mierze na rozpoznawaniu wzorów, a nie tylko na analizie logicznej, jak w przypadku szachów i innych gier niezależnych od elementów. Ogromny efektywny współczynnik rozgałęzień, wymagany do znalezienia wysokiej jakości rozwiązań, mocno ogranicza perspektywę, która może być użyta w ramach wyszukiwania sekwencji ruchów.

Gry komputerowe

Algorytm genetyczny może być wykorzystywany w grach komputerowych do tworzenia sztucznej inteligencji (komputer gra przeciwko tobie). To pozwala na bardziej realistyczne doświadczenie gry; jeśli ludzki gracz może znaleźć sekwencję kroków, które zawsze prowadzą do sukcesu, nawet jeśli powtarzane w różnych grach, nie może być wyzwanie lewo. I odwrotnie, jeśli technika uczenia się, taka jak algorytm genetyczny dla stratega, może uniknąć powtarzania błędów z przeszłości, gra będzie miała większą grywalność.

Algorytmy genetyczne składają się z następujących elementów:

• Metoda reprezentacji wyzwania w kategoriach rozwiązania (np. kierowanie żołnierzy do ataku w grze strategicznej)
• Funkcja kondycji lub oceny w celu określenia jakości instancji (np. pomiar obrażeń zadanych przeciwnikowi w takim ataku).

Funkcja kondycji przyjmuje zmutowaną instancję encji i mierzy jej jakość. Funkcja ta jest dostosowana do domeny problemu. W wielu przypadkach, szczególnie tych obejmujących optymalizację kodu, funkcja fitness może być po prostu funkcją czasową systemu. Po zdefiniowaniu reprezentacji genetycznej i funkcji kondycji, algorytm genetyczny będzie instancjonował początkowych kandydatów, jak opisano wcześniej, a następnie poprawiał poprzez powtarzalne stosowanie operatorów mutacji, krzyżowania, inwersji i selekcji (zgodnie z domeną problemu).

Ograniczenia

Istnieją ograniczenia stosowania algorytmu genetycznego w porównaniu z alternatywnymi algorytmami optymalizacyjnymi:

• Wielokrotna ocena funkcji fitness dla złożonych problemów jest często najbardziej ograniczającym segmentem sztucznych algorytmów ewolucyjnych. Znalezienie optymalnego rozwiązania dla złożonych problemów często wymaga bardzo kosztownych ocen funkcji fitness. W rzeczywistych problemach, takich jak optymalizacja strukturalna, pojedyncza ocena funkcji może wymagać od kilku godzin do kilku dni pełnej symulacji. Typowe metody optymalizacyjne nie radzą sobie z tego typu problemami. Często konieczne jest zastosowanie aproksymacji, gdyż obliczenie dokładnego rozwiązania trwa zbyt długo. Algorytmy genetyczne czasami łączą różne modele aproksymacji, aby rozwiązać złożone problemy rzeczywiste.
• Algorytmy genetyczne nie skalują się dobrze. Oznacza to, że tam, gdzie liczba elementów poddawanych mutacji jest duża, często następuje wykładniczy wzrost rozmiaru przestrzeni przeszukiwania. Sprawia to, że zastosowanie tej techniki do takich problemów jak projektowanie silnika, domu czy samolotu jest niezwykle trudne. Aby wykorzystać algorytmy genetyczne do takich problemów, muszą one zostać rozbite na możliwie najprostszą reprezentację. Z tego powodu widzimy algorytmy ewolucyjne kodujące projekty łopatek wentylatorów zamiast silników, kształty budynków zamiast szczegółowych planów konstrukcyjnych oraz profile lotnicze zamiast całych projektów samolotów. Drugim problemem złożoności jest kwestia, jak chronić części, które ewoluowały, by reprezentować dobre rozwiązania, przed dalszą destrukcyjną mutacją, szczególnie gdy ich ocena sprawności wymaga, by dobrze łączyły się z innymi częściami.
• Rozwiązanie "lepsze" jest tylko w porównaniu z innymi rozwiązaniami. W rezultacie, kryterium zatrzymania nie jest jasne w każdym problemie.
• W wielu problemach algorytmy genetyczne mają tendencję do zbiegania w kierunku lokalnego optimum lub nawet arbitralnych punktów, a nie globalnego optimum problemu. Oznacza to, że algorytm nie "wie jak" poświęcić krótkoterminową sprawność, aby zyskać sprawność długoterminową. Prawdopodobieństwo wystąpienia takiej sytuacji zależy od kształtu funkcji fitness: pewne problemy ułatwiają znalezienie globalnego optimum, inne mogą ułatwiać funkcji znalezienie lokalnych optimów. Problem ten można zmniejszyć poprzez użycie innej funkcji fitness, zwiększenie tempa mutacji lub zastosowanie technik selekcji, które utrzymują zróżnicowaną populację rozwiązań. Powszechną techniką utrzymywania różnorodności jest użycie "kary niszowej": każda grupa osobników o wystarczającym podobieństwie (promieniu niszy) ma dodaną karę, która zmniejszy reprezentację tej grupy w kolejnych pokoleniach, pozwalając innym (mniej podobnym) osobnikom pozostać w populacji. Ta sztuczka może jednak nie być skuteczna, w zależności od krajobrazu problemu. Inną możliwą techniką byłoby po prostu zastąpienie części populacji losowo wygenerowanymi osobnikami, gdy większość populacji jest zbyt podobna do siebie. Różnorodność jest ważna w algorytmach genetycznych (i programowaniu genetycznym), ponieważ krzyżowanie jednorodnej populacji nie daje nowych rozwiązań. W strategiach ewolucyjnych i programowaniu ewolucyjnym różnorodność nie jest niezbędna ze względu na większą zależność od mutacji.
• Operowanie na dynamicznych zbiorach danych jest trudne, ponieważ genomy zaczynają się wcześnie zbiegać w kierunku rozwiązań, które mogą już nie być poprawne dla późniejszych danych. Zaproponowano kilka metod, aby rozwiązać ten problem poprzez zwiększenie różnorodności genetycznej i zapobieganie wczesnej konwergencji, albo poprzez zwiększenie prawdopodobieństwa mutacji, gdy jakość rozwiązania spada (tzw. hipermutacja wywołana), albo poprzez sporadyczne wprowadzanie całkowicie nowych, losowo wygenerowanych elementów do puli genów (tzw. losowi imigranci). Ponownie, strategie ewolucji i programowanie ewolucyjne mogą być implementowane z tzw. strategią przecinkową, w której rodzice nie są utrzymywani, a nowi rodzice są wybierani tylko z potomstwa. Może to być bardziej efektywne w przypadku problemów dynamicznych.
• Algorytmy genetyczne nie mogą skutecznie rozwiązywać problemów, w których jedyną miarą przydatności jest pojedyncza miara dobra/zła (jak problemy decyzyjne), ponieważ nie ma sposobu na zbieżność rozwiązania (nie ma wzgórza do pokonania). W takich przypadkach, wyszukiwanie losowe może znaleźć rozwiązanie tak szybko jak GA. Jeśli jednak sytuacja pozwala na powtórzenie próby sukcesu/porażki dającej (być może) różne wyniki, to stosunek sukcesów do porażek stanowi odpowiednią miarę kondycji.
• Dla określonych problemów optymalizacyjnych i instancji problemowych, inne algorytmy optymalizacyjne mogą być bardziej efektywne niż algorytmy genetyczne pod względem szybkości zbieżności. Algorytmy alternatywne i uzupełniające obejmują strategie ewolucyjne, programowanie ewolucyjne, symulowane wyżarzanie, adaptację gaussowską, wspinaczkę po wzgórzu, inteligencję roju (np.: ant colony optimization, particle swarm optimization) oraz metody oparte na programowaniu liniowym całkowitoliczbowym. Przydatność algorytmów genetycznych zależy od stopnia znajomości problemu; dobrze znane problemy często mają lepsze, bardziej wyspecjalizowane podejścia.

Historia

W 1950 r. Alan Turing zaproponował "maszynę uczącą się", która byłaby równoległa do zasad ewolucji. Komputerowa symulacja ewolucji rozpoczęła się już w 1954 roku od pracy Nilsa Aall Barricellego, który używał komputera w Institute for Advanced Study w Princeton, New Jersey. Jego publikacja z 1954 roku nie została szeroko zauważona. Począwszy od 1957 roku, australijski genetyk ilościowy Alex Fraser opublikował serię prac dotyczących symulacji sztucznej selekcji organizmów z wieloma loci kontrolującymi mierzalną cechę. Od tych początków, komputerowe symulacje ewolucji przez biologów stały się bardziej powszechne na początku lat 60-tych, a metody zostały opisane w książkach Frasera i Burnella (1970) oraz Crosby'ego (1973). Symulacje Frasera zawierały wszystkie istotne elementy współczesnych algorytmów genetycznych. Ponadto, Hans-Joachim Bremermann opublikował w latach 60-tych serię prac, w których również przyjął populację rozwiązań problemów optymalizacyjnych, poddawaną rekombinacji, mutacji i selekcji. Badania Bremermanna zawierały również elementy współczesnych algorytmów genetycznych. Inni godni uwagi pionierzy to Richard Friedberg, George Friedman i Michael Conrad. Wiele wczesnych prac zostało przedrukowanych przez Fogela (1998).

Choć Barricelli w pracy, którą przedstawił w 1963 r., symulował ewolucję zdolności do gry w prostą grę, sztuczna ewolucja stała się powszechnie uznaną metodą optymalizacji w wyniku prac Ingo Rechenberga i Hansa-Paula Schwefela w latach 60. i na początku lat 70. Grupa Rechenberga była w stanie rozwiązywać złożone problemy inżynierskie za pomocą strategii ewolucyjnych. Innym podejściem była technika programowania ewolucyjnego Lawrence'a J. Fogela, która została zaproponowana do generowania sztucznej inteligencji. Programowanie ewolucyjne pierwotnie wykorzystywało maszyny stanów skończonych do przewidywania środowisk, a następnie używało zmienności i selekcji do optymalizacji logiki predykcyjnej. Algorytmy genetyczne stały się popularne dzięki pracy Johna Hollanda na początku lat 70-tych, a w szczególności dzięki jego książce Adaptation in Natural and Artificial Systems (1975). Jego praca wywodzi się z badań nad automatami komórkowymi, prowadzonych przez Hollanda i jego studentów na Uniwersytecie Michigan. Holland wprowadził sformalizowane ramy do przewidywania jakości następnej generacji, znane jako twierdzenieHollanda o schemacie. Badania nad GA pozostały w dużej mierze teoretyczne aż do połowy lat 80-tych, kiedy to w Pittsburghu w Pensylwanii odbyła się Pierwsza Międzynarodowa Konferencja Algorytmów Genetycznych.