Siguiente: Sobre la Utilidad de Anterior: Manejo de óptimos locales Arriba: Presentación de FANS

El Algoritmo

El esquema de FANS se muestra en la Fig. 1. Cada iteración comienza con una llamada al administrador de vecindario $\mathcal{NS}$ con los siguientes parámetros: la solución actual $S_{cur}$, la valoración difusa $\mu()$ y el operador de modificación $\mathcal{O}$. Como resultado de la ejecución de $\mathcal{NS}$ pueden ocurrir 2 cosas: se pudo encontrar una solución vecina aceptable $S_{new}$ (en términos de $\mu()$), o no se pudo.

En el primer caso, $S_{new}$ pasa a ser la solución actual y los parámetros de $\mu()$ son adaptados. Por ejemplo, si $\mu()$ representa la similaridad respecto a la solución actual, entonces la valoración difusa debe ser adaptada para reflejar este cambio en la solución de referencia.

Si $\mathcal{NS}$ no pudo retornar una solución aceptable, es decir, en el vecindario inducido por el operador no se pudo encontrar una solución suficientemente buena, entonces se aplica el nuevo mecanismo de escape: se ejecuta el administrador de operación $OS$ el cual retornara una versión modificada del operador $\mathcal{O}$. La próxima vez que $\mathcal{NS}$ se ejecute, dispondrá de un operador modificado para buscar soluciones, y por lo tanto es posible que el resultado sea diferente.

La condición $HayEstancamiento?()$ será verdadera cuando (por ejemplo) se hayan realizado $Tope$ llamadas a $OS$ sin haber obtenido mejoras en la solución actual. Es decir, se probaron varios operadores y no se obtuvieron mejoras. En este caso, se ejecutará el procedimiento $Escape()$, se evaluará el costo de la nueva solución y se adaptará la valoración difusa $\mu()$. Posteriormente, se reiniciará la búsqueda.

Debe quedar claro que lo que varía en cada iteración son los parámetros utilizados en las llamadas a $\mathcal{NS}$. El algoritmo comienza con $\mathcal{NS}$ ( $s_0,\mathcal{O}^{t_0},\mu_0$). Si $\mathcal{NS}$ puede retornar una solución aceptable, entonces en la siguiente iteración la llamada será $\mathcal{NS}$ ( $s_1,\mathcal{O}^{t_0},\mu_1$); es decir cambia la solución actual y por lo tanto se modifica la valoración difusa. Si en cierta iteración $l$, $\mathcal{NS}$ no puede retornar una solución aceptable, entonces se ejecutará el administrador de operación el cual devolverá una versión modificada del operador. La iteración siguiente, $\mathcal{NS}$ será llamado con $\mathcal{NS}$ ( $s_l,\mathcal{O}^{t_1},\mu_l$).

Durante la ejecución del algoritmo pueden ocurrir dos situaciones problemáticas: primero, se realizaron varias llamadas $\mathcal{NS}(s_j,\mathcal{O}^{t_i},\mu_j)$ con $i \in [1,2,\ldots,k]$, lo cual significa que se probaron $k$ formas diferentes de obtener una solución aceptable y ninguna tuvo éxito; o segundo, la búsqueda se está moviendo entre soluciones aceptables pero en las ultimas $m$ llamadas no se consiguió mejorar la mejor solución de todas las visitadas hasta el momento.

Cuando cualquiera de las dos situaciones ocurra, se ejecutará el procedimiento $Escape()$ para el cual se plantean las dos posibilidades siguientes: $\mathcal{NS}$ ( $\hat s_0,\mathcal{O}^{t_j},\hat\mu_{0}$) o $\mathcal{NS}$ ( $\hat s_0,\mathcal{O}^{t_0},\hat \mu_{0}$), donde $\hat s_0$ es una nueva solucion inicial (generada aleatoriamente, por ejemplo), y $\hat \mu_{0}$ es la valoración difusa obtenida en función de $\hat s_0$. Respecto al operador, se puede mantener con los mismos parámetros ( $\mathcal{O}^{t_j}$) o también se lo puede ``reinicializar'' ( $\mathcal{O}^{t_0}$).

El algoritmo finaliza cuando el número de evaluaciones de la función de costo alcanza cierto límite o cuando se realizó un número predeterminado de evaluaciones.