Opposition-based learning (OBL) was recently proposed to extend di erent machine learning
algorithms. The main idea of OBL is to consider opposite estimates, actions or states
as 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 algorithms
are based on the trail laying and following behaviour of ants. They have been successfully
applied to many complex optimization problems. However, like any other technique, they
can benefit from performance improvements. Thus, this work was motivated by the idea of
developing more complex pheromone and path selection behaviour for the algorithm using
the concept of opposition.
This work proposes opposition-based extensions to the construction and update phases
of the ant algorithm. The modifications that focus on the solution construction include
three direct and two indirect methods. The three direct methods work by pairing the ants
and synchronizing their path selection. The two other approaches modify the decisions of
the ants by using opposite-pheromone content. The extension of the update phase lead to
an approach that performs additional pheromone updates using opposite decisions.
Experimental validation was done using two versions of the ant algorithm: the Ant
System and the Ant Colony System. The di erent OBL extensions were applied to the
Travelling Salesman Problem (TSP) and to the Grid World Problem (GWP). Results
demonstrate that the concept of opposition is not easily applied to the ant algorithm.
One pheromone-based method showed performance improvements that were statistically
significant for the TSP. The quality of the solutions increased and more optimal solutions
were found. The extension to the update phase showed some improvements for the TSP
and led to accuracy improvements and a significant speed-up for the GWP. The other
extensions showed no clear improvement.
The proposed methods for applying opposition to the ant algorithm have potential, but
more investigations are required before ant colony optimization can fully benefit from opposition.
Most importantly, fundamental theoretical work with graphs, specifically, clearly
defining opposite paths or opposite path components, is needed. Overall, the results indicate
that OBL ideas can be beneficial for ant algorithms.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3233 |
| Date | January 2007 |
| Creators | Malisia, Alice Ralickas |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0022 seconds