Diseño de un modelo de optimización de colonias de hormigas aplicado al problema del clique máximo

Abstract

Esta investigación consiste en la propuesta de un modelo basado en la metaheurística de Optimización con Colonias de Hormigas aplicado al problema del clique máximo, con el desarrollo de este modelo se pretende explorar de una manera más eficiente el espacio de búsqueda para encontrar mejores resultados, al encontrar un equilibrio entre la exploración y la explotación. En el trabajo se describen 5 contribuciones principales: (1) Una tabla en la cual se muestran los principales problemas que se han resueltos con colonias de hormigas, así como los principales investigadores de cada uno de estos problemas. (2) El desarrollo de diversos modelos de optimización de colonias de hormigas implementados, lós cuales fueron desarrollados para analizar sus características y comportamiento al trabajar y de esta manera poder diseñar un mejor algoritmo, los modelos implemetados fueron todos para resolver el problema del clique máximo. (3) Se muestra un estudio empírico de estos algoritmos desarrollados al tratar de analizar cómo trabajan para obtener sus bondades al momento de resolver los problemas utilizando 29 de los benchmarks de la DIMACS. (4) Se muestra un estudio estadístico para determinar los mejores valores en los parámetros relacionados con el número de hormigas, el número de iteraciones y la forma de colocar inicialmente las hormigas. (5) Se realizó un análisis de la complejidad de los algoritmos.