Bibliothèque de L'IMIST/CNRST

PH.D Université Mohammed V 2017

Les travaux de recherche présentés dans ce mémoire concernent principalement l'élaboration d'un ensemble d'algorithmes approchés pour résoudre des problèmes d’optimisation combinatoire (POCs) NP-difficiles. Le but est de concevoir des adaptations efficaces de méthodes méta-heuristiques en vue de trouver de bonnes solutions dans un temps raisonnable. Dans cette perspective, quatre contributions essentielles sont proposées.
La première contribution est la proposition d'une nouvelle version de l'algorithme de la recherche du coucou pour les POCs en utilisant les clés aléatoires. La deuxième contribution concerne l'adaptation de la recherche locale à évasion (BLS) au célèbre problème du voyageur de commerce (TSP). Cette récente méta-heuristique alterne entre une recherche locale classique pour retrouver les minima locaux et une stratégie de diversification adaptative pour se déplacer d'un minimum local vers un autre de l'espace de recherche. Les problèmes rencontrés dans les situations réelles sont bien plus compliqués que les problèmes de référence. Les problèmes réels sont souvent composés de deux ou plusieurs composantes, où chaque sous-problème influence les autres sous-problèmes. Nous nous sommes intéressés à l'étude et la résolution du problème du voyageur voleur (TTP) qui combine deux problèmes NP-difficiles : le problème du voyageur de commerce (TSP) et le problème du sac à dos (KP). Le TTP est un nouveau POC utilisé comme modèle de référence pour les problèmes à plusieurs composantes interdépendantes. Ainsi, La troisième contribution propose des algorithmes de recherche locale pour résoudre le TTP. La quatrième contribution est une adaptation d'un algorithme mémétique.
Diverses autres contributions portent sur des applications aux problèmes du monde réel.