DAA - Algorithme d'escalade

Les algorithmes discutés dans les chapitres précédents fonctionnent systématiquement. Pour atteindre l'objectif, un ou plusieurs chemins précédemment explorés vers la solution doivent être stockés pour trouver la solution optimale.

Pour de nombreux problèmes, le chemin vers l'objectif est sans importance. Par exemple, dans le problème N-Queens, nous n'avons pas besoin de nous soucier de la configuration finale des reines ni de l'ordre dans lequel les reines sont ajoutées.

Escalade

L'escalade est une technique permettant de résoudre certains problèmes d'optimisation. Dans cette technique, nous commençons avec une solution sous-optimale et la solution est améliorée à plusieurs reprises jusqu'à ce qu'une condition soit maximisée.

L'idée de commencer avec une solution sous-optimale est comparée au départ de la base de la colline, l'amélioration de la solution est comparée à la montée de la colline, et enfin la maximisation de certaines conditions est comparée à l'atteinte du sommet de la colline.

Par conséquent, la technique d'escalade peut être considérée comme les phases suivantes -

• Construire une solution sous-optimale obéissant aux contraintes du problème
• Améliorer la solution étape par étape
• Améliorer la solution jusqu'à ce que plus aucune amélioration ne soit possible

La technique d'escalade est principalement utilisée pour résoudre des problèmes complexes de calcul. Il ne regarde que l'état actuel et l'état futur immédiat. Par conséquent, cette technique est efficace en mémoire car elle ne maintient pas d'arbre de recherche.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Amélioration itérative

Dans la méthode d'amélioration itérative, la solution optimale est obtenue en progressant vers une solution optimale à chaque itération. Cependant, cette technique peut rencontrer des maxima locaux. Dans cette situation, il n'y a pas d'état proche pour une meilleure solution.

Ce problème peut être évité par différentes méthodes. L'une de ces méthodes est le recuit simulé.

Redémarrage aléatoire

C'est une autre méthode pour résoudre le problème des optima locaux. Cette technique effectue une série de recherches. À chaque fois, il part d'un état initial généré aléatoirement. Par conséquent, une solution optimale ou presque optimale peut être obtenue en comparant les solutions des recherches effectuées.

Problèmes de la technique d'escalade

Maxima locale

Si l'heuristique n'est pas convexe, l'escalade peut converger vers des maxima locaux, au lieu de maxima globaux.

Crêtes et ruelles

Si la fonction cible crée une crête étroite, le grimpeur ne peut grimper la crête ou descendre l'allée qu'en zig-zag. Dans ce scénario, le grimpeur doit faire de très petits pas nécessitant plus de temps pour atteindre l'objectif.

Plateau

Un plateau est rencontré lorsque l'espace de recherche est plat ou suffisamment plat pour que la valeur renvoyée par la fonction cible ne puisse être distinguée de la valeur renvoyée pour les régions proches, en raison de la précision utilisée par la machine pour représenter sa valeur.

Complexité de la technique d'escalade

Cette technique ne souffre pas de problèmes liés à l'espace, car elle ne regarde que l'état actuel. Les chemins précédemment explorés ne sont pas stockés.

Pour la plupart des problèmes de la technique d'escalade à redémarrage aléatoire, une solution optimale peut être obtenue en temps polynomial. Cependant, pour les problèmes NP-Complete, le temps de calcul peut être exponentiel basé sur le nombre de maxima locaux.

Applications de la technique d'escalade

La technique d'escalade de colline peut être utilisée pour résoudre de nombreux problèmes, où l'état actuel permet une fonction d'évaluation précise, comme le flux réseau, le problème du voyageur de commerce, le problème 8-Queens, la conception de circuits intégrés, etc.

L'escalade est également utilisée dans les méthodes d'apprentissage inductives. Cette technique est utilisée en robotique pour la coordination entre plusieurs robots dans une équipe. Il existe de nombreux autres problèmes où cette technique est utilisée.

Exemple

Cette technique peut être appliquée pour résoudre le problème du voyageur de commerce. Tout d'abord, une solution initiale est déterminée qui visite toutes les villes une seule fois. Par conséquent, cette solution initiale n'est pas optimale dans la plupart des cas. Même cette solution peut être très mauvaise. L'algorithme Hill Climbing commence par une telle solution initiale et y apporte des améliorations de manière itérative. Finalement, un itinéraire beaucoup plus court est susceptible d'être obtenu.