Un modelo general de colonia de hormigas para resolver problemas de optimización combinatoria

Abstract

Un Sistema de Hormigas es un sistema artificial basado en el comportamiento de colonias de hormigas reales, que se utiliza para resolver problemas combinatorios. Este es un algoritmo distribuido compuesto por un conjunto de agentes cooperantes llamados hormigas que cooperan entre ellos para encontrar buenas soluciones a problemas de optimización combinatoria. La cooperación sigue el comportamiento de hormigas reales utilizando una forma indirecta de comunicación mediada por una feromona. En este trabajo, presentamos un nuevo algoritmo distribuido basado en conceptos de Ant System, llamado General Ant System, para resolver problemas de optimización combinatoria. Nuestro enfoque consiste en mapear el espacio de solución del Problema de Optimización Combinatoria sobre el espacio donde se emparedarán las hormigasc, y en definir la probabilidad de transición del Sistema Hormiga de acuerdo a la función objetivo del Problema de Optimización Combinatoria. Probamos nuestro enfoque sobre la partición de grafos y los problemas del viajante de comercio. Los resultados muestran que nuestro enfoque tiene el mismo rendimiento que las versiones anteriores de Ant Systems.