Résolution d’un taquin a l’aide des algorithmes génétiques

Publié le par k'

Les algorithmes génétiques sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de la génétique et des mécanismes d'évolution de la nature : croisements, mutations, sélections, etc. Ils appartiennent á la classe des algorithmes évolutionnaires.  

Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode exacte (ou que la solution est inconnue) pour le résoudre en un temps raisonnable.

 

Historique du jeu de taquin :


En 1878, Sam Loyd, grand amateur et créateur d'énigmes mathématiques, proposa une récompense de mille dollars à la première personne qui réussirait à remettre en ordre une série de 15 pièces coulissantes de forme carrée disposées dans un cadre carré de 16 places. L'espace vide permet de faire coulisser les pièces, et la solution semblait assurée. Le casse-tête, qui connut un succès phénoménal dans le monde entier, porte aujourd'hui le nom de Taquin dans les pays francophones.[1]

 

Le taquin est connu sous différente version 4x4 ,5x5 et celui est utiliser pour cet article est le Taquin 3x3 C’est-à-dire 8 case et une vide.

 

Problématique:

 

Résoudre un taquin à l'aide des algorithmes génétiques :


Bien que les algorithmes génétiques sont adaptés a des problèmes ou il n'existe pas de méthode exacte pour le résoudre en un temps raisonnable l’appliquer au taquin peut être très enrichissant pédagogiquement parlant surtout après avoir résolu ce problème avec  divers méthodes qu’elles soient tiré de l’IA ou pas (Algorithme A*, parcours d’arbre largeur et hauteur, système expert). Résoudre un problème avec l’algorithme  génétique revient à générer une population d’individu qui représente des solutions admissibles du problème et ça de façon aléatoire, Pour passer d’une population k à une population k+1 trois opérations sont répétés pour tous les individus de la population k. On sélectionne des couples de parant s on leurs applique l’operateur de croisement,  on mute des individus  ensuite on élimine un nombre d’individus qui sont moins adapté   (sur le critère d’une fonction qui est dans notre cas le nombre de case mal placer par rapport au but rechercher).

Différents critères d'arrêt de l'algorithme peuvent être choisis :

  • Le nombre de générations que l'on souhaite exécuter peut être fixé à priori. C'est ce que l'on est tenté de faire lorsque l'on doit trouver une solution dans un temps limité.
  • L'algorithme peut être arrêté lorsque la population n'évolue plus ou plus suffisamment rapidement.

Nous allons maintenant détailler chacun de ces points:

 

Codage d'une population:

croisement-copie-1

 

1. Figure qui représente le croisement.

 private Chromosome hybridation() { Chromosome temp = new Chromosome(); int higherDivision = profondeur - 1; int division = (int) (Math.random() * higherDivision) + 1; temp.addAll(population.getChromosomeHazard().subList(0, division)); temp.addAll(population.getChromosomeHazard().subList(division, profondeur)); return temp; } 
Fonction d'évaluation et fonction fitness :

Pour calculer le coût d'un point de l'espace de recherche, on utilise une
fonction d'évaluation. L'évaluation d'un individu ne dépendant pas de celle des autres individus, le résultat fournit par la fonction d'évaluation va permettre de sélectionner ou de refuser un individu pour ne garder que les individus ayant le meilleur coût en fonction de la population courante : c'est le rôle de la fonction fitness.

La fonction fitness utilisé dans ce tp choisie les chromosomes par rapport au nombre de case mal placer à la fin de l’exécution des mouvements dicté par le chromosome, ainsi plus ce nombre est petite plus cet individu est considéré comme plus adapter à « rester ».

 

 private Population fitness(Population population) { Population populationTemp = population; int[] distanceErreur = new int[population.size()]; for (int i = 0; i < population.size(); i++) { Config config = this.configdefaut.clone(); for (int j = 0; j < this.profondeur; j++) { config = config.move(population.get(i).get(j)); } distanceErreur[i] = config.getPieceJuste(); if(distanceErreur[i] == 8){ solution = true; } } //tri de la selection par rapport a la distance de l'erreur int bool = 1; for (int i = 0; bool == 1 && i < populationTemp.size(); i++) { bool = 0; for (int j = 0; j < populationTemp.size() - i - 1; j++) { if (distanceErreur[j] < distanceErreur[j + 1]) { bool = 1; int temp = distanceErreur[j]; distanceErreur[j] = distanceErreur[j + 1]; distanceErreur[j + 1] = temp; Chromosome formTemp = populationTemp.get(j); populationTemp.set(j, populationTemp.get(j + 1)); populationTemp.set(j + 1, formTemp); } } } Population sublist = new Population(); for (int i = 0; i < this.taillePopulation; i++) { sublist.add(populationTemp.get(i)); } return sublist; }  

Je prfére nous arêter ici, et diviser l'article en deux partie

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article

alain 01/02/2016 17:09

Bonjour,
Je m'intéresse aux algo génétiques et sur ce type d'application j'ai du mal à voir comment représenter les solutions sous forme de chromosome (une suite de 2 bits indiquant chaque déplacement car 4 directions possibles ?) et surtout comment procéder à l'hybridation (question identique déjà posée) : car l'hybridation de 2 cheminements ne forme peut-être pas un cheminement possible.
Avez-vous publier un article sur cette partie ?
D'avance merci,

imen 20/05/2012 09:56

salut, Je viens de lire votre article et je l’ai trouvé très intéressant .et je voudrais savoir si je pourrais lire la deuxième partie de votre article le plus tôt possible. Merci

etudiante 29/04/2011 18:15


Salut
Je tu remercies pour le tutoriel malgré qu’il y a des trucs non clair je veux-tu pose la question suivante dans l’étape de mutation tu fais la division de deux chromosomes en suite tu colles les
deux partie divers, asque ca est correcte si les deux portion ne produisant pas une chaine(le dernier élément de chromosome1 n’est pas un voisinage de premier élément de chromosome2 ?
merci


etudiant 29/04/2011 18:13


Salut
Je tu remercies pour le tutoriel malgré qu’il y a des trucs non clair je veux-tu pose la question suivante dans l’étape de mutation tu fais la division de deux chromosomes en suite tu colles les
deux partie divers, asque ca est correcte si les deux portion ne produisant pas une chaine(le dernier élément de chromosome1 n’est pas un voisinage de premier élément de chromosome2 ?
merci


drSd12 31/03/2011 01:59


Salut,
Article très intéressant juste deux point :
1- Pouvez vous écrire le code avec une autre couleur(pas très visible pour ma part)
2- Je ne suis pas un expert mais c'est du code java ? certaine class ne sont pas défini (une publication de tout le code sera plus utile a mon avis)
Merci encore.