# 2 / 4 La Méthode de descente est une Heuristique ou Méta-Heuristique ?

Une heuristique est un algorithme d’optimisation qui permet de trouver rapidement une solution à un problème sans toutefois fournir de garantie sur la qualité des solutions.
Une métaheuristique est un algorithme heuristique de haut niveau qui peut être adapté à divers problèmes.
La recherche locale et la méthode de descente sont des mécanismes heuristiques utilisés et développés par des méta-heuristiques comme la méthode tabou, recuit simulé et autres…
Les méthodes de descente (Hill Climbing (escalade) en cas de maximisation ) Les méthodes de descente sont assez anciennes et doivent leur succès à leur rapidité et leur simplicité.
A chaque pas de la recherche, cette méthode progresse vers une solution voisine de meilleure qualité.
La descente s’arrête quand tous les voisins candidats sont moins bons que la solution courante ; c’est-à-dire lorsqu’un optimum local est atteint. On distingue différents types de descente:
La descente déterministe,
La descente stochastique et
La descente vers le premier meilleur.
Les méthodes de descente sont spécifique pour la résolution d’un problème donné, elle ne sont pas généralisées pour tous type de problème (heuristique).
On distingue différents types de descente en fonction de
La stratégie de génération de la solution de départ : solution initiale et
La détermination du voisinage et le déplacement (son parcours).
La méta-heuristique utilise le principe de la méthode de descente avec améliorations en injectant des procédures avancées plus générales.
Le principal défaut des méthodes de descente est qu’elles s’arrêtent au premier minimum local rencontré.
Un minimum local pour une structure de voisinage ne l’est pas forcément pour une autre structure.
Le choix de N peut donc avoir une grand influence sur l’efficacité d’une méthode de descente.
Une Méta-heuritique qui améliore l’heuristique de descente:
Pour éviter d’être bloqué au premier minimum local rencontré, on peut décider d’accepter, sous certaines conditions, de se déplacer d’une solution xi vers une solution voisine xi+1 ∈ N(xi) telle que f(xi+1) ≥ f(xi) (un parcours plus intelligent) comme le font certaines méthodes méta-heuristique comme la méthode tabou.

[@tarikomar7]

Merci