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.


David Pelta 2003-10-22