Méthode hill-climbing

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir hill-climbing.

La méthode hill-climbing 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]