Algoritmos meméticos para la resolución de problemas combinatorios de satisfacción con restricciones y con simetrías

Abstract

Este trabajo se enfoca en la resolución de problemas complejos de optimización, principalmente con el objetivo de prestar atención al modelado y ajuste de diversas técnicas metaheurísticas con el fin de resolver problemas de optimización con simetrías. La principal motivación para el desarrollo de esta investigación ha sido presentar una metodología que reúna las líneas principales que se deben seguir al momento de abordar este tipo de problemas. Es por ello que hemos utilizado un enfoque incremental de corte integrativo que involucre aspectos relacionados con la construcción o aplicación de modelos adecuados para la representación de los problemas objeto de estudio, considerando diferentes formas de representación enmarcados en la teoría de la dualidad, e intentando emplear algún mecanismo que permita reducir el paisaje de búsqueda (esto es, ruptura de simetrías). Se ha empleado un esquema de colaboración utilizando diferentes modelos de arquitectura, así como algoritmos híbridos evolutivos con diferentes métodos de búsqueda local. Además, consideraremos la utilización de un enfoque colaborativo entre las metaheurísticas propuestas a través de la definición de topologías de comunicación entre los diferentes componentes que participan en dicho esquema. Este enfoque propuesto se engloba dentro del paradigma de los algoritmos meméticos y ha sido validado empíricamente por medio dos problemas de optimización combinatoria que presentan un alto grado de complejidad, cuyos espacios de búsqueda son ricos en lo que se refiere a presencia de estados simétricos, y que han sido tradicionalmente formulados y resueltos por medio de técnicas de programación lineal entera (ILP) y programación con restricciones (CP). A tal fin, se presenta un extenso análisis de los resultados obtenidos con el fin de validar la adecuación y la eficacia de las técnicas metaheurísticas propuestas.