Tari, Sara
[VerfasserIn]
;
Angers
[MitwirkendeR];
Goëffon, Adrien
[MitwirkendeR]
Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire ; Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems
Titel:
Stratégies d'exploration de paysages de fitness : application à la résolution approchée de problèmes d'optimisation combinatoire ; Fitness landscape exploration strategies : application of combinatorial optimization problems to the approximate solution of combinatorial optimization problems
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
De nombreux problèmes d'optimisation combinatoire sont difficiles à résoudre et mettent en échec les méthodes de résolution exactes. 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. L'étude proposée porte sur les métaheuristiques de type recherche locale. Des mécanismes basiques 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. Nous étudions la navigation dans ces paysages, 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ériorant 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 très bonnes solutions sur divers paysages. ; Many combinatorial optimization problems are hard to solve and in many cases, exact approaches are impracticable. Among partial search algorithms, metaheuristics are generic algorithms, widely studied in ...