Si hay una metaheurística de ascender montañas tiene que haber otra de bajarlas. El descenso del gradiente se basa en usar el gradiente de guía para encontrar el mínimo de una función. El gradiente indica la pendiente máxima en un punto y hacia donde tenemos que dirigirnos para ascender (a favor del gradiente) o descender (en contra del gradiente). Sabiendo eso solo hay que moverse en la dirección indicada por el gradiente. ¿Cuanto? Ahí está el problema. Si el paso es muy grande podrías pasarte el mínimo y si es muy corto puedes acabar dando un gran número de pasos. Cómo lo de dar un gran número de pasos solo es un problema cuando lo haces con papel y lápiz y los ordenadores no se cansan de caminar (siendo cada paso una iteración del algoritmo) es preferible el segundo caso. Cada vez que se llega a un nuevo punto se calcula el gradiente en ese punto y se avanza en esa nueva dirección.

Supongamos que aún con nuestras precauciones de dar pasitos pequeños nos pasamos del mínimo. ¿Cómo podemos saberlo?. En la imagen de debajo se puede ver un ejemplo. Primero empezamos a «rebotar» de un lado a otro de la función, mientras el valor decrezca vamos bien. El problema surge si el valor aumenta (en la imagen el paso del punto f al g) . En ese caso hemos de volver al punto anterior, reducir el tamaño del paso y seguir probando hasta que se obtenga un valor fitness menor.

Lo ideal sería llegar a un punto donde la pendiente sea 0 (eso indica que es un máximo o un mínimo). Pero en la practica no siempre es posible y al final hemos de depender de las condiciones habituales, llegar a una solución lo suficientemente próxima a la ideal, alcanzar cierto numero de iteraciones o llegar a un tamaño de paso tan pequeño que no merezca la pena continuar.

Ya hemos visto como calcular de forma numérica la derivada y el gradiente. Ahora hemos de aplicar ese conocimiento para calcular el gradiente de la función fitness. Como el descenso del gradiente esta pensado para minimizar, hemos de elegir una función fitness que a menor valor mejor resultado.

Cada nueva coordenada seria la antigua coordenada menos el valor de la derivada de la funcion para esa coordenada multiplicado por el tamaño del paso Kstep.

cordX = cordX – (Kstep * dF/dx)

O lo que es lo mismo en código:

var grad = diff.grad(cords, this.model.calculateFitness);
for(var i = 0; i < this.parameters.dimensions; ++i){
  cords[i] -= this.parameters.step*grad[i];
}

Si el nuevo valor de fitness es menor adoptamos esas coordenadas como nueva solución, si es mayor reducimos el tamaño del paso y volvemos a probar:

if(newFitness < this.fitness){
this.cords = newCords;
this.fitness = newFitness;
} else {
this.parameters.step *= this.parameters.reduceStep;
}

El código completo puede verse aqui.