Esta metaheurística tiene la ventaja de que es sencilla de entender y de aplicar. En su forma más simple consiste en partir de un punto aleatorio del espacio de soluciones, elegir aleatoriamente una solución cercana, si es peor se elige otra, si es mejor movernos a ella y volver a elegir otra solución desde ahí.

La implementación es fácil y su ejecución es rápida o al menos hasta donde lo permita el cálculo del fitness de la solución elegida.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
}

Por desgracia su desempeño solo es bueno en espacios de búsqueda sencillos. Es fácil que se quede atrapada en un óptimo local. Todo depende del tamaño del área en que se busca la nueva solución. Un tamaño muy grande hace que le cueste mucho más converger, uno muy pequeño causa que se quede atrapada en máximos locales. Y no hay una buena solución para todos los problemas, los valores dependen del espacio de búsqueda. Ahora es cuando estaréis pensando: «¿Y si hacemos el tamaño del área de selección variable?». Mala suerte, llegáis unas cuantas décadas tarde. Hay varios algoritmos que usan esta táctica.

Primero un detalle, el «Tamaño del área de selección» se le llama también «tamaño del paso» ya que sería el símil a lo que puede avanzar en cada iteración por el espacio de búsqueda (generalmente hay tendencia a representar el espacio de búsqueda como montañas y a nuestro algoritmo caminando por ahí).

Volviendo a las búsquedas aleatorias con «paso de tamaño variable». Hay varias estrategias, unas intentan calcular el tamaño del paso analizando la función a optimizar, otros van ajustando el valor de forma dinámica. La forma más sencilla de hacerlo es simplemente ir aumentando el tamaño del paso cada vez que compruebas un vecino y es peor que la solución actual. Una vez encuentras una solución mejor vuelves al tamaño de paso inicial. Con cuidado de no superar un tamaño máximo de paso para evitarnos problemas como superar el espacio de búsqueda.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
  this.step = this.parameters.step;
} else { //variamos tamaño del paso
  this.step.map(function(step){return step*this.parameters.increaseStep}, this);
}

Aunque se puede usar como optimizador global suele tener mejor desempeño como optimizador local que parte de los resultados obtenidos por un optimizador global.

Hay algunas modificaciones interesantes que mejoran algunos aspectos.

Por ejemplo, al ser el punto de origen aleatorio solo explora una pequeña parte del espacio de búsqueda. La forma más fácil de resolverlo es ejecutarlo varias veces con puntos de inicio diferentes y quedarse con la mejor. Esto permite su uso como optimizador global. Además lo hace fácilmente paralelizable. A este algoritmo se le denomina «con reinicio».

El código completo esta en este repositorio de github.