Computación emergente y auto-organización aplicada al diseño de algoritmos bio-inspirados de búsqueda heurística

Abstract

El presente trabajo de tesis doctoral se enmarca dentro de los métodos de búsqueda heurística en Inteligencia Artificial. Más concretamente se ha centrado en el diseño de algoritmos utilizando una perspectiva de computación emergente y auto-organización. El diseño se inspira en las capacidades de auto-organización de las colonias de insectos. Esta auto-organización consiste en ajustar la conducta en función de la respuesta obtenida al realizar una acción en un determinado entorno. Este mismo esquema se ha trasladado a un algoritmo de búsqueda: las acciones serían la generación de soluciones y el entorno sería el problema que se desea resolver. De este modo se consigue que el algoritmo se auto-organice según el estado de la búsqueda. El punto de partida ha sido un sistema multi-agente: la meta-heurística Ant Colony Optimisation. La cual ha sido modificada para aplicar un enfoque clásico de Inteligencia Artificial: búsquedas en espacios de estados. Los agentes del sistema operan de manera asíncrona. De este modo, se reduce la influencia a la que se ve sometido cada agente, lo cual se traduce en un mejor proceso de búsqueda, al reducirse el riesgo de estancarse por una pérdida de diversidad. Además, se ha desarrollado una dinámica auto-organizativa para regular la población de agentes. Esta dinámica de población permite mantener un equilibrio en la búsqueda mediante el balance de la población de agentes tanto en tamaño como en composición. Estas técnicas de diseño permiten disminuir el número de parámetros del algoritmo. Todo este conjunto de ideas se materializan en la implementación de un nuevo algoritmo: Ant Colony Extended, el cual ha obtenido buenos resultados en problemas de búsqueda y optimización muy diferentes tales como el problema del viajante de comercio (TSP), problemas clásicos de programación genética, y planificación-optimización de maniobras para barcos.