Siguiente: Presentación de FANS
Anterior: FANS: una Heurística basada
Arriba: FANS: una Heurística basada
El diseño, la construcción y la búsqueda de algoritmos que permitan
resolver problemas que surgen en la vida real, son objetivos esenciales de las
Ciencias de la Computación. A pesar de la alta complejidad que suelen
presentar dichos problemas, deben ser resueltos pues son de notable
importancia. Ambos aspectos, dificultad e importancia, han potenciado el
desarrollo de técnicas heurísticas que, aunque pueden llevar a la
obtención de soluciones sub-óptimas, son capaces de resolver el problema en
términos de ``satisfacción'' del usuario. En general, estos métodos
obtienen soluciones ``buenas'' en términos de
cierta función de costo, pero también es posible que, además, el usuario
considere otras características que en ocasiones pueden ser de naturaleza
subjetiva y por lo tanto, modelizables mediante conjuntos difusos.
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.
David Pelta 2003-10-22