Siguiente: Presentación de FANS Anterior: FANS: una Heurística basada Arriba: FANS: una Heurística basada

Introducción

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 $ P$. De esta forma, las soluciones tienen asignado un grado de pertenencia a dicho conjunto (por ejemplo, el conjunto de soluciones $ P=aceptables$) lo cual permite definir subconjuntos de soluciones del tipo muy $ P$, algo $ P$, no $ P$, 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 ($ VNS$)[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