Sprawdzalne stwierdzenia na temat algorytmów genetycznych

Algorytmy genetyczne nie cieszą się dużą popularnością w świecie teorii, ale są one dość dobrze stosowaną metodą metaheurystyczną (przez metaheurystyczny mam na myśli technikę, która ogólnie stosuje się w wielu problemach, takich jak wyżarzanie, opadanie gradientu i tym podobne). W rzeczywistości technika podobna do GA jest dość skuteczna w przypadku euklidesowej TSP w praktyce.

Niektóre metaheurystyki są dość dobrze zbadane teoretycznie: trwają prace nad lokalnym wyszukiwaniem i wyżarzaniem. Mamy całkiem dobre wyczucie, jak działa naprzemienna optymalizacja ( np. K-średnie ). Ale o ile wiem, algorytmy genetyczne nie są tak naprawdę przydatne.

Czy istnieje jakaś solidna teoria algorytmiczna / złożoności dotycząca zachowania algorytmów genetycznych w jakikolwiek sposób, kształcie lub formie? Chociaż słyszałem o takich rzeczach, jak teoria schematu , wykluczam ją z dyskusji opartej na moim obecnym zrozumieniu tego obszaru, ponieważ nie jestem szczególnie algorytmiczny (ale mogę się tutaj mylić).

Y. Rabinovich, A. Wigderson. Techniki ograniczania współczynnika konwergencji algorytmów genetycznych. Algorytmy struktur losowych, vol. 14, nr 2, 111-138, 1999. (Dostępne również ze strony głównej Avi Wigderson )

Zobacz pracę Benjamina Doerr z grupy Algorytmy z Maxa Plancka (MPI). Chodzi o próbę wniesienia możliwego do udowodnienia wkładu w algorytmy ewolucyjne.

W szczególności Doerr jest współredaktorem najnowszej książki Theory of Randomized Search Heuristics

Oprócz pracy nad symulowanym wyżarzaniem, Ingo Wegener miał pewne teoretyczne wyniki dotyczące algorytmów ewolucyjnych. Teza jego doktoranta Dirk Sudholt jest także warte obejrzenia.

Czy znasz ten artykuł:

Jens Jägersküpper. Łączenie analizy łańcucha Markowa i analizy dryfu: Algorytm ewolucyjny (1 + 1) dla funkcji liniowych załadowano ponownie .

Pokazuje oczekiwany czas działania dla funkcji liniowych dla klasy algorytmów ewolucyjnych.$O(n\log n)$

W ciągu ostatniej dekady poczyniono znaczne postępy w analizie w czasie wykonywania algorytmów ewolucyjnych, optymalizacji kolonii mrówek i innych metaheurystyk. Ankieta znajduje się w Oliveto i in. (2007) .

Lovasz i Vempala (wydanie specjalne J. Comp. System Sci. FOCS 2003) wykorzystują wariant symulowanego wyżarzania, aby uzyskać lepszy ( ) algorytm do obliczania objętości ciała wypukłego. Oczywiście mogą udowodnić coś o używanym wariancie, aby uzyskać możliwą do udowodnienia górną granicę swojego ogólnego algorytmu.$O^*(n^4)$

Sprawdź te referencje:

Lothar Schmitt, Teoria algorytmów genetycznych II: modele operatorów genetycznych w odniesieniu do reprezentacji populacji przez tensor strunowy i konwergencja do globalnych optymów dla arbitralnej funkcji sprawności pod skalowaniem

Shiu Yin Yuen; BKS Cheung, Granice prawdopodobieństwa sukcesu klasycznego algorytmu genetycznego opartego na odległości hamowania

Chang CY Dorea; Judinor A. Guerra Jr .; Rafael Morgado; Andre GC Pereira, Wielostopniowe modelowanie łańcucha Markowa algorytmu genetycznego i wyniki konwergencji

C. Dombry, Ważony model chodzenia losowego. Zastosowanie do algorytmu genetycznego

Istnieje również artykuł D. BHANDARI, CA MURTHY i SK PAL (niestety niedostępny w Internecie), który zapewnia dowód zbieżności przy dwóch założeniach:

• Wybór elitystów: najlepszym rozwiązaniem generacji musi być generacjat + $t$$t+1$
• Operator mutacji pozwala na przejście z jednego rozwiązania do drugiego w skończonej liczbie kroków

Dowód konwergencji wykorzystuje model łańcuchowy Markowa.

Oto odniesienie: Dinabandhu Bhandari, Kalifornia Murthy: Genetic Algorytm z modelem elitarnym i jego konwergencja. IJPRAI 10 (6): 731-747 (1996)

Modele matematyczne algorytmów genetycznych ze skończonymi, ale niejednolitymi populacjami są nieporęczne i jak dotąd okazały się niemożliwe do analizy dla wszystkich oprócz najbardziej trywialnych funkcji sprawności. Co ciekawe, jeśli jesteś gotów zaakceptować argument symetrii , argument, innymi słowy, nie sformułowany w ramach formalnego systemu aksjomatycznego, to można uzyskać ekscytujący i piękny wynik dotyczący mocy obliczeniowej algorytmów genetycznych.

W szczególności algorytm genetyczny z jednorodnym przejściem jest w stanie oszacować ogromną liczbę gruboziarnistych partycji schematu niejawnie i równolegle i może skutecznie identyfikować partycje, których schematy składowe mają różne średnie wartości sprawności. Ta forma niejawnego paralelizmu jest w rzeczywistości silniejsza niż ta opisana przez Johna Holland'a i jego uczniów, i w przeciwieństwie do niejawnej paralelizmu opisanego przez Holandię, można zweryfikować eksperymentalnie. (Zobacz ten post na blogu.)

W poniższym artykule wyjaśniono, w jaki sposób algorytmy genetyczne z jednolitym przejściem krzyżowym sugerują równoległość równoległą do heurystycznej optymalizacji globalnej o nazwie hyperclimbing :

Wyjaśnienie optymalizacji algorytmów genetycznych z jednolitym zwrotem krzyżowym . Wystąpić w obradach konferencji Podstawy algorytmów genetycznych 2013.

(Uwaga: Jestem autorem artykułu)

Raphael Cerf zrobił doktorat tezę o Algorytmy genetyczne w Montpellier pod nadzorem Alain Berlinet, z matematycznego punktu widzenia. Jest dość stary, ale prawdopodobnie należałby do dowolnej bibliografii na temat algorytmów genetycznych.