Generalización de algoritmos de búsqueda estocástica local por medio de métodos de representación conjunta de soluciones

Abstract

Durante las últimas décadas, se ha producido un aluvión de contribuciones al campo de la computación evolutiva. Se han desarrollado algoritmos inspirados en todo tipo de especies naturales, además de híbridos entre varios de ellos. No obstante, el comportamiento intrínseco de muchos es esencialmente el mismo. Esto ha permitido dividirlos en tres grandes grupos: los que se parecen a los algoritmos genéticos (GA), a los de enjambre de partículas (PSO) y a los de colonia de hormigas (ACO), respectivamente. En este trabajo se da un paso más y se diseña un algoritmo generalizado al que pueden reducirse todos. Además, se propone una particularización del mismo (AEMP) que centra su atención únicamente en la distribución de probabilidad de las soluciones consideradas en cada momento. Este nuevo algoritmo permite crear variantes e híbridos entre ellas de forma completamente directa, sin necesidad de tomar inspiración en la naturaleza. Los experimentos realizados en este trabajo muestran, además, que no existen diferencias significativas entre los resultados obtenidos por ciertas variantes de AEMP y métodos clásicos como PSO al enfrentarse a problemas de optimización NP-difíciles.

Over the last decades, there has been a flood of contributions to the field of evolutionary computation. Algorithms inspired in all kinds of natural species have been developed, as well as hybrids between several of them. However, the intrinsic behavior of many is essentially the same. This has allowed authors to sort them into three large groups: those similar to genetic algorithms (GA), to particle swarm optimization (PSO) algorithms and to ant colony optimization (ACO) algorithms, respectively. In this work, we go one step forward and design an algorithm that generalizes all of them. Moreover, we propose a particularization of it (AEMP) that only focuses on the probability distribution of the solutions considered at any moment. This novel algorithm allows us to create variants and hybrids between them in a way that is completely direct, without the need for natural inspiration. Experiments conducted in this work also show that no significant difference exists between results obtained by certain AEMP variants and classical methods such as PSO when facing NP-hard optimization problems.