6.1 Introducción

El resolver un problema combinatorio se resume a encontrar la ``mejor'' / ``óptima'' solución dentro de un conjunto finito o contablemente infinito de alternativas.

Asumimos que la calidad de la solución es cuantificable y comparable con cualquier otra solución y asumimos que las soluciones son finitas.

Muchos problemas combinatorios son NP, por lo que normalmente se buscan soluciones ``rápidas'' sub-óptimas.

Una instancia de un problema combinatorio se puede formalizar por un par $(S,f)$ donde el espacio solución $S$ denota el conjunto finito de todas las posibles soluciones y $f$ denota la función de costo:

$$f : S \rightarrow \cal R$$

Lo que se trata (en minimización) es encontrar una solución $i_{opt} \in S$ tal que $f(i_{opt}) \leq f(i)$ para toda $i \in S$.

Los algoritmos de búsqueda local constituyen una clase de algoritmos aproximados basados en la exploración de vecinos. Estos presuponen que existe una función de costo y una estructura de vecindad.

La estructura de vecindad define para cada $i \in S$ un conjunto $S_i \subset S$ que son cercanos a $i$ en algún sentido. Se asume que $j \in S_i \Leftrightarrow i \in S_j$.

El mecanismo de generación se define como la forma de seleccionar una solución $j$ en la vecindad $S_i$ de la solución $i$.

Los algoritmos de búsqueda local normalmente iteran partiendo de una solución aleatoria, generando un vecino que sea mejor hasta que se llegue a una solución que no tiene mejores vecinos.

Ya hemos visto varias alternativas que se han propuesto para tratar de evitar quedarse en mínimos locales:

• Ejecutar el algoritmo de búsqueda local a partir de muchos puntos iniciales.
• Introducir restricciones adicionales a la función objetivo.
• Introducir una estructura de vecinos más compleja para buscar en regiones más grandes del espacio.
• Alterar soluciones buscando diversidad.
• Introducir mecanismos de memoria para evitar regresar a estados visitados.

Recocido simulado se basa en aceptar en forma limitada transiciones que no mejoren la función de costo usando un mecanismo no determinista.

Recocido simulado se llama así por su analogía con el proceso físico de recocido de sólidos, en el cual:

• Se incrementa la temperatura de un sólido cristalino a una temperatura alta.
• Se decrementa la temperatura muy lentamente hasta alcanzar un estado base de mínima energía, con una estructura cristalina lo más regular posible.

Lo que hace recocido simulado es establecer una conexión entre este tipo de proceso termodinámico y la búsqueda de un mínimo global.

Otro proceso relacionado es el de quenching en el cual la temperatura se baja inmediatamente.

El núcleo de recocido simulado lo consituye lo que se conoce como el algoritmo de Metropolis.