Algorithme de descente stochastique

La stratégie de l’algorithme Stochastic Hill Climbing consiste à itérer le processus de sélection aléatoire d’un voisin pour une solution candidate et à ne l’accepter que si cela entraîne une amélioration. La stratégie proposée visait à remédier aux limites des techniques déterministes d’escalade susceptibles de rester bloquées dans les optima locaux en raison de leur acceptation cupide des déménagements voisins.

Stochastic Hill Climbing a été conçu pour être utilisé dans des domaines discrets à voisins explicites tels que l’optimisation combinatoire (par rapport à l’optimisation continue des fonctions). La stratégie de l’algorithme peut être appliquée à des domaines continus en utilisant une étape pour définir les voisins candidats à la solution (telle que la recherche aléatoire localisée et la recherche aléatoire déterminée de taille pas à pas).

Le Stochastic Hill Climbing est une technique de recherche locale et peut être utilisé pour obtenir un résultat après l’exécution d’un algorithme de recherche globale. Même si la technique utilise un processus stochastique, elle peut rester bloquée dans les optima locaux. Les voisins avec un coût égal ou supérieur doivent être acceptés, permettant à la technique de naviguer à travers des ensembles équivalents du domaine de définition.

L’algorithme peut être redémarré et répété plusieurs fois après sa convergence pour fournir un résultat amélioré (appelé Multiple Restart Hill Climbing). La procédure peut être appliquée simultanément à plusieurs solutions candidates, ce qui permet l’exécution simultanée de plusieurs algorithmes (appelée Parallel Hill Climbing).

hillclimbing

Publicités