Risolvi il cruciverba con algoritmo genetico, fitness, mutazione

Question

Sto cercando di fare un laboratorio per la scuola. Sto cercando di risolvere un cruciverba usando algoritmi genetici. Il problema è che non è molto buono (è ancora troppo casuale) cercherò di dare una breve spiegazione su come è implementato il mio programma ora:

Se ho il puzzle (# è blocco, 0 è spazio vuoto)

#000
00#0
#000

e una raccolta di parole candidate alla soluzione di questo puzzle. Il mio DNA è semplicemente la matrice come un array 1D.

La mia prima serie di individui ha DNA generati casuali dal pool di lettere che le mie parole contengono.

Faccio selezione usando la selezione della roulette. Ci sono alcuni parametri sulla possibilità di combinazione e mutazioni, ma se si verificherà mutazione, cambierò sempre il 25% del DNA. Lo cambio con lettere casuali dal mio pool di lettere. (Questo può avere effetti negativi, poiché le mutazioni possono distruggere parole già formate)

Ora la funzione di fitness: attraverso la matrice sia orizzontalia che verticale: se trovo una parola allora fitness += word.lengh +1

Se trovo una stringa che fa parte di qualche parola, allora fitness += word.length / (puzzle_size*4). Comunque dovrebbe dare un valore compreso tra 0 e 1. in modo che possa trovare "a" da "strumento" e annunci x alla forma fisica, quindi subito dopo aver trovato "troppo" da "strumento" e aggiunge un'altra Y alla forma fisica.

Le mie generazioni non stanno effettivamente migliorando nel tempo. Sembrano casuali. Quindi anche dopo 400 generazioni con un pool di 1000-2000 (questi numeri non contano davvero) ottengo una soluzione con 1-2 parole (di 2 o 3 lettere) quando la soluzione dovrebbe avere 6 parole.

Answer 1

Penso che la tua funzione di fitness potrebbe essere mal definita. Lo imposterei in modo che ogni riga abbia un livello di fitness binario. O una riga è in forma, o non lo è. (Ad esempio, una riga è una parola o non è una parola) quindi l'idoneità complessiva della soluzione sarebbe #fit righe / righe totali (sia orizzontalmente che verticalmente). Inoltre, potresti cambiare troppo del DNA, farei quella variabile e sperimenterei.

Answer 2

La tua funzione di fitness mi sembra a posto, anche se senza maggiori dettagli è difficile ottenere un'immagine davvero buona di quello che stai facendo.

Non si specifica la probabilità di mutazione, ma quando si muta, il 25% è una mutazione molto elevata. Inoltre, la selezione delle ruote della roulette si applica a quantità di pressione di selezione. Quello che vedi spesso è che l'algoritmo abbastanza presto trova una soluzione che è un po 'meglio di tutte le altre, e la selezione delle ruote della roulette fa sì che l'algoritmo lo selezionasse con una probabilità così elevata che si finisce rapidamente con una popolazione piena di copie di quella. A quel punto, la ricerca si ferme ad eccezione della mutazione occasionale ciecamente fortunata, e poiché le tue mutazioni sono così grandi, è molto improbabile che troverai una mossa in miglioramento senza distruggere il resto del cromosoma.

Proverei la selezione dei tornei binari e un operatore di mutazione più sensato. Le solite persone euristiche usano per la mutazione è (in media) capovolgere un "bit" di ogni cromosoma. Tuttavia, non vuoi una modifica deterministica di una lettera ogni volta. Qualcosa come questo:

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();
    }
}