## Simplification Strategies for the Ant System

##### B. Bullnheimer, Production and Operations Management, Dept. of Management
Science, University of Vienna, Austria

Email: bullnhei@pom.bwl.univie.ac.at

Attempts to solve hard combinatorial optimization problems by using
ideas similar to the behaviour of real ants initiated the development of
several new distributed meta-heuristics and a movement which can be
summarized as Ant Colony Optimization (ACO). The Ant System (AS), a
colony of cooperating agents was initially applied to the Traveling
Salesman Problem (TSP). Further applications to the TSP as well as to
many other hard combinatorial optimization problems like Quadratic
Assignment, Scheduling, Graph Colouring, Vehicle Routing and Sequential
Ordering followed.
Moreover, various algorithmic improvements to the original Ant System
Algorithm have been proposed since. One drawback of the original
algorithm and all modifications that followed is the number of
parameters involved. Each parameter has to be fine-tuned carefully in
order to allow the artificial ants to generate good solutions. At the
same time, this fine-tuning often leads to parameter values that work
well for one particular instance but not necessarily for other
instances. Most crucial in this respect in AS are the parameters that
regulate the relative influence of the pheromone trails and the
heuristic information, respectively.

In this paper we present two simplified versions of the Ant System
that do not use these parameters and therefore are independent of the
problem under consideration let alone the actual instance of that
problem. We use the TSP to demonstrate the new algorithms and give an
outlook on applications to other combinatorial optimization problems.