Elegir un buen vecino

Gran parte de las metaheurísticas y heurísticas tienen el paso “Elegir un nuevo vecino/solución” pero no entran mucho en detalle de cómo elegirlo. La papeleta generalmente se resuelve eligiendo el vecino con el mejor fitness o uno aleatorio. Pero no son las únicas estrategias y dependiendo el tipo de espacio de búsqueda tampoco son las mejores. Vamos a ver algunas alternativas.

¿Qué es un vecino? La respuesta depende del espacio de búsqueda y el tipo de problema y la función usada para “generar” a los vecinos. La forma más generica de definirlo que se me ocurre seria: “Son vecinos de una solución S todas aquellas soluciones que se pueden alcanzar desde S”. En algunos casos queda claro quienes son los vecinos, por ejemplo en un grafo. En otros la definición de que es un vecino se va a tener que ajustar como un parámetro más del algoritmo. Por ejemplo cuando definimos el vecino de una solución como todas aquellas soluciones que estén a una distancia igual o menor que d. En este caso d se convierte en un parámetro más a tener en cuenta.

Hay que distinguir entre dos tipos de vecindarios:

  • Poco poblados: cuando el número de vecinos es limitado y podemos calcular el fitness de todos. Suelen ser los vecindarios asociados a problemas combinacionales o a valores discretos. Eso no quiere decir que este tipo de problemas no puedan crecer tanto que se conviertan en el siguiente tipo de vecindario. Ojo al detalle de poder calcular el fitness, si la función que lo calcula es muy costosa puede resultar más rentable tratarlos como si fueran vecindarios muy poblados.
  • Muy poblados: cuando el número de vecinos es infinito o tan grande que es imposible (o su coste en tiempo es demasiado alto) recorrerlos todos. Generalmente corresponde a espacios de soluciones continuos.

Antes de empezar con estrategias  complicadas empecemos por la  y más simple y menos costosa que además funciona en ambos tipos de vecindarios. Elegir un vecino cualquiera al azar. El problema es que puede retrasar mucho la convergencia a un óptimo.

Las estrategias son distintas dependiendo del tipo de vecindario. Vamos a empezar por los vecindarios poco poblados. En este caso las estrategias más simple que se nos puede ocurrir es la de escoger el mejor: de todas las opciones buscamos la que tiene mejor fitness y la elegimos. El problema de asta estrategia es que dificulta la exploración. Pero  por otro lado reduce el tiempo que cuesta llegar al óptimo, aunque aumenta el riesgo que sea un óptimo local. Un pequeño cambio puede solucionarlo. Elegimos una al azar pero no todas tienen la misma probabilidad sino que la probabilidad de seleccionar una solución es proporcional a su fitness.

Para los vecindarios muy poblados podemos hacer un truco para seleccionar los vecinos como si fueran vecindarios poco poblados, elegimos n vecinos al azar y luego aplicamos la selección sobre esos n vecinos como si fueran los únicos del vecindario.

En el caso de espacios de soluciones continuas se suelen elegir como vecinos cualquier solución que esté a una distancia D o menor. Pero esta es la versión más simple, en lugar de elegir todos los vecinos a una distancia D con igual probabilidad podemos hacer que sea más probable seleccionar los que más cerca están o los más lejanos o los que estén a una distancia intermedia. Incluso fijar una distancia mínima. Jugando con estos valores podemos alterar el comportamiento del algoritmo (exploración/convergencia) sin modificar sus valores.

Otra forma de mejorar la selección de vecinos puede ser priorizar la dirección en la que antes ya has encontrado una buena solución esperando que sigamos mejorando en esa dirección. Por ejemplo supongamos que hemos ido del punto (5, 5) al (6, 8). Eso significa que hemos sumado el vector (1, 3). Lo primero que podríamos hacer es mirar el punto (7, 11) = (6, 8)+(1, 3). Es decir repetir el mismo paso y a partir de ahí mirar cerca de ese punto. El problema de hacerlo así es que acabamos repitiendo pasos iguales cuando realmente lo que nos interesa es solo la dirección. ¿Cómo extraerla?. Dividimos cada componente del vector por la distancia recorrida. El vector que hemos sumado ha sido (1,3). La distancia es la raíz cuadrada de la suma del cuadrado de cada elemento. SQRT(1^2+3^2) = 3.1622… Así que la dirección sería (1/3.1622, 3/1622) = (0.31, 0.93). Ya lo tenemos. Ahora podemos avanzar la distancia que queramos en esa dirección. Solo hemos de multiplicar la distancia por cada uno de los valores del vector dirección. Podemos avanzar en esta dirección hasta que deje de mejorar.

Pero estos cálculos pueden ser usados de otra manera. Si elegimos varios vecinos al azar y dividimos lo que mejora la solución entre la distancia del paso tendremos una manera de estimar en qué dirección las soluciones mejoran más rápido. Estamos calculando una aproximación del gradiante. En este caso podemos priorizar los que más rápido varíen.

Hay una versión de esta selección que se usaba originalmente para la metaheurística hill climbing que no requiere cálculos. Si tenemos una solución con múltiples coordenadas modificamos una a una hasta que deje de mejorar en esa coordenada. En el ejemplo anterior sería el caso de usar el vector dirección (1,0) hasta que deje de mejorar y luego usar (0,1). Tiene la desventaja de que puede quedarse atrapado cuando los mejores vecinos están en las diagonales.

Una última mejora es guardar un histórico de soluciones ya seleccionadas para evitar elegir una ya elegida o muy cercana (lo que sería el equivalente a andar en círculos). Según el coste en memoria de almacenarlas y en tiempo de compararlas puede ser mejor almacenar solo las últimas. Esta opción solo es válida cuando la selección del siguiente vecino es determinista, por ejemplo eligiendo el de mayor gradiante o cuando se inspeccionan todas las opciones y lo más probable es que se elija el mismo vecino la última vez que se “visitó” esa solución. Guardar información de los vecinos ya visitados no puede ahorrar “dar vueltas” y reducir el coste computacional.

Templado Simulado

El templado o cocido o temple o recocido simulado es una metaheurística inspirada en el templado (o cocido o temple…) de metales (en algunos sitios hablan de espadas samuráis para hacerlo parecer más interesante. Como si una metaheurística necesitara algo más para parecer interesante…mejor no respondáis). La idea es que durante el templado los átomos van colocándose en las posiciones de menor energía aunque a veces pueden moverse a una de mayor energía. Este caso depende de la temperatura a la que esté en el material y a mayor temperatura más probable es que ocurra. Tampoco todos los saltos son igual de probables, a mayor diferencia de energía también es menos probable que ocurra.

Sonará ridículo, pero uno de los problemas que he encontrado con este algoritmo es que se suelen usar términos químicos para describirlo lo cual resulta confuso para los pobres programadores que no estamos acostumbrados a ellos. Así que dejando de lado el modelo real en que se inspira, el algoritmo es similar a la búsqueda aleatoria con el añadido de que tiene cierta probabilidad de aceptar una solución cuyo valor sea peor que la actual. Es decir, que las soluciones peores que la actual no se descartan siempre, se deja al azar si se conserva la actual (la mayoría de las veces) o se remplaza por la nueva solución. Esto le permite escapar de óptimos locales explorando zonas que de otra forma no visitaría. Eso sí, para evitar ir saltando de un lado a otro a lo loco y lograr converger en un máximo la diferencia entre los valores de la función fitness no puede superar un límite que se reduce con cada iteración con lo que es menos probable que se elija una solución peor que la actual. La formula que se aplica es que una solución de fitness f’ peor que f se acepta siempre y cuando:

e ^ (f-f’/ Ti ) > rnd(0,1)

Podemos ver que se usa e ^ x para calcular la posibilidad de que se elija esa solución. Para ello calculamos la diferencia entre ambas soluciones y la dividimos entre la temperatura actual. Hay que tener en cuente que este caso solo sirve cuando busquemos el mínimo (f’ es peor si f’ > f) pero si buscamos el máximo debería de ser f’-f  ( f’ es peor si f’ < f). con esto debería de darnos siempre un resultado negativo ya que si f’ es mejor que f se elegiría directamente y no llegaríamos a este punto.

if(newFitness  Math.random()){
    this.cords = newCords;
    this.fitness = newFitness;
}

Si nos fijamos en la gráfica de la función e ^ x entre -5 y 0 vemos que su valor decrece según aumenta la diferencia entre ambos valores. También podemos ver, que al estar dividida por la temperatura, cuanto mayor sea la misma más “tolerante” es con la diferencia. Como según se itera el algoritmo la temperatura se reduce cada vez es menos probable elegir una solución peor que la actual. Según disminuye la temperatura y el comportamiento del algoritmo se asemeja más a una búsqueda aleatoria.

ex

Gráfica de e^x para x < 0

Función de enfriamiento

La función de enfriamiento es la operación que se ocupa de reducir el valor de la temperatura cada iteración. Es más importante de lo que parece ya que es la temperatura la que permite saltar a soluciones peores y explorar el espacio de soluciones. Las dos más habituales son:

Restar un valor que sea muy pequeño “casi cero”

Ti = To – k * i     =     Ti = Ti-1 – k

Tiene la ventaja de que se puede calcular muy rápidamente. El problema es que es demasiado lineal y no suele dar tan buen resultado.

Multiplicar por un valor menor que uno pero cercano a él. O sea que sea “casi 1”.

Ti = T0 * k ^ i    =   Ti = Ti-1 * k

Es rápida de calcular y da buen resultado. Variando el valor de k variamos “el comportamiento” alargando o acortando el rápido descenso inicial o lo “exploradora” que sea la metaheurística.

Algunas más complejas:

Ti = T0*k*i

Ti = (To/imax) * i

Ti = To/(1+k*ln(1+i))

La temperatura controla el umbral de aceptación de una variable. Si es alta es más fácil que una solución peor “pase el filtro”. Así que lo ideal sería poder adaptarla según lo necesite el algoritmo. Acelerar su descenso, retrasarlo e incluso invertirlo. Para que el algoritmo converja en una solución es necesario que la tendencia general de la temperatura sea descender pero puede sufrir momentos puntuales de aumento. En concreto lo ideal sería que la temperatura aumente cuando esté intentando “escapar” de un óptimo local. ¿Como sabemos cuándo es eso? Sencillo, ocurre cada vez que se elige una solución peor que la actual. Nos podemos imaginar que la solución

Siendo

fbest la solución seleccionada hasta ese momento

f el valor de fitness para la solución elegida

Ti la temperatura calculada para la iteración i por alguno de los métodos anteriores

T’ = (1+(f-fbest/f))*Ti

Como f solo puede ser igual o mayor (es peor) a fbest. La formula actúa compensando la disminución de la temperatura cuando  la solución empeora. De tal forma que combina ciclos de descenso con otros de ascenso aunque en teoría tendencia general es que la temperatura disminuya. ¡Ojo! Que es en teoría. Puesto que al subir la temperatura aumenta la probabilidad de que seleccione soluciones peores y cada vez que selecciona una soluciones peor aumenta la temperatura puede llegar realimentarse hasta que el aumento de temperatura se dispara.

Al final yo he optado por:

T’ = (1+(f-fbest/f))*Kinc + Ti

Al ser una suma se frena el aumento de temperatura y el parámetro Kinc permite controlar esta variación.

Aunque con los parámetros iniciales adecuados puede encontrar una correcta aproximación al óptimo global su desempeño en espacios de búsqueda muy grandes o con muchas dimensiones no suele ser muy bueno. También se usa como optimizador local.

Puedes encontrar el código aquí.

Random Search

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.