Algorytmy genetyczne i procesy ewolucyjne Wykład 4.pdf

Algorytmygenetyczneiprocesyewolucyjne

Wykład 4 – kryteria zatrzymania algorytmu, operatory

krzy»owania i mutacji

Jacek Bieganowski

InstytutInformatykiiElektroniki

UniwersytetZielonogórski

email:J.Bieganowski@iie.uz.zgora.pl

http://www.uz.zgora.pl/~jbiegano/agipe09

23 marca 2009

Algorytmygenetyczneiprocesyewolucyjne–W4

Zatrzymaniealgorytmu

Kryteria zatrzymania algorytmu mo»na podzieli¢ na dwie grupy:

kryteria polegaj¡ce na monitorowaniu warto±ci funkcji

przystosowania, bazuj¡ce na spostrze»eniu, »e wraz z

kolejnymi generacjami maleje szansa na znalezienie lepszych

osobników od dotychczasowych,

kryteria polegaj¡ce na monitorowaniu zdolno±ci

eksploracyjnych algorytmu

ró»norodno±ci osobników pozwalaj¡cej na modyﬁkacj¦ w

wyniku krzy»owania,

zasi¦gu operatora mutacji gdy jest samoczynnie adoptowany.

Algorytmygenetyczneiprocesyewolucyjne–W4

Monitorowanierozwi¡za«(1)

Kryteriummaksymalnegokosztu jest najprostszym w

implementacji, polega ono no zatrzymaniu algorytmu gdy

zostanie przekroczony maksymalny koszt algorytmu.

Maksymalny koszt mo»e wynika¢ ze specyﬁki zadania –

wymagany jest okre±lony czas na znalezienie odpowiedzi.

Maksymalny koszt zale»y od parametrów zadania (np

liczebno±¢ populacji).

Kryteriumzadowalaj¡cegopoziomufunkcji

przystosowania jest spełnione, gdy algorytm znajdzie

rozwi¡zanie o warto±ci funkcji przystosowania przekraczaj¡cej

zadany przez u»ytkownika próg. Wad¡ tego kryterium jest

potrzeba znajomo±ci funkcji przystosowania oraz mo»liwo±¢

praktycznie niesko«czenie długiego poszukiwania warto±ci

powy»ej progu.

Algorytmygenetyczneiprocesyewolucyjne–W4

Monitorowanierozwi¡za«(2)

Kryteriumminimalnejszybko±cipoprawy bazuje na

obserwacji szybko±ci zmian wyniku osi¡ganego przez algorytm.

Algorytm jest zatrzymywany, je±li w kolejnych generacjach

nie uda si¦ poprawi¢ wyniku o wi¦cej ni» " , czyli spełniony jest

warunek

Algorytmygenetyczneiprocesyewolucyjne–W4

| ( ^ X ( t − )) −| ( ^ X ( t )) |¬ ".

Cz¦sto przyjmuje si¦, »e " = 0 – czyli, »e algorytm jest

zatrzymywany, je±li nie uda si¦ znale¹¢ lepszego rozwi¡zania w

kolejnych generacjach.

Monitorowaniepopulacji

Kryteriumzanikuró»norodno±cipopulacji bazuje na

obserwacji ró»norodno±ci populacji, która maleje wraz z

kolejnymi generacjami. Obni»enie ró»norodno±ci poni»ej

pewnego progu, ±wiadczy o przej±ciu algorytmu do etapu

eksploatacji ekstremum. Na przykład ró»norodno±¢ populacji

mo»na okre±li¢ badaj¡c odchylenia standardowe genotypów

( X i − X i ( t )) 2 .

Zaniksamoczynnieadaptowanegooperatoramutacji

opiera si¦ na spostrze»eniu, »e je±li w algorytmie stosuje si¦

adaptacj¦ zasi¦gu mutacji, to od pewnego momentu zasi¦g

ten ma trwał¡ tendencj¦ do zmniejszania si¦. Wi¡»e si¦ to z

faktem, »e algorytm zaczyna eksploatacj¦ znalezionego

ekstremum. W tym kryterium przyjmuje si¦, »e zmniejszenie

±redniej warto±ci odchyle« standardowych poni»ej zadanego

progu powoduje zako«czenie poszukiwa«.

Algorytmygenetyczneiprocesyewolucyjne–W4

1 / ( µ − 1 ) X

X 2 P t

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: