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

24

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

algorithms optimization genetic-algorithms

— Max
źródło

13

Utknięcie w lokalnym minimum.

— Louis,

Nawet w prawdziwym życiu korzystne mutacje nie / większa sprawność środowiskowa nie gwarantuje przeżycia osobom z nimi / nim, co faktycznie pozwala wyrazić większą różnorodność cech (i może być potencjalnie korzystne, jeśli środowisko niespodziewanie się zmieni, choć nie jest tak prawdopodobne w przypadku algorytmu optymalizującego). ... I to stwierdzono na końcu odpowiedzi Nicka, więc cokolwiek.

— JAB

1

Jeśli cały czas zabijasz słabych, to co masz oprócz zwykłego wspinacza?

— Raphael

35

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

wprowadź opis zdjęcia tutaj

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

— Nick Alger
źródło

2

„W prawdziwym świecie ewolucji biologicznej, pozwalanie przetrwać suboptymalnym jednostkom, stwarza solidność, gdy zmienia się krajobraz ewolucyjny” - szaleje jako biolog. Osobom o niskiej sprawności nie wolno „przetrwać”, aby zmaksymalizować kondycję, która jest po prostu naturą rzeczywistości. Organizmy o niskiej sprawności fizycznej starają się przetrwać tak samo jak wszystko inne.

— Jack Aidley,

Oczywiście masz rację, natura nie decyduje się na nic ani nie zezwala, po prostu się zdarza. Z drugiej strony istnieje wiele przykładów, w których ludzie wybiórczo hodowali rośliny i zwierzęta, utrzymując tylko „najlepsze”, tworząc monokulturę, która nie jest odporna, gdy pojawia się nowa choroba lub zmienia się środowisko.

— Nick Alger,

Istnieją inne techniki zwalczania tego efektu, np. Wykonywanie większych kroków i ponowne uruchamianie z losowymi początkowymi populacjami. Dodatkowo, w przypadku krzyżowej rekombinacji, utrzymanie słabszego genotypu może być pomocne, jeśli silniejszy mutuje, a krzyżowanie między tymi dwoma okazuje się jeszcze silniejsze.

— Raphael

13

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 z prawdopodobieństwem , a my również narzucamy warunek, że . Zakładamy również, że dla wszystkich ; 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 z prawdopodobieństwem: $i$ $j$

min (1, \frac{F (j)}{F (i)})

$\min\left(1, \frac{F(j)}{F(i)}\right)$

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$ $j$ $\frac{F(j)}{F(i)}$

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

Oczywiście jest to:

P (i, j) = Q (i, j) min (1, \frac{F (j)}{F (i)})

$P(i,j) = Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

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

F (i) P (i, j)

$F(i) P(i,j)$

= F (i) Q (i, j) min (1, \frac{F (j)}{F (i)})

$= F(i) Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

= F (i) Q (i, j)

$= F(i) Q(i,j)$

= Q (j, i) m i n (1, \frac{F (i)}{F (j)}) F (j)

$= Q(j,i) min\left(1, \frac{F(i)}{F(j)}\right) F(j)$

= F (j) P (j, i)

$= F(j) P(j,i)$

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

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

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$

\sum_{i} F (i) P (i, j) = \sum_{i} F (j) P (j, i)

$\sum_i F(i) P(i,j) = \sum_i F(j) P(j,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$

F (j) = \sum_{i} F (i) P (i, j)

$F(j) = \sum_i F(i) P(i,j)$

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.

— Pseudonim
źródło

Cudowna odpowiedź! Chciałbym móc głosować wielokrotnie. Jedno pytanie: czy możesz uzasadnić, dlaczego wybraliśmy ? Czy wybrano to, ponieważ cała reszta matematyki okazuje się bardzo fajna? Czy jest jakiś zewnętrzny powód, dla którego jest to naturalny wybór dla ? (Spodziewałbym się, że jedna wartość naturalna dla byłaby o jeden większa od liczby out-edge od stanu , w którym to przypadku nie mielibyśmy ponieważ ogólnie stopień i mogą się różnić.)

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

Q

$Q$

Q (i, j)

$Q(i,j)$

i

$i$

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

i

$i$

j

$j$

— DW

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

F

$F$ to stacjonarny pdf. Jeśli chcesz, aby twój pdf był nieruchomy, pomaga to w pewnym sensie odwrócić proces. Ponadto, jeśli to pomaga, algorytm MH został zaprojektowany dla ciągłych problemów (transport neutronów), gdzie nie ma dyskretnej liczby granic zewnętrznych. Oczywiście, jeśli próbujesz znaleźć globalne maksimum, przeszukiwanie całego pliku pdf nie zawsze jest tym, czego naprawdę chcesz. To było wyłącznie w celach ilustracyjnych.

— pseudonim

7

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.

— Roślina
źródło

6

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 .:-)).

— Omer Iqbal
źródło

0

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 ”

— vzn
źródło