Résoudre mots croisés avec algorithme génétique, la forme physique, mutation

Question

Je suis en train difficile de faire un laboratoire pour l'école. Je suis en train de résoudre un puzzle de mots croisés en utilisant des algorithmes génétiques. Le problème est que ce n'est pas très bon (il est encore trop aléatoire) Je vais essayer de donner une brève explication de la façon dont mon programme est mis en œuvre maintenant:

Si j'ai le casse-tête (# est bloc, 0 est l'espace vide)

#000
00#0
#000

et une collection de mots qui sont candidats à la solution de ce casse-tête. Mon ADN est simplement la matrice comme un tableau 1D.

Mon premier ensemble d'individus ont générés au hasard de ADNs la piscine de lettres que mes mots contient.

Je fais sélection à l'aide de la roulette de sélection. Il y a quelques paramètres sur la possibilité de combinaison et des mutations, mais si la mutation se produira alors je toujours changer 25% de l'ADN. Je changer avec des lettres au hasard de ma piscine de lettres. (Cela peut avoir des effets négatifs, comme les mutations peuvent destroy déjà formé des mots)

Maintenant, la fonction de remise en forme: Je traverse la matrice à la fois horizontalement et verticalement: Si je trouve un mot puis FITNESS + = word.lengh +1

Si je trouve une chaîne qui est une partie d'un mot puis FITNESS + = word.length / (puzzle_size * 4). Quoi qu'il en soit, il devrait donner une valeur comprise entre 0 et 1. Il peut donc trouver « à » de « outil » et annonces X FITNESS, puis à droite après qu'il trouve « trop » de « outil » et ajoute une autre Y FITNESS.

Mes générations ne sont pas réellement améliorées au fil du temps. Ils apparaissent au hasard. Ainsi, même après 400 générations avec une piscine de 1000-2000 (ces chiffres vraiment ne importe) je reçois une solution avec 1-2 mots (de 2 ou 3 lettres) lorsque la solution doit avoir 6 mots.

Answer 1

Je pense que votre fonction de remise en forme peut être mal définie. Je le mettre en place pour que chaque ligne a un niveau de forme binaire. Soit une rangée est apte ou non. (Par exemple une ligne est un mot ou il est pas un mot), la condition physique générale de la solution serait de lignes #fit / nombre total de lignes (horizontalement et verticalement). En outre, vous pourriez être en train de changer trop de dna, je ferais cette variable et d'expérimenter avec cela.

Answer 2

Votre fonction de remise en forme semble OK pour moi, mais sans plus de détails, il est difficile d'obtenir une très bonne image de ce que vous faites.

Vous ne spécifiez pas la probabilité de mutation, mais quand vous faites muter, 25% est une mutation très élevée. En outre, la sélection de roulette applique une beaucoup de la pression de sélection. Ce que vous voyez souvent est que l'algorithme assez tôt trouve une solution qui est tout à fait un peu mieux que tous les autres, et la sélection de roulette provoque l'algorithme pour le sélectionner avec une telle probabilité élevée que vous vous rapidement avec une population pleine de copies de ça. À ce moment, la recherche arrête l'exception de la mutation ponctuelle aveuglément la chance, et que vos mutations sont si grandes, il est très peu probable que vous trouverez un mouvement d'améliorer sans détruire le reste du chromosome.

Je vais essayer la sélection du tournoi binaire, et un opérateur de mutation plus sensible. Les personnes heuristiques habituelles utilisent pour la mutation est (en moyenne) un flip « bit » de chaque chromosome. Vous ne voulez pas un changement déterministe d'une lettre à chaque fois que. Quelque chose comme ceci:

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