Metaheurísticas de trayectoria y poblacional aplicadas a problemas de optimización combinatoria

Abstract

En el mundo existen una multitud de problemas cotidianos que, precisan de una solución que cumpla con un conjunto de requisitos de la manera más apropiada maximizando o minimizando un determinado valor. Sin embargo, para encontrar una solución óptima para ciertos problemas de optimización puede ser una tarea increíblemente difícil o imposible. Esto es, porque cuando un problema se vuelve lo suficientemente grande, tenemos que buscar a través de un enorme número de posibles soluciones, la solución más eficiente, es decir, la que tiene costo menor. Las metaheurísticas son una de las estrategias que ha obtenido una gran aceptación y que han ido consiguiendo un importante cuerpo formal; ya que estás establecen estrategias para recorrer y explorar el espacio de soluciones del problema normalmente generadas en forma aleatoria y de manera iterativa. La principal ventaja de estas técnicas es su flexibilidad y robustez, lo que permite aplicarlas a un amplio conjunto de problemas. En este trabajo proponemos concentrarnos en una metaheurística basada en trayectoria Simulated Annealing y una basada en población Algoritmo Genético Celular con el objetivo de realizar un estudio y comparación de los resultados obtenidos en su aplicación para la resolución de un conjunto de problemas académicos de optimización combinatoria.

Keywords

• metaheurísticas
• algoritmo
• genético
• celular
• simulated
• annealing
• problemas
• optimización
• combinatoria