Wann sind genetische Algorithmen eine gute Wahl für die Optimierung?

20

Genetische Algorithmen sind eine Form der Optimierungsmethode. Oft ist der stochastische Gradientenabstieg und seine Derivate die beste Wahl für die Funktionsoptimierung, aber manchmal werden noch genetische Algorithmen verwendet. Die Antenne der NASA-Raumsonde ST5 wurde beispielsweise mit einem genetischen Algorithmus erstellt:

ST5 Antenne

Wann sind genetische Optimierungsmethoden die bessere Wahl als häufigere Gradientenabstiegsmethoden?

Gus
quelle
7
+1 Für das Beispiel habe ich das Originalpapier gefunden: alglobus.net/NASAwork/papers/Space2006Antenna.pdf
Tim

Antworten:

19

Genetische Algorithmen (GA) sind eine Familie von Heuristiken, die empirisch in vielen Fällen eine anständige Antwort liefern , obwohl sie selten die beste Option für eine bestimmte Domäne sind.

Sie erwähnen Algorithmen, die auf Derivaten basieren, aber auch ohne Derivate gibt es viele Optimierungsalgorithmen ohne Derivate, die weitaus bessere Ergebnisse erzielen als GAs. Sehen Sie dies und diese Antwort für einige Ideen.

Was viele Standard-Optimierungsalgorithmen gemeinsam haben (sogar ableitungsfreie Methoden), ist die Annahme, dass der zugrunde liegende Raum eine glatte Mannigfaltigkeit (möglicherweise mit einigen diskreten Dimensionen) ist und die Funktion zur Optimierung sich etwas gut verhält.

Es sind jedoch nicht alle Funktionen auf einem glatten Verteiler definiert. Manchmal möchten Sie über einen Graphen oder andere diskrete Strukturen optimieren (kombinatorische Optimierung) - hier gibt es dedizierte Algorithmen, aber GAs funktionieren auch.

Je mehr Sie sich mit Funktionen befassen, die über komplexe, diskrete Strukturen definiert sind, desto nützlicher können GAs sein, insbesondere wenn Sie eine Darstellung finden, in der die genetischen Operatoren optimal arbeiten (was viel Hand-Tuning und Domänenwissen erfordert).

Natürlich könnte die Zukunft dazu führen, GAs ganz zu vergessen und Methoden zu entwickeln, um diskrete Räume auf kontinuierliche Räume abzubilden und die Optimierungsmaschinerie zu verwenden, die wir für die kontinuierliche Darstellung haben.

lacerbi
quelle
2

Genetische Methoden eignen sich gut für die Optimierung von Multikriterien, wenn der Gradientenabstieg der Optimierung von Monokriterien gewidmet ist. Gradientenabstieg erlaubt es, ein Minimum an Funktionen zu finden, wenn Ableitungen existieren und es nur eine optimale Lösung gibt (wenn wir lokale Minima ausnehmen). Ein genetischer Algorithmus kann bei Problemen mit mehreren Kriterien eingesetzt werden und zu einem Kontinuum von Lösungen führen, bei denen sich jedes einzelne Individuum einer Population aus einer ursprünglichen Population entwickelt hat. Die zu optimierenden Werte sind die Phänotypen der Individuen und es kann mehrere Phänotypen geben. Im Allgemeinen hat keines der Individuen gleichzeitig den besseren Wert jedes Phänotyps, so dass es nicht nur eine Lösung gibt. Die Individuen in der Endpopulation, die alle Lösungen der Optimierung sind, sind Teil der "Pareto-Front" und als "Pareto-Rang Eins" gekennzeichnet. Einzelpersonen. Dies bedeutet, dass im Vergleich zu allen anderen Individuen, die für jeden Phänotyp die gleiche Leistung aufweisen, sie für einen Phänotyp mindestens besser sind als die anderen.

