Seminarium ZTI

Zbieżność algorytmów genetycznych

Stefan Kotowski

piątek, 27 października 2006, godz. 10:00, sala S-4

Zagadnienie zbieżności pewnych typów algorytmów genetycznych Stefan Kotowski Instytut Podstawowych Problemów Techniki PAN Algorytmy genetyczne należą do metod optymalizacyjnych, które czerpią inspirację z procesów zachodzących w przyrodzie, takich jak naturalna ewolucja i adaptacja. Różne typy obliczeń ewolucyjnych różnią się zakresem i sposobem naśladowania naturalnej ewolucji. Analiza teoretyczna algorytmów jest nadal cząstkowa i bazuje na modelu Prostego Algorytmu Genetycznego. Analiza zachowań asymptotycznych algorytmów korzysta z modelu Markowa Prostego Algorytmu Genetycznego. Korzystając z modelu algorytmu w postaci procesu Markowa, udowodnione zostało twierdzenie o istnieniu rozkładu niezmienniczego (asymptotycznej stabilności), dla algorytmu genetycznego, niezależnego od warunków początkowych (populacji początkowej). Twierdzenie jest prawdziwe dla prostego algorytmu genetycznego (model z selekcją i mutacją dla populacji skończonych). Tak więc udowodnione zostało, że prosty algorytm genetyczny jest zbieżny w sensie probabilistycznym. Podobnie analizowano problem punktowej asymptotycznej stabilności (zbieżności do jednej, konkretnej populacji). Uzyskane zostały warunki punktowej asymptotycznej stabilności oraz oszacowano prędkość takiej zbieżności. Prezentowane badania są uogólnieniem poprzednio otrzymanych wyników na przypadek gdy parametry algorytmu genetycznego są dostrajane (sterowane) a selekcja nie jest ruletkową. Udowodniono zbieżność algorytmów których parametry są poddane procesowi samoadaptacji, lub są modyfikowane przez równoległy algorytm genetyczny. Dowiedziono też zbieżność algorytmu z selekcją elitarną .