Resolver el crucigrama con algoritmo genético, aptitud, mutación

Question

Estoy tratando de hacer un laboratorio para la escuela. Estoy tratando de resolver un crucigrama usando algoritmos genéticos. El problema es que no es muy bueno (todavía es demasiado aleatorio) intentaré dar una breve explicación de cómo se implementa mi programa ahora:

Si tengo el rompecabezas (# es bloque, 0 es espacio vacío)

#000
00#0
#000

y una colección de palabras que son candidatos a la solución de este rompecabezas. Mi ADN es simplemente la matriz como una matriz 1D.

Mi primer conjunto de individuos tiene ADN generados aleatorios del grupo de letras que contienen mis palabras.

Selección usando la selección de ruleta. Hay algunos parámetros sobre la posibilidad de combinación y mutaciones, pero si la mutación ocurre, siempre cambiaré el 25% del ADN. Lo cambio con letras aleatorias de mi grupo de letras (esto puede tener efectos negativos, ya que las mutaciones pueden destruir palabras ya formadas)

Ahora la función de aptitud física: atravieso la matriz tanto horizontal como vertical: si encuentro una palabra, entonces aptitud += word.lengh +1

Si encuentro una cadena que es parte de alguna palabra, entonces Fitness += Word.length / (Puzzle_Size*4). De todos modos, debería dar un valor entre 0 y 1. para que pueda encontrar "a" de "herramienta" y anuncios x a la forma física, luego justo después de que encuentre "también" de "herramienta" y agrega otra y a la condición física.

Mis generaciones en realidad no están mejorando con el tiempo. Aparecen aleatorios. Entonces, incluso después de 400 generaciones con un grupo de 1000-2000 (estos números realmente no importan) obtengo una solución con 1-2 palabras (de 2 o 3 letras) cuando la solución debe tener 6 palabras.

Answer 1

Creo que su función de aptitud física podría estar mal definida. Establecería esto para que cada fila tenga un nivel de aptitud binaria. O una fila está en forma o no lo es. (por ejemplo, una fila es una palabra o no es una palabra), entonces la aptitud general de la solución sería #Fit filas / filas totales (tanto horizontal como verticalmente). Además, podría estar cambiando demasiado del ADN, haría esa variable y experimentaría con eso.

Answer 2

Tu función de acondicionamiento físico me parece bien, aunque sin más detalles es difícil obtener una muy buena imagen de lo que estás haciendo.

No especifica la probabilidad de mutación, pero cuando se muta, el 25% es una mutación muy alta. Además, la selección de la rueda de la ruleta aplica un lote de presión de selección. Lo que a menudo ve es que el algoritmo bastante temprano encuentra una solución que es bastante mejor que todas las demás, y la selección de la rueda de la ruleta hace que el algoritmo lo seleccione con una probabilidad tan alta que termine rápidamente con una población llena de copias. de eso. En ese momento, la búsqueda se detiene, excepto por la mutación ocasional ciegamente afortunada, y dado que sus mutaciones son tan grandes, es muy poco probable que encuentre un movimiento mejorado sin restringir el resto del cromosoma.

Probaría la selección del torneo binario y un operador de mutación más sensible. La gente heurística habitual que usa para la mutación es (en promedio) voltear un "bit" de cada cromosoma. Sin embargo, no desea un cambio determinista de una letra cada vez. Algo como esto:

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