Remerciez-le!

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

1 Université Mohamed El-Bachir El-Ibrahimi Bordj Bou Arreridj Faculté des mathé

1 Université Mohamed El-Bachir El-Ibrahimi Bordj Bou Arreridj Faculté des mathématiques et d’informatique Département de la recherche opérationnelle MEMOIRE En vue de l’obtention du diplôme de MASTER FILIERE DES MATHEMATIQUE APPLIQUEE Spécialité : Méthodes Et Outils pour La Recherche Opérationnelle Algorithme hybride (aco-ape) pour La Résolution du problème de Voyageur de commerce Réalisé par : Sous la direction de : Kenza Bechtoula. Hadjer Bouguerra. Dr. Adel Saha. Soutenu le: 27/09/2021 Devant le jury composé de : - Dr. MAACHE SALAH. - Dr. FARHAT FILALI. Année universitaire 2020-2021 2 Remerciements Nous tenons tout d’abord à remercier Dieu le tout puissant et miséricordieux, qui nous a donné la force et la patience d’accomplir ce modeste travail. Nous remercions Dr : Saha Adel, notre encadreur, proposé ce sujet et son conseil dès le début. Un grand merci au Dr : Mokhnache Abdelaziz pour son soutien et son accompagnement durant ce travail. Nous remercions également tous enseignants durant notre parcours académique. Nous remercions aussi tous les étudiants RO dans l’université de BBA, ceux de la promotion 2019-2021. Ce travail n’aurait pu être réalisé sans le soutien et les encouragements de notre famille que nous remercie tout particulièrement. Enfin, nous tenons à remercier tous ceux qui, de près ou de loin, ont contribué à la réalisation de ce travail. 3 Dédicaces Grace a tout puissant, j’ai pu terminer ce modeste travail que je dédie : A mes parents, ma mère pour ses encouragements et ses prières tout au long de mes études, mon père pour tous ce qu’il avait fait pour avoir ce résultat. Que dieu les protègent. A mon adorable sœur "Sahra", qui a toujours été là pour moi tout au long de mes études. A ma chére cousin Nour, qui grâce à lui j'ai accompli mon travail A tous mes amis, mes collègues et tous ceux qui me connaissent. Kenza 4 Dédicaces Je dédie ce travail : A ma chére mère A mon père qui nous a quitté le dans le mérite les sacrifices et les qualités humaines m’ont permis de vivre ce jour A mes frères et ma sœur A mon mari pour leur encouragement leurs soutien moral Hadjer 5 INTRODUCTION GENERALE ............................................................................................................. 1 CHAPITRE I : OPTIMISATION COMBINATOIRE............................................................................ 4 Introduction ............................................................................................................................................................ 5 I.1. L’optimisation .................................................................................................................................................. 5 I.2. Formulation mathématique des problèmes d’optimisation ......................................................................... 6 I.2.1. Problèmes mono-objectifs ................................................................................................................................................ 6 I.2.2. Problèmes multi-objectifs ................................................................................................................................................. 7 I.3. Optimisation combinatoire ............................................................................................................................. 7 I.4. Terminologie .................................................................................................................................................... 8 I.4.1. Voisinage .......................................................................................................................................................................... 8 I.4.2. Optimum local .................................................................................................................................................................. 8 I.4.3. Optimum global ................................................................................................................................................................ 8 I.4.4. Fonction objective ............................................................................................................................................................. 9 I.4.5. Variables de décision ........................................................................................................................................................ 9 I.5. Classification des problèmes d’optimisation ................................................................................................. 9 I.6. La théorie de complexité ............................................................................................................................... 10 I.6.1. La classe P (polynomial time) ......................................................................................................................................... 10 I.6.2. La classe NP (Not Deterministe Plynomial Time) ......................................................................................................... 10 I.6.3. Problème NP-Complet .................................................................................................................................................... 11 I.6.4. Problème NP-difficile ..................................................................................................................................................... 11 I.7. Exemple de problèmes d’optimisation combinatoire .................................................................................. 11 I.7.1. Le problème du sac à dos ................................................................................................................................................. 11 I.7.2. Problème d’ordonnancement .......................................................................................................................................... 12 I.7.3. Problème d’emploi du temps ........................................................................................................................................... 13 I.7.4. Le problème du voyageur de commerce (PVC) .............................................................................................................. 13 I.8. Résolution d’un problème d’optimisation combinatoire ............................................................................ 14 I.8.1. Les méthodes exactes ...................................................................................................................................................... 17 I.8.2. Les méthodes approchées (heuristiques) ......................................................................................................................... 17 I.8.3. Méta-heuristiques ........................................................................................................................................................... 18 TABLE DES MATIERES 6 I.9. Méthodes hybrides ........................................................................................................................................ 18 Conclusion ............................................................................................................................................................ 19 CHAPITRE Ⅱ : COLONIES DE FOURMIS ....................................................................................... 20 Introduction .......................................................................................................................................................... 21 II.1. Les fourmis réel et l'inspiration biologique ................................................................................................ 22 II.2. L’intelligence collective des fourmis ........................................................................................................... 22 II.3. Les fourmis artificielles ................................................................................................................................ 23 II.4. L'algorithme de colonies de fourmis pour résoudre le PVC ..................................................................... 24 II.5. L'algorithme adjacent pairwaise exchange APE ....................................................................................... 32 II.6. Présentation des modèles ............................................................................................................................. 33 II.6.1. Description de la méthode proposée par Mahi & AL .................................................................................................... 35 Conclusion ............................................................................................................................................................ 37 CHAPITRE Ⅲ : IMPLEMENTATIONS ET RESULTATS ................................................................ 38 Introduction .......................................................................................................................................................... 39 Ⅲ.1. Langage de programmation (MatLab) ...................................................................................................... 39 Ⅲ.2. Résultats et discutions ................................................................................................................................ 40 Ⅲ.2.1. Paramètres utilisés ........................................................................................................................................................ 40 Ⅲ.2.2. Résultats ....................................................................................................................................................................... 41 Ⅲ.2.2.1 Description de la première stratégie .................................................................................................................................................. 41 Ⅲ.2.2.2 Description de la deuxième stratégie ................................................................................................................................................. 46 Ⅲ.3. Discussion globale ....................................................................................................................................... 51 Conclusion ............................................................................................................................................................ 51 CUNCLUTION GENERALE ................................................................................................................ 52 Résumé.....................................................................................................................................................57 7 Chapitre Ⅰ Figure.Ⅰ.1 : Classification générale des méthodes d’optimisation monobjectif……….…15 Figure.Ⅰ.2 : Classification de méthode de résolution de problème d’optimisation…...…..16 Chapitre Ⅱ Figure.Ⅱ.1 : Expérience de sélection des branches les plus courtes par une colonie de fourmis: (a) Au début de l’expérience, (b) à la fin de l’expérience………………………25 Figure.Ⅱ.2 : La méthode hybride de MAHI & AL…………………………….…………34 Figure.Ⅱ.3 : Notre modèle hybride………………………………………………………36 Chapitre Ⅲ Figure.Ⅲ.1: MATLAB R2017a…………………..……………………………………..39 Figure.Ⅲ.2: La première méthode de modification hybride…………………………….41 Figure.Ⅲ.3: L’interface des résultats…………………………………………………...43 Figure.Ⅲ.4: L’interface des résultats………………………………….………………...44 Figure.Ⅲ.5: La deuxième méthode de modification hybride……………………………46 Figure.Ⅲ.6: L’interface des résultats………………………………….………………...48 Figure.Ⅲ.7: L’interface des résultats………………………………….………………...49 Liste des Figures 8 Tableau.Ⅲ.1 : Les résultats de la première stratégie du premier modèle……...…………45 Tableau.Ⅲ.2 : Les résultats de la première stratégie de notre modèle………..…….……45 Tableau.Ⅲ.3 : Les résultats de la deuxième stratégie du premier modèle………...……...50 Tableau.Ⅲ.4 : Les résultats de la deuxième stratégie de notre modèle…………...….......50 Liste des Tableaux 9 Algorithme Ⅱ.1 : Algorithme de colonies de fourmis (Ant System) ………………….…28 Algorithme Ⅱ.2: Algorithme OCF……………………………………………………....31 Algorithme Ⅲ.1 : Implémentation de l’algorithme APE de la première stratégie en utilisant MATLAB………………………………………………………………...……42 Algorithme Ⅲ.2 : Implémentation de l’algorithme APE de la deuxième stratégie en utilisant MATLAB………………………………………………………………...……47 Liste des Algorithms 10 ACO : Ant Colony Optimization. PSO : Particle swarm optimization. APE : adjacent pairwaise axchange. PVC : problème de voyageur de commerce. TSP : travelling salesman problem. POC : problème d’optimisation combinatoire. AS : ant system. ACS : Ant colony system. OFC : optimisation par colonies de fourmies. Liste des Abréviation 1 Introduction Générale 2 _____________________________________________________Introduction générale Introduction générale Dans la vie courante, nous sommes souvent en contact avec des problèmes et des difficultés qui nécessitent des études, des décisions et des solutions. Parmi les domaines qui mettent en évidence ces problèmes figurent : les mathématiques, la physique, l'informatique et recherche opérationnelle. Le domaine le plus important est la "recherche opérationnelle", cette science appartient aux mathématiques appliquées, elle repose sur le regroupement de toutes les méthodes et techniques rationnelles afin d’étudier et résoudre les problèmes, elle visant à trouver la meilleure décision et les meilleurs résultats possibles pour permettre aux décideurs de choisir des solutions plus efficaces. C'est ce que l'on appelle " optimisation". Les problèmes d’optimisation que les on rencontre quotidiennement, ils sont modélisés par des spécialistes et mis sur la table d'étude pour chercher des solutions aux plusieurs domaines tels que : l'ingénierie, l'industrie, la gestion du marketing, l'armée, les transports...etc. La résolution d’un problème d’optimisation consiste à trouver la ou les meilleures solutions vérifiant un ensemble de contraintes et d’objectifs définis par l'utilisateur. Suivant le problème d’optimisation, on distingue des méthodes dites exactes qui garantissent la résolution d'un problème, mais au coût de temps de calculs prohibitifs, en citant par exemple la méthode de simplexe. Néanmoins, lorsqu'on veut résoudre un problème complexe, ces méthodes prennent un temps de calcul qui croit exponentiellent avec la taille des instances du problème, ceci conduit souvent à une explosion combinatoire. Parmi les problèmes de l’optimisation combinatoire, nous trouvons le problème de voyageur de commerce, bien qu'il est facile à comprendre mais difficile à résoudre. Pour éviter ce type de problème, on fait appel aux méthodes approchées qui ne cherchent pas forcément l'optimum absolu mais donnent une solution très proche, montrant l'existence d'une solution sensiblement meilleure et largement acceptée. 3 _____________________________________________________Introduction générale En effet, les chercheurs du domaine ont trouvé des méthodes d'une inspiration biologique (exemple : colonie de fourmis, algorithme génétique). Ces méthodes ont des limites c’est pour ça les chercheurs ont combiné ces derniers avec d’autres pour avoir des méthodes hybride comme le modèle proposé par Mahi & Al -2005- (ACO+PSO+3-OPT) pour résoudre le problème de voyageur de commerce et le modèle que nous allons présenter (ACO+PSO+APE) et qui sera étudié dans les chapitres suivants. Notre étude dans ce mémoire est résumée suivant la question ci-après : Est-ce que le modèle ACO+PSO+APE est meilleur que le modèle ACO+PSO+3- OPT ? Afin de voir les performances de ce modèle, six instances du problème PVC de la base TSPLIB sont étudiés et à la fin nous avons comparé nos résultats avec ceux trouver par les modifications apportées sur model de Mahi & Al. Ce mémoire est organisé de la façon suivante : – Le premier chapitre est consacré à la présentation des problèmes d’optimisation combinatoire et la classification des méthodes de résolution existantes ; – Dans le deuxième chapitre, nous focalisons plus particulièrement sur l’optimisation par Colonies de Fourmies avec l’explication de deux modelés hybrides ; – Le troisième et le dernier chapitre, est une partie d’application et d’implémentation d’algorithmes, il abord aussi une analyse des résultats avec quelques changements de paramètres. 4 Chapitre Ⅰ OPTIMISATION COMBINATOIRE 5 _______________________________________Chapitre Ⅰ : Optimisation Combinatoire Introduction L’optimisation combinatoire occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Son importance se justifie d’une part par la grande difficulté des problèmes d’optimisation et d’autre parte par la variété des applications pratiques est pouvant uploads/Geographie/lnskh-l-khyr-lltbaa-memoure.pdf