La Variable Neighborhood Search no es tan poética como el Simmulated Annealing, pero también podemos intentar explicarla parabólicamente. Esta búsqueda está basada asimismo en búsqueda local, pero con una filosofía bastante distinta. Como sabemos, la búsqueda local elige un punto cualquiera de la función que queremos minimizar/maximizar y mira si alguno de los puntos de alrededor son «mejores»; si lo son, sigue buscando a partir de dicho punto. En la gráfica, el verde es el punto inicial, y la flechita 1 marca la solución encontrada siguiendo búsqueda local en un problema de minimización. Éste es también el primer paso en la VNS.

Lo novedoso de VNS es que modifica el concepto de «puntos de alrededor». Por ejemplo, los vecinos del 11 no serán ya el 10 y el 12, sino que podré definir un segundo vecindario en el que los vecinos sean puntos a distancia 10 entre sí (1, 21, 31, …), un tercer vecindario con puntos a distancia creciente en potencias de 2 (…, 5, 9, 13, 17, 25, 31, …), un cuarto vecindario elevando ese número a sí mismo (121, 1331, …), y así sucesivamente. Si me quedo sólo con el primer vecindario, puede ocurrir que las soluciones mejoren lentamente y se estanquen en un mínimo local. La idea del VNS básico es cambiar de vecindario cuando ya no sea posible mejorar una solución en el vecindario actual.

En la gráfica, el punto Y sería vecino del mínimo local en 1, y el punto Z del mínimo local en 2. Para que esta historia no se convierta en una búsqueda a ciegas, los vecindarios se definen con cierta lógica dentro del problema que estamos estudiando; esta «lógica» es la heurística que guía a tu algoritmo para que no vaya dando bandazos aleatoriamente.

VNS

Dijo aquél que sólo entiendes algo cuando eres capaz de explicárselo a tu abuela… yo no soy capaz, salta a la vista. Próxima entrega, algoritmos genéticos.