Recherche locale guidée

La stratégie de l’algorithme de recherche locale guidée consiste à utiliser des pénalités pour encourager une technique de recherche locale à échapper aux optima locaux et à découvrir les optima globaux. Un algorithme de recherche locale est exécuté jusqu’à ce qu’il se coince dans un optima local. Les caractéristiques des optima locaux sont évaluées et pénalisées, dont les résultats sont utilisés dans une fonction de coût augmenté utilisée par la procédure de recherche locale. La recherche locale est répétée plusieurs fois en utilisant les derniers optima locaux découverts et la fonction de coût augmenté qui guide l’exploration loin des solutions avec des fonctionnalités présentes dans les optima locaux découverts.

La procédure de recherche locale guidée est indépendante de la procédure de recherche locale intégrée. Une procédure de recherche adaptée au domaine doit être identifiée et utilisée.

La procédure de recherche locale guidée peut devoir être exécutée pour des milliers à des centaines de milliers d’itérations, dont chaque itération suppose l’exécution d’un algorithme de recherche locale pour converger.

L’algorithme a été conçu pour des problèmes d’optimisation discrets où une solution est composée de «fonctionnalités» évaluables indépendamment telles que l’optimisation combinatoire, bien qu’il ait été appliqué à l’optimisation de fonction continue modélisée sous forme de chaînes binaires.

Le paramètre λ est un facteur d’échelle pour la pénalisation des fonctionnalités qui doit être dans la même proportion aux coûts de la solution candidate de l’instance de problème spécifique à laquelle l’algorithme est appliqué. En tant que telle, la valeur de λ doit être significative lorsqu’elle est utilisée dans la fonction de coût augmenté (comme lorsqu’elle est ajoutée à un coût de solution candidate en minimisation et soustraite d’un coût dans le cas d’un problème de maximisation).