Author:

Keywords:

Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science, Software Engineering, Computer Science, Theory & Methods, Computer Science

Abstract:

In this paper we propose the Multi-type Ant Colony system, which is an extension of the well known Ant System. Unlike the Ant System the ants are of a predefined type. In the Multi-type Ant Colony System ants have the same goal as their fellow types ants, however are in competition with the ants of different types. The collaborative behavior between identical type ants is modeled the same way as in ant systems, 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.