Multiple Ant Colonies Algorithm Based on Colony Level Interactions

Abstract

SUMMARY Recently, researchers in various fields have shown interest in the behavior of creatures from the viewpoint of adaptiveness and flexibility. Ants, known as social insects, exhibit collective behavior in performingtasks that can not be carried out by an individual ant. In ant colonies, chemical substances, called pheromones, are used as a way to communicate important information on global behavior. For example, ants lookingfor food lay the way back to their nest with a specific type of pheromone. Other ants can follow the pheromone trail and find their way to baits efficiently. In 1991, Colorni et al. proposed the ant algorithm for Traveling Salesman Problems (TSPs) by using the analogy of such foraging behavior and pheromone communication. In the ant algorithm, there is a colony consistingof many simple ant ag ents that continuously visit TSP cities with opinions to prefer subtours connectingnear cities and they lay strongpheromones. The ants completingtheir tours lay pheromones of various intensities with passed subtours accordingto distances. Namely, subtours in TSP tourns that have the possibility of beingbetter tend to have strongpheromones, so the ant agents specify good regions in the search space by using this positive feedback mechanism. In this paper, we propose a multiple ant colonies algorithm that has been extended from the ant algorithm. This algorithm has several ant colonies for solving a TSP, while the original has only a single ant colony. Moreover, two kinds of pheromone effects, positive and negative pheromone effects, are introduced as the colony-level interactions. As a result of colony-level interactions, the colonies can exchange good schemata for solvinga problem and can maintain their own variation in the search process. The proposed algorithm shows better performance than the original algorithm with almost the same agent strategy used in both algorithms except for the introduc