Algorithmes génétiques
Le Mastermind
Le jeu
Le Mastermind est un jeu de société pour deux joueurs dont le but est de trouver une combinaison de pions avec pour chaque pion associe une couleur parmis une liste de 8 couleurs.
La combinaison de pion peut avoir plusieurs fois une même couleur en son sein.
source : wikipédia
Pour ce TP, la combinaison caché sera définit par 4 pions et la liste des couleurs sera définit par une liste :
Les individus
Création
Un individu pour ce problème aura comme valeur une liste de couleur. Le nombre de couleur / la taille de la liste dépendra donc de la taille donnée ors de sa création. De plus lors de la création, de l'individu, les couleurs seront choisis de façon aléatoire.
Consigne - Implémenter la méthode init_value(self) de la classe Combinaison.
Croisement
Afin de simplifier, nous utiliserons uniquement des croisements en 1 Points.
Lorsque l'on voudra croiser 2 individus
- on prendra aléatoirement un indice compris entre 0 et la taille max de la liste de couleur
- on cré 2 nouveaux individus :
- new_ind_1 <- individu_1[:indice] + individu_2[indice:]
- new_ind_2 <- individu_2[:indice] + individu_1[indice:]
- renvoi new_ind_1 et new_ind_2
Consigne - Implémenter la méthode cross_with(self, other) de la classe Combinaison.
Mutation
Pour un individu, un gêne est représenté par une couleur (qui appartient à la variable COLOR). Muter un gêne revient alors à remplacer ce gêne par un autre, c'est à dire par une autre couleur.
La fonction mutate(self, probability) de la classe Combinaison, va parcourir tous les gênes de l'individu et va aléatoirement lancer une mutation en fonction de la probabilité qui lui est donné en paramètre.
Consigne - Implémenter la méthode mutate_gene(self, gene) de la classe Combinaison.
Le problème
Création
Lorsque l'on va instancier le problème, on lui donnera une combinaison de couleur, cette combinaison est ce que l'algorithme doit trouver.
Pour la résolution du problème, nous avons besoin de définir une méthode qui va générer des individus de façon aléatoire en fonction de la taille de la combinaison solution.
Consigne - Implémenter la méthode create_individual(self) de la classe Mastermind.
Evaluation
Pour évaluer un individu, on va comparé gêne par gêne sa combinaison avec la combinaison solution. Le résultat de l'évaluation sera alors le nombre de gêne valide et correctement bien placé.
Consigne - Implémenter la méthode evaluate_fitness(self, individual) de la classe Mastermind.
Tournoi
L'algorithme va progressivement faire des tournois entre les individus afin de garder les meilleurs.
La méthode sort_population(self, population) prend en paramètre une population de combinaison et va la triée dans l'ordre décroissant de score.
Consigne - Implémenter la méthode best_individual(self, population) de la classe Mastermind.
Consigne - Implémenter la méthode tournament(self, first, second) de la classe Mastermind qui compare 2 individus et renvoie le meilleur des 2.
Algo_gen
Population
Parmi les attributs de la classe AlgoGen, se trouve un attribut pour la population qui est vide au départ ainsi qu'un attribut pour la taille de la population.
Consigne - Implémenter la méthode genesis(self) de la classe AlgoGen qui aura comme effet de bord la création de la population.
Evaluation
Un individu à sa création voit son score à None. Il va donc falloir, après avoir générer la population, évaluer chaque individu afin que tous ai un score mis à jour.
Consigne - Implémenter la méthode evaluate_population(self, population) de la classe AlgoGen qui prend une population et évalue chaque individu de cette dernière.
Tournoi
Afin d'améliorer la population, nous allons effectué une multitude de tournoi entre la première moitié de la population avec l'autre moitié. Ainsi on obtiendra une population avec les n//2 meilleur individu de la population avec n étant la taille de la population.
Consigne - Implémenter la méthode next_generation_tournament(self, population) de la classe AlgoGen.
Croisement
La population d'une étape i (avec i non nulle), est la concaténation entre le résultat de la méthode des tournois et de la méthode des croisements.
La méthode de croisement prendra les n//2 (avec n la taille de la population) premiers individus de la populations et va les croiser avec les n//2 derniers individus de la population. Ainsi nous aurons une liste d'individus de taille n//2.
Consigne - Implémenter la méthode crossover(self, population) de la classe AlgoGen.
Mutation
Après avoir créé la population, la dernière étape consiste à faire les mutations de chaque individu selon la probabilité se trouvant dans les attributs de la classe.
Consigne - Implémenter la méthode mutate(self, individuals) de la classe AlgoGen.
Test
Maintenant que les classes sont implémentées, il nous reste plus qu'à tester notre algorithme génétique :
# on importe le module de l'algorithme génétique ainsi que la classe pour définir un problème
from algo_gen import *
from mastermind import *
if __name__=="__main__":
# création du problème
p = Mastermind(["bleu", "blanc", "blanc", "rouge"])
# création d'algogen
a = AlgoGen(p, 12, 0.1)
# on lance la résolution au problème
a.solve(15)
Consigne - Tester le programme.
Dernière mise à jour : 15/06/2026