next up previous
Next: 4.4 Búsqueda Local Iterativa Up: 4. Búqueda Local y Previous: 4.2.3.2 Búsqueda local guiada


4.3 Variable Neighbourhood Search

La idea básica es ir cambiando en forma sistemática la vecindad al momento de realizar la búsqueda.

Sea $N_k$ un conjunto finito de vecindades predefinidas y $N_k(x)$ el conjunto de soluciones en la $k$-ésima vecindad de $x$.

La mayoría de los algoritmos de búsqueda local usan una sola vecindad.

Las vecindades a veces se pueden inducir a partir de una o más métricas que se tengan en el espacio de solución.

VNS se basa en tres hechos simples:

  1. Un mínimo local con respecto a una estructura de vecindad no lo es necesariamente con respecto a otra.
  2. Un mínimo global es un mínimo local con respecto a todas las posibles estructuras de vecindades.
  3. En muchos problemas el mínimo local con respecto a una o varias estructuras de vecindad están relativamente cerca.

La última observación es empírica e implica que un mínimo local muchas veces nos de información acerca del óptimo global.

Se pueden hacer tres estrategias: (i) determinística, (ii) estocástica, y (iii) combinación de las dos.

Variable neighborhood descent (VND): es un método determinístico. La idea es buscar sistemáticamente en diferentes esquemas de vecindad hasta llegar a un mínimo local que es mínimo con respecto a todos los esquemas de vecindad (ver tabla 4.4).


Tabla 4.4: Algoritmo de búsqueda de vecindad variable decendente.
\begin{table} \begin{tabbing} 123\=123\=123\= \kill Sea $N_k$, para $k=1,\ldots,... ...k \leftarrow 1$ \\ \> \> \> sino $k \leftarrow k + 1$ \end{tabbing}\end{table}


Reduced VNS (RVNS): es un método aleatorio. Es exactamente igual que la anterior, sólo que los vecinos en cada vecindad son seleccionados aleatoriamente (ver tabla 4.5).


Tabla 4.5: Algoritmo de búsqueda de vecindad variable reducida.
\begin{table} \begin{tabbing} 123\=123\=123\= \kill Sea $N_k$, para $k=1,\ldots,... ...k \leftarrow 1$ \\ \> \> \> sino $k \leftarrow k + 1$ \end{tabbing}\end{table}


VNS básico (VNS): combina cambios determinísticos y estocásticos. La idea es seleccionar un punto aleatorio en cierta vecindad y luego aplicarle a ese punto búsqueda local. Como en los casos anteriores, si se encuentra una mejor solución, se re-emplaza la solución actual y se empieza otra vez con el primer esquema de vecindad. Si no se busca una mejora en el siguiente esquema de vecindad (ver tabla 4.6).


Tabla 4.6: Algoritmo de búsqueda de vecindad variable básico.
\begin{table} \begin{tabbing} 123\=123\=123\= \kill Sea $N_k$, para $k=1,\ldots,... ...k \leftarrow 1$ \\ \> \> \> sino $k \leftarrow k + 1$ \end{tabbing}\end{table}


Se han propuesto diferentes variantes al algoritmo básico:

En esta, así como en otras técnicas que vamos a hacer, se han propuesto esquemas híbridos, e.g., VNS y búsuqeda Tabú, VNS y GRASP, VNS con satisfacción de restricciones, etc.

next up previous
Next: 4.4 Búsqueda Local Iterativa Up: 4. Búqueda Local y Previous: 4.2.3.2 Búsqueda local guiada
Eduardo Morales Manzanares 2004-11-02