OPPOSITE LEARNING STRATEGIES FOR IMPROVING THE SEARCH PROCESS OF ANT-BASED ALGORITHMS

Abstract

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 solvingConstraint 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.