Définition - Que signifie l'escalade?
L'escalade est une méthode heuristique d'optimisation mathématique utilisée pour résoudre des problèmes complexes de calcul qui ont plusieurs solutions. Il s'agit d'une méthode itérative appartenant à la famille de recherche locale qui commence par une solution aléatoire puis améliore de manière itérative cette solution un élément à la fois jusqu'à ce qu'elle aboutisse à une solution plus ou moins optimisée.
Definir Tech explique l'escalade
L'escalade est une technique d'optimisation utilisée pour trouver une solution «optimale locale» à un problème de calcul. Cela commence par une solution très pauvre par rapport à la solution optimale, puis s'améliore de manière itérative à partir de là. Il le fait en générant des solutions "voisines" qui sont relativement un pas meilleures que la solution actuelle, choisit la meilleure et répète ensuite le processus jusqu'à ce qu'il arrive à la solution la plus optimale car il ne peut plus trouver d'améliorations.
Variantes:
- Simple - Le premier nœud ou solution le plus proche à trouver est choisi.
- Ascension la plus raide - Toutes les solutions successives disponibles sont prises en compte, puis la plus proche est sélectionnée.
- Stochastique - Une solution voisine est sélectionnée au hasard, et il est ensuite décidé de passer ou non à cette solution en fonction de la quantité d'amélioration par rapport au nœud actuel.
L'escalade se fait de manière itérative - elle passe par une procédure entière et la solution finale est stockée. Si une itération différente trouve une meilleure solution finale, la solution ou l'état stocké est remplacé. Ceci est également appelé escalade de colline de fusil de chasse, car il essaie simplement différents chemins jusqu'à ce qu'il frappe le meilleur, tout comme le fait qu'un fusil de chasse est inexact mais peut toujours atteindre sa cible en raison de la large diffusion des projectiles. Cela fonctionne très bien dans de nombreux cas car il s'avère qu'il est préférable de dépenser des ressources CPU pour explorer différents chemins plutôt que d'optimiser soigneusement à partir d'une condition initiale.