Méthode hill-climbing
Pour les articles homonymes, voir hill-climbing.
La méthode hill-climbing ou méthode d'escalade est une méthode d'optimisation permettant de trouver un optimum local parmi un ensemble de configurations.
Description
[modifier | modifier le code]Le hill-climbing une méthode générale qui prend en entrée trois objets : une configuration, une fonction qui pour chaque configuration donne un ensemble de configurations voisines, et une fonction-objectif qui permet d'évaluer chaque configuration. La méthode consiste simplement à partir de la configuration initiale, à évaluer les solutions voisines, et à choisir la meilleure de celles-ci, et à recommencer l'opération jusqu'à arriver à une position meilleure que les positions voisines[1]. C'est alors un optimum local.
Comparaison
[modifier | modifier le code]Le hill-climbing une méthode itérative, locale, et gloutonne. Elle est similaire à la méthode de la descente de gradient mais est plutôt utilisée dans un contexte discret où le gradient n'est pas défini. Certains auteurs donnent une définition plus restreinte du hill-climbing, où chaque configuration correspond à un vecteur, et chaque voisinage considéré ne fait varier qu'une seule coordonnée.
Notes et références
[modifier | modifier le code]- Hugo Larochelle, « Méthode Hill-climbing », sur Université de Sherbrooke
