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.