Les soutenances et rendus du projet auront lieu le 7 avril
Rendus du projet :
Un rapport de 5 - 6 pages décrivant comment vous avez utliser les algorithmes génétiques pour reoudre le probleme. Quels choix avez vous fait ? Vous montrez aussi les résultats obtenues. Ajouter le code du programme en anexe. Rapport a rendre le jour de la soutenance en version papier.
Un programme avec une interface graphique simple permettant de générer aléatoirement N villes et de voir l'algorithme génétique resoudre le probleme.
Soutenance. Il s agit d'un simple démonstration de votre programme pendant une dizaine de minutes. Pas de slides a faire. Apportez votre PC pour montrer votre programme tourner. Je poserai des questions durant la présentation.
Sujet : Voyageur de commerce avec les algorithmes génétiques
Le problème du voyageur de commerce consiste à passer par un ensemble de villes en minimisant la distance totale du trajet. C’est un problème dit NP-complet, ce qui signifie qu’il n’existe pas d’algorithme en temps polynomial permettant de trouver une solution exacte à ce problème. Dans ce projet nous tacherons de résoudre ce problème à l’aide des algorithmes génétiques.
Les algorithmes génétiques s’inspirent de la théorie de l’évolution des espèces. Comme dans la vie, les espèces peuvent se reproduire pour créer de nouveaux individus, et leur ADN peut subir des mutations au cours de leur vie. De plus, à l’instar de ce qu’on observe dans la nature, plus un individu est “fort”, plus il a de chance de se reproduire.
Un algorithme génétique est constitué de 5 grandes étapes :
Création d'une population initiale de solutions
Evaluation de la "fitness" (qualité) des individus
Création de nouveaux individus
Ajout des nouveaux individus dans la population
Retour à la seconde étape
Le but de l’algorithme génétique est de faire évoluer notre population initiale contenant des solutions aléatoires vers une population contenant de meilleures solutions.