Verstößt die Definition des Haltepunkts eines genetischen Algorithmus gegen den Zweck des Algorithmus?

11

Wikipedia definiert den Endpunkt einer GA dazu:

Im Allgemeinen wird der Algorithmus beendet, wenn entweder eine maximale Anzahl von Generationen erzeugt wurde oder ein zufriedenstellendes Fitnessniveau für die Bevölkerung erreicht wurde. Wenn der Algorithmus aufgrund einer maximalen Anzahl von Generationen beendet wurde, kann eine zufriedenstellende Lösung erreicht worden sein oder nicht.

Wenn es nun endet, wenn ein zufriedenstellendes Fitnessniveau erreicht wurde und Sie dieses Fitnessniveau definieren, warum könnten Sie dann nicht einfach von Anfang an das "perfekte" Genom selbst erstellen, da Sie die Eigenschaften bereits kennen dieses perfekten Genoms?

Ich glaube, ich bin hier nur ein bisschen verwirrt. Ich dachte, der Zweck eines GA war es, uns ständig weiterzuentwickeln und uns möglicherweise eine noch bessere Lösung zu zeigen, als wir gedacht hatten, und unsere Fitnessfunktion war nur etwas, das ihm auf dem Weg geholfen hat, und nicht etwas, das wir als Abschluss auf das Podest gestellt haben. " perfekter "Zustand. Zerstört das nicht den Punkt?

slandau
quelle
1
Wahrscheinlich besser für die Theorie geeignet.
Karl Bielefeldt
Nicht obwohl es das gab :)
slandau
1
@ Karl: Die Frage ist ein bisschen weich für die Theorie. Es wird wahrscheinlich dort geschlossen sein.
Robert Harvey
2
Danke, @Robert. Jetzt erinnere ich mich, warum ich dort nicht besuche. Ich denke, dies ist eine dieser Fragen "zwischen den Rissen".
Karl Bielefeldt
1
Sie kennen auch schon die Eigenschaften Ihres "perfekten Partners": Sie werden Sie vollkommen glücklich machen! Aber das reicht nicht aus, um sie zu finden (geschweige denn von Grund auf neu zu konstruieren ...). Experimente sind ebenfalls notwendig.
Kilian Foth

Antworten:

17

Die Fitnessfunktion wertet die Ausgabe Ihres Algorithmus aus. Es ist durchaus möglich, eine ideale Ausgabe zu erkennen, wenn Sie sie sehen, aber nicht die Schritte kennen, um diese Ausgabe aus einer bestimmten Eingabe zu erzeugen. Hier sind genetische Algorithmen am nützlichsten.

Eine häufig unterhaltsame Anwendung von GA ist beispielsweise die Erstellung einer Animation, mit der eine virtuelle Kreatur auf effiziente Weise bewegt werden kann. Es ist leicht zu erkennen, ob sich die Kreatur mit einer bestimmten Geschwindigkeit in einer relativ geraden Linie bewegt. Das ist deine Fitnessfunktion. Es ist viel schwieriger, die genaue Abfolge der "Muskel" -Bewegungen zu bestimmen, um dies zu erreichen.

Karl Bielefeldt
quelle
3
Es sollte auch beachtet werden, dass Sie häufig nach x Generationen aufhören, weil sich die GA auf unbestimmte Zeit drehen kann, weil sie auf lokalen Minima / Maxima "hängen bleibt", die Ihre optimale Fitnessbewertung nicht erfüllen. Dies kann passieren, wenn Ihre Auswahl- / Crossover- / Mutationsfunktionen nicht gut genug für das Problem eingestellt sind.
Steven Evers
@Karl Ich erinnere mich an Andrew Cookes genetische Algorithmuslösung zur Herstellung der ersten Malbolge "Hello World" und verlor dann eine bessere Lösung per E-Mail an stackoverflow.com/questions/5338627/…
pageman
8

Es ist häufig der Fall, dass Sie die Eignung einer Lösung bestimmen können, aber die Lösung selbst nicht direkt bestimmen können. Angenommen, Sie versuchen, schnelle Kaninchen zu entwickeln, und es gibt eine Handvoll Gene, die die Geschwindigkeit von Kaninchen beeinflussen. Sie können die Geschwindigkeit von Kaninchen testen, aber die Aufzählung aller Kombinationen geschwindigkeitsbezogener Gene wäre unpraktisch. In einem solchen Fall haben Sie möglicherweise eine GA, die Kaninchen rast und die schnellsten züchtet. Sie könnten das für immer tun, aber Sie würden wahrscheinlich lieber aufhören, wenn:

  • Sie haben ein Kaninchen gefunden, das schneller als X ist, oder
  • Die schrittweise Verbesserung über n Generationen ist unter einen bestimmten Schwellenwert gefallen, oder
  • Sie haben Kaninchen durch m Generationen gezüchtet
