Multi-type Ant System: The introduction of competition to Ant algorithms

Scriptie/Masterproef: Master's Thesis


In this dissertation we propose the Multi-type Ant Colony system, which is an extension of the well known Antsystem. Unlike the AntSystem the ants are not of a single type. In the Multi-type ant system ants are of a given type and have the same goal as their fellow typs ants, but are in competition with the ants of different types. The collaborative behavior between identical type ants is modeled the same way as in Antsystems, i.e. ants are attracted to pheromone of ants of the same type. The competition between different types is obtained because ants are repulsed by the pheromone of ants of other types. This paradigm is interesting for applications where collaboration as well as competition is needed in order to obtain good solutions. In this paper we illustrate the algorithm on the problem of finding disjoint paths in graphs. A first experiment shows on a simple graph two ants types that find successfully two completely disjoint paths. A second experiment shows a more complex graph where the number of required disjoint paths exceeds the number of possible disjoint paths. The results show that the paths found by the ants are distributed proportionally to the cost of the paths. A last experiment shows the influence of the exploration parameter on a complex graph. Good results are obtained if the exploration parameter is gradually decreased.
Datum prijs2 jul 2004
Originele taalEnglish
BegeleiderAnn Nowe (Promotor) & Katja Verbeeck (Advisor)

Citeer dit