Zeitliche Komplexität genetischer Algorithmen

Wie bestimmen Sie die zeitliche Komplexität eines genetischen Algorithmus (im Allgemeinen)? Wenn möglich.

Ich habe viel darüber nachgedacht, und alle meine Lehren beziehen sich auf die Bestimmung der zeitlichen Komplexität von Problemen, die viel weniger stochastischer Natur sind.

Genetische Algorithmen sind metaheuristisch und als solche gibt es keine allgemeine Analyse, die für alle genetischen Algorithmen gleichzeitig gilt (ohne super locker zu sein). Wenn Sie nach Informationen zur Laufzeit genetischer Algorithmen suchen, haben Sie im Allgemeinen mehr Glück, wenn Sie die Begriffe "Konvergenzzeit" verwenden, da dies die gebräuchlichste Terminologie ist. Ein guter Anfang für einige formale Techniken:

Y. Rabinovich, A. Wigderson. Techniken zur Begrenzung der Konvergenzrate genetischer Algorithmen. Random Structures Algorithms, vol. 14, nein. 2, 111-138, 1999.

Weitere Ressourcen zu formalen Behandlungen finden Sie in der theoretischen Frage: Bereitstellbare Aussagen zu genetischen Algorithmen .

Ich stimme den vorherigen Antworten zu und füge auch Folgendes hinzu.

Wir kümmern uns normalerweise nicht um die zeitliche Komplexität eines genetischen Algorithmus. In der Regel ist es uns wichtig, wie gut die Ergebnisse im Vergleich zu einigen Benchmarks sind und wie hoch die Konvergenzrate ist.

Sie können jedoch sehen, dass genetische Algorithmen in Iterationen ausgeführt werden. Zu Beginn wird eine Reihe von Lösungen zufällig erzeugt ( wird als Population bezeichnet). Die Kosten der Lösungen von werden berechnet. Einige Operationen werden über die Lösungen von in jeder Iteration ausgeführt, wie z. B. Überkreuzung, Mutation usw. Die besten Lösungen in werden in und wir fahren wie zuvor fort. Nach der letzten Iteration geben wir die beste Lösung aus, die wir gefunden haben.$S$$S$$S$$S$$k$$k$$S$

Sie können hier feststellen, dass die Zeitkosten einer Iteration von den inneren Operationen abhängen (z. B. Überkreuzungen, Mutationen und andere, Finden der besten unterschiedlichen Lösungen, Generieren zufälliger Lösungen, Berechnen der Kosten der Lösungen von usw.), die normalerweise einfach zu handhaben sind implementieren und auch problemabhängig. Im Allgemeinen hängen sie von der Größe einer Lösung ab.$k$$S$

Die Ausführungszeit eines genetischen Algorithmus hängt auch von der Anzahl der Iterationen ab (offensichtlich!). Normalerweise möchten wir aufhören, wenn wir zu einer Lösung konvergieren , die kaum verbessert wird. Wie finde ich die Anzahl der Iterationen, die dies garantieren? Es gibt einige probabilistische Analysen, um die durchschnittliche Konvergenzzeit zu ermitteln. Siehe zum Beispiel [1] (ziemlich interessante Ergebnisse). Sie werden jedoch feststellen, dass wir die Analyse der komplexen Probleme, bei denen genetische Algorithmen verwendet werden, noch nicht erreicht haben. Daher wird in vielen Fällen die Anzahl der Iterationen in einem genetischen Algorithmus experimentell bestimmt.

[1] Oliveto, Pietro S., Jun He und Xin Yao. "Zeitliche Komplexität evolutionärer Algorithmen zur kombinatorischen Optimierung: Ein Jahrzehnt der Ergebnisse." Internationales Journal für Automatisierung und Datenverarbeitung 4.3 (2007): 281-293.