Ant Colony Optimisation

Dhananjay Thiruvady, Clayton School of Information Technology.
The Ant Colony Optimisation project relates to the estimation of distribution algorithms, constraint programming and branch and bound techniques (beam search) for combinatorial optimisation problems. The project is particularly interested in the integration of these techniques to develop more effective and efficient algorithms that are not problem-dependent, as the problems that have been identified to date include job scheduling, bin packing, tournament scheduling and layout.

Within the project, there are a number of different classes of algorithms, and two are of particular importance because they are incomplete and/or stochastic (EDAs and beam search). Hence, proving their properties and comparing them is a very complex and computationally-intensive endeavour. A primary method of dealing with these algorithms is to conduct a large number of experiments and statistically compare the algorithms in order to determine their attribute, and this can be accomplished by using the resources present through the Monash Sun Grid and the East Enterprise Grid. By utilising the computational power of Monash's HPC infrastructure, the researchers involved with this project are able to conduct large numbers of experiments effectively, and with considerable speed.

Output of a bin packing probem derived from a variant of Ant Colony Optimisation algorithms