Algorytmy genetyczne i procesy ewolucyjne Wykład 3.pdf

(220 KB) Pobierz
Algorytmy genetyczne i procesy ewolucyjne - Wykªad 3 -- metody selekcji
Algorytmy genetyczne i procesy ewolucyjne
Wykład 3 – metody selekcji
Jacek Bieganowski
InstytutInformatykiiElektroniki
UniwersytetZielonogórski
email:J.Bieganowski@iie.uz.zgora.pl
15 marca 2009
Algorytmygenetyczneiprocesyewolucyjne–W3
95028868.003.png 95028868.004.png
Schemat algorytmu genetycznego
procedure SGA begin
t := 0
inicjacja P 0
ocena P 0
while ( not warunek stopu) do
begin
T t := reprodukcja P t
O t := krzyzowanie i mutacja T t
ocena O t
P t + 1 := O t
t := t + 1
end
end
Algorytmygenetyczneiprocesyewolucyjne–W3
95028868.005.png
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.
Algorytmygenetyczneiprocesyewolucyjne–W3
95028868.006.png
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.
Algorytmygenetyczneiprocesyewolucyjne–W3
95028868.001.png
Reprodukcja i sukcesja
Selekcja (reprodukcja + sukcesja) skutkuje w ukierunkowaniu
algorytmu w stron¦ rozwi¡za« lepszych od dotychczasowych.
Reprodukcja polega na utworzeniu populacji tymczasowej T t ,
która jest nast¦pnie poddawana operacjom genetycznym w
celu uzyskania populacji potomnej O t .
Sukcesja polega na utworzeniu nowej populacji bazowej P t + 1
na podstawie:
osobników z populacji potomnej O t (sukcesja z całkowitym
zast¦powaniem),
populacji potomnej O t oraz starej populacji bazowej P t
(sukcesja z cz¦±ciowym zast¦powaniem).
Algorytmygenetyczneiprocesyewolucyjne–W3
95028868.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin