Siguiente: FANS como heurística de Anterior: Ejemplo 2: Hill Climbing Arriba: Sobre la Utilidad de

Ejemplo 3: Recocido Simulado

En el método de Recocido Simulado, la aceptación de soluciones esta gobernada por un parámetro denominado ``Temperatura''. Las soluciones que mejoran el costo actual siempre son aceptadas. Aquellas que lo empeoran también pueden ser aceptadas con cierta probabilidad, que será alta al inicio de la ejecución. A medida que la búsqueda progresa, la temperatura disminuye, decrementando entonces la probabilidad de aceptación de soluciones peores. Hacia el final de la ejecución, solo las soluciones mejores son aceptadas.

Para reflejar este comportamiento mediante la valoración difusa, se puede utilizar la siguiente definición de ``Aceptabilidad'':

$\mu(\hat s, s) = \begin{cases} 0& \text{si $f(\hat s) > \beta$}\\ \frac{\be... ...s) \leq f(\hat s) \leq \beta$}\\ 1& \text{si $f(\hat s) < f(s)$} \end{cases}$

donde $f$ es la función objetivo, $s$ es la solución actual y $\hat s$ es una solución del vecindario operativo.

El valor $\beta$ representa el límite para lo que se considera aceptable. Este valor es clave ya que en última instancia determina que soluciones pertenecen o no al vecindario semántico. Si se define $\beta$ como una función $h(s,\hat s,t)$ donde $t$ es un parámetro que represente por ejemplo el número actual de iteraciones, el límite de deterioro aceptable puede ser reducido a medida que la búsqueda progresa. Hacia el final de la ejecución, solo aquellas soluciones mejores que la actual serán tenidas en cuenta. Un ejemplo para la función $h$ es:

$$h=f(s)*(1+\frac{1}{1+e^{(f(s)-f(\hat s))/t}})$$ (3)

donde el segundo término de la suma representa la distribución de probabilidad de Boltzmann.

En términos más generales, $\beta$ representan el umbral de aceptabilidad y por lo tanto, su variación está reflejando una clase de algoritmos más amplia, los algoritmos de umbral.