Búsqueda Local: Conceptos Fundamentales y Estrategias Avanzadas
La Búsqueda Local es una metaheurística fundamental usada para resolver problemas de optimización combinatoria y continua. En lugar de explorar todo el espacio de solución, la Búsqueda Local opera moviendo iterativamente de una solución a una solución vecina con la esperanza de mejorar el valor objetivo.
Es particularmente útil cuando:
- El espacio de solución es grande.
- Evaluar una sola solución es rápido.
- Un algoritmo exacto es muy lento o inviable.
¿Qué es la Búsqueda Local?
La Búsqueda Local comienza con una solución inicial y repetidamente se mueve a un mejor vecino hasta que no sea posible mejorar — es decir, se alcanza un óptimo local.
Marco Genérico
función BúsquedaLocal(S):
repetir:
S' ← MejorVecino(S)
si S' es mejor que S:
S ← S'
sino:
retornar S
¿Qué es un Movimiento? ¿Qué es un Operador?
En Búsqueda Local:
- Un movimiento es una modificación aplicada a una solución para generar un vecino.
- Un operador define el tipo de movimiento.
Ejemplos:
| Problema | Operador | Descripción del Movimiento |
|---|---|---|
| Viajante de Comercio | 2-opt | Intercambiar dos aristas para reducir distancia total |
| Programación de Trabajos | Intercambio | Intercambiar dos trabajos |
| Mochila | Agregar/Remover | Insertar o remover un ítem de la mochila |
| Coloreo de Grafos | Recolorear | Cambiar color de un nodo |
Los operadores definen la estructura de vecindario de la búsqueda.
¿Qué es un Vecindario?
El vecindario de una solución S, denotado N(S), es el conjunto de todas las soluciones que se pueden alcanzar mediante una aplicación de un movimiento.
- Los vecindarios varían en tamaño y estructura dependiendo del operador.
- Los vecindarios grandes pueden ser poderosos pero costosos de explorar.
Compromiso clave: Tamaño del vecindario vs. costo de exploración.
Primera vs. Mejor Mejora
La Búsqueda Local puede implementarse con dos estrategias principales al elegir el próximo movimiento:
1. Primera Mejora
- Evaluar vecinos uno por uno.
- Aceptar el primer movimiento que mejora.
- Más rápido, más exploratorio.
para S' en N(S):
si S' es mejor que S:
retornar S'
2. Mejor Mejora
- Evaluar todos los vecinos.
- Seleccionar el que tiene la mayor mejora.
- Más exhaustivo, potencialmente más lento.
mejor ← S
para S' en N(S):
si S' es mejor que mejor:
mejor ← S'
retornar mejor
Cómo Hacer la Búsqueda Local Más Rápida
Aunque la Búsqueda Local es efectiva, su rendimiento puede degradarse en vecindarios grandes o problemas complejos. Aquí hay estrategias para hacerla más rápida:
Poda de Vecindario
Evitar evaluar movimientos que no pueden llevar a mejora.
Usar listas de candidatos o filtros heurísticos.Evaluación Incremental
En lugar de recomputar el costo completo de un vecino, actualizar el costo incrementalmente basado en el movimiento.
Esto puede reducir drásticamente el tiempo de computación.Exploración Aleatorizada del Vecindario
Muestrear un subconjunto de vecinos en lugar de evaluar todos.
Útil cuando el vecindario es muy grande.Mejoras de Búsqueda Tabú
Mantener una lista tabú de movimientos o soluciones recientes para evitar ciclos.
Fomenta exploración más allá de óptimos locales.No Evaluar Movimientos Simétricos
En problemas simétricos, muchos movimientos son equivalentes. Evaluar solo representantes canónicos.Estructuras de Datos Eficientes
Usar estructuras de datos especializadas (p. ej., heaps, union-find, arreglos delta) para generar y evaluar movimientos rápidamente.
Variantes Avanzadas y Extensiones
La Búsqueda Local es un componente básico para metaheurísticas más avanzadas:
- Búsqueda Local Iterada (ILS): Aplicar repetidamente Búsqueda Local desde soluciones perturbadas.
- Búsqueda de Vecindarios Variables (VNS): Cambiar la estructura del vecindario dinámicamente.
- Recocido Simulado: A veces acepta movimientos peores para escapar óptimos locales.
- Búsqueda Tabú: Evita ciclos con una estructura de memoria.
Conclusión
La Búsqueda Local es una técnica poderosa y versátil que forma la columna vertebral de muchos métodos de optimización heurísticos y metaheurísticos. Entender sus componentes — movimientos, operadores, vecindarios — y cómo explorarlos eficientemente es clave para resolver problemas de optimización del mundo real.
Ya sea usada de forma independiente o como parte de un marco más complejo, la Búsqueda Local eficiente puede mejorar significativamente la calidad de soluciones en una amplia variedad de dominios.
Lectura Adicional
- Aarts, E., & Lenstra, J. K. (1997). Local Search in Combinatorial Optimization. Wiley.
- Michiels, W., Aarts, E., & Korst, J. (2007). Theoretical Aspects of Local Search. Springer.
- Glover, F., & Kochenberger, G. A. (2003). Handbook of Metaheuristics.