Improving the Exploration Ability of Ant-Based Algorithms

The chapter discusses the application of Opposition-Based Optimization (OBO) to ant algorithms. Ant Colony Optimization (ACO) is a powerful optimization technique that has been used to solve many complex problems. Despite its successes, ACO is not a perfect algorithm: it can remain trapped in local optima, miss a portion of the solution space or, in some cases, it can be slow to converge. Thus, we were motivated to improve the accuracy and convergence of the current algorithm by extending it with the concept of OBO. In the case of ACO, the application of opposition can be challenging because ACO usually optimizes using a graph representation of problems, where the opposite of solutions and partial components of the solutions are not clearly defined.

The chapter presents two types of opposition-based extensions to the ant algorithm. The first type, called Opposite Pheromone per Node (OPN), involves a modification to the construction phase of the algorithm which affects the decisions of the ants by altering the pheromone values used in the decision. Basically, there is an opposite rate that determines the frequency at which opposite pheromone will be used in the construction step. The second method, Opposite Pheromone Update (OPU), involves an extension to the update phase of the algorithm that performs additional updates to the pheromone content of opposite decisions. The opposition-based approaches were tested using the Travelling Salesman Problem (TSP) and the Grid World Problem (GWP).

Overall, the application of some fundamental opposition concepts led to encouraging results in the TSP and the GWP. OPN led to some accuracy improvements and OPU demonstrated significant speed-ups. However, further work is necessary to fully evaluate the benefits of opposition. Theoretical work involving the application of opposition to graphs is necessary, specifically in establishing the ‘opposite graph’.