Remerciez-le!

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

Algorithme genetique au probleme du voyageur de commerce

MASTER I INFORMATIQUE 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 CTable des matières Introduction Problème de Voyageur de Commerce Théoriquement Pratiquement Complexité du Problème Intérêt Algorithme Génétique La Création de la Population Initiale L ? Évaluation des Individus La Création de Nouveaux Individus Les Selections La Selection par Roulette La Selection par Rang La Selection par Tournoi L ? Élitisme Les Croisements Le Croisement CPA Le Croisement X Le Croisement MPX Master I CTABLE DES MATIÈRES Le Croisement OX Le Croisement CX La Mutation L ? Insertion des Nouveaux Individus dans la Population Réitération du processus Application de l ? AG au PVC L ? Objectif Les Statistics sur les Paramètres de L ? AG Conclusion Références Site Web Documents A L ? Interface Graphiique B Codage des Opérateurs B Codage de Selection Par Roulette B Codage de Selection Par Rang B Codage de Selection Par Tournoi B Codage de Croisement CPA B Codage de Croisement X B Codage de Croisement MPX B Codage de Croisement OX Master I CTABLE DES MATIÈRES Résumé Le problème du voyageur de commerce étant combinatoire le nombre de solutions 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 CRemerciements Je tiens à remercier M Nakechbandi et M Boukachour pour leur encadrement et leur nom- breuses explications du sujet Master I CChapitre Introduction Les algorithmes génétiques ont été inventés par Jonh Holland dans les années Repris notamment par Golberg dans les années 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 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èrement à intégrer des nouveaux opérateurs de sélection et de croisement génétique Master I CChapitre Problème de Voyageur de Commerce 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 Pratiquement Un voyageur de