Thesis:

Opposite Learning Strategies for Improving the Search Process of Ant-based Algorithms

Esta tesis propone una estrategia de aprendizaje inspirada en lo opuesto (Opposite-Inspired Learning) para algoritmos basados en hormigas que han sido diseñados para resolver problemas combinatorios. Nuestro interés radica en mejorar el proceso de búsqueda de un algoritmo basado en hormigas objetivo, en términos de la calidad de las soluciones que puede obtener. Nuestra estrategia se enfoca en aprender sobre características no deseadas que pueden sesgar algunas decisiones intermedias durante el proceso de construcción. Usualmente, estas decisiones intermedias dan prioridad a componentes localmente interesantes y, en algunos casos, solo se alcanzan soluciones de baja calidad. Inspirados en el concepto de anti-feromona, la idea es generar un efecto de repulsión para evitar (temporalmente) componentes que estén relacionados con una característica no deseada. La hipótesis de nuestro trabajo es la siguiente: si invertimos una cierta cantidad de recursos en identificar y aprender sobre alguna característica no deseada, el proceso de búsqueda podría enfocarse mejor tomando decisiones basadas en este conocimiento, lo que permitiría obtener instancias completas de mejor calidad. El objetivo de nuestra estrategia es modificar algunas decisiones intermedias, permitiendo que el algoritmo basado en hormigas seleccionado considere componentes que inicialmente no pueden ser evaluados o que son descartados. Para evaluar nuestra estrategia, seleccionamos algoritmos basados en hormigas diseñados para resolver dos tipos diferentes de problemas combinatorios: el Problema de la Mochila Multidimensional (un problema de optimización con restricciones) y Problemas de Satisfacción de Restricciones (CSPs). Seleccionamos el algoritmo Ant Knapsack como base para resolver el Problema de la Mochila Multidimensional, y Focused Ant Solver para resolver Problemas de Satisfacción de Restricciones. La inclusión de nuestra estrategia requiere el estudio de ambos problemas y algoritmos. Los resultados en instancias de referencia muestran que ambos algoritmos lograron alcanzar soluciones de mejor calidad. En el caso de Ant Knapsack, el uso de información opuesta permite al algoritmo alcanzar soluciones de mayor calidad. En cuanto al Focused Ant Solver, el uso de información opuesta permitió al algoritmo resolver más problemas durante la fase de transición. Se presentan diagramas de caja (boxplots), análisis estadísticos y gráficos de ajuste-distancia (fitness-distance) para evaluar cómo se modifica el proceso de búsqueda de estos algoritmos basados en hormigas. Además, el proceso de búsqueda de los dos algoritmos base fue capaz de obtener soluciones diferentes, tanto en calidad como en estructura. Además de la evaluación de nuestra estrategia en Ant Knapsack y Focused Ant Solver, se presenta un esquema cooperativo denominado COISA como trabajo preliminar en esta tesis. El objetivo de este esquema es evaluar la colaboración de diferentes subcolonias de hormigas utilizando información opuesta.

This thesis proposes an Opposite-Inspired Learning strategy for ant-based algorithms that weredesigned and are able to solve combinatorial problems. We are interested in improving the searchprocess of a target ant-based algorithm, in terms of the quality of the solutions it can obtain.Our strategy is focused on learning about such an undesirable characteristic that can bias someintermediate decisions performed during the construction process. Usually, these intermediatedecisions give priority to locally interesting components and in some cases, only poor qualitysolutions can be reached. Inspired in the concept of anti-pheromone, the idea is to produce a repeleect to (temporarily) avoid components that were related to an undesirable characteristic. Theclaim of our work is the following: if we consume a certain amount of resources in identifying andlearning about some undesired characteristic, the search process could be further focused makingdecisions using this knowledge so that we can obtain complete instantiations of a better quality.The objective of our strategy is to change some intermediate decisions allowing the selected antbasedalgorithm to consider components that could not be evaluated or are initially discarded. To evaluate our strategy we selected ant-based algorithms designed for solving two differentcombinatorial problems: the Multidimensional Knapsack Problem (a Constraint OptimizationProblem) and Constraint Satisfaction Problems (CSPs). We selected Ant Knapsack as the baselinealgorithm for solving the Multidimensional Knapsack Problem and Focused Ant Solver, for solving Constraint Satisfaction Problems. The inclusion of our strategy requires the study of both problemsand algorithms. Results in benchmark instances show that both algorithms were allowed to reachbetter quality solutions. In the case of Ant Knapsack, the use of opposite information allowsthe algorithm to reach better quality solutions. About Focused Ant Solver, the use of oppositeinformation allowed the algorithm to solve more problems from the transition phase. Boxplots,statistical analysis and tness-distance plots are presented to assess how the search process of theseant-based algorithms are modi ed. Moreover, the search process of the two baseline algorithmswere able to obtain different solutions, in terms of quality and structure.In addition to the evaluation of our strategy in Ant Knapsack and Focused Ant Solver, acooperative scheme named COISA is presented as a preliminary work in this Thesis. The objectiveof this scheme is to evaluate the collaboration of different sub-colonies of ants using oppositeinformation.