Nach dem, was ich gelesen habe, werden genetische Algorithmen normalerweise (immer?) Auf Chromosomen von Bits angewendet. Wenn ein Problem darin besteht, eine Funktion zu maximieren, die ganzzahlige Werte annimmt, werden die ganzen Zahlen zuerst als Bits codiert.
Ist diese Zuordnung notwendig? Es scheint, dass Sie Chromosomen von ganzen Zahlen nehmen und Crossover und Mutation direkt anwenden könnten. Wenn ich also eine Funktion habe, die 35 Ganzzahl-Eingaben akzeptiert, kann ich die genetischen Operatoren einfach auf diese Ganzzahlen anwenden und nicht auf die 35xB-Bits (wobei B die Anzahl der Bits ist, die zum Codieren einer Ganzzahl benötigt werden). Gibt es einen Grund, warum dies nicht getan wird?
Vielleicht würde der Algorithmus darunter leiden, weil das Problem gröber definiert ist (das heißt, ein Problem kann mit kürzeren Chromosomen definiert werden, wenn wir keine Bits verwenden), aber ich bin gespannt, ob jemand eine bessere Antwort hat.
quelle
Antworten:
Das Codieren der Werte als Bits ist nicht erforderlich. Schauen Sie sich das 2D-Box-Auto an (verschwenden Sie nicht zu viel Zeit damit), um ein Beispiel zu erhalten, bei dem die Frequenzweiche für ganze (Float-) Werte durchgeführt wird. Ganze 'Baugruppen' werden überkreuzt. Dies trägt zur Erkennbarkeit der Quelle bei (Teil der Ästhetik des Spiels), macht es jedoch so, dass die Variationen zwischen einem bestimmten Chromosom und seinen Eltern geringer sind.
Der Grund für die Verwendung von Bits anstelle von Ganzzahlen hängt mit dem Datenbereich zusammen, mit dem der Pool gesetzt wird. 35 Ganzzahlen bedeuten, dass eine Überkreuzung nur bei 35 Werten auftreten kann, die als ganze Werte betrachtet werden. 1120 Bit (35 * 32-Bit-Ganzzahlen) ergeben eine feinere Granularität (berücksichtigen Sie die traditionellen "genetischen Algorithmen", die an ATCG arbeiten - nicht die gesamten "Werte" von Aminosäuren oder Proteinen).
Mit Bits können Sie "sauberere" Mutationen (ein bisschen umdrehen) und eine Überkreuzung erzielen, die den oberen Teil einer Ganzzahl und den unteren Teil einer anderen Ganzzahl übernimmt. Beides trägt dazu bei, die potenzielle Vielfalt der Nachkommen zu erhöhen.
Betrachten Sie das Chromosom von nur zwei Bytes (wir machen eher Bytes als ganze Zahlen, um das Sehen zu erleichtern):
Eine Überkreuzung zwischen diesen beiden Chromosomen kann nur an begrenzten Stellen erfolgen. Sie werden am Ende haben mit:
Wenn dies stattdessen als Bits gemacht wurde:
Jetzt können Sie die
^Sites für Crossover-Spenden auswählen :Dies liefert ein reichhaltigeres Modell mit mehr möglichen Variationen zwischen zwei Chromosomen.
quelle
Solange Sie einen Crossover haben und mutieren, sind Sie im Geschäft. Der zugrunde liegende Typ spielt keine Rolle. Ich habe GAs in Diagrammstrukturen gesehen, bei denen Crossover und Mutate direkt in Diagrammen arbeiten und Knoten hinzufügen oder kombinieren.
Eigentlich codiere ich normalerweise alles in Zeichen und stelle dann Crossover und Mutation auf Byte-Ebene bereit, anstatt auf Bits. Das Hinzufügen einer Bitmaske, um es auf die Bitebene zu bringen, ist nicht schwer, aber das Leben ist einfach zu kurz.
quelle
In GA werden normalerweise alle Chromosomen als Bitfolgen dargestellt. Sie können Ausnahmen haben, aber vergessen wir sie vorerst.
Ein Chromosom ist eine mögliche Lösung für Ihr Problem. Wenn Ihre Lösung also eine Ganzzahl ist, muss sie eine binäre Darstellung haben, damit die genetischen Operationen funktionieren. Zum Glück, ganze Zahlen haben bereits diese binäre Darstellung (in der Tat, * sie sind nativ Bitfolgen), so eröffnen Sie bitte etwas zu tun haben, gelten nur die Betreiber über Einzelpersonen Ihrer Bevölkerung entlang des Evolutionsprozesses.
quelle
Die Zuordnung ist nicht erforderlich.
Die Differential Evolution (DE) ist eine sehr erfolgreiche "Teilmenge" des breiteren Raums genetischer Algorithmen.
Die erste große Änderung besteht darin, dass DE tatsächliche reelle / ganzzahlige Zahlen anstelle von Bitfolgen verwendet (normalerweise reelle Zahlen zur numerischen Optimierung, ganze Zahlen in anderen Feldern).
Auf jeden Fall ist es schön, Dinge als tatsächliche Zahlen darstellen zu können.
Dies ist eine Möglichkeit, Computerressourcen effizient zu nutzen und die Eingabe und Ausgabe für den Benutzer transparent zu machen: Parameter können als normale Zahlen eingegeben, bearbeitet und ausgegeben werden, ohne jemals als Gene mit einer anderen binären Darstellung neu formatiert zu werden.
Für das Problem der "gröberen Definition" verwendet DE modifizierte Mutations- / Crossover-Operatoren, die den Unterschied zwischen zwei oder mehr ganzzahligen / reellen Vektoren in der Population nutzen, um einen neuen Vektor zu erstellen (z. B. durch Hinzufügen eines zufälligen Anteils des Unterschieds) zu einem der vorhandenen Vektoren plus einer kleinen Menge zufälligen Rauschens).
Von der differentiellen Evolution - Ein praktischer Ansatz zur globalen Optimierung
quelle