Naseer26 Hussein
Our proposed system Ant Colony Optimization (ACO) is a meta- heuristic introduced by Dorigo et al. [9] which uses ideas from nature to find solutions to instances of the Travelling Salesman Problem (TSP) and other combinatorial optimisation problems. In this paper we analyse the parameter settings of the ACO algorithm. These determine the behavior of each ant and are critical for fast convergence to near optimal solutions of a given problem instance. We classify TSP instances using three measures of complexity and uniformity. We describe experimental work that attempts to correlate ‘types’ of TSP problems with parameter settings for fast convergence. We found these optimal parameter settings to be highly problem specific and dependent on the required accuracy of the solution. This inspired us to explore techniques for automatically learning the optimal parameters for a given TSP instance. We devised and implemented a hybrid ACO algorithm, similar to the one independently developed in [16], which used a genetic algorithm in the early stages to ‘breed’ a population of ants possessing near optimal behavioural parameter settings for a given problem. This hybrid algorithm converges rapidly for a wide range of problems when given a population of ants with diverse behavioural parameter settings.