manu190466
quelle
Ok für eine Ablehnung, aber kannst du erklären, wo ich falsch liege?
manu190466
5
Diese Site bewertet Antworten, die Kontext und Hintergrund liefern. Auf dieser Hilfeseite erfahren Sie, wie Sie Antworten bereitstellen, die unser Repository mit nützlichen Antworten auf interessante Fragen ergänzen. Das Erklären Ihrer Antwort ist auch ein guter Weg, um Ihr eigenes Verständnis zu testen. In diesem Fall möchten Sie beispielsweise näher erläutern, wie genetische Algorithmen "für die Optimierung von Multikriterien gut geeignet sind", da die Wikipedia-Seite einwertige Fitnessfunktionen als Ziele für genetische Algorithmen zu implizieren scheint.
EdM
0

Am besten in welchem ​​Sinne?

Nach meiner Erfahrung sind GAs einer der pragmatischsten Optimierer. Während viel genauere Algorithmen Zeit und Mühe erfordern, um reale Probleme in der mathematischen Welt zu formalisieren, können GAs jede Kostenfunktion mit komplexen Regeln und Einschränkungen bewältigen (GAs werden nach einem Ausführungsansatz und nicht nach einer spezifischen Berechnung verknüpft). Dieser Vorgang ist unkompliziert und Sie können viele Ansätze für die Erkundungsarbeit ausprobieren.

Ich schätze auch die Möglichkeit, vergangene Lösungen für zukünftige Läufe wieder in den Algorithmus einzufügen, was für wiederholte Aufgaben gut ist.

Konzeptionell kann ein genetischer Algorithmus durch eine Hashmap von Funktionen dargestellt werden und eignet sich daher für funktionale Sprachen wie Clojure, eine Sprache, mit der Sie sehr schnell große Ergebnisse erzielen können.

Genetische Algorithmen können auch verschachtelt werden: Die Kostenfunktion einer GA kann eine GA sein! Diese Algorithmen nutzen moderne Hardware und Infrastruktur, die es ihnen ermöglichen, eine sehr große Population zu berechnen, sodass Sie selbst mit einfachen Mutations- / Auswahloperationen immer noch gute Ergebnisse erzielen.

Selbst bei einfachen Problemen wie dem Auffinden des Minimums einer Wellenfunktion sind GAs nicht so schlecht und können in akzeptabler Zeit eine anständige Präzision erreichen.

Ja, analytische Lösungen haben zwar eine schnellere Ausführungszeit und Präzision, aber die Zeit, die erforderlich ist, um diese Übergewichte zu erzielen, hat häufig Vorteile! Also wann? Fast immer für mich, zumindest zur Meta-Optimierung.

Joseph Yourine
quelle
Der Hauptschwerpunkt dieses Arguments scheint darin zu liegen, dass genetische Algorithmen Black-Box-Optimierer sind. Aber es gibt viele Black-Box-Optimierer. Warum sollte dies besser sein als andere Entscheidungen? Außerdem glaube ich nicht, dass GAs wirklich leicht mit Einschränkungen umgehen können. Wenn zum Beispiel die Funktion mit Ausnahme eines 3D-Subraums in einer 4D-Welt undefiniert ist, würde eine Vanille-GA mit Sicherheit versagen.
Cliff AB
@CliffAB Tatsächlich habe ich nichts dazu gesagt und vielleicht eher das Gegenteil. In GA haben Sie viel Kontrolle über die Kernberechnung, die GA selbst besteht aus einer Abfolge von Schritten und einer leichten Reihenfolge. Wenn Sie Kostenfunktionen definieren, können Sie alle Funktionen ausführen, auch externe Einschränkungen, die Sie abfragen können. Meine Hauptargumente sind: Behandeln Sie viele Probleme, Sie müssen sich nicht um die Kompatibilität mit dem Framework kümmern (Sie müssen nur Kosten erstatten), und in den meisten Geschäftsfällen AUCH dann, wenn dies nicht immer der Fall ist, eine vernünftige reale Lösung finden das beste
Joseph Yourine