6.8 Variantes

Se han propuesto varias variantes al algoritmo de recocido simulado. Una de las más conocidos en threshold accepting propuesta independientemente por Dueck y Scheuer (1990) y por Moscato y Fontanari (1990).

Threshold accepting o aceptación por umbral, propone aceptar un movimiento siempre y cuando rebase un cierto umbral ($Thres_k$) determinístico y decreciente con respecto a la iteración $k$.

$$P(\mbox{ aceptaci\'{o}n }) = \left \{ \begin{array}{ll} 1 & \... ... f < Thres_k \\ 0 & \mbox{de otra forma} \end{array} \right .$$

Aunque mucho más rápido, se pierden las propiedades de convergencia hacia el mínimo global.

Una variante de esto es cambiar el valor del umbral al hacer la búsqueda. Si se dejan de aceptar soluciones en el esquema de vecindad, entonces se aumenta el umbral, en caso contrario se reduce, buscando escapar de mínimos locales (dwindling expectation).

En general, en todos los algoritmos que hemos visto es donde se tiene un criterio de aceptación basado en la mejora sobre la función objetivo, se puede reemplazar por un criterio basado en recocido simulado, que permita aceptar peores soluciones al principio de la búsqueda y gradualmente quedarse solo con mejoras.

Algunos consejos de implementación incluyen:

• En lugar de calcular la diferencia de funciones hacer una aproximación a esa diferencia.
• Seleccionar vecinos en forma inteligente (no aleatoria).
• Usar otra distribución de probabilidad (e.g., decaimiento exponencial).
• Utilizar un esquema de enfriamiento adecuado.
• Pensar ciudadosamente en el esquema de vecindad.