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

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?

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.

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

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.

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.

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?

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!

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.

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!