Dlaczego osoby o niskiej sprawności mają szansę przeżyć do następnego pokolenia?

Obecnie czytam i obserwuję algorytm genetyczny i uważam go za bardzo interesujący (nie miałem okazji go studiować, gdy byłem na uniwersytecie).

Rozumiem, że mutacje oparte są na prawdopodobieństwie (losowość jest źródłem ewolucji), ale nie rozumiem, dlaczego przetrwanie.

Z tego, co rozumiem, osoba która ma sprawność fizyczną tak jak dla innej osoby która ma sprawność fizyczną , mamy , wtedy większe prawdopodobieństwo niż przeżycia do następnej generacji.F ( i ) J F ( j ) F ( i ) > F ( j ) I $I$$F(i)$$J$$F(j)$$F(i) > F(j)$$I$$J$

Oznacza to, że prawdopodobieństwo może przetrwać i może nie (z „pecha”). Nie rozumiem, dlaczego to w ogóle jest dobre? Jeśli to zawsze przetrwać wybór, co by się nie udać w algorytmie? Domyślam się, że algorytm byłby podobny do algorytmu zachłannego, ale nie jestem pewien.$J$ $I$ $I$

Główną ideą jest to, że umożliwiając przetrwanie suboptymalnym osobnikom, możesz przełączyć się z jednego „szczytu” w krajobrazie ewolucyjnym na inny poprzez sekwencję małych przyrostowych mutacji. Z drugiej strony, jeśli wolno ci wejść tylko pod górę, wymaga to gigantycznej i bardzo mało prawdopodobnej mutacji, aby przełączyć szczyty.

Oto schemat pokazujący różnicę:

Praktycznie ta właściwość globalizacji jest głównym punktem sprzedaży algorytmów ewolucyjnych - jeśli chcesz znaleźć lokalne maksima, istnieją bardziej wydajne techniki specjalistyczne. (np. L-BFGS z gradientem różnic skończonych i wyszukiwaniem linii)

W prawdziwym świecie ewolucji biologicznej umożliwienie przetrwania suboptymalnym osobnikom stwarza solidność, gdy zmienia się krajobraz ewolucyjny. Jeśli wszyscy są skoncentrowani na szczycie, wówczas jeśli szczyt ten stanie się doliną, cała populacja umiera (np. Dinozaury były gatunkami najbardziej odpowiednimi do momentu uderzenia asteroidy i zmiany krajobrazu ewolucyjnego). Z drugiej strony, jeśli populacja będzie zróżnicowana, to gdy zmieni się krajobraz, niektóre przetrwają.

Odpowiedź Nicka Algera jest bardzo dobra, ale zamierzam uczynić ją trochę bardziej matematyczną za pomocą jednej przykładowej metody, Metropolis-Hastings.

Scenariusz, który zamierzam zbadać, to populacja jednego. Proponujesz mutację ze stanu do stanu j z prawdopodobieństwem Q ( i , j ) , a my również narzucamy warunek, że Q ( i , j ) = Q ( j , i ) . Zakładamy również, że F ( i ) > 0 dla wszystkich i ; jeśli nie masz sprawności w swoim modelu, możesz to naprawić, dodając wszędzie mały epsilon.$i$$j$$Q(i,j)$$Q(i,j) = Q(j,i)$$F(i)>0$$i$

Akceptujemy przejście z na j z prawdopodobieństwem:$i$$j$

