En las últimas décadas se produjo un flujo de información importante desde áreas clásicas, como la Investigación Operativa o la Teoría de Control, hacia el área de los Conjuntos y Sistemas Difusos y que permitió obtener resultados verdaderamente fructíferos. Hoy en día, términos como ``Control Difuso'', ``Programación Matemática Difusa'', ``Sistemas basados en reglas difusas'', etc, resultan familiares a cualquier investigador. Para ver ejemplos de esta interacción, el lector interesado puede referirse a [18,13] y también a la recopilación bibliográfica de Cordón et al. [10], donde se presenta una buena muestra de la combinación de conjuntos y lógica difusa con algoritmos genéticos. Además en [28] se describen aplicaciones exitosas de heurísticas para optimización basadas en conjuntos difusos.
Siguiendo en esta dirección, mostraremos como un método clásico de optimización combinatoria se puede combinar con elementos básicos del área de los conjuntos y sistemas difusos para dar lugar a una herramienta de optimización adaptativa y robusta que permita abordar la resolución de problemas complejos de forma satisfactoria. Para ello, se plantea como objetivo la presentación de las ideas esenciales de un método de búsqueda por entornos, adaptativo y difuso, denominado FANS por las iniciales de su nombre en inglés: Fuzzy Adaptive Neighborhood Search. FANS, incorpora como elementos destacables la utilización de una valoración difusa o subjetiva para evaluar las soluciones, y el uso de varios operadores para explorar el espacio de búsqueda.
La motivación para la utilización de la valoración subjetiva, parte de la
idea que en ocasiones se suele hablar de soluciones Diferentes, Similares,
Razonables, etc, siendo estas características de naturaleza subjetiva o
vaga. Por lo general, las reglas de transición entre soluciones en los
métodos clásicos de búsqueda local son de naturaleza crisp, es decir, consideran a una
solución como ``mejor'' o no, ``diferente'' o no, etc. En el contexto de
FANS, las soluciones son vistas como elementos de un conjunto
difuso1 cuya función de pertenencia es
dicha valoración difusa, la cual representa cierta propiedad denominada
genéricamente . De esta forma, las soluciones tienen asignado un grado de
pertenencia a dicho conjunto (por ejemplo, el conjunto de soluciones
) lo cual permite definir subconjuntos de soluciones del tipo
muy
, algo
, no
, etc. A través de esta valoración difusa,
el comportamiento de FANS puede ser modificado de forma tal que se logra
reflejar el comportamiento cualitativo de otros métodos de búsqueda local.
De esta manera, veremos que FANS es en realidad un ``framework'' o molde de
métodos de búsqueda local.
La utilización de varios operadores en el proceso de búsqueda es un área
relativamente poco explorada, pero con una justificación muy simple: que una
solución sea localmente óptima bajo cierto vecindario (inducido por un
operador), no implica que dicha condición de optimalidad se verifique en otro
vecindario2. Esta
idea de variación del vecindario a explorar, también se utiliza en una variante muy
poco investigada de variable neighborhood search ()[15] denominada
variable neighborhood descent [16].
Siendo además un método de búsqueda por entornos, resulta simple de comprender, implementar y mejorar, y por lo tanto resulta atractivo como herramienta para realizar las primeras aproximaciones para la resolución de un problema dado.
En este artículo se detallan las tareas realizadas para alcanzar el objetivo descrito, utilizando la siguiente estructura: en la Sección 2 se describen los elementos básicos de FANS y se presenta el esquema general del algoritmo. Posteriormente en la Sección 3 se describe la motivación y utilidad de la valoración difusa y se muestra como este componente puede ser utilizado para variar el comportamiento del algoritmo, dando lugar a un ``framework'' de métodos de búsqueda por entornos. La Sección 4 esta dedicada a verificar la utilidad del segundo elemento novedoso de FANS: el uso de varios operadores en el proceso de búsqueda. Luego, en la Sección 5, se describen la aplicación y resultados obtenidos mediante FANS sobre cuatro problemas de optimización.