Natural algorithms for optimisation problems final year project report

Abstract

Many computational techniques borrow ideas from nature in one way or another. Neural networks imitate the structure of our human brain, genetic algorithms simulate evolution and swarms of insects inspired algorithms for stochastic combinatorial optimisation. These techniques are characterised by inherent parallelism, adaptivity, positive feedback and some element of randomness. This report details the investigations into certain features of one such technique: the Ant System meta-heuristic proposed by Dorigo. The algorithm is applied to several variations of the well-known Travelling Salesman Problem, including asymmetric and dynamic ones. Furthermore, di erent approaches to parallelise the algorithm are investigated. Good parameters are needed to instantiate the generic algorithm e ciently and research to nd optimal parameter settings has been conducted in the course of this project. An ontology to classify instances of the TSP is introduced and a thorough analysis of the dependency between parameters and classes of problems is presented. During this analysis, optimal parameters have been found for a given problem instance that led to the discovery of a new shortest tour for this instance. A novel algorithm, the Genetically Modi ed Ant System(GMAS), is then proposed that employs ideas from the eld of genetic algorithms to eliminate the need to set parameters for a given problem explicitly. An implementation is described and the new system is evaluated with respect to the standard Ant System and also compared to other more specialised heuristics.