Investigación dispersa
La búsqueda dispersa (SS) es un método evolutivo propuesto por (Glover y Laguna 1997). Se propuso en el marco de la resolución de problemas combinatorios.
Este metaheurística difiere de los algoritmos evolutivos clásicos por el uso de un procedimiento de busqueda local y por la generalización del operador de cruce. Al igual que el algoritmos genéticos, se basa en una población de soluciones que evoluciona en el tiempo utilizando tanto un operador de selección, la combinación lineal de soluciones de la población para crear una nueva solución provisional (no necesariamente entera o admisible), de un operador de proyección que permite hacer la admisibilidad de la solución provisional y de los operadores de eliminación.
Descripción del método
El concepto general de investigación dispersa dado por (Glover et al. 1998) se basa en los siguientes tres fundamentos:
- La información útil sobre la solución óptima suele estar contenida en una colección diversa de soluciones de élite.
- Las estrategias de combinación de soluciones contienen mecanismos que incorporan la diversificación e intensificación en la generación de nuevas soluciones.
- El uso de varias combinaciones de soluciones de referencia aumenta la oportunidad de explotar la información contenida en la unión de soluciones de élite.
El modelo de algoritmo de búsqueda dispersa se basa en la definición de los siguientes cinco componentes principales (conocidos como métodos):
- Método de generación de diversificación: Consiste en generar una colección de varias soluciones de partida.
- Método de mejora: los puntos se optimizan mediante la búsqueda local.
- Método para actualizar el conjunto de referencia RI: construye y mantiene un conjunto de referencia obtenido al seleccionar las mejores soluciones b encontradas.
- Método de generación de subconjuntos: genera subconjuntos DI del conjunto de referencia.
- Método de combinación de soluciones: genera soluciones combinando las soluciones de cada subconjunto DI para producir el conjunto CI.
Algoritmo
ES 
FR 
EN