Hill Climbing

Tanto imaginarnos que el espacio de soluciones es un pasaje con colinas y depresiones que antes o después el nombre alguna metaheurística tenía que hacer referencia a subir colinas. Su desarrollo es sencillo. Situado en un punto, revisa todos sus vecinos o, si son demasiados, una muestra aleatoria de ellos. Tras ello se mueve al vecino cuyo valor es mayor que el actual, allí repite el proceso. El algoritmo continua hasta que no se pueda encontrar un vecino mejor o se haya realizado un número de iteraciones prefijado.

Como optimizador local funciona bastante bien por lo que muchas veces se usa para “mejorar” el resultado de un optimizador global. Existe una versión para optimización global que consiste en lanzarlo varias veces desde puntos de origen distintos, a esta versión se le denomina “con reinicio” ya que una vez que deja de mejorar o se alcanza un número determinado de iteraciones se reinicia el algoritmo desde un nuevo origen.

Su funcionamiento es muy parecido a de random search, con la diferencia de que consulta todos (o al menos una muestra) sus vecinos para seleccionar el mejor. Hay otra forma de implementarlo. En lugar de visitar N vecinos se van comprobando vecinos de uno en uno hasta encontrar uno que mejore el resultado actual en por lo menos un valor umbral fijado, todos cuya mejora sea inferior a ese umbral son descartados. Si ese umbral es muy pequeño el comportamiento es similar al de random search.

Para que el código no sea muy parecido al de random search vamos a incluir una mejora. En lugar de mirar solo el fitness de los vecinos para compararlos vamos a usar la pendiente que sería igual a la variación del fitness dividido por la distancia a entre las coordenadas de la solución actual y el vecino que se compara. Es decir vamos a elegir el camino que más rápido sube. Por lo tanto el nuevo valor que usaremos para comparar vecinos es:

fdist(Ni) = f(Ni) – f(S) / dist(Ni, S)

Siendo Ni el vecino que se evalua y S el punto donde se encuentra ahora la búsqueda. Ojo y no confundir está pendiente calculada grosso modo con la pendiente de una función en un punto.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
var newVarition = (auxFitness-this.fitness)/this.distance(newCords, this.cords); //dif_fitness/distance

También se incluye un algoritmo para la variación del tamaño del paso de búsqueda en caso de que no se encuentre una solución mejor.

step = step*increaseStep

Para evitar que el tamaños del paso se dispare a valores absurdos se permite fijar un limite de veces que se multiplicara por el incremento. Cada vez que se encuentre una buena solución se volverá al tamaño de paso original.

if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
  this.step = this.parameters.step;
  this.numberIncreaseSteps = 0;
} else {
  this.numberIncreaseSteps++;
  if(this.numberIncreaseSteps < this.parameters.maxTimesIncreaseStep){
    for(var i = 0; i < this.parameters.dimensions; ++i){
      this.step[i] *= this.parameters.increaseStep[i];
    }
  }
}

 

El código se puede encontrar en github.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.