Chercher moins pour trouver mieux. De l#039;intérêt de la descente stochastique pour la résolution de problèmes combinatoires

摘要

Au sein des algorithmes de recherche locale, les méthodes de descente font rarement lu27objet du27études expérimentales dédiées. Cependant, ces techniques de recherche sont à la base du27un grand nombre de métaheuristiques modernes et peuvent avoir une influence non négligeable quant à la capacité du27un algorithme à atteindre de bonnes solutions de lu27espace de recherche. Lu27an passé, nous avons comparé des descentes basées sur différentes règles pivot (premier ou meilleur améliorant) et différentes politiques de gestion de la neutralité (descente stricte, stochastique, ou stricte avec perturbations neutres), puis comparé empiriquement leur efficacité sur des paysages de recherche de type NK-landscapes, de différentes tailles et enregistrant différents niveaux de rugosité et de neutralité.Nous étendons cette année cette étude à des paysages de recherche issus de problèmes combinatoires académiques (MAXSAT, QAP, Flow-shop), après avoir introduit des indicateurs de caractérisation des paysages de recherche. Dans une large étude expérimentale, nous montrons que la stratégie du meilleur améliorant est plus efficace sur les paysages lisses et/ou de petites tailles mais est rapidement dominée par la stratégie du premier améliorant sur les paysages plus rugueux et/ou plus grands. Parallèlement, nous indiquons que la descente stochastique, qui accepte indifféremment des voisins neutres tout au long de la recherche (même avant du27avoir atteint un optimum local), permet non seulement une convergence plus rapide de la recherche, mais surtout du27atteindre la plupart du temps des optimums locaux de meilleure qualité. Enfin, une étude sur les NKr-landscapes montre que la création artificielle de plateaux (en arrondissant les valeurs fitness), permet du27atteindre de bien meilleures solutions quu27à partir du paysage originel. En effet, lisser la fonction du27évaluation permet du27éviter du27être piégé trop tôt dans des optimums locaux.