offres d'emploi formations actualités contact accès annuaire intranet
Séminaires >

Stratégies d’exploration de paysages de fitness au travers de recherches locales

Sara Tari
Univ. Lille

jeudi 9 janvier 2020 à 13h30

salle à préciser


De nombreux problèmes d’optimisation combinatoire sont difficiles à résoudre et mettent en échec les méthodes de résolution exacte. Parmi les algorithmes de résolution approchée, les métaheuristiques sont des algorithmes génériques largement étudiés dans la littérature. La capacité d’une métaheuristique donnée à trouver de bonnes solutions varie selon la nature des problèmes traités et selon les données qui les composent, et il est difficile d’étudier efficacement la dynamique de ces algorithmes pour des instances de grandes tailles. Ces travaux se focalisent sur les métaheuristiques de type recherche locale.

Des mécanismes de navigation des recherches locales sont étudiés afin d’améliorer la compréhension de leur comportement et d’évaluer leur capacité à trouver de bonnes solutions sur différents types de problèmes. Nous abstrayons plusieurs problèmes d’optimisation, munis d’une relation de voisinage entre solutions, sous forme de paysages de fitness afin d’analyser la dynamique des méthodes selon des caractéristiques générales de ces paysages.

La navigation dans ces paysages est étudiée, en se restreignant en premier lieu aux mouvements strictement améliorants. En particulier, nous proposons le critère d’expansion pour guider la recherche et évaluons sa pertinence pour guider les descentes vers de bonnes solutions. Différentes variantes approchant ce principe sont proposées et évaluées, offrant divers compromis entre efficacité et coût calculatoire permettant d’envisager de les intégrer dans des métaheuristiques plus complexes.

Enfin nous étudions des recherches locales à voisinage partiel qui acceptent les mouvements détériorants et montrons que dans ce contexte des règles pivot simples peuvent suffire à obtenir de bons compromis entre intensification et diversification, et ainsi atteindre de bonnes solutions sur divers paysages. L’étude des solutions rencontrées durant ces recherches nous donne des pistes pour évaluer leur capacité exploratrice et d’envisager des mécanismes pour améliorer les meilleures solutions trouvées.