| Contenidos |
1.- |
Descripción. |
| 2.- |
Estructuras
de entorno. |
| 3.- |
Variantes. |
|
|
Búsqueda
Reducida por Entornos Variables. |
|
|
Búsqueda por
Entornos Variables con Descomposición. |
|
|
Búsqueda Sesgada
por Entornos Variables. |
| 4.- |
Aplicaciones. |
|
|
| Una de las alternativas para
subsanar el inconveniente que supone quedar atrapado en un óptimo local no global
consiste en modificar de forma sistemática la estructura de entorno empleada. Tras
presentar esta alternativa, se describe en detalle el procedimiento Búsqueda por
Entornos Variables. Además, se estudia la influencia que tienen las estructuras de
entorno en el comportamiento del procedimiento. Asimismo, se enumeran algunas de las
variantes del método propuestas en la literatura. Estas permiten abordar problemas de
mayor tamaño o con estructuras topológicas particulares. Por último, se detallan
algunas aplicaciones de la técnica. |
|
|
| Objetivos del tema |
| 1.- |
Conocer la técnica
Búsqueda por Entorno Variable |
| 2.- |
Estudiar la
influencia que tiene sobre el procedimiento la estructura de entorno empleada. |
| 3.- |
Ser capaz de
proponer Búsquedas por Entornos Variables para un problema arbitrario. |
| 4.- |
Valorar las
ventajas que poseen las variantes del método para abordar problemas de mayor tamañoo o
con estructuras topológicas determinadas. |
| 5.- |
Conocer algunas de
las aplicaciones de este método. |
|
|
| Material recomendado |
|
|
1.- |
Variable
Neighborhood Search. Nenad Mladenovic. Computers and Operations Research Vol. 24 N.
11 pp. 1097-1100 (1997) |
|
Primer trabajo
publicado en una revista científica dedicado a la Búsqueda con Entornos Variables. La
técnica propuesta consiste en cambiar de forma sistemática la estructura de entorno
empleada en una búsqueda local. La efectividad del método se ilustra por medio de las
mejoras que introduce en el algoritmo GENIUS para el problema del Viajante de Comercio. |
2.- |
Variable
Neighborhood Search: Principles and Applications. Pierre Hansen, Nenad Mladenovic.
Tutorials and Research Reviews. 16th European Conference on Operational Research (1998) |
|
Tutorial dedicado a
la Búsqueda por Entornos Variables. Se presenta el esquema básico que puede
implementarse fácilmente con cualquier procedimiento de búsqueda local para el problema
considerado. Asimismo, se describen algunas variantes: Búsqueda por Entornos Variables
con Descomposición, en la que, tras fijar el valor de algunas variables, se resuelve el
problema construido de menor dimensión por medio de otra Búsqueda por Entornos
Variables; y Búsqueda Sesgada por Entornos Variables, en la que se induce la búsqueda en
regiones alejadas de la solución actual modificando la función objetivo para que tenga
en cuenta la distancia entre soluciones. El trabajo recoge también algunas aplicaciones
éxitosas del métido y finaliza describiendo algunos problemas sobre los que actualmente
se trabaja. |
3.- |
Variable
Neighborhood Decomposition Search. Pierre Hansen, Nenad Mladenovic, Dionisio Pérez
Brito. Les Cahiers du GERAD, G-98-53 (1998) |
|
Se presenta la
Búsqueda por Entornos Variables con Descomposición. Tal y como se apuntó anteriormente,
el método fija el valor de algunas variables y resuelve, empleando una Búsqueda por
Entornos Variables, el problema de menor dimensión que surge. Esta variante permite a los
autores resolver problemas de mayor tamaño. La bondad del método se evalúa sobre
problemas de localización de la p-mediana. |
|
|
|
|