Przedwczesna konwergencja
W algorytmach ewolucyjnych (EA) termin przedwczesnej zbieżności oznacza, że populacja dla problemu optymalizacji zbiegła się zbyt wcześnie, co spowodowało, że była nieoptymalna. W tym kontekście rozwiązania rodzicielskie, przy pomocy operatorów genetycznych , nie są w stanie wygenerować potomstwa, które przewyższa lub przewyższa rodziców. Przedwczesna konwergencja jest powszechnym problemem występującym w algorytmach ewolucyjnych w ogóle i algorytmach genetycznych w szczególności, ponieważ prowadzi to do utraty lub zbieżności dużej liczby alleli, co w konsekwencji bardzo utrudnia poszukiwanie określonego genu, w którym allele były obecne. Allel jest uważany za utracony, jeśli w populacji występuje gen, w którym wszystkie osobniki mają tę samą wartość dla tego konkretnego genu. Allel jest, zgodnie z definicją De Jonga, uważany za allel zbieżny, gdy 95% populacji ma tę samą wartość dla określonego genu (patrz także konwergencja ).
Strategie zapobiegania przedwczesnej konwergencji
Strategie odzyskiwania zmienności genetycznej mogą być następujące:
- strategia kojarzenia zwana zapobieganiem kazirodztwu ,
- jednolita zwrotnica ,
- uprzywilejowana zamiana podobnych osobników ( preselekcja lub zatłoczenie ),
- segmentacja osób o podobnej sprawności fizycznej ( fit sharing ),
- zwiększająca się wielkość populacji.
Zmienność genetyczną można również odzyskać przez mutację, chociaż proces ten jest wysoce losowy.
Jednym ze sposobów zmniejszenia ryzyka przedwczesnej konwergencji jest użycie ustrukturyzowanych populacji zamiast powszechnie stosowanych populacji panmiktycznych, patrz poniżej .
Identyfikacja występowania przedwczesnej konwergencji
Trudno określić, kiedy nastąpiła przedwczesna konwergencja i równie trudno przewidzieć jej obecność w przyszłości. Jednym ze sposobów jest wykorzystanie różnicy między średnimi i maksymalnymi wartościami przystosowania, jak zastosowali Patnaik i Srinivas, aby następnie zróżnicować prawdopodobieństwa krzyżowania i mutacji. Różnorodność populacji to kolejna miara, która była szeroko stosowana w badaniach do pomiaru przedwczesnej konwergencji. Jednak chociaż powszechnie przyjęto, że spadek różnorodności populacji prowadzi bezpośrednio do przedwczesnej konwergencji, przeprowadzono niewiele badań dotyczących analizy różnorodności populacji. Innymi słowy, używając terminu różnorodność populacji, argument przemawiający za badaniem dotyczącym zapobiegania przedwczesnej konwergencji nie jest solidny, chyba że określono, jaka jest ich definicja różnorodności populacji.
Przyczyny przedwczesnej konwergencji
Istnieje wiele przypuszczalnych lub hipotetycznych przyczyn występowania przedwczesnej konwergencji.
Mutacje samoadaptacyjne
Rechenberg wprowadził ideę samoadaptacji dystrybucji mutacji do strategii ewolucyjnych . Według Rechenberga parametry kontrolne dla tych rozkładów mutacji ewoluowały wewnętrznie poprzez samoadaptację, a nie z góry określone. Nazwał to zasadą 1/5 sukcesu strategii ewolucyjnych (1 + 1) -ES: Parametr kontroli rozmiaru kroku byłby zwiększony o pewien czynnik, gdyby względna częstość pozytywnych mutacji w określonym okresie czasu była większa niż 1/ 5, odwrotnie, jeśli jest mniejsza niż 1/5. Mutacje samoadaptacyjne mogą równie dobrze być jedną z przyczyn przedwczesnej konwergencji. Dokładne lokalizowanie optymów można poprawić dzięki mutacji samoadaptacyjnej, a także przyspieszeniu wyszukiwania tych optymów. Zostało to powszechnie uznane, chociaż podstawy tego mechanizmu zostały słabo zbadane, ponieważ często nie jest jasne, czy optima występuje lokalnie, czy globalnie. Metody samoadaptacyjne mogą doprowadzić globalną konwergencję do globalnego optimum, pod warunkiem, że stosowane są metody selekcji elitaryzmu , jak również, że zasada samoadaptacji nie koliduje z rozkładem mutacji, który ma właściwość zapewniania dodatniego minimalnego prawdopodobieństwa trafienia w losowy podzbiór. Dotyczy to niewypukłych funkcji celu ze zbiorami obejmującymi ograniczone dolne poziomy niezerowych pomiarów. Badanie przeprowadzone przez Rudolpha sugeruje, że mechanizmy samoadaptacji wśród elitarnych strategii ewolucyjnych rzeczywiście przypominają zasadę 1/5 sukcesu i równie dobrze mogą zostać złapane przez lokalne optimum, które obejmuje dodatnie prawdopodobieństwo.
Populacje panmiktyczne
Większość EA wykorzystuje populacje nieustrukturyzowane lub panmiktyczne , w których zasadniczo każdy osobnik w populacji kwalifikuje się do wyboru partnera na podstawie sprawności. Tak więc informacja genetyczna tylko nieznacznie lepszego osobnika może rozprzestrzenić się w populacji w ciągu kilku pokoleń, pod warunkiem, że w tym czasie nie wyda się żadne inne lepsze potomstwo. Zwłaszcza w stosunkowo małych populacjach może to szybko doprowadzić do utraty różnorodności genotypowej, a tym samym do przedwczesnej konwergencji. Dobrze znanym środkiem zaradczym jest przejście na alternatywne modele populacji które wprowadzają do populacji substruktury zachowujące zróżnicowanie genotypowe przez dłuższy czas, a tym samym przeciwdziałają tendencji do przedwczesnej konwergencji. Zostało to wykazane dla różnych EA, takich jak algorytmy genetyczne, strategia ewolucji, inne EA lub algorytmy memetyczne.