iMOACOR: un nuevo algoritmo de optimización multi-objetivo basado en colonias de hormigas para espacios de búsqueda continuos



iMOACOR: un nuevo algoritmo de optimización multi-objetivo basado en colonias de hormigas para espacios de búsqueda continuos

Jesús Guillermo Falcón Cardona
 

Texto completo de la Tesis            Video del evento          

 



Resumen

 

En los ámbitos ingenieril, científico e industrial existen problemas que requieren de la optimización simultánea de varios objetivos que se encuentran normalmente en conflicto entre sí. Estos son los llamados problemas de optimización multi-objetivo (POMs). Debido al conflicto entre los objetivos, existen varias soluciones que satisfacen un POM en lugar de tener una única solución global como en el caso de un problema de optimización mono-objetivo. Estas soluciones conforman el denominado "conjunto óptimo de Pareto", mientras que su imagen es denominada "frente óptimo de Pareto" Las técnicas de programación matemática surgieron como un medio de solución de POMs. Sin embargo, bajo ciertas circunstancias, éstas presentan varios inconvenientes que deterioran su desempeño. En consecuencia, el uso de algoritmos evolutivos y otras metaheurísticas bioinspiradas para resolver POMs ha aumentado de manera significativa en los últimos 20 años. Esto ha dado pie al surgimiento de una gran variedad de algoritmos evolutivos multi-objetivo (AEMOs) en la literatura especializada. Por otra parte, la optimización mediante colonias de hormigas (OCH) es una metaheurística inspirada por el comportamiento social de las hormigas en su búsqueda de alimento. Las ideas principales de OCH son la auto-organización y la comunicación indirecta basada en modificaciones al ambiente empleando una sustancia denominada feromona. A través de la feromona, una hormiga puede sesgar probabilísticamente las decisiones de otras hormigas. OCH fue diseñado inicialmente para resolver problemas de optimización combinatoria (como el problema del viajero) debido a que se descubrió que los trazos de feromona convergían al camino más corto entre el nido y la fuente de alimento. Posteriormente, OCH fue extendido para la resolución de problemas de optimización continua dando buenos resultados y siendo ACOR una de las mejores propuestas de este tipo disponible en la actualidad. Sin embargo, el diseño de algoritmos de optimización multi-objetivo basados en OCH ha sido muy poco explorada en la literatura especializada. En esta tesis se propone un nuevo algoritmo de optimización multi-objetivo basado en OCH para la resolución de POMs en espacios de búsqueda continuos. La propuesta emplea ACOR como su motor de búsqueda y es denominada indicator-based Multi-Objective Ant Colony Optimization Algorithm for Continuous Search Spaces (iMOACOR). Este algoritmo también es capaz de resolver POMs de alta dimensionalidad debido al uso de un esquema de selección basado en el indicador de desempeño R2. El enfoque propuesto es comparado con respecto a AEMOs representativos del estado del arte (NSGA-III, MOEA/D, SMS-EMOA y MOACOR) empleado problemas de prueba e indicadores de desempeño estándar de la literatura especializada. Los resultados experimentales indican que iMOACOR es competitivo con respecto a NSGA-III y MOEA/D y supera a SMS-EMOA y MOACOR en la mayoría de los problemas de prueba adoptados. Además, iMOACOR presenta un mejor desempeño conforme aumenta la dimensionalidad del problema. De esta forma, iMOACOR parece ser un buen punto de partida para obtener un optimizador muti-objetivo basado en OCH altamente competitivo.

 

Abstract

Within engineering, science and industry, there are problems that require the simultaneous optimization of several objectives, which are normally in con ict with each other. These are the so-called multi-objective optimization problems (MOPs). Due to the con ict among the objectives, there are several solutions that satisfy a MOP, instead of having a single global solution as it happens when dealing with a singleobjective optimization problem. These solutions constitute the so-called ((Pareto optimal set)), whereas the image of this set is called ((Pareto optimal front)). Mathematical programming techniques were proposed as an alternative for solving MOPs. However, under several circumstances, such techniques have several drawbacks that deteriorate their performance. Consequently, the use of evolutionary algorithms and other bio-inspired metaheuristics for solving MOPs has signi cantly increased in the last 20 years. This has given rise to a wide variety of multi-objective evolutionary algorithms (MOEAs) in the specialized literature. On the other hand, ant colony optimization (ACO) is a metaheuristic inspired on the social behavior of ants that are seeking for food. The core ideas of ACO are selforganization and indirect communication based on modi cations to the environment using a substance called pheromone. Through the pheromone, an ant can probabilistically bias the decisions of other ants. ACO was initially designed to solve combinatorial optimization problems (such as the traveling salesperson problem) because it was discovered that pheromone trails converge to the shortest path between the nest and the food source. Later on, ACO was extended for the solution of continuous optimization problems, providing good results, being ACOR one of the best currently available proposals. However, the design of multi-objective optimization algorithms based on ACO has been only scarcely explored in the specialized literature. In this thesis, we propose a new multi-objective optimization algorithm based on ACO for solving MOPs in continuous search spaces. The proposed approach adopts ACOR as its search engine and is called indicator-based Multi-Objective Ant Colony Optimization Algorithm for Continuous Search Spaces (iMOACOR). This approach is also able to solve high-dimensionality MOPs because it adopts a selection scheme based on the performance indicator R2. The proposed approach is compared with respect to MOEAs that are representative of the state-of-the-art (NSGA-III, MOEA/D, SMS-EMOA and MOACOR) using standard test problems and performance indicators taken from the specialized literature. Our experimental results indicate that iMOACOR is competitive with respect to NSGA-III and MOEA/D and it outperforms SMS-EMOA and MOACOR in most of the test problems adopted. Furthermore, iMOACOR has a better performance as the dimensionality of a problem increases. This way, iMOACOR seems to be a good departing point for producing a highly competitive multi-objective optimizer based on ACO.