Sommaire

Descente de gradient

La descente de gradient est une métaheuristique incrémentale. À partir d’une première solution, choisie aléatoirement ou donnée comme base (par exemple la meilleure solution connue des experts), l’algorithme va chercher une optimisation en ne modifiant la solution que d’une unité.

Lorsque le problème est une fonction mathématique, on calcule la dérivée au point représentant la solution actuelle, et on suit la direction de la dérivée la plus forte négativement.

La dérivée d’une fonction représente sa pente : si elle est positive, alors la courbe est croissante, sinon elle est décroissante. De plus, plus la dérivée est importante et plus la pente est forte.

Sur le schéma suivant, les différentes solutions obtenues itérativement sont indiquées : on part de la solution la plus haute, et on va aller dans le sens du gradient, jusqu’à atteindre le minimum.

images/05DP07.png

Intuitivement, c’est l’algorithme utilisé par un randonneur en forêt : si celui-ci cherche à atteindre le sommet d’une montagne, mais qu’il ne peut savoir où celui-ci se trouve, alors il regarde autour de lui dans quelle direction le chemin monte le plus et le suit. À force de monter, il va forcément se retrouver en haut du massif sur lequel il est. La démarche est la même s’il cherche à atteindre la vallée ...