Innymi słowy, jeśli jest bardziej sprawny, zawsze bierzemy to, ale jeśli jest mniej sprawny, bierzemy to z prawdopodobieństwem , w przeciwnym razie próbujemy ponownie, dopóki nie zaakceptujemy mutacja.j F ( j $j$$j$$\frac{F(j)}{F(i)}$

Teraz chcielibyśmy zbadać , faktyczne prawdopodobieństwo przejścia z na .i $P(i,j)$$i$$j$

Oczywiście jest to:

Załóżmy, że . Następnie = 1, a więc:min ( 1 , F ( j $F(j) \ge F(i)$$\min\left(1, \frac{F(j)}{F(i)}\right)$

Uruchomienie argumentu do tyłu, a także zbadanie trywialnego przypadku, w którym , widać, że dla wszystkich i :$i=j$$i$$j$

Jest to niezwykłe z kilku powodów.

Prawdopodobieństwo przejścia jest niezależny od . Oczywiście może minąć trochę czasu, zanim skończymy w atraktorze, a zaakceptowanie mutacji może zająć trochę czasu. Gdy mamy do prawdopodobieństwo przejścia jest całkowicie zależne od , a nie na .$Q$$F$$Q$

Zsumowanie wszystkich daje:$i$

Najwyraźniej musi sumować się do jeśli zsumujesz wszystkie (to znaczy prawdopodobieństwo przejścia z jednego stanu musi sumować się do ), więc otrzymujesz:$P(j,i)$$1$$i$$1$

Oznacza to, że jest (nienormalizowaną) funkcją gęstości prawdopodobieństwa, dla której stanów wybiera metodę. Nie tylko masz gwarancję odkrycia całego krajobrazu, ale robisz to proporcjonalnie do tego, jak „pasuje” każdy stan.$F$

Oczywiście jest to tylko jeden z wielu przykładów; jak zauważyłem poniżej, okazuje się, że jest to metoda bardzo łatwa do wyjaśnienia. Zazwyczaj używasz GA nie do eksploracji pdf, ale do znalezienia ekstremum, i możesz rozluźnić niektóre warunki w tym przypadku i nadal zagwarantować ostateczną zbieżność z dużym prawdopodobieństwem.

Zaletą korzystania z GA jest to, że możesz eksplorować szersze przestrzenie wyszukiwania, podążając ścieżkami pochodzącymi od potencjalnie gorszych kandydatów. Powinni przejść gorzej kandydaci, aby zbadać te różne obszary wyszukiwania, nie wiele, ale zdecydowanie kilka. Jeśli zaczniesz brać tylko to, co najlepsze, za każdym razem, gdy usuniesz ten aspekt eksploracji algorytmu i stanie się on bardziej wspinaczem górskim. Również ciągłe wybieranie najlepszych może prowadzić do przedwczesnej konwergencji.

W rzeczywistości algorytmy wyboru przyjmują oba podejścia. Jednym ze sposobów jest to, co zasugerowałeś, a drugim jest to, że osoby o wyższej sprawności są wybierane, a osoby z niższymi nie.

Podejście do wyboru jest również dostosowane do problemu, który próbujesz wymodelować. W eksperymencie w szkole staraliśmy się ewoluować graczy karcianych, zmuszając ich do gry przeciwko sobie (tj. Wyboru turnieju ). W takim scenariuszu bardzo dobrze moglibyśmy zawsze faworyzować nad (z twojego przykładu), ponieważ aspekt „szczęścia” jest już w samej grze. Nawet jeśli dla dowolnych dwóch i , w dowolnej rundzie, wyłącznie ze względu na układ rozdań i sposób, w jaki grali inni, mógł wygrać rundę, a zatem moglibyśmy skończyć z$I$$J$$F(i) > F(j)$$I$$J$$J$$F(j) > F(i)$. Należy pamiętać, że populacja jest często na tyle duża, że ​​można sobie pozwolić na utratę niektórych dobrych osób, a ogólnie nie będzie to miało większego znaczenia.

Ponieważ GA są modelowane wokół ewolucji w świecie rzeczywistym, kiedy stosuje się rozkłady probabilistyczne, są one przede wszystkim modelowane wokół tego, jak ewoluują prawdziwe społeczności, w których czasami osoby o niższej sprawności mogą przetrwać, podczas gdy osoby o wyższej sprawności mogą nie przetrwać (prymitywna analogia: wypadki samochodowe, naturalne katastrofy itp .:-)).

jest to bardzo proste, od jednego pow: czasem rozwiązania „podrzędne” o wyższej sprawności mogą się rodzić z rozwiązań „nadrzędnych” o niższej sprawności za pomocą krzyżowania lub mutacji (to w rzeczywistości wiele teorii algorytmów genetycznych). więc ogólnie chce się szukać / nosić rozwiązania o wyższej sprawności, ale zbyt duży nacisk na utrzymanie / hodowanie tylko rozwiązań o wysokiej sprawności może prowadzić do utknięcia w lokalnych minimach i nie poszukiwania dużego „krajobrazu ewolucyjnego”. w rzeczywistości można uczynić „wyższą granicę sprawności” dla przeżycia tak surową lub rozluźnioną, jak się chce i eksperymentować z tym, jak wpływa to na jakość ostatecznego rozwiązania. zarówno zbyt surowe, jak i zbyt luźne strategie odcięcia doprowadzą do gorszych ostatecznych rozwiązań. oczywiście wszystko to ma pewien związek z prawdziwą ewolucją biologiczną. tam jest więcej ”