Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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

Résumé :

Au sein des algorithmes de recherche locale, les méthodes de descente font rarement l'objet d'études expérimentales dédiées. Cependant, ces techniques de recherche sont à la base d'un grand nombre de métaheuristiques modernes et peuvent avoir une influence non négligeable quant à la capacité d'un algorithme à atteindre de bonnes solutions de l'espace de recherche. L'an 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 d'avoir atteint un optimum local), permet non seulement une convergence plus rapide de la recherche, mais surtout d'atteindre 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 d'atteindre de bien meilleures solutions qu'à partir du paysage originel. En effet, lisser la fonction d'évaluation permet d'éviter d'être piégé trop tôt dans des optimums locaux.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03256584
Contributeur : Okina Université d'Angers <>
Soumis le : jeudi 10 juin 2021 - 12:29:06
Dernière modification le : vendredi 11 juin 2021 - 03:29:58

Identifiants

  • HAL Id : hal-03256584, version 1
  • OKINA : ua7683

Collections

Citation

Matthieu Basseur, Adrien Goëffon. Chercher moins pour trouver mieux. De l'intérêt de la descente stochastique pour la résolution de problèmes combinatoires. Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF), 2014, Bordeaux, France. ⟨hal-03256584⟩

Partager

Métriques

Consultations de la notice

7