Caleb
quelle
5

Der gesamte Sinn der GA besteht darin, Ihnen die Lösung für das Problem zu geben, das dieses Fitnessniveau aufweist. Diese Lösung ist mit anderen konventionelleren Suchalgorithmen nur sehr schwer zu finden, weshalb Sie normalerweise in erster Linie eine GA verwenden.

Anstelle eines Fitnesswertlimits können Sie auch entscheiden, wie viele Generationen Sie ausführen möchten (je mehr Generationen Sie ausführen, desto höher ist die Wahrscheinlichkeit, dass Sie immer höhere Fitnesswerte finden). Beispiel: Beim Problem mit reisenden Verkäufern erhalten Sie einen Pfad mit den niedrigsten Kosten zwischen den Städten, die Sie durchqueren müssen.

Ob Ihr Stoppzustand ein bestimmtes Fitnessniveau aufweist, das akzeptabel ist, oder eine bestimmte Zeitbeschränkung (Ausführen des GA für einen maximalen Zeitraum oder eine begrenzte Anzahl von Generationen für zeitkritische Anwendungen wie Pfadfindung oder KI-Anwendungen), hängt normalerweise von Ihrem Problem ab Domain.

Aphex
quelle
3

Intuitiv besteht der Zweck eines genetischen Algorithmus darin, eine algorithmische Lösung für ein Problem zu formulieren, das sich nicht für eine einfache logische Analyse eignet. Sobald dieses Ziel erreicht ist, muss die GA nicht weiter verfolgen.

Wenn eine bessere "Fitness" gewünscht wird, kann der genetische Algorithmus natürlich laufen gelassen werden, um zu sehen, ob er eine besser optimierte Lösung finden kann, oder der genetische Algorithmus kann selbst optimiert werden, um zu sehen, ob er zu einer besseren Lösung konvergiert.

Robert Harvey
quelle
2

Ein genetischer Algorithmus erfordert eine Möglichkeit, gute Gene mit größerer Ausbreitung zu belohnen. Wenn Sie keine Möglichkeit hätten, gute Gene von schlechten Genen zu unterscheiden, könnten Sie überhaupt keinen genetischen Algorithmus verwenden.

Damit ein genetischer Algorithmus funktioniert, müssen Sie zulassen, dass sich die besser geeigneten Lösungen gegenüber den weniger geeigneten Lösungen reproduzieren. Andernfalls würden Sie nur zufällige Lösungen ausprobieren.

Hier ist ein typisches Beispiel aus meiner eigenen Erfahrung: Bei der Entwicklung eines der ersten Sprachwahlsysteme fiel es uns schwer, einen Algorithmus zu finden, mit dem ein gesprochener Name einer gespeicherten Kopie desselben Namens zugeordnet werden kann. Uns wurde gesagt, dass eine Genauigkeit von 95% bei der Auswahl eines von 25 Namen ausreichend sei. Wir hatten ein gespeichertes Korpus von Leuten, die jeweils 10 Mal 25 Namen sagten.

Zuerst haben wir ein Eingabesystem entwickelt, das die Länge des gesprochenen Wortes und die Frequenzenergie in mehreren normalisierten Teilen davon misst. Dann entwickelten wir einen Algorithmus, der den Übereinstimmungen dieser Parameter Gewichte zuwies und zwei Parametersätze anhand dieser Gewichte verglich.

Nun hatten wir einen letzten Schritt - wie sollte der Wert dieser Gewichte sein?

Wir haben 1.000 zufällige Gewichtssätze erstellt und diese gegen den Korpus getestet. Wir haben die 500 weggeworfen, die am schlechtesten abschnitten. Für die restlichen 500 haben wir jedes dupliziert und in einem von ihnen zufällig eines der Gewichte angehoben oder abgesenkt.

Wir haben diesen Vorgang etwa zwei Wochen lang auf einem Computer wiederholt, bis er schließlich eine Reihe von Gewichten hatte, die das 95% ige Genauigkeitskriterium erfüllten. Dann haben wir es an Daten getestet, die nicht im Korpus sind. Es war ungefähr 92% genau. Wir liefen also länger, um eine Genauigkeit von 98% für den Korpus zu erreichen, und dieser Satz von Gewichten ergab eine Genauigkeit von 95% für Daten, die nicht im Korpus enthalten waren.

Der Punkt ist also, dass Sie eine Fitnessfunktion haben müssen, um einen genetischen Algorithmus auszuführen. Wenn Sie keine Möglichkeit haben, gute Gene von schlechten Genen zu unterscheiden, wie können Sie sicherstellen, dass sich die guten Gene reproduzieren und die schlechten Gene nicht?

David Schwartz
quelle
0

Iterieren Sie, bis sich eine Lösung nicht wesentlich von der vorherigen unterscheidet. Bitte verstehen Sie für sehr viel eine feste Toleranz.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

Wenn in diesem Beispiel Ihre feste Toleranz 0,01 betrug, fordert Sie (n + 1) auf, anzuhalten, da abs (Lösung (n + 1) -Lösung (n)) <0,01 ist.

Weiter, dann kann Ihr Algorithmus sagen: Das wird nicht besser!

daniloquio
quelle
0

Für eine schnelle Antwort auf Ihre Hauptfrage: Es gibt einen großen Unterschied zwischen dem Wissen, was Sie erreichen möchten, und dem Wissen, wie Sie dorthin gelangen.

Genauer gesagt, zum Beispiel mit einem der beliebtesten Probleme, die mithilfe genetischer / evolutionärer Algorithmen gelöst werden, normalerweise einer Fallstudie im Unterricht, um die optimale Route in einem Diagramm zu finden. Dies wird häufig in Netzwerken verwendet, um die günstigste Route von einem Ende zum anderen zu finden. Wenn Sie die Kosten definieren (Anzahl der Hopfen, Kosten für jeden Hopfen usw.), definieren Sie auch Ihre Zielkosten (Fitnesslevel), bei denen Sie mit dem Ergebnis zufrieden sind. Ihr Algorithmus findet möglicherweise nicht das beste, aber er findet ein algorithmisch akzeptables Optimum. Damit meine ich, dass das Kosten-Nutzen-Verhältnis, eine bessere Antwort zu finden, verboten ist.

Mit GA / EA werden Sie feststellen, dass es normal ist, dass Sie sehr schnell eine optimale Antwort von 95% + finden, aber die Eingrenzung der letzten 5% ist exponentiell teurer. Die Theorie ist also, dass Sie ein akzeptables Optimum definieren, um das beste Ergebnis in kürzester Zeit zu erzielen. Da die Kosten für das Finden, beispielsweise die obersten 1%, die Vorteile gegenüber den obersten 5% überwiegen können, definieren Sie Ihr akzeptables Optimum.

Zusammenfassend lässt sich sagen, dass Sie jetzt keine Antwort auf ein bestimmtes Problem haben. Sie definieren lediglich pro Problem Ihr akzeptables Optimum, den Punkt, an dem es nicht praktikabel ist, eine bessere Antwort zu finden.

AJC
quelle
0

Es gibt einige Untersuchungen zur Behebung von Fehlern in C mit genetischen Algorithmen, indem negative und positive Testfälle als Fitnessfunktionen sowie fehlerhafter Code als Eingabe bereitgestellt werden. Dies ist ein Beispiel für ein Problem, das von einem Menschen gelöst werden könnte , für einen genetischen Algorithmus jedoch einfacher ist. Es ist wichtig zu beachten:

Obwohl die in diesem Dokument beschriebenen Methoden keine neuen Programme von Grund auf neu entwickeln, zeigen sie, wie ältere Software entwickelt werden kann, um vorhandene Fehler zu beheben.

Aber auch neue Programme sind von Grund auf neu-nur nicht in C. Die wenigen nicht - triviale Programme geschrieben in der entwickelt worden Malbolge esoterische Programmiersprache haben alle (meines Wissens) wurde entwickelt, das nicht geschrieben. Die Sprache ist zu komplex für einen Programmierer und zu kompliziert, um Programme allein aus der Logik effizient abzuleiten. Daher wurde die Mehrzahl der darin geschriebenen Programme mit genetischen Algorithmen erstellt. Die Fitnessfunktion ist im Allgemeinen die Bearbeitungsentfernung zur erwarteten Ausgabe.

Das ist in gewisser Weise schön kreisförmig. Indem wir beobachten, dass komplexer genetischer Code durch evolutionäre Prozesse geschrieben wird, können wir evolutionäre Prozesse simulieren, um Code in einer anderen komplexen Sprache zu erzeugen, ohne zu wissen, wie der Code funktioniert!

Jon Purdy
quelle