Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire

De nombreux problemes d'optimisation combinatoire sont difficiles a resoudre et mettent en echec les methodes de resolution exactes. Parmi les algorithmes de resolution approchee, les metaheuristiques sont des algorithmes generiques largement etudies dans la litterature. La capacite d’une metaheuristique donnee a trouver de bonnes solutions varie selon la nature des problemes traites et selon les donnees qui les composent, et il est difficile d’etudier efficacement la dynamique de ces algorithmes pour des instances de grandes tailles. L'etude proposee porte sur les metaheuristiques de type recherche locale. Des mecanismes basiques sont etudies afin d'ameliorer la comprehension de leur comportement et d'evaluer leur capacite a trouver de bonnes solutions sur differents types de problemes. Nous abstrayons plusieurs problemes d'optimisation, munis d’une relation de voisinage entre solutions, sous forme de paysages de fitness afin d’analyser la dynamique des methodes selon des caracteristiques generales de ces paysages. Nous etudions la navigation dans ces paysages, en se restreignant en premier lieu aux mouvements strictement ameliorants. En particulier, nous proposons le critere d’expansion pour guider la recherche et evaluons sa pertinence pour guider les descentes vers de bonnes solutions. Differentes variantes approchant ce principe sont proposees et evaluees, offrant divers compromis entre efficacite et cout calculatoire permettant d’envisager de les integrer dans des metaheuristiques plus complexes. Enfin nous etudions des recherches locales a voisinage partiel qui acceptent les mouvements deteriorants et montrons que dans ce contexte des regles pivot simples peuvent suffire a obtenir de bons compromis entre intensification et diversification, et ainsi atteindre de tres bonnes solutions sur divers paysages.