Recherches locales guidées par le critère d'expansion

Session : META / Métaheuristiques
Vendredi 12 février 10:30 - 11:50 Salle : RP7
Sara Tari, Matthieu Basseur et Adrien Goeffon

Les algorithmes de recherche locale, qui utilisent la notion de voisinage pour naviguer dans l'espace de recherche des solutions, sont à la base de nombreuses méthodes de résolution de problèmes d'optimisation combinatoire. Ceux-ci diffèrent principalement selon leur stratégie de sélection de mouvements à appliquer, appelée règle pivot. Nous cherchons ici à déterminer des règles pivot permettant d'atteindre les meilleurs optimums locaux possibles par le biais d'un algorithme de descente. Nous proposons ici d'utiliser des informations supplémentaires fournies par un voisinage étendu afin de sélectionner le mouvement à appliquer. Cela nous a conduit à définir la stratégie du maximum d'expansion, qui consiste à sélectionner les solutions maximisant les possibilités d'amélioration à l'étape suivante de la recherche. Les expérimentations réalisées sur des instances de problèmes à base de permutations indiquent que le score d'expansion est un critère pertinent pour atteindre de bons optimums locaux.

Mots clés : Recherche locale, Descente stochastique, Optimisation combinatoire