Problem przedwczesnej zbieżności
Zagadnienie k-ramiennego bandyty [14] dobrze ilustruje dylemat między intensywnością przeszukiwania nowych rejonów przestrzeni rozwiązań (eksploracja) a optymalizacją lokalną wokół znalezionych minimów (eksploatacja). W przypadku Algorytmów Genetycznych - im większy napór selekcyjny, tym większy nacisk na eksploatację, co grozi przedwczesną zbieżnością. Zbyt mały napór grozi brakiem konwergencji i uzyskaniem równie złych rezultatów. Konieczny jest pewien kompromis.
Trzy sposoby na poradzenie sobie z tym problemem pochodzą z pracy De Jonga [8]. Pierwszy to tzw. model ze ściskiem. Nowowygenerowany potomek zastępuje osobnika nie losowego, lecz podobnego do niego pod względem genotypu. W ten sposób maleją szanse na nagromadzenie się dużej ilości podobnych osobników.
Kolejnym pomysłem De Jonga jest współczynnik wymiany G ∈ (0,1). Współczynnik określa jaką część populacji w kolejnej generacji będą stanowić potomkowie, podczas gdy pozostałą wypełnią rodzice.
Trzecia idea to model wartości oczekiwanej, który steruje selekcją potomków do reprodukcji. Każdemu osobnikowi przyporządkowuje się kredyt proporcjonalny do relatywnej względem reszty populacji wartości przystosowania. Kredyt następnie zmniejsza się po każdej reprodukcji. Gdy jego wartość spadnie poniżej zera, osobnik nie może już brać udziału w reprodukcji.
Wszystkie zaproponowane przez De Jonga usprawnienia zmniejszają prawdopodobieństwo przedwczesnej zbieżności.
Kolejną grupą pomysłów stanową bariery reprodukcyjne sterujące selekcją osobników przeznaczonych do krzyżowania. Hollstein zaproponował technikę kojarzenia krewniaczego ze sporadycznym krzyżowaniem. Polega ona na kojarzeniu podobnych chromosomów (należących do jednej rodziny) tak długo, aż występuje poprawa. Po tym następuje krzyżowanie między rodzinami. Booker wprowadził wzorce kojarzeniowe, które są dołączane do części funkcjonalnej (właściwej) chromosomu i razem z nim ewoluują. We wzorcu zawarta jest informacja, z jakimi chromosomami może się krzyżować, a z jakimi nie. Ewolucji podlegają więc nie tylko same rozwiązania, ale i "preferencje" krzyżowania.
Do ciekawych rozwiązań należy skalowanie osobników przed selekcją. Aby zapewnić optymalny poziom konkurencyjności, różnice między przystosowaniem najlepszych i najgorszych osobników nie mogą być zbyt małe ani zbyt duże. Dla zbyt dużych różnic selekcja ruletkowa zapewni dominację superosobnikom, natomiast dla zbyt małych różnic algorytm będzie błądzić. Istnieje kilka przekształceń skalujących, np. liniowe, potęgowe, σ-obcinające. Podobną metodą jest nadawanie i ocenianie według rang, a nie wartości przystosowania.
Goldberg i Richardson zaproponowali funkcję współudziału (ang. sharing functioń), aby zapobiec zbytniemu nagromadzeniu się osobników w jednej niszy. Wszystkie powyższe metody można znaleźć w [14].
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.