LMD Licence 3 – SCI Université Abdelhamid Mehri-Constantine 2
Module Systèmes Intelligents SI Faculté NTIC, Département IFA
Dr. NECIBI Khaled Session 2018-2019
Application des Algorithmes Génétiques
TP N=° 01
« Résolution du problème de voyageur de commerce –salesman- »
Dans ce TP, il est demandé aux étudiants de suivre ce tutoriel afin de pouvoir réaliser un
petit programme de résolution d’un problème donné en utilisant une parmi les techniques de
recherche informées vu en cours qui est « les algorithmes génétiques »
Le tutoriel suivant sera principalement en Python, mais comme déjà mentionné, libre aux
étudiants de choisir le langage de programmation qui leur convient. Il est aussi possible de récupérer
des codes sur le net y on a beaucoup, mais l’important c’est de les comprendre et réussir à les
compiler tout en rependant aux questions soulevés dans l’énoncé.
Les étudiants peuvent trouvés le travail qui leur ait demandé dans la section « Travail
demandé ».
Le problème à résoudre dans ce tutoriel est le voyageur de commerce ou Traveling salesman
partiellement vu pendant le cours (carte de Romanie et le traversé de Arad vers Bucharest).
Rappelant nous que ce problème est décrit comme suit : « étant donné une liste de cités est des
distances entre chaque paire de cité, quel est le chemin le plus court à prendre pour visité chaque
cité (chaque cité doit être visitée une seul fois) et se rendre par la suite à la cité de départ ? »
Rappel et complément (Voir Cours Recherche informé stochastique) :
Pour concevoir un algorithme génétique, il faut suivre les étapes suivantes :
1- Création de la population
2- Déterminer la fonction objective ou la fonction fitness
3- La sélection des individus ou mating pool
4- Croisement ou breed
5- Mutation
6- Répéter le processus jusqu’à ce qu’un individu ait la valeur de fitness la plus optimal, ou
assez de temps a été écoulé
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Environnement de Développement Intégré
Il est fortement conseiller d’utiliser Python avec un IDE pour éviter les complications de la console
pour les gens qui n’ont pas assez d’expérience avec Python. Quand à Python, il s’agit d’un langage
de programmation très simple et très facile à apprendre.
Parmi les IDE pour Python on en trouve :
- Eclipse + PyDev (lien : [Link], [Link])
- Gnu Emacs (lien : [Link]
- Visual Studio (lien : [Link] [Link] les tools
Visual Studio pour Python ou PTVS)
- PyCharm (lien : [Link]
- Spyder (lien : [Link]
- Thonny (lien : [Link]
Dans ce tutoriel, nous allons expliquer en détails comment il est possible de concevoir un algorithme
génétique pour résoudre le problème du voyageur de commerce en utilisant Python et l’IDE
PyCharm.
Après avoir installé PyCharm (ou un autre autre IDE), quelques packages sont au départ nécessaires
afin de rendre les choses beaucoup plus facile à manipuler : « numpy », « random », « operator »,
« pandas » et « [Link] ». Pour installer ces derniers il faut les rajouter lors de la
paramétrisation du projet (pour une première installation ; accès à internet est nécessaire ; voir figure
suivante)
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Une fois installés, les packages doivent être importés en utilisant les lignes de 1 – 5 Python suivantes :
Avant de passer aux étapes de création d’un algorithme génétique, il faut créer deux classes City et
Fitness qui représentent respectivement les cités qui doivent être traversées par le voyageur de
commerce et la fonction Fitness.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
La classe « City »
Les cités sont représentées par des coordonnées (x, y). Dans la classe City on rajoute une fonction
distance pour déterminer la distance entre une paire de cité (lignes 14 - 18)
La classe « Fitness »
Le but ici est de minimiser la distance traversée, la valeur (ou score) de Fitness la plus grande est la
mieux placée pour la résolution du problème de voyageur de commerce. Vu que le principe et de
démarrer et de finir dans la même cité, ceci peut être assuré dans la ligne 38 du code de définition
de la classe Fitness.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Après avoir définir les deux classe City et Fitness, passant maintenant aux 05 étapes pour créer notre
algorithme génétique.
1- Création de la population (première génération d’individus)
Dans cette étape, il nous faut un moyen pour créer une fonction qui produit les routes liant les cités.
Pour créer un individu, on va aléatoirement sélectionner l’ordre dans lequel chaque cité est visitée.
Selon le code suivant, un seul individu sera créé.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Vu que nous avons besoin de représenter une population entière, une simple boucle à travers la
fonction createRoute nous donnera plusieurs routes pour créer la population, comme montré dans
Le code suivant.
Maintenant, il ne reste qu’à utiliser ces fonctions pour créer la population initiale.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
2- Déterminer la valeur de Fitness
Pour le choix des individus dans notre population (les cités et les routes) il faut utiliser la classe Fitness
pour classer via la méthode rankRoute, par valeur, chaque individu dans la population, et ce avant
de passer à l’étape suivante de notre algorithme génétique (croisement et mutation).
Cela va afficher une liste ordonnée de routes avec leur IDs et chaque valeur de Fitness attribuée.
3- La sélection des individus (ou mating pool) pour l’étape du croisement et de mutation
Afin de permettre la création d’une nouvelle génération après l’étape du croisement, les individus
doivent être dans un premier lieu « sélectionnés ». Le but ici est de sélectionner les meilleurs
individus (avec des meilleures caractéristiques) pour la reproduction. Pour cela une technique
d’élitisme est utilisée (ou elitism).
Premièrement, on va utiliser le retour de la fonction rankRoute pour déterminer quelles sont les
routes à sélectionnées dans la fonction selection.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Les lignes 80 – 82 un poids relatif est calculé pour chaque individu. La ligne 86, une comparaison
d’un nombre tiré au hasard aux poids déterminés pour chaque individu est effectuée afin de
sélectionner les individus pour la reproduction (ou mating pool).
Il est aussi nécessaire de ne garder que les meilleurs chemins, la ligne 84 introduit la notion d’élitisme
(elitism).
Finalement, la fonction selection va retourner une liste des identificateurs de routes IDs qui sont
utilisés par la suite pour créer l’ensemble de la reproduction des individus ou le mating pool. Le
code suivant montre comment créer la fonction mating pool. Il s’agit simplement d’extraire les
individus sectionnés.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
4- Croisement (ou breed)
Avec le mating pool créé, il est désormais possible de produire la prochaine génération dans un
processus appelé croisement. Dans le problème de voyageur de commerce, il est possible d’utiliser
une fonction de croisement ordonnée.
Il s’agit de sélectionner au hasard un sous ensemble de la première chaine de caractère du parent
(String représentant le parent, voir la figure suivante ; ligne 116 du code de la fonction breed), ensuite
(ligne 119 du code de la fonction breed) il faut remplir le reste de la route avec les gènes du deuxième
parent selon leur ordre d’apparition (sans duplication des gènes dans le sous-ensemble sélectionné
du premier parent). La figure suivante montre l’étape offspring = fils produit après le croisement.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Maintenant, il faut généraliser ce processus pour créer la population offspring (fonction
breedPopulation ; voir le code suivant). Donc il faut utiliser elitism (ligne 130) afin de ne garder que
les meilleures routes à partir de la population courante. Ensuite, on utilisera la fonction breed afin
de remplir le reste de la prochaine génération (ligne 134).
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
5- Mutation
Maintenant on passe à l’étape de mutation afin de pouvoir introduire de nouvelles routes qui
permettent d’explorer d’autres états de l’espace de recherche. Dans le problème de voyageur de
commerce, et lors de la mutation, deux cités vont échangées leur places sur l’itinéraire (swap) lorsque
la probabilité obtenue est faible. La fonction mutate suivante montre la faisabilité de ceci.
Ensuite, il faut appliquer la fonction mutate sur la nouvelle population en utilisant la fonction
mutatePopulation suivante (ligne 157) :
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
6- Répéter le processus
Maintenant il nous reste qu’à recoller les morceaux en créant une fonction qui va produire une
nouvelle génération et qui doit effectuer les actions suivantes :
- Classement des routes de la génération courante en utilisant la fonction rankRoutes
- Déterminer les meilleurs parents en faisant appel à la fonction selection
- La fonction selection permet de créer le matingPool pour la production de la prochaine
génération
- Créer ensuite une nouvelle génération en faisant appel à la fonction breedPopulation
- Finalement, effectuer la mutation en faisant appel à la fonction mutatePopulation
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Créer l’algorithme génétique
La dernière étape est de créer l’algorithme génétique général (voir le code illustré dans la figure
suivante), regroupant toutes les étapes expliquées précédemment. On peut créer une population
initiale et parcourir autant de générations que nous souhaitons.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Vu que le but est d’avoir le meilleur chemin, la distance initiale est déterminée dans la ligne 173, la
distance finale est déterminée dans la ligne 178 et le meilleur chemin ou route dans la ligne 180.
Exécuter l’algorithme génétique
En deux étape, on a besoin premièrement d’une liste de cités ; à titre d’exemple nous allons créer
une liste aléatoire de 25 cités comme illustré dans les lignes de code suivantes :
Ensuite et en deuxième partie, on exécute notre algorithme génétique sur 100 individus dans chaque
génération, garder 20 individus d’élite, utiliser un ratio de mutation de 1% et finalement compiler le
code à travers 500 générations (voir le code illustré dans la figure suivante).
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
Etudier l’évolution de l’algorithme génétique créé
Le but ici est de suivre l’évolution des distances parcourues à travers chaque génération dans une
liste progress, ensuite tracer les résultats obtenus dans une courbe via la fonction
geneticAlgorithmPlot suivante :
Travail Demandé
- Il est demandé aux étudiants de faire cette démonstration sur leur machines pour résoudre
le problème de voyageur de commerce en utilisant les algorithmes génétiques
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
- Il est demandé ensuite de faire varier les paramètres de l’algorithme génétique (nombre
initial de cités, taille de population, nombre d’individus sélectionnés, ratio de mutation et le
nombre des prochaines générations)
- Tracer à chaque fois la courbe d’évolution de distance par rapport à chaque génération
- Discuter les résultats trouvés (les étudiants doivent mentionner les résultats de la variation
des paramètres de l’algorithme génétique dans la deuxième partie de l’exposé : voir la fiche
descriptive du TP_02)
Quelques Remarques
- Les étudiants peuvent utiliser un autre langage de programmation
- Les étudiants peuvent utiliser un autre environnement de développement intégré IDE
- Les étudiants peuvent récupérer d’autres codes sur le net, à condition qu’ils répondent aux
questions soulevées précédemment
- Le présent TP est disponible sur la plateforme e-learning de l’université
N.B. Ce travail sera évalué juste après le passage des examens. Une date vous serait communiquée.
Tout travail supplémentaire (référence 4 de la section « Quelques liens utiles »), amélioration ou
effort fourni par l’étudiant est pris en considération lors de l’évaluation.
Quelques liens utiles
1- Tutoriel en Anglais : [Link]
genetic-algorithm-tutorial-for-python-6fe5d2b3ca35
2- Liste des IDEs et Editeurs pour Python : [Link]
guide/
3- Code source du tutoriel sur GitHub : [Link]
algorithm/blob/master/genetic_algorithm_TSP.ipynb
4- Source code from the book Genetic Algorithms with Python by Clinton Sheppard :
[Link]
Bon Courage.
Résolution de problème – Algorithme. G 2019 Dr. NECIBI Khaled
