Metaheurística

Una metaheurística es un término paraguas para marcos algorítmicos estratégicos de alto nivel diseñados para explorar el espacio de búsqueda más allá de óptimos locales. El término fue acuñado por Glover (1986) en el contexto de tabu search y se estandarizó en la literatura de IO en los años 1990. Las principales familias de metaheurísticas: (1) tabu search (Glover 1989) — prohíbe movimientos locales recientes mediante una lista tabú para evitar ciclos; (2) recocido simulado (Kirkpatrick, Gelatt y Vecchi 1983) — parámetro de temperatura inspirado en la física que acepta probabilísticamente movimientos peores; (3) algoritmo genético (Holland 1975) — búsqueda evolutiva con población, selección, cruzamiento y mutación; (4) variable neighborhood search (Mladenović y Hansen 1997) — transiciones sistemáticas entre múltiples estructuras de vecindad; (5) GRASP (Feo y Resende 1995) — construcción aleatoria-voraz más búsqueda local; (6) optimización por colonia de hormigas (Dorigo 1992) y enjambre de partículas (Kennedy y Eberhart 1995). Las metaheurísticas híbridas (matheurísticas) han ganado importancia en los últimos veinte años, usando un solver MIP como solucionador de subproblemas dentro de un bucle metaheurístico. El ajuste de parámetros (longitud de lista tabú, esquema de enfriamiento, tamaño de población, tasa de mutación) determina en gran medida el equilibrio calidad-tiempo. Referencias estándar: Glover y Kochenberger (2003), Talbi (2009) y Gendreau y Potvin (2010) Handbook of Metaheuristics.