Bases des méthodes de recherche locale

Bases des méthodes de recherche locale

• Cette présentation aborde les bases des méthodes de recherche locale en optimisation combinatoire.
• Un problème d'optimisation combinatoire vise à trouver la meilleure solution parmi un ensemble fini de solutions possibles.
• L'espace des solutions (S) comprend toutes les solutions possibles du problème.
• Une fonction objectif (f) est assignée à chaque solution s ∈ S, et représente la valeur de l'objectif à minimiser.
• L'objectif principal est de déterminer la solution optimale s* ∈ S qui minimise la fonction objectif f(s).
• La formule pour la solution optimale est f(s*) = min f(s), où s parcourt tout l'espace des solutions.
• La distinction entre optimum local et optimum global est cruciale.
• Un optimum local est une solution qui est au moins aussi bonne que toutes ses solutions voisines.
• Un optimum global (solution optimale) s* est une solution dont la valeur de la fonction objectif est inférieure ou égale à celle de toutes les autres solutions dans l'espace des solutions S.

Optimisation locale vs Optimisation globale

• L'optimisation locale vise à trouver une solution aussi bonne que ses voisines dans l'espace des solutions.
• Une solution est optimum local si, et seulement si, sa valeur de la fonction objectif est inférieure ou égale à celle des autres solutions voisines dans un voisinage défini de la solution.

Méthodes de recherche locale

• Les méthodes de recherche locale sont des algorithmes itératifs qui explorent l'espace des solutions en se déplaçant pas à pas d'une solution à une autre.
• L'exploration commence généralement avec une solution initiale ou obtenue par une méthode constructive.
• Le passage d'une solution à une autre se détermine par un ensemble de modifications élémentaires.
• L'exploration termine selon des critères d'arrêt spécifiques.
• Les passages successifs définissent un itinéraire d'exploration de l'espace de solution.

Méthodes de recherche locale : éléments de base

• Les algorithmes de recherche locale sont des stratégies pour explorer l'espace de recherche.
• La solution de départ est une composante essentielle qu'on peut obtenir grâce à des heuristiques constructives.
• La représentation des solutions est un autre élément crucial.
• La définition du voisinage d'une solution est également importante.
• L'algorithme de descente (Climber) est une stratégie pour trouver une solution optimale locale.

Heuristiques constructives (Solutions de départ)

• La plupart des heuristiques constructives sont de type "glouton".
• Elles construisent la solution pas à pas, en sélectionnant à chaque étape la meilleure option à chaque étape
• L'objectif est de trouver rapidement une solution fonctionnelle, sans garantir l'optimalité globale.
• Elles présentent cependant des inconvénients, notamment le fait de ne pas garantir d'atteindre l'optimum global.
• En dépit de ses limites, elle est souvent utilisée comme point de départ d'autres méthodes plus sophistiquées, en particulier dans les contextes où la rapidité de résolution est prioritaire.

Heuristiques constructives: exemples

• Exemples de problèmes où les heuristiques constructives sont applicables, incluant le problème du voyageur de commerce
• Une présentation de l'algorithme du plus proche voisin
• Illustration de l'algorithme d'insertion la moins distante.
• Méthodes pour construire des arbres couvrants de poids minimum (Algorithme de Kruskal).
• Cas particulier d'un problème de sac-à-dos avec des heuristiques constructives.

Représentation des solutions

• Différents types de représentations des solutions qui permettent de définir l'espace de recherche pour les problèmes comme le sac-à-dos ou le voyageur de commerce.
• Vecteur 0-1.
• Permutation circulaire.
• Des indicateurs d'élements pour les différentes représentations possibles.

Voisinage et espace de recherche

• Le voisinage d'une solution est un ensemble de solutions atteignables à partir de la solution courante par une modification élémentaire.
• Les voisines sont proches, en termes de coût.
• Les bons voisinages permettent de représenter efficacement l'espace des solutions voisines.
• Les illustrations visuelles (diagrammes) montrent la structure relationnelle entre les solutions de l'espace de recherche.
• Le voisinage joue un rôle crucial pour définir l'exploration de l'espace de recherche et, par conséquent, l'efficacité de la recherche locale.

Voisinages pour l'espace des permutations

• Différentes présentations du type de voisinage dans l'espace des permutations, à savoir N1, N2 et jusqu'à N3.
• Les présentations illustrent les relations des solutions voisins.

Voisinages pour le voyageur de commerce

• Les voisinages dans le cadre du voyageur de commerce, tels que les voisinages 2-opt et 3-opt sont explicites.
• Illustration des méthodes 2-opt et 3-opt.
• L'illustration visuelle permet aux étudiants d'appréhender les modifications entre les solutions voisin en termes de parcours.

Algorithmes de descente (Climbers)

• Les algorithmes de descente sont des approches itératives pour améliorer progressivement une solution en explorant son voisinage.
• À chaque itération, on sélectionne une solution voisine qui améliore la fonction objectif par rapport à la solution courante.
• Illustration des algorithmes de descente (Climbers) pour différents cas (ordonnancement, voyageur de commerce symétrique/asymétrique)

Algorithmes de recherche locale

• Les différents aspects d'un espace de recherche à considérer sont mentionnés, tels que la connectivité, le nombre de solutions voisines, et la distance entre deux solutions.
• Les limites des algorithmes de recherche locale, tels que l'arrêt prématuré, la dépendance à la solution de départ et le choix du voisinage, sont explicitées.

GRASP comme métaheuristique

• Il s'agit d'une méthodologie qui combine la construction gloutonne et l'amélioration locale afin de s'accrocher à une meilleure solution.
• Les illustrations présentent la procédure GRASP et ses étapes (construction d'une solution gloutonne, recherche locale).
• Les techniques comme la randomisation et l'échantillonage du problème, décrites dans la présentation, sont des stratégies pour étendre l'espace de recherche.
• Les avantages de l'approche GRASP pour les méthodes de résolution sont explicites

Faiblesses des algorithmes de recherche locale

• Il existe des problèmes, avec ces algorithmes, au niveau du voisinage et de la convergence.
• Pour contourner ces limites, des métaheuristiques sont employées.