Beweisbare Aussagen über genetische Algorithmen

Genetische Algorithmen werden in der Welt der Theorie nicht sehr gut aufgenommen, aber sie sind eine einigermaßen gut verwendete metaheuristische Methode (mit metaheuristisch meine ich eine Technik, die generisch auf viele Probleme wie Tempern, Gradientenabstieg und dergleichen angewendet wird). Tatsächlich ist eine GA-ähnliche Technik für euklidische TSP in der Praxis ziemlich effektiv .

Einige Metaheuristiken sind theoretisch einigermaßen gut untersucht: Es wird an der lokalen Suche und dem Tempern gearbeitet. Wir haben ein ziemlich gutes Gespür dafür, wie alternierende Optimierung ( wie k-means ) funktioniert. Aber soweit ich weiß, ist nichts wirklich Nützliches über genetische Algorithmen bekannt.

Gibt es eine solide algorithmische / Komplexitätstheorie zum Verhalten genetischer Algorithmen in irgendeiner Weise, Form oder Gestalt? Während ich von Dingen wie der Schematheorie gehört habe, würde ich sie von der Diskussion ausschließen, basierend auf meinem gegenwärtigen Verständnis des Gebiets, weil sie nicht besonders algorithmisch ist (aber ich könnte mich hier irren).

Y. Rabinovich, A. Wigderson. Techniken zur Begrenzung der Konvergenzrate genetischer Algorithmen. Random Structures Algorithms, vol. 14, nein. 2, 111-138, 1999. (Auch auf der Homepage von Avi Wigderson erhältlich )

Schauen Sie sich die Arbeit von Benjamin Doerr aus der Gruppe Algorithmen am Max-Planck-Institut (MPI) an. Es geht darum, nachweisbare Beiträge zu evolutionären Algorithmen zu leisten.

Insbesondere hat Doerr ein relevantes aktuelles Buch, Theory of Randomized Search Heuristics, mitherausgegeben

Ingo Wegener beschäftigte sich nicht nur mit simuliertem Tempern, sondern auch mit evolutionären Algorithmen. Sehenswert ist auch die Dissertation seines Doktoranden Dirk Sudholt.

Kennen Sie dieses Papier:

Jens Jägersküpper. Kombination von Markov-Ketten-Analyse und Drift-Analyse: Der (1 + 1) -Entwicklungsalgorithmus für lineare Funktionen neu geladen .

Es zeigt eine erwartete Laufzeit von für lineare Funktionen für eine Klasse von evolutionären Algorithmen.$O(n\log n)$

Während des letzten Jahrzehnts wurden erhebliche Fortschritte bei der Laufzeitanalyse von Evolutionsalgorithmen, der Optimierung von Ameisenkolonien und anderen Metaheuristiken erzielt. Eine Übersicht finden Sie bei Oliveto et al. (2007) .

Lovasz und Vempala (FOCS 2003, Sonderausgabe von J. Comp. System Sci.) Verwenden eine Variante des simulierten Temperns, um einen besseren ( ) - Algorithmus zur Berechnung des Volumens eines konvexen Körpers zu erhalten. Offensichtlich können sie etwas über die von ihnen verwendete Variante beweisen, um die nachweisbare Obergrenze für ihren Gesamtalgorithmus zu erhalten.$O^*(n^4)$

Überprüfen Sie diese Referenzen:

Lothar Schmitt, Theorie genetischer Algorithmen II: Modelle für genetische Operatoren über die String-Tensor-Darstellung von Populationen und die Konvergenz zu globalen Optima für beliebige Fitnessfunktionen unter Skalierung

Shiu Yin Yuen; BKS Cheung, Grenzen für die Erfolgswahrscheinlichkeit des klassischen genetischen Algorithmus basierend auf der Hamming-Distanz

Chang CY Dorea; Judinor A. Guerra Jr .; Rafael Morgado; Andre GC Pereira, Mehrstufige Markov-Kettenmodellierung des genetischen Algorithmus und Konvergenzergebnisse

C. Dombry, Ein gewichtetes Zufallsmodell. Anwendung auf einen genetischen Algorithmus

Es gibt auch eine Veröffentlichung von D. BHANDARI, CA MURTHY und SK PAL (online leider nicht verfügbar), die einen Konvergenzbeweis unter zwei Voraussetzungen liefert:

• Auswahl der Eliten: Die beste Lösung der Generation muss in der Generationt + $t$$t+1$
• Mit dem Mutationsoperator kann in endlichen Schritten von einer beliebigen Lösung zu einer anderen gewechselt werden

Der Konvergenznachweis verwendet ein Markov-Kettenmodell.

Hier die Referenz: Dinabandhu Bhandari, CA Murthy: Genetischer Algorithmus mit elitärem Modell und seiner Konvergenz. IJPRAI 10 (6): 731-747 (1996)

Mathematische Modelle genetischer Algorithmen mit endlichen, aber nicht einheitlichen Populationen sind unhandlich und konnten bisher nur für die trivialsten Fitnessfunktionen analysiert werden. Interessanterweise gibt es ein aufregendes und schönes Ergebnis über die Rechenleistung genetischer Algorithmen , wenn Sie bereit sind, ein Symmetrieargument anzunehmen , ein Argument, das sich also nicht auf die Grenzen eines formalen axiomatischen Systems beschränkt.

Insbesondere kann ein genetischer Algorithmus mit einheitlicher Überkreuzung eine große Anzahl grober Schemapartitionen implizit und parallel auswerten und Partitionen effizient identifizieren, deren konstituierende Schemata unterschiedliche durchschnittliche Fitnesswerte aufweisen. Diese Form der impliziten Parallelität ist tatsächlich mächtiger als die von John Holland und seinen Schülern beschriebene und kann im Gegensatz zu der von Holland beschriebenen impliziten Parallelität experimentell verifiziert werden. (Siehe diesen Blog-Beitrag.)

Der folgende Artikel erklärt, wie genetische Algorithmen mit einheitlichem Crossover-Parlay Parallelität in eine allgemeine, globale Optimierungsheuristik namens Hyperclimbing implizieren :

Erklären der Optimierung in genetischen Algorithmen mit einheitlicher Frequenzweiche . Erscheinen im Tagungsband der Foundations of Genetic Algorithms 2013.

(Haftungsausschluss: Ich bin der Autor des Papiers)

Raphael Cerf hat seine Doktorthese auf genetische Algorithmen in Montpellier unter der Leitung von Alain Berlinet, aus mathematischer Sicht. Es ist ziemlich alt, würde aber wahrscheinlich zu jeder Bibliographie über genetische Algorithmen gehören.