Investigating the Application of Opposition-Based Ideas to Ant Algorithms

ant colony optimization;opposition-based learning;machine learning;ant colony system;ant system;OBL;ant algorithm;System Design Engineering

Malisia, Alice Ralickas

University of Waterloo

关键词: ant colony optimization;    opposition-based learning;    machine learning;    ant colony system;    ant system;    OBL;    ant algorithm;    System Design Engineering;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3233/1/amalisia_thesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Opposition-based learning (OBL) was recently proposed to extend di erent machine learningalgorithms. The main idea of OBL is to consider opposite estimates, actions or statesas an attempt to increase the coverage of the solution space and to reduce exploration time.OBL has already been applied to reinforcement learning, neural networks and genetic algorithms.This thesis explores the application of OBL to ant algorithms. Ant algorithmsare based on the trail laying and following behaviour of ants. They have been successfullyapplied to many complex optimization problems. However, like any other technique, theycan benefit from performance improvements. Thus, this work was motivated by the idea ofdeveloping more complex pheromone and path selection behaviour for the algorithm usingthe concept of opposition.This work proposes opposition-based extensions to the construction and update phasesof the ant algorithm. The modifications that focus on the solution construction includethree direct and two indirect methods. The three direct methods work by pairing the antsand synchronizing their path selection. The two other approaches modify the decisions ofthe ants by using opposite-pheromone content. The extension of the update phase lead toan approach that performs additional pheromone updates using opposite decisions.Experimental validation was done using two versions of the ant algorithm: the AntSystem and the Ant Colony System. The di erent OBL extensions were applied to theTravelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Resultsdemonstrate that the concept of opposition is not easily applied to the ant algorithm.One pheromone-based method showed performance improvements that were statisticallysignificant for the TSP. The quality of the solutions increased and more optimal solutionswere found. The extension to the update phase showed some improvements for the TSPand led to accuracy improvements and a significant speed-up for the GWP. The otherextensions showed no clear improvement.The proposed methods for applying opposition to the ant algorithm have potential, butmore investigations are required before ant colony optimization can fully benefit from opposition.Most importantly, fundamental theoretical work with graphs, specifically, clearlydefining opposite paths or opposite path components, is needed. Overall, the results indicatethat OBL ideas can be beneficial for ant algorithms.