Quelles sont les limites de l'algorithme d'escalade et comment les surmonter?

Réponses:

6

Comme @nbro l'a déjà dit, Hill Climbing est une famille d' algorithmes de recherche locale . Donc, quand vous avez dit Escalade dans la question, j'ai supposé que vous parliez de l'escalade standard. La version standard de la montée de côte a certaines limites et se retrouve souvent bloquée dans le scénario suivant:

  • Maxima locale: algorithme d'escalade atteignant à proximité une valeur maximale locale, se dirige vers le sommet et s'y bloque, n'ayant pas d'autre endroit où aller .
  • Ridges: Ce sont des séquences de maxima locaux , ce qui rend difficile la navigation de l'algorithme.
  • Plateaux: Il s'agit d'une région plate de l'espace d'état . Comme il n'y a pas de montée, l'algorithme se perd souvent dans le plateau.

Pour résoudre ces problèmes, de nombreuses variantes d'algorithmes de montée de côte ont été développées. Ce sont les plus couramment utilisés:

  • L'escalade stochastique sélectionne au hasard parmi les mouvements en montée. La probabilité de sélection varie avec la raideur de la montée.
  • First-Choice Climbing implémente celui ci-dessus en générant des successeurs au hasard jusqu'à ce qu'un meilleur soit trouvé.
  • Redémarrage aléatoire de l'escalade recherche à partir de mouvements initiaux générés aléatoirement jusqu'à ce que l'état de but soit atteint.

Le succès des algorithmes de montée de colline dépend de l'architecture du paysage de l'espace d'état. Chaque fois qu'il y a peu de maxima et de plateaux, les variantes des algorithmes de recherche de montée de colline fonctionnent très bien. Mais dans le monde réel, les problèmes ont un paysage qui ressemble plus à une famille très dispersée de porcs-épics chauves sur un sol plat, avec des porcs-épics miniatures vivant à l'extrémité de chaque aiguille de porc-épic (comme décrit dans le 4ème chapitre du livre Intelligence artificielle: A Approche moderne). Les problèmes NP-Hard ont généralement un nombre exponentiel de maxima locaux pour rester bloqués.
Des algorithmes donnés ont été développés pour surmonter ces types de problèmes:

  • Recuit stimulé
  • Recherche de faisceaux locaux
  • Algorithmes génétiques

Ouvrage de référence - Intelligence artificielle: une approche moderne

Ugnes
la source
Il existe plus d'alternatives disponibles pour surmonter les problèmes de l'escalade; à savoir les groupes de permutation, les bases de données de modèles et la recherche basée sur la grammaire. Ils utilisent des connaissances spécifiques au domaine pour une recherche plus rapide dans l'espace d'état.
Manuel Rodriguez
Oui @ManuelRodriguez. Les algorithmes dépendants des connaissances spécifiques au domaine donnent d'excellents résultats. Mais j'ai essayé de garder la réponse aux problèmes génériques, en mentionnant quelques-uns des moyens qui peuvent surmonter les limites de Hill Climb Search.
Ugnes
5

L'escalade n'est pas un algorithme, mais une famille d'algorithmes de «recherche locale». Les algorithmes spécifiques qui entrent dans la catégorie des algorithmes "d'escalade" sont 2-opt, 3-opt, 2.5-opt, 4-opt ou, en général, tout N-opt. Voir le chapitre 3 de l'article « Le problème du voyageur de commerce: une étude de cas dans l'optimisation locale » (par David S. Johnson et Lyle A. McGeoch) pour plus de détails sur certains de ces algorithmes de recherche locale (appliqués au TSP).

Ce qui différencie un algorithme de cette catégorie de l'autre, c'est la «fonction de voisinage» qu'ils utilisent (en termes simples, la façon dont ils trouvent des solutions voisines à une solution donnée). Notez que, dans la pratique, ce n'est pas toujours le cas: souvent ces algorithmes ont plusieurs implémentations différentes.

La limitation la plus évidente des algorithmes d'escalade est due à leur nature, c'est-à-dire qu'il s'agit d'algorithmes de recherche locaux. Par conséquent, ils ne trouvent généralement que des maxima (ou minima) locaux . Donc, si l'un de ces algorithmes a déjà convergé vers un minimum local (ou maximum) et, dans la solution ou l'espace de recherche, il y a, à proximité de cette solution trouvée, une meilleure solution, aucun de ces algorithmes ne pourra le trouver meilleure solution. Ils seront essentiellement piégés.

Les algorithmes de recherche locaux ne sont généralement pas utilisés seuls. Ils sont utilisés comme sous-routines d'autres algorithmes méta-heuristiques, comme le recuit simulé, la recherche itérative locale ou dans l'un des algorithmes ant-colony. Donc, pour surmonter leurs limites, nous ne les utilisons généralement pas seuls, mais nous les utilisons en conjonction avec d'autres algorithmes, qui ont une nature probabiliste et peuvent trouver des minima ou des maxima globaux (par exemple, n'importe lequel des algorithmes ant-colony).

nbro
la source
Belle réponse (+1)! Pouvez-vous recommander une ressource (YouTube, article de blog, papier arxive, livre) pour en savoir plus sur les algorithmes ant-colonie? Je n'en ai jamais entendu parler et j'aimerais en avoir une idée approximative.
Martin Thoma
1
@MartinThoma J'ai bien peur de ne pas vraiment connaître un très bon tutoriel sur ACS. Vous pouvez peut-être commencer par le bref didacticiel suivant et la mise en œuvre correspondante: cleveralgorithms.com/nature-inspired/swarm/… . Si vous êtes également intéressé par une implémentation plus sérieuse, appliquée au TSP, alors jetez un œil à celle-ci: aco-metaheuristic.org/aco-code , implémenté par Stützle (et autres), l'un des contributeurs au développement de ces techniques.
nbro
Le demandeur sait quelle est la définition formelle de l'escalade parce qu'il a lu l'article Wikipedia. La question va plus dans le sens de son utilisation pour l'intelligence artificielle. Il est connu que l'escalade ne peut rechercher que dans l'espace local, ce qui rend difficile les problèmes liés à l'IA. Habituellement, la recherche est bloquée dans un optima local, ce qui signifie que l'itinéraire le plus court dans le problème des vendeurs itinérants est introuvable.
Manuel Rodriguez
1
@MartinThoma Quoi qu'il en soit, vous pouvez également consulter les articles de recherche. Je ne peux que vous dire quelques chercheurs importants: Dorigo (le premier qui a introduit ces techniques, AFAIK), Gambardella et Stützle. Regardez leurs papiers. Je ne sais pas lequel suggérer. Il y a aussi un livre consacré à l'intelligence en essaim (par Bonabeau), si vous voulez vraiment entrer dans les détails.
nbro