Lösen Sie das Kreuzworträtsel mit genetischem Algorithmus, Fitness, Mutation

Question

Ich bemühe mich, ein Labor für die Schule zu machen. Ich versuche, ein Kreuzworträtsel mit genetischen Algorithmen zu lösen. Problem ist, dass dies nicht sehr gut ist (es ist immer noch zu zufällig). Ich werde versuchen, eine kurze Erklärung zu geben, wie mein Programm jetzt implementiert wird:

Wenn ich das Puzzle habe (# ist Block, ist 0 leerer Raum)

#000
00#0
#000

und eine Sammlung von Wörtern, die Kandidaten für die Lösung dieses Puzzles sind. Meine DNA ist einfach die Matrix als 1D -Array.

Mein erster Satz von Individuen hat zufällig generierte DNAs aus dem Pool der Buchstaben, die meine Wörter enthalten.

Ich habe die Auswahl mit Roulette-Auswahl. Es gibt einige Parameter über die Wahrscheinlichkeit von Kombination und Mutationen, aber wenn Mutation eintritt, werde ich immer 25% der DNA ändern. Ich ändere es mit zufälligen Buchstaben aus meinem Buchsteb Pool. (Dies kann negative Auswirkungen haben, da die Mutationen bereits gebildete Wörter zerstören können)

Jetzt die Fitnessfunktion: Ich durchquere die Matrix sowohl horizontalisch als auch vertikal: Wenn ich ein Wort dann finde, dann Fitness += Word.lengh +1

Wenn ich eine Zeichenfolge finde, die Teil eines Wortes ist, dann Fitness += Word.length / (puzzle_size*4). Wie auch immer, es sollte einen Wert zwischen 0 und 1 geben, sodass es "von" Tool "und Anzeigen X zu Fitness finden kann, dann direkt nachdem es" auch "aus" Tool "gefunden hat und ein weiteres Y zu Fitness hinzufügt.

Meine Generationen verbessern sich im Laufe der Zeit nicht wirklich. Sie erscheinen zufällig. Selbst nach 400 Generationen mit einem Pool von 1000-2000 (diese Zahlen spielt keine Rolle), erhalte ich eine Lösung mit 1-2 Wörtern (von 2 oder 3 Buchstaben), wenn die Lösung 6 Wörter haben sollte.

Answer 1

Ich denke, Ihre Fitnessfunktion könnte schlecht definiert sein. Ich würde dies einrichten, damit jede Reihe ein binäres Fitnessniveau hat. Entweder ist eine Reihe fit oder nicht. (zB einer Zeile ist ein Wort oder es ist kein Wort) Dann wäre die Gesamtfitness der Lösung #fit -Zeilen / Gesamtzeilen (sowohl horizontal als auch vertikal). Außerdem ändern Sie zu viel von der DNA, ich würde diese Variable machen und damit experimentieren.

Answer 2

Ihre Fitnessfunktion sieht für mich in Ordnung aus, obwohl es ohne Details schwierig ist, ein wirklich gutes Bild von dem zu machen, was Sie tun.

Sie geben die Mutationswahrscheinlichkeit nicht an, aber wenn Sie mutieren, sind 25% eine sehr hohe Mutation. Auch die Auswahl der Roulette -Rad gilt a viel Auswahldruck. Was Sie oft sehen, ist, dass der Algorithmus ziemlich früh eine Lösung findet, die ein bisschen besser ist als alle anderen, und die Roulette -Radauswahl führt dazu davon. Zu diesem Zeitpunkt hält die Suchhöfe mit Ausnahme der gelegentlichen blind glücklichen Mutation an, und da Ihre Mutationen so groß sind, ist es sehr unwahrscheinlich, dass Sie einen Verbesserungszug finden, ohne den Rest des Chromosoms zu zerstören.

Ich würde eine binäre Turnierauswahl und einen vernünftigeren Mutationsoperator ausprobieren. Die üblichen heuristischen Menschen, die für Mutation verwendet werden, besteht darin, (im Durchschnitt) eines "Bits" jedes Chromosoms zu drehen. Sie möchten jedoch nicht jedes Mal eine deterministische Änderung eines Buchstabens. Etwas wie das:

for(i=0; i<chromosome.length(); ++i) {
    // random generates double in the range [0, 1)
    if(random() < 1.0/chromosome.length()) {
       chromosome[i] = pick_random_letter();
    }
}