Skąd wiemy, że następne pokolenie będzie lepsze?

Niedawno zapoznałem się z algorytmami genetycznymi w tym artykule MSDN , w którym nazywa je ewolucją kombinatoryczną, ale wydaje się, że jest to samo i staram się zrozumieć, w jaki sposób połączenie dwóch potencjalnych rozwiązań zawsze da nowe rozwiązanie, które jest przynajmniej tak samo dobry jak jego rodzice.

Dlaczego tak jest? Z pewnością łączenie może przynieść coś gorszego.

O ile rozumiem, algorytm opiera się na koncepcji, że gdy samiec i samica gatunku rodzą potomstwo, potomstwo to będzie miało cechy obojga rodziców. Niektóre kombinacje będą lepsze, niektóre gorsze, a niektóre równie dobre. Te, które są lepsze (bez względu na to, co jest właściwe zdefiniowanie „lepszego”), mają większą szansę na przeżycie i wytworzenie potomstwa, które ma ulepszone cechy. Jednak nie będzie mieć kombinacje, które są słabsze. Dlaczego nie jest to problem z GA?

Algorytm genetyczny próbuje ulepszyć w każdym pokoleniu poprzez ubicie populacji. Każdy członek jest oceniany zgodnie z funkcją fitness i tylko jego część z wysoką liczbą punktów może się rozmnażać.

Masz jednak rację: nie ma gwarancji, że następna generacja poprawi wynik swojego poprzednika.

Zastanówmy się nad programem łasicy Dawkinsa : „ewolucja” łańcucha "Methinks it is like a weasel". Począwszy od populacji losowych ciągów, funkcja fitness ocenia najbliższe dopasowanie tekstowe, które jest zaburzone w celu uzyskania następnej generacji. Dzięki prostej reprodukcji krzyżowej dwa połączone ze sobą łańcuchy o wysokiej punktacji mogą bardzo łatwo wytworzyć potomstwo o niższej punktacji. Nawet „bezpłciowa” losowa mutacja pojedynczego łańcucha o wysokiej sprawności może obniżyć sprawność dziecka.

Myślę, że warto zauważyć, że niekoniecznie jest to wada. Przy tego rodzaju wyszukiwaniu powstaje idea lokalnych maksimów . Członek populacji może reprezentować rozwiązanie, które nie jest optymalnym rezultatem, ale jest najlepszym, jakie można osiągnąć bez pogorszenia się po drodze.

Wyobraź sobie, że funkcja przydatności programu łasicy nie tylko wyszukuje odległość edycji, ale ma pewne pojęcie „słowo” i sprawdza, czy ostatnim słowem ciągu jest imię zwierzęcia. Każde imię zwierzęcia osiąga dobre wyniki, ale "weasel"dostaje dużą premię.

Co się stanie, jeśli "Methinks it is like a walrus"ewoluuje? Dobrze się spisuje. Nie tak jak ostateczny ciąg docelowy, ale lepszy niż "Methinks it is like a walrut"lub inne bliskie odmiany, które można osiągnąć jednym krokiem mutacji.

Łańcuch morsa jest lokalnym maksimum i wyszukiwanie może tam utknąć, chyba że program pozwoli na pogorszenie wyniku następnego pokolenia.

Nie wiemy, że będzie lepiej, wiemy, że nie będzie gorzej.

W każdym pokoleniu nie polega tylko na tworzeniu najlepszych elementów, ale obejmuje także same najlepsze elementy - klony, jeśli wolisz. Ponieważ nadal są obecni, zdobędą tyle samo, co wcześniej. Oznacza to, że jeśli żadne z potomków nie będzie lepsze, zwycięzcy poprzednich generacji ponownie wygrają - i zostaną zmutowani / rozmnażają się.

Zastanów się: gdy osoba będąca przodkiem jest literą, np A . Zmutowane dziecko jest zdefiniowane przez dodanie liczby, np. A1Rozwiązania krzyżowe są pisane w nawiasach wokół rodzica, np. (A1B2) I rdzeń fitness każdego indywidualnego napisanego po nim - im wyższy, tym lepszy[12]

Dla celów demonstracyjnych rozważmy pulę 5, w której trzymamy najlepsze 2. i wypełniamy 1 mutantem każdego z nich oraz krzyżówką

Generacja 1

• A [10]
• B [5]
• C [4]
• D [3]
• E [1]

Zachowaj A, Bponieważ są to dwa najlepsze, i uzupełnij pozostałe 3 miejsca o potomków

Generacja 2

• A [10]
• B [5]
• (AB) [7]
• A1 [12]
• B1 [4]

Trzymaj A, a (AB)ponieważ są to najlepsze 2 - oznacza to, że dziadek Anadal będzie w basenie, ponieważ większość dzieci pracuje słabiej

Generacja 3

• A [10]
• (AB) [12]
• (A(AB)) [14]
• A2 [8]
• (AB)1 [13]

Zachowaj (AB)1i (A(AB))- tym razem nie utrzymano dziadków, ponieważ dwoje ich dzieci biło je. Ale gdyby (AB1)wystąpił tylko nieco gorzej, zatrzymalibyśmy go (AB).

Trwa to do momentu ustabilizowania się wyniku. Co oznacza, że ​​osiągnąłeś jakieś lokalne maksima (potencjalnie maksymalne globalne). Jednym z powodów, dla których należy to wykryć, jest to, że te same osoby będą „klonowane” do następnej generacji. (choć w przypadku problemów z dużymi wymiarami, które mogą trwać zbyt długo, być może lepiej po prostu sprawdzić poprawę <konkretna tolerancja)

Ogólnie rzecz biorąc, algorytmy genetyczne działają poprzez tworzenie wielu (losowych) odmian rodziców w każdym pokoleniu. Następnie stosowana jest pewna funkcja selekcji, a potomstwo, które najlepiej pasuje do tej funkcji, przeżyje. Więc potomstwo niekoniecznie jest lepsze, ponieważ zmiana jest losowa, ale w połączeniu z selekcją zyskujesz z czasem poprawę.

Kiedy studiowałem algorytmy genetyczne na studiach, wyjaśniono to w następujący sposób:

Wyobraź sobie, że rozwiązaniem jest kombinacja „genów”, w których każdy gen wpływa na to, jak dobre jest rozwiązanie jako całość. Po połączeniu dwóch roztworów ich geny są wybierane losowo od każdego z rodziców.

Teraz, jeśli gen prowadzi ogólnie do dobrego rozwiązania, jego częstotliwość w puli genowej wzrasta. W skrajnym przypadku gen zdominuje populację.

Więc kiedy myślisz o algorytmach genetycznych (i ogólnie ewolucji), nie powinieneś myśleć o osobach. Powinieneś pomyśleć o genach i populacjach jako całości. Nawet jeśli jedno „najlepsze” rozwiązanie zostanie utracone, nie oznacza to, że utracono geny.

Istnieje również idea elitaryzmu w algorytmach genetycznych. Oznacza to, że najlepsze rozwiązania są zawsze utrzymywane przez pokolenia. Może to przyspieszyć konwergencję algorytmu, ale łatwiej jest utknąć algorytmowi w lokalnych optymach.

Algorytmy GA nie są deterministyczne, nie gwarantują poprawy w każdym pokoleniu, a także nie gwarantują znalezienia optymalnego poziomu. Jednak faza selekcji GA, wykorzystująca funkcję fitness, zwiększa szanse na przetrwanie „dobrych rozwiązań”.