Métaheuristiques parallèles hybrides : application au problème d'affection quadratique

Abstract

Ce memoire presente une etude sur la conception de methodes hybrides efficaces pour l'optimisation combinatoire. Nous avons mene cette etude sur trois fronts : - la structure intrinseque des instances du QAP (probleme d'affectation quadratique) ; - les metaheuristiques sur environnements distribues ; - les mecanismes d'hybridation et de coevolution. Pour analyser les instances, nous avons etudie leurs paysages de fitness. Nous avons adopte une demarche basee sur le comportement d'une methode de descente et avons propose des indicateurs qui font ressortir trois tendances : type I - un paysage plat et rugueux ; type II - regroupement central des optima locaux constituant un massif ; type III - plusieurs massifs d'optima locaux eparpilles. Cette taxinomie originale rejoint d'autres classements obtenus de maniere empirique. Pour etudier les metaheuristiques paralleles, nous avons distingue les recherches locales des methodes a population. Pour les deux cas, nous avons propose un modele et avons selectionne differentes formes de parallelisation. Pour les executions, nous avons utilise diverses plates-formes paralleles. Nous avons constate que les recherches locales sont plus efficaces sur les instances uniformes (type I) et qu'a l'inverse, les methode a population sont plus performantes sur les instances structurees (type II). Ces constatations nous ont amene a considerer l'hybridation pour resoudre les instances de type III. Dans notre presentation des metaheuristiques hybrides, outre une taxinomie originale, nous avons propose une methode hybride parallele qui associe puissance de calcul et coevolution. Cet hybride repose sur la coevolution d'agents de recherche locale, de diversification, et d'intensification. Ces agents cooperent a travers une memoire adaptative. Nous avons applique ce modele coevolutionniste au QAP, et avons egale, pour de nombreuses instances du QAP, les meilleurs resultats connus.