Simplification Strategies for the Ant System

B. Bullnheimer, Production and Operations Management, Dept. of Management Science, University of Vienna, Austria
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.