Búsquedas Estocásticas: Templado Simulado
Cuando los espacios de búsqueda son extremadamente grandes o tienen estructuras relativamente complejas, los procedimientos de búsqueda deterministas suelen obtener muy malos resultados. La Búsqueda Estocástica introduce factores de aleatoriedad en esos procesos de forma que, bien usada, puede reducir considerablemente la complejidad del problema. Por supuesto, en este proceso se pierde algo, y es que se sustituye la optimalidad por la tratabilidad en tiempo (es decir, el problema se puede resolver en un tiempo razonable, pero ya no podemos estar 100% seguros de que vayamos a encontrar la solución siempre).
Hay dos algoritmos de búsqueda estocásticos triviales que podemos identificar claramente:
- Búsqueda Aleatoria: En cada paso, se selecciona al azar un elemento del espacio de búsqueda y comprobamos si tiene las propiedades deseadas.
- Camino Aleatorio sin información: En cada paso, se selecciona al azar un vecino del estado actual y nos desplazamos a él.
Obviamente, estas dos modificaciones para introducir la aleatoriedad tienen pocas opciones de ser eficientes en espacios relativamente grandes, pero suponen un punto de partida sobre el que construir otros algoritmos estocásticos que arrojan buenos resultados. El más famoso de ellos es el algoritmo del Templado Simulado (o Enfriamiento Simulado), que veremos a continuación:
Templado Simulado
Hay muchas veces en los que los algoritmos de búsqueda por ascenso se quedan atascados enseguida en óptimos no demasiado buenos. Para estos casos se han diseñado algoritmos que a veces pueden dar soluciones relativamente buenas, como el que veremos en esta sección: templado simulado (simulated annealing).
Este algoritmo está inspirado en un fenómeno físico que se observa en el templado de metales y en la cristalización de disoluciones:
Todo conjunto de átomos o moléculas tiene un estado de energía que depende de cierta función de la temperatura del sistema. A medida que lo vamos enfriando, el sistema va perdiendo energía hasta que se estabiliza. El fenómeno físico que se observa es que, dependiendo de cómo se realiza el enfriamiento, el estado de energía final es muy diferente. Por ejemplo, si una barra de metal se enfría demasiado rápido la estructura cristalina a la que se llega al final está poco cohesionada (un número bajo de enlaces entre átomos) y ésta se rompe con facilidad. Si el enfriamiento se realiza más lentamente, el resultado final es totalmente diferente, el número de enlaces entre los átomos es mayor, y se obtiene una barra mucho más difícil de romper. Durante este enfriamiento controlado se observa que la energía del conjunto de átomos no disminuye de manera constante, sino que a veces la energía total puede ser mayor que en un momento inmediatamente anterior. Esta circunstancia hace que el estado de energía final que se alcanza sea mejor que cuando el enfriamiento se hace rápidamente.
A partir de este fenómeno físico se puede obtener un algoritmo que permite, en ciertos problemas, obtener soluciones mejores que las proporcionadas por los algoritmos vistos hasta ahora. En este algoritmo el nodo siguiente a explorar no será siempre el mejor vecino, sino que se elige aleatoriamente (en función de los valores de unos parámetros) de entre todos los vecinos (los buenos y los malos). Una ventaja de este algoritmo es que no hay por qué generar todos los sucesores de un nodo, basta elegir un sucesor al azar y decidir si continuamos por él o no.
El algoritmo de templado simulado intenta transportar la analogía física al problema que se quiere solucionar. En primer lugar, se denomina función de energía a la función heurística que mide la calidad de una solución. Tendremos un parámetro de control que denominaremos temperatura, que permitirá controlar el funcionamiento del algoritmo. También se tendrá una función que dependerá de la temperatura y de la diferencia de calidad entre el nodo actual y un sucesor. Esta función dirigirá la elección de los sucesores de la forma siguiente:
- Cuanta mayor sea la temperatura, más probabilidad habrá de que al generar como sucesor un estado peor éste sea elegido.
- La elección de un estado peor dependerá de su diferencia de calidad con el estado actual, cuanta más diferencia, menos probabilidad de elegirlo.
El último elemento es la estrategia de enfriamiento. Por ejemplo, el algoritmo podría realizar un número total de iteraciones prefijado y cada cierto número de ellas el valor de la temperatura disminuye en cierta cantidad, partiendo desde una temperatura inicial y llegando a cero (o a un valor mínimo) en la última iteración. La elección de estos dos parámetros (número total de iteraciones y número de iteraciones entre cada bajada de temperatura) determina el comportamiento completo del algoritmo, y puede modificar su eficiencia de forma dramática. Aunque hay algunos resultados teóricos acerca de la influencia de estos parámetros, en general hay que decidir experimentalmente cuál es la temperatura inicial más adecuada y también la forma más adecuada de hacer que vaya disminuyendo.
Algoritmo: Templado Simulado
T ← T0
Mientras T > 0 hacer:
// Paseo aleatorio por el espacio de soluciones
Para un numero prefijado de iteraciones hacer:
s_nuevo ← Genera_vecino_al_azar(s_actual)
∆E ← E(s_actual) − E(s_nuevo)
Si ∆E > 0 entonces
s_actual ← s_nuevo
si no
con probabilidad exp(∆E/T): s_actual ← s_nuevo
Fin Si
Fin Para
Disminuir T
Fin Mientras
Como en la analogía física, si el número de pasos es muy pequeño, la temperatura bajará muy rápidamente, y el camino explorado será relativamente aleatorio. Si el número de pasos es más grande, la bajada de temperatura será más suave y la búsqueda será mejor. Observa que el algoritmo facilita la disminución de la energía, $E$, ya que $\Delta E>0$ es equivalente a que $E(s_{actual}) > E(s_{nuevo})$, y en ese caso $s_{nuevo}$ se convierte en el estado actual. Cuando $\Delta E < 0$, se tiene que $e^{\Delta E /T}<1$ y, de hecho:
$$\lim_{T\to 0} e^{\Delta E /T} = 0$$
por lo que el hecho de admitir nuevos estados que empeoran la búsqueda se hace cada vez más improbable a medida que avanza el algoritmo. Además, los estados que empeoran mucho la energía $E$ (es decir, aquellos que hacen que $\Delta E$ sea más negativo) se hacen menos probables que los que la empeoran menos.
Es importante observar que la búsqueda se ha transformado en un problema de optimización (en este caso, de minimización), porque realmente pasamos de buscar un estado con ciertas propiedades generales a buscar un estado que tiene valor mínimo respecto a la función de energía, $E$, considerada. Esta función tiene muchas similitudes con las funciones heurísticas de algoritmos como $A^*$, ya que de alguna forma mide lo buena, o cerca de la solución ideal, que está el estado actual, pero tiene una ventaja computacional, y es que no imponemos ninguna propiedad adicional (en $A^*$, la función heurística debía ser admisible para asegurar la convergencia a la solución, por ejemplo). En cualquier caso, a $E$ se le supone un comportamiento bastante básico:
- $E(s)\geq 0$, para cualquier estado, $s$, de nuestro espacio.
- $E(s)=0$ solo en el caso en que $s$ sea una solución adecuada del problema.
- $E(s_1)<E(s_2)$, si $s_1$ es mejor solución que $s_2$.
Este algoritmo es especialmente bueno para problemas con un espacio de búsqueda grande en los que el óptimo está rodeado de muchos óptimos locales, ya que le es más fácil escapar de ellos. Se puede utilizar también para problemas en los que encontrar una heurística discriminante es difícil (una elección aleatoria es tan buena como otra cualquiera), ya que en estos casos el algoritmo de ascenso de colinas no tiene mucha información con la que trabajar y se queda atascado enseguida, mientras que el templado simulado puede explorar más espacio de soluciones y tiene mayor probabilidad de encontrar una solución buena.
El mayor problema de este algoritmo es determinar los valores de los parámetros, y requiere una importante labor de experimentación que depende de cada problema. Los valores óptimos de estos parámetros varían con el dominio e incluso con el tamaño de la instancia concreta del problema.
|
|
|
