Algorytmy genetyczne i procesy ewolucyjne
Wykład 3  metody selekcji
Jacek Bieganowski
Instytut Informatyki i Elektroniki
Uniwersytet Zielonogórski
email: [e-mail]
http://www.uz.zgora.pl/~jbiegano/agipe09
15 marca 2009
Algorytmy genetyczne i procesy ewolucyjne  W3
Schemat algorytmu genetycznego
procedure SGA begin
t := 0
inicjacja P0
ocena P0
while (not warunek stopu) do
begin
Tt := reprodukcja Pt
Ot := krzyżowanie i mutacja Tt
ocena Ot
Pt+1 := Ot
t := t + 1
end
end
Algorytmy genetyczne i procesy ewolucyjne  W3
Eksploracja i eksploatacja
Przez eksploatację można rozumieć przeszukiwanie obszaru
przyciągania ekstremum w celu wyznaczenia maksimum
lokalnego.
Eksploracja polega na wybraniu obszaru zawierającego
maksimum globalne ze zbioru ekstermów lokalnych.
Algorytmy genetyczne i procesy ewolucyjne  W3
Nacisk selektywny
Najsilniejszą tendencję do opuszczania obszarów przyciągania
ekstremum lokalnego ma algorytm błądzenia przypadkowego.
Największą szybkość podążania w kierunku ekstermum
globalnego ma algorytm wzrostu. Niestety algorytm ten łatwo
może utknąć w ekstremum lokalnym.
Algorytm optymalizacji globalnej równoważy ekslplorację
(opuszczanie obszarów przyciągania) i eksploatację (podążanie
w kierunku ekstremum).
Proporcje eksploracji i eksploatacji nazywa się naciskiem
selektywnym. Nacisk selektywny jest tym większy im algorytm
przypomina metodę wzrostu.
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja i sukcesja
Selekcja (reprodukcja + sukcesja) skutkuje w ukierunkowaniu
algorytmu w stronę rozwiązań lepszych od dotychczasowych.
Reprodukcja polega na utworzeniu populacji tymczasowej Tt,
która jest następnie poddawana operacjom genetycznym w
celu uzyskania populacji potomnej Ot.
Sukcesja polega na utworzeniu nowej populacji bazowej Pt+1
na podstawie:
osobników z populacji potomnej Ot (sukcesja z całkowitym
zastępowaniem),
populacji potomnej Ot oraz starej populacji bazowej Pt
(sukcesja z częściowym zastępowaniem).
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja proporcjonalna (ruletkowa)
W reprodukcji proporcjonalnej prawdopodobieństwo
wylosowania osobnika jest wprost proporcjonalna do jego
przystosowania.
Ś(X)
pr (X) =
Ś(Y)
Y"Pt
Reprodukcja ruletkowa nie może być stosowana gdy funkcja
przystosowania przyjmuje wartości ujemne.
Reprodukcja proporcjonalna jest  wrażliwa na dodanie
wartości stałej do funkcji przystosowania.
Intensywność nacisku selektywnego zmniejsza się wraz z
kolejnymi generacjami, ponieważ większość osobników
uzyskuje zbliżone wartości przystosowania.
Na początku działania algorytmu nacisk selektywny jest silny i
może powodować tendencję do przedwczesnej zbieżności.
Algorytmy genetyczne i procesy ewolucyjne  W3
Modyfikacja reprodukcji ruletkowej
Ograniczenia reprodukcji proporcjonalnej można ominąć
dokonując korekty dopasowania według wzorów:
Ś (X) = Ś(X) - Ś0, gdzie ("X "D Ś0 Ś(X)
t
Ś (X) = Ś(X) - Śt, gdzie Śt infX"P Ś(X).
Pierwszy wzór zapewnia, że wartość funkcji przystosowania nie
będzie ujemna.
Drugi wzór pozwala dodatkowo na utrzymanie nacisku
selektywnego dopóki istnieje choć niewielkie zróżnicowanie
populacji.
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja rangowa
W metodzie tej prawdopodobieństwo reprodukcji każdego
osobnika jest wyznaczane na podstawie jego rangi czyli liczby
charakteryzującej tego osobnika na tle innych osobników w
populacji.
Populacja jest sortowana wg nierosnących wartości
przystosowania osobników.
Ranga osobnika odpowiada jego pozycji w szeregu, wartości
rangi są kolejnymi liczbami całkowitymi począwszy od 0.
Możliwe są dwa sposoby określenia rangi dla osobników o tym
samym przystosowaniu:
osobniki o jednakowym przystosowaniu otrzymają różne
wartości rangi,
osobniki o jednakowym przystosowaniu otrzymują tą samą
wartość rangi.
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja rangowa  funkcja pp reprodukcji
Po określeniu rang, przypisuje się każdemu osobnikowi
prawdopodobieństwo reprodukcji na podstawie jego rangi.
Wybór funkcji prawdopodobieństwa reprodukcji dokonywany
jest przez projektanta algorytmu.
Należy zadbać aby funkcja określająca prawdopodobieństwo
była nierosnąca wraz z numerem rangi.
Liniowa funkcja prawdopodobieństwa:
r(X)
pr (X) = a + k(1 - ) gdzie rmax = maxX "Pt r(X)
rmax
Parametry a i k są dobierane tak aby były spełnione warunki:
�

pr (X) = 1 i 0 pr (X) 1.
i=1
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja rangowa - funkcja potęgowa
Reprodukcja rangowa z liniową funkcją prawdopodobieństwa
jest często określana jako mało efektywna.
Inny wariant funkcji prawdopodobieństwa to funkcja potęgowa:
pr (X) = a + k(rmax - r(X))b.
Parametry a, b, i k dobiera się podobnie jak w funkcji liniowej.
Parametry pr (X) pozwalają na kształtowanie nacisku
selektywnego. Parametr a powoduje globalne osłabienie
nacisku selektywnego. Parametr b zwiększa zróżnicowanie pp
reprodukcji lepszych i gorszych osobników.
Prawdopodobieństwo reprodukcji jest z góry określone dla
każdej rangi i może być stałe lub zmieniać się wraz z
numerem generacji.
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja turniejowa
Reprodukcja turniejowa jest dwuetapowa. W pierwszym etapie
wybiera się losowo q  kandydatów do turnieju Q �" Pt.
Następnie przeprowadza się turniej miedzy osobnikami z Q, z
którego jest wyłaniany osobnik o największej wartości funkcji
przystosowania. Osobnik ten trafia do populacji potomnej.
Parametrem sterującym intensywnością nacisku selektywnego
jest liczność turnieju q.
Wybór osobników do turnieju może odbywać się na dwa
sposoby:
losowanie ze zwracaniem,
losowanie bez zwracania.
Wariant pierwszy pozwala na reprodukcje wszystkim
osobnikom z niezerowym prawdopodobieństwem. Wariant
drugi powoduje, że q - 1 najgorszych osobników nie będzie w
ogóle reprodukować.
Algorytmy genetyczne i procesy ewolucyjne  W3
Reprodukcja progowa
Reprodukcja progowa jest szczególnym przypadkiem
reprodukcji rangowej. Funkcja prawdopodobieństwa
reprodukcji ma postać:

1
dla 0 r(X) ��
��
pr (X) =
0 w przeciwnym przypadku
Wartość � jest wskaz
nikiem nacisku selektywnego - im jest
ona mniejsza tym mniej osobników będzie reprodukowac i tym
większa będzie liczebność potomstwa.
W skrajnym przypadku gdy � = 1/� do reprodukcji wybierany
jest tylko jeden osobnik.
Parametr � przyjmuje się na poziomie 0, 15 � 0, 5.
Algorytmy genetyczne i procesy ewolucyjne  W3