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 :

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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 :

Espaces de recherche à valeur réelle

Plusieurs méthodes existent pour effectuer une recherche locale d' espaces de recherche à valeur réelle :

Les références

Bibliographie