Recherche locale (optimisation) - Local search (optimization)
En informatique , la recherche locale est une méthode heuristique pour résoudre des problèmes d' optimisation difficilement calculables . La recherche locale peut être utilisée sur des problèmes qui peuvent être formulés comme la recherche d'une solution maximisant un critère parmi un certain nombre de solutions candidates . Les algorithmes de recherche locale se déplacent de solution en solution dans l'espace des solutions candidates (l' espace de recherche ) en appliquant des changements locaux, jusqu'à ce qu'une solution jugée optimale soit trouvée ou qu'une limite de temps soit écoulée.
Les algorithmes de recherche locale sont largement appliqués à de nombreux problèmes de calcul difficiles, y compris les problèmes de l' informatique (en particulier l' intelligence artificielle ), les mathématiques , la recherche opérationnelle , l' ingénierie et la bioinformatique . Des exemples d'algorithmes de recherche locale sont WalkSAT , l' algorithme 2-opt pour le problème du voyageur de commerce et l' algorithme Metropolis-Hastings .
Exemples
Certains problèmes où la recherche locale a été appliquée sont :
- Le problème de couverture de sommets , dans lequel une solution est une couverture de sommets d' un graphe , et l' objectif est de trouver une solution avec un nombre minimal de nœuds
- Le problème du voyageur de commerce , dans lequel une solution est un cycle contenant tous les nœuds du graphe et la cible est de minimiser la longueur totale du cycle
- Le problème de satisfiabilité booléenne , dans lequel une solution candidate est une affectation de vérité, et la cible est de maximiser le nombre de clauses satisfaites par l'affectation ; dans ce cas, la solution finale n'est utile que si elle satisfait toutes les clauses
- Le problème d'horaire des infirmières où une solution est une affectation des infirmières à des quarts de travail qui satisfait toutes les contraintes établies
- Le problème de clustering k-medoid et d'autres problèmes de localisation d'installations connexes pour lesquels la recherche locale offre les meilleurs rapports d'approximation connus dans la perspective du pire des cas
- Le problème des réseaux de neurones de Hopfield pour lequel trouver des configurations stables dans le réseau de Hopfield .
La description
La plupart des problèmes peuvent être formulés en termes d'espace de recherche et de cible de plusieurs manières différentes. Par exemple, pour le problème du voyageur de commerce, une solution peut être un cycle et le critère à maximiser est une combinaison du nombre de nœuds et de la durée du cycle. Mais une solution peut aussi être un chemin, et être un cycle fait partie de la cible.
Un algorithme de recherche locale part d'une solution candidate, puis se déplace de manière itérative vers une solution voisine . Ceci n'est possible que si une relation de voisinage est définie sur l'espace de recherche. A titre d'exemple, le voisinage d'une couverture de sommet est une autre couverture de sommet ne différant que d'un nœud. Pour la satisfiabilité booléenne, les voisins d'une affectation de vérité sont généralement les affectations de vérité n'en différant que par l'évaluation d'une variable. Le même problème peut avoir plusieurs quartiers différents définis dessus ; L'optimisation locale avec des voisinages qui impliquent de changer jusqu'à k composants de la solution est souvent appelée k-opt .
En règle générale, chaque solution candidate a plus d'une solution voisine ; le choix vers lequel se déplacer se fait en utilisant uniquement des informations sur les solutions au voisinage de celle en cours, d'où le nom de recherche locale . Lorsque le choix de la solution voisine se fait en prenant celle maximisant localement le critère, la métaheuristique prend le nom d' escalade . Lorsqu'aucune configuration d'amélioration n'est présente dans le voisinage, la recherche locale est bloquée à un point localement optimal . Ce problème local-optima peut être résolu en utilisant des redémarrages (recherche locale répétée avec différentes conditions initiales), ou des schémas plus complexes basés sur des itérations, comme la recherche locale itérée , sur la mémoire, comme l'optimisation de recherche réactive, sur des modifications stochastiques sans mémoire, comme recuit simulé .
La fin de la recherche locale peut être basée sur une limite de temps. Un autre choix courant est de terminer lorsque la meilleure solution trouvée par l'algorithme n'a pas été améliorée dans un nombre d'étapes donné. La recherche locale est un algorithme à tout moment : il peut renvoyer une solution valide même si elle est interrompue à tout moment avant de se terminer. Les algorithmes de recherche locale sont généralement des algorithmes approximatifs ou incomplets , car la recherche peut s'arrêter même si la meilleure solution trouvée par l'algorithme n'est pas optimale. Cela peut arriver même si la terminaison est due à l'impossibilité d'améliorer la solution, car la solution optimale peut se situer loin du voisinage des solutions traversées par les algorithmes.
Pour des problèmes spécifiques, il est possible de concevoir des quartiers très grands, éventuellement de taille exponentielle. Si la meilleure solution dans le voisinage peut être trouvée efficacement, ces algorithmes sont appelés algorithmes de recherche de voisinage à très grande échelle .
Voir également
La recherche locale est un sous-champ de :
Les champs de la recherche locale incluent :
- Escalade
- Recuit simulé (adapté à la recherche locale ou globale)
- Recherche tabou
- Acceptation tardive de l'escalade
- Optimisation de la recherche réactive (combinant apprentissage automatique et heuristique de recherche locale)
Espaces de recherche à valeur réelle
Plusieurs méthodes existent pour effectuer une recherche locale d' espaces de recherche à valeur réelle :
- Luus–Jaakola recherche localement en utilisant une distribution uniforme et une plage de recherche décroissante de façon exponentielle.
- L'optimisation aléatoire recherche localement en utilisant une distribution normale .
- La recherche aléatoire recherche localement en échantillonnant une hypersphère entourant la position actuelle.
- La recherche de motif fait des pas le long des axes de l'espace de recherche en utilisant des tailles de pas décroissantes de façon exponentielle.
Les références
Bibliographie
- Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Recherche réactive et optimisation intelligente . Springer Verlag . ISBN 978-0-387-09623-0. Archivé de l'original le 2012-03-16.
- Hoos, HH et Stutzle, T. (2005) Recherche locale stochastique : fondements et applications, Morgan Kaufmann.
- Vijay Arya et Naveen Garg et Rohit Khandekar et Adam Meyerson et Kamesh Munagala et Vinayaka Pandit, (2004): Local Search Heuristics for k -Median and Facility Location Problems , SIAM Journal of Computing 33(3).
- Juraj Hromkovič : Algorithmique pour les problèmes difficiles : Introduction à l'optimisation combinatoire, à la randomisation, à l'approximation et à l'heuristique (Springer)
- Wil Michiels, Emile Aarts, Jan Korst : Aspects théoriques de la recherche locale (Springer)