human
Veuillez expliquer ce qu'est "l'escalade"
gpt
Dans l'analyse numérique, l'escalade est une technique d'optimisation mathématique qui appartient à la famille de la recherche locale.Il s'agit d'un algorithme itératif qui commence par une solution arbitraire à un problème, puis tente de trouver une meilleure solution en apportant un changement incrémentiel à la solution.Si le changement produit une meilleure solution, un autre changement incrémentiel est apporté à la nouvelle solution, et ainsi de suite jusqu'à ce qu'aucune autre amélioration ne puisse être trouvée.
Par exemple, l'escalade peut être appliquée au problème des vendeurs itinérants.Il est facile de trouver une solution initiale qui visite toutes les villes mais sera probablement très médiocre par rapport à la solution optimale.L'algorithme commence par une telle solution et y apporte de petites améliorations, telles que le changement de l'ordre dans lequel deux villes sont visitées.Finalement, une route beaucoup plus courte est susceptible d'être obtenue.
L'escalade en colline trouve des solutions optimales pour les problèmes convexes - pour d'autres problèmes, il ne trouvera que l'optima local (solutions qui ne peuvent être améliorées par aucune configuration voisine), qui ne sont pas nécessairement la meilleure solution possible (l'optimum global) de toutes les solutions possibles (l'espace de recherche).Des exemples d'algorithmes qui résolvent les problèmes convexes par l'escroquerie de collines incluent l'algorithme simplex pour la programmation linéaire et la recherche binaire: 253 pour éviter de rester coincé dans l'optima local, on pourrait utiliser des redémarrages (c'est-à-dire une recherche locale répétée), ou des schémas plus complexes basésSur les itérations (comme la recherche locale itérée), ou sur la mémoire (comme l'optimisation de la recherche réactive et la recherche tabu), ou sur les modifications stochastiques sans mémoire (comme le recuit simulé).
La simplicité relative de l'algorithme en fait un premier choix populaire parmi les algorithmes d'optimisation.Il est largement utilisé dans l'intelligence artificielle, pour atteindre un état d'objectif à partir d'un nœud de départ.Différents choix pour les nœuds suivants et les nœuds de démarrage sont utilisés dans des algorithmes associés.Bien que des algorithmes plus avancés tels que le recuit simulé ou la recherche tabu puissent donner de meilleurs résultats, dans certaines situations, l'escalade des collines fonctionne aussi bien.L'escalade peut souvent produire un meilleur résultat que d'autres algorithmes lorsque le temps disponible pour effectuer une recherche est limité, comme avec les systèmes en temps réel, tant qu'un petit nombre d'incréments convergent généralement sur une bonne solution (la solution optimaleou une approximation proche).À l'autre extrême, le tri des bulles peut être considéré comme un algorithme d'escalade de colline (chaque échange d'éléments adjacent diminue le nombre de paires d'éléments désordonnées), mais cette approche est loin d'être efficace pour une N même modeste, car le nombre d'échanges requis augmente quadratique.
L'escalade est un algorithme à tout moment: il peut retourner une solution valide même si elle est interrompue à tout moment avant sa fin.