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

32

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?

Avrohom Yisroel
źródło
12
However, there will be combinations that are weaker. Why isn't this an issue with GA?- Ponieważ słabsze kombinacje są odrzucane.
Robert Harvey,
6
Wiemy, że następne pokolenie nie będzie gorsze, ponieważ nie wyrzucamy dobrych, ale wyrzucamy złych. Istnieje spora szansa, że ​​połączenie niektórych dobrych da jeszcze lepszą, ale nie jest to gwarantowane.
user253751,
7
Why isn't this an issue with GA?Cóż, a właściwie może być. Jednym z wielu (wielu) parametrów optymalizacji przy użyciu GA jest wielkość populacji: jeśli jest zbyt mała, możesz produkować tylko słabsze osobniki, ale jeśli jest zbyt wysoka, czas obliczeń związany z funkcją fitness może być zbyt długi.
Loufylouf,
3
Różnica między hodowlą a odchwaszczaniem : etap hodowlany może (będzie) dawać gorsze potomstwo, ale etap odchwaszczania (powinien) wyeliminować najgorsze wyniki przed kolejnym etapem hodowlanym.
TripeHound,
Dzięki Wam wszystkim. Jeśli dobrze rozumiem, to sposób, w jaki sformułował to w artykule, zrzucił mnie z tropu. Powiedział: „ Nowy, prawdopodobnie bardzo dobry, dziecięcy organizm zastępuje biedny organizm ”, co skłoniło mnie do pytania. Wygląda na to, że było źle :)
Avrohom Yisroel,

Odpowiedzi:

43

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.

Josh Caswell
źródło
1
Istotne: youtube.com/watch?v=YT1vXXMsYak - prezentacja programu komputerowego Dawkina trwa około 12 minut, chociaż warto obejrzeć cały wykład, ponieważ opisuje on podstawowe teoretyczne podstawy, na których ewolucja (biologiczna lub symulowana) jest uziemiony.
Periata Breatta
24
Rzeczywiście, czasami pozwalasz przeżyć pewnemu procentowi słabszych członków punktacji, aby zwiększyć „różnorodność genetyczną”, a także wprowadzić całkowicie losowe mutacje, które nie są oparte na żadnym istniejącym członku.
Jörg W Mittag,
@JoshCaswell Dzięki za to. Chociaż wszystkie odpowiedzi były doskonałe, oznaczę to jako zaakceptowane, ponieważ obejmuje wszystko, o co prosiłem, i kilka rzeczy, o które jeszcze nie pytałem!
Avrohom Yisroel,
Cieszę się, że mogłem pomóc, @AvrohomYisroel
Josh Caswell
6

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)

Lyndon White
źródło
1
„W każdym pokoleniu nie polega tylko na tworzeniu najlepszych elementów, ale obejmuje także same najlepsze elementy”. Zależy to od implementacji. Niektóre implementacje tego nie robią. Jest to czasem nazywane „elitarnością”.
jpmc26
4

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ę.

JacquesB
źródło
4
Ach, więc wygląda na to, że artykuł był trochę mylący. Powiedział „ Nowy, prawdopodobnie bardzo dobry, dziecięcy organizm zastępuje biedny organizm ”, co mnie zdezorientowało. Myślę, że jeśli łączy on wiele organizmów, to ogólnie rzecz biorąc spodziewalibyśmy się wzrostu, nawet jeśli pojedyncze nowe organizmy mogą być słabsze niż poprzednie. Czy to prawda? Dzięki
Avrohom Yisroel
@AvrohomYisroel: Dokładnie.
JacquesB,
1
@AvrohomYisroel: Strzeż się przybliżonego zrozumienia osób niebędących specjalistami. (Uważaj też na precyzyjną „ścianę żargonu” specjalistów).
Eric Towers
@EricTowers Tak, widzę problem! Sądziłem, że był ekspertem, sądząc po poprzednich artykułach, które napisał, ale najwyraźniej popełnił kilka poważnych błędów w tym artykule.
Avrohom Yisroel,
4

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.

Euforyk
źródło
2

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ń”.

Doktor Brown
źródło