Etablissement
Ecole Nationale Supérieure d'informatique
Affiliation
Département de Post-Graduation
Auteur
HADJI, Riad
Directeur de thèse
Benatchba Karima
Co-directeur
Bessedik Malika
Filière
Informatique
Diplôme
Doctorat
Titre
Une approche biomimétique pour la résolution de problème de la coloration par listes. Application au problème d’affectation de fréquence.
Mots clés
Métaheuristiques, Optimisation combinatoire, Approche biomimétique, coloration par listes, parallélisation.
Résumé
Les problèmes d’optimisation combinatoire tels que les problèmes d‘ordonnancement, le problème de recouvrement d’ensembles, le problème du voyageur de commerce ou le problème de coloration de graphe apparaissent dans plusieurs domaines de la vie quotidienne notamment les secteurs économiques et industriels. Plusieurs méthodes de résolutions issues de la recherche opérationnelle et de l’intelligence artificielle trouvent les solutions optimales en un temps raisonnable pour des problèmes de petites tailles. Cependant, dès que la taille des instances dépasse une certaine valeur, le temps de traitement ou de recherche augmente exponentiellement et peut atteindre des milliers d’années. Dans la théorie de la complexité des algorithmes, ces problèmes figurent dans la classe des problèmes NP-complet ou NP-difficile. Les métaheuristiques tentent de caractériser des zones de l’espace de recherche où l’optimum ne peut se trouver, dont l’exploration n’est pas nécessaire ; et/ou tentent d’identifier des zones prometteuses, dans lesquelles l’optimum a de grandes chances d’être, et qu’il faut exploiter en priorité. Du coup, le temps de résolution est réduit. En toute généralité, une bonne heuristique est une méthode qui réussit un juste équilibre entre l’exploration de nouvelles régions de l’espace de recherche et l’exploitation des bonnes solutions déjà trouvées. Une autre approche, pour obtenir des temps de calculs raisonnables, est l’emploi de calculateurs puissants. Aujourd’hui, des contraintes technologiques limitant la puissance d’un processeur unique, les plates-formes puissantes sont des machines parallèles qui intègrent plusieurs processeurs ou des environnements distribués qui utilisent plusieurs machines connectées en réseau. Ainsi, pour gagner en efficacité, il convient d’intégrer à l’optimisation combinatoire des techniques de parallélisation pour concevoir des méthodes d’optimisation parallèles, plus performantes. En effet, ces dernières années, les calculateurs parallèles ont permis d’obtenir des résultats satisfaisants sur des instances de grandes tailles. L’objectif de cette thèse est d’explorer les différentes méthodes de parallélisation des métaheuristiques et leurs implémentations sur les différentes architectures parallèles et distribuées.
Statut
Vérifié