ePublications@bond

Solution biases and pheromone representation selection in ant colony optimisation

James Montgomery, PhD (Awarded in 2005)
Bond University, School of Information Technology

Advisor

Marcus Randall

Abstract

Combinatorial optimisation problems (COPs) pervade human society: scheduling, design, layout, distribution, timetabling, resource allocation and project management all feature problems where the solution is some combination of elements, the overall value of which needs to be either maximised or minimised (i.e., optimised), typically subject to a number of constraints. Thus, techniques to efficiently solve such problems are an important area of research. A popular group of optimisation algorithms are the metaheuristics, approaches that specify how to search the space of solutions in a problem independent way so that high quality solutions are likely to result in a reasonable amount of computational time. Although metaheuristic algorithms are specified in a problem independent manner, they must be tailored to suit each particular problem to which they are applied. This thesis investigates a number of aspects of the application of the relatively new Ant Colony Optimisation (ACO) metaheuristic to different COPs.

The standard ACO metaheuristic is a constructive algorithm loosely based on the foraging behaviour of ant colonies, which are able to find the shortest path to a food source by indirect communication through pheromones. ACO’s artificial pheromone represents a model of the solution components that its artificial ants use to construct solutions. Developing an appropriate pheromone representation is a key aspect of the application of ACO to a problem. An examination of existing ACO applications and the constructive approach more generally reveals how the metaheuristic can be applied more systematically across a range of COPs. The two main issues addressed in this thesis are biases inherent in the constructive process and the systematic selection of pheromone representations.

The systematisation of ACO should lead to more consistently high performance of the algorithm across different problems. Additionally, it supports the creation of a generalised ACO system, capable of adapting itself to suit many different combinatorial problems without the need for manual intervention.

Year Manuscript Completed

2005

Subject Category

Computer Science (0984)

Keywords

Combinatorial optimisation problems; metaheuristic algorithms; Ant Colony Optimisation (ACO)

Rights

The author has granted permission for Bond University to archive and make this thesis available in this repository. The author retains all proprietary rights such as patent rights, the right of attribution as well as the right to use all or part of the thesis in future works (such as articles or books). Use of this thesis is limited to private study or research in accordance with the Commonwealth of Australia Copyright Act, 1968 as amended.

Language

EN