Aufbringen Crossover und Mutation zu einem Diagramm (genetischer Algorithmus)

Question

Ich spiele arround mit einem genetischen Algorithmus, in dem ich will Graphen entwickeln. Kennen Sie einen Weg, Kreuzung und Mutation anzuwenden, wenn die Chromosomen sind Graphen?

Oder bin ich eine Codierung für die Graphen fehlen, die lassen Sie mich „normalen“ Crossover und Mutation über Bitfolgen anwenden?

Vielen Dank! Jede Hilfe, auch wenn sie nicht direkt zu meinem Problem zu tun hat, so wird geschätzt!

Manuel

Answer 1

ich wie Sandor Vorschlag von Ken Stanley mit NEAT-Algorithmus .

wurde NEAT entwickelt neuronale Netze mit beliebigen Topologien zu entwickeln, aber die sind im Grunde nur gerichtete Graphen. Es gab viele Möglichkeiten, neuronale Netze vor NEAT zu entwickeln, aber einen von NEAT wichtigsten Beiträge waren, dass es einen Weg zu zur Verfügung gestellt führen sinnvolles Crossover zwischen zwei Netzwerken, die unterschiedlichen toplogies haben .

Um dies zu erreichen, NEAT verwendet historische Markierungen jedes Gen zu „line up“ die Gene von zwei Genomen in crossover (ein Prozess nennen Biologen angebracht Synapse ). Zum Beispiel:

_{(Quelle: natekohl.net )}

(In diesem Beispiel ist jedes Gen ein Kasten ist und stellt eine Verbindung zwischen zwei Knoten. Die Zahl an der Spitze eines jedes Gens der historischen ist für diesen Genmarkierungs-.)

Zusammenfassend :. Gene Reihung auf der Grundlage historischer Markierungen ist ein prinzipien Wege-Crossover ohne teure topologische Analyse zwischen zwei Netzwerken ausführen

Answer 2

Sie könnte genauso gut versuchen Genetic Programming . Ein Graph wäre die nächste Sache zu einem Baum und GP verwendet Bäume ... wenn Sie noch GAs wollen GPs stattdessen verwenden dann einen Blick darauf werfen, wie Crossover auf einem GP durchgeführt wird, und das könnte Ihnen eine Idee geben, wie es auszuführen auf den graphischen Darstellungen der GA:

_{(Quelle: geneticprogramming.com )}

Hier ist, wie Crossover für Bäume (und Grafiken) funktioniert:

1. Sie wählen 2 Proben für die Paarung.
2. Sie wählen einen zufälligen Knoten von einem Elternteil und tauschen sie mit einem zufälligen Knoten in dem anderen Elternteil.
3. Die resultierenden Bäume sind die Nachkommen.

Answer 3

Wie andere erwähnt haben, ein gemeinsamer Weg zu Quer Graphen (oder Bäumen) in einem GA ist zu Swap-Subgraphen (Teilbäume). Für Mutation, nur zufällig einige der Knoten ändern (w / geringe Wahrscheinlichkeit).

Alternativ, wenn Sie eine Grafik als Adjazenzmatrix darstellen, dann könnten Sie mutieren Elemente in den Matrizen vertauschen / (Art wie ein zweidimensionales Bit-String verwendet wird).

Answer 4

Ich bin nicht sicher, ob ein Bitstring verwendet, ist die beste Idee, würde ich eher zumindest stellen die Gewichte mit realen Werten. Dennoch bitstrings kann auch arbeiten.

Wenn Sie eine feste Topologie haben, dann beide Crossover und Mutation sind ganz einfach (vorausgesetzt, Sie nur die Gewichte des Netzes entwickeln):

Crossover: Nehmen Sie ein paar Gewichte von einem Elternteil, der Rest von den anderen, sehr einfach durchgeführt werden können, wenn Sie die Gewichte als Array oder einer Liste darstellen. Für weitere Informationen oder Alternativen finden Sie unter http://en.wikipedia.org/wiki/Crossover_% 28genetic_algorithm% 29 .

Mutation:. Einfach einige der Gewichte aus und stellen Sie sie etwas

einige andere Sachen Evolving (zum Beispiel Aktivierungsfunktion) ist ziemlich ähnlich wie diese.

Wenn Sie auch die Topologie entwickeln wollen, dann werden die Dinge viel interessanter. Es gibt einige ziemlich zusätzliche Mutation Möglichkeiten, wie das Hinzufügen eines Knotens (höchstwahrscheinlich mit zwei bereits vorhandenen Knoten), Splitting eine Verbindung (anstelle von A-> B weisen A-> C-> B), das Hinzufügen einer Verbindung oder die Gegensätze von diesen.

Aber Crossover nicht zu einfach sein (zumindest, wenn die Anzahl der Knoten ist nicht festgelegt), weil Sie wahrscheinlich wollen „matching“ Knoten finden (wo Matching kann alles sein, aber wahrscheinlich auf eine ähnliche Beziehung gesetzt werden „Rolle “oder ein ähnlicher Platz im Netz). Wenn Sie es auch tun mögen, würde ich empfehlen, bereits vorhandene Techniken zu studieren. Eines, das ich kenne, und wie wird NEAT genannt. Sie können einige Informationen über sie an
finden http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
und http://www.cs.ucf.edu/~kstanley/neat.html

Answer 5

Nun, ich habe noch nie mit einer solchen Implementierung gespielt, aber schließlich für Crossover könnte man einen Zweig eines der Diagramme auswählen und tauschen sie mit einem Zweig von einem anderen Graphen.
Für Mutation Sie zufällig einen Knoten in der Graphik, mit geringer Wahrscheinlichkeit ändern könnten.