Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MASTER I INFORMATIQUE 2005/2006 LIU YINAN Rapport de Mémoire Application des Al

MASTER I INFORMATIQUE 2005/2006 LIU YINAN Rapport de Mémoire Application des Algorithmes Génétiques au Problème du Voyageur de Commerce Encadrants : M. Nakechbandi J. Boukachour UNIVERSITÉ DU HAVRE Table des matières 1 Introduction 5 2 Problème de Voyageur de Commerce 6 2.1 Théoriquement . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Pratiquement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Complexité du Problème . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Intérêt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Algorithme Génétique 8 3.1 La Création de la Population Initiale . . . . . . . . . . . . . . . . 9 3.2 L’Évaluation des Individus . . . . . . . . . . . . . . . . . . . . . 9 3.3 La Création de Nouveaux Individus . . . . . . . . . . . . . . . . 9 3.3.1 Les Selections . . . . . . . . . . . . . . . . . . . . . . . 9 3.3.1.1 La Selection par Roulette . . . . . . . . . . . . 9 3.3.1.2 La Selection par Rang . . . . . . . . . . . . . . 10 3.3.1.3 La Selection par Tournoi . . . . . . . . . . . . 11 3.3.1.4 L’Élitisme . . . . . . . . . . . . . . . . . . . . 11 3.3.2 Les Croisements . . . . . . . . . . . . . . . . . . . . . . 11 3.3.2.1 Le Croisement CPA . . . . . . . . . . . . . . . 11 3.3.2.2 Le Croisement 1X . . . . . . . . . . . . . . . . 12 3.3.2.3 Le Croisement MPX . . . . . . . . . . . . . . . 13 Master I 2005/2006 1 TABLE DES MATIÈRES 3.3.2.4 Le Croisement OX . . . . . . . . . . . . . . . . 14 3.3.2.5 Le Croisement CX . . . . . . . . . . . . . . . . 15 3.3.3 La Mutation . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.4 L’Insertion des Nouveaux Individus dans la Population . . 16 3.3.5 Réitération du processus . . . . . . . . . . . . . . . . . . 16 4 Application de l’AG au PVC 18 4.1 L’Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Les Statistics sur les Paramètres de L’AG . . . . . . . . . . . . . 18 5 Conclusion 20 6 Références 21 6.1 Site Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 A L’Interface Graphiique 22 B Codage des Opérateurs 25 B.1 Codage de Selection Par Roulette . . . . . . . . . . . . . . . . . . 25 B.2 Codage de Selection Par Rang . . . . . . . . . . . . . . . . . . . 26 B.3 Codage de Selection Par Tournoi . . . . . . . . . . . . . . . . . . 26 B.4 Codage de Croisement CPA . . . . . . . . . . . . . . . . . . . . 27 B.5 Codage de Croisement 1X . . . . . . . . . . . . . . . . . . . . . 29 B.6 Codage de Croisement MPX . . . . . . . . . . . . . . . . . . . . 30 B.7 Codage de Croisement OX . . . . . . . . . . . . . . . . . . . . . 32 Master I 2005/2006 2 TABLE DES MATIÈRES Résumé Le problème du voyageur de commerce étant combinatoire (le nombre de so- lutions est de l’ordre n !, n nombre de villes), le but du projet est d’appliquer des algorithmes génétiques pour trouver le meilleur circuit de coût minimal. La mise en oeuvre de cet algorithme consiste particulièrement à intégrer des nouveaux opérateurs de sélection et de croisement génétique. Master I 2005/2006 3 Remerciements Je tiens à remercier : M. Nakechbandi et M. Boukachour pour leur encadrement et leur nom- breuses explications du sujet. Master I 2005/2006 4 Chapitre 1 Introduction Les algorithmes génétiques ont été inventés par Jonh Holland dans les années 60. Repris notamment par Golberg dans les années 70,Le principe des algorithmes génétiques s’inspire directement des lois de la sélection naturelle, décrites par Darwin. cette technique connait aujourd’hui un franc succès. On l’utilise dans la résolution de problèmes complexes, nécessitant des temps de calcul élevés. 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. Les applications des AG sont multiples : traitement d’image (alignement de photos satellites, reconnaissance de suspects...), optimisation d’emplois du temps, optimisation de design, apprentissage des réseaux de neurones [Renders, 1995], etc. Le but de ce projet est d’appliquer l’algorithme génétique au problème de voyageur de commerce, la mise en œuvre de cet algorithme consiste particulière- ment à intégrer des nouveaux opérateurs de sélection et de croisement génétique. Master I 2005/2006 5 Chapitre 2 Problème de Voyageur de Commerce 2.1 Théoriquement soit un graphe G = (S, A) , problème est de trouver une parcours qui passe par tous les sommets une et une seule fois et qui soit de poids minimal. En general, on travaille sur un graphe complet. 2.2 Pratiquement Un voyageur de commerce doit visiter N villes données en passant par chaque ville exactement une fois. Il commence par une ville quelconque et termine en re- tournant à la ville de départ. Les distances entre les villes sont connues. Quel che- min faut-il choisir aﬁn de minimiser la distance parcourue ? La notion de distance Master I 2005/2006 6 CHAPITRE 2. PROBLÈME DE VOYAGEUR DE COMMERCE peut-être remplacée par d’autres notions comme le temps qu’il met ou l’argent qu’il dépense : dans tous les cas, on parle de coût. 2.3 Complexité du Problème La complexité du problème croît comme la factorielle du nombre de villes. Si l’on considère des permutations simples, il existe 3 628 000 permutations de 10 villes. Pour 100 villes, on passe à 10 puissance 158. La complexité du problème croît de manière plus que polynomiale (problème dit NP). n Nombre de possibilités Temps de calcul 5 12 micro-seconde 10 181440 deuxième de seconde 15 43 milliards dizaine d’heures 20 60.1015 milliers d’années 25 310.1021 milliards d’années 2.4 Intérêt Le PVC fournit un exemple d’étude d’un problème NP-complets dont les méthodes de résolution peuvent s’appliquer à d’autres problèmes de mathéma- tiques discrète. Néanmoins, il a aussi des applications directes, notamment dans les transports et la logistique. Par exemple, trouver le chemin le plus court pour les bus de ramassage scolaire ou, dans l’industrie, pour trouver la plus courte distance que devra parcourir le bras mécanique d’une machine pour percer les trous d’un circuit imprimé (les trous représentent les villes). Master I 2005/2006 7 Chapitre 3 Algorithme Génétique Les algorithmes génétiques s’inspirent de l’évolution des espèces dans leur cadre naturel. Les espèces s’adaptent à leur cadre de vie qui peut évoluer, les individus de chaque espèce se reproduisent, créant ainsi de nouveaux individus, certains subissent des modiﬁcations de leur ADN, certains disparaissent .... Un algorithme génétique va reproduire ce modèle d’évolution dans le uploads/Geographie/ algorithme-genetique-au-probleme-du-voyageur-de-commerce.pdf