Metaheurísticas: Aproximando soluciones de problemas complejos de optimización

Autor: Pamela Jocelyn Palomo Martínez
Los problemas de optimización surgen en muy diversas aplicaciones, como lo son el transporte y la distribución de bienes, la planificación de líneas de producción, el diseño de rutas de turistas, el diseño de horarios de empleados, etcétera. Sin embargo, muchas veces no es posible resolver estos problemas haciendo uso de un método exacto, debido a restricciones de tiempo o a limitaciones computacionales. Una metaheurística es un esquema que combina el uso de diferentes algoritmos de aproximación (heurísticas), con la finalidad de encontrar soluciones suficientemente buenas de problemas de optimización de una manera rápida y haciendo uso de una menor cantidad de recursos computacionales que un algoritmo exacto. En este curso se presentarán las características de algunas de las metaheurísticas más populares en la literatura y se darán ejemplos de los tipos de problemas para los cuales estos algoritmos se han utilizado de manera exitosa. Las metaheurísticas que se discutirán en el curso, son las siguientes: *Recocido simulado (Simulated Annealing, SA) *Algoritmos genéticos (Genetic Algorithms, GA) *Búsqueda dispersa (Scatter Search, SS) *Procedimiento de búsqueda voraz, aleatorizada y adaptativa (Greedy Randomized Adaptive Search Procedure, GRASP) *Búsqueda por entornos variables (Variable Neighborhood Search, VNS) *Búsqueda adaptativa por grandes vecindarios (Adaptive Large Neighborhood Search, ALNS)