Multi-Population Agent Search: Stigmergy and Heterogeneity

Ant systems normally rely on identical agents that cooperate indirectly using pheromone trails to find a problem solution. This uniformity may be inadequate in solving difficult problems where complex behavior patterns are needed. A new ant-based model is developed with the aim of promoting non-uniformity in the agent population by enhancing each agent with properties that induce heterogeneity. Agents are endowed with different pheromone sensitivity levels. Highly-sensitive agents are essentially influenced in the decision making process by stigmergic information and thus likely to select strong pheromone-marked moves. Agents with low sensitivity are biased towards random search inducing diversity for exploration. Sensitive agents allow many types of reactions to a changing environment facilitating an efficient balance between exploration and exploitation. This balance is pursued by organizing the agents in several subpopulations based on a sensitivity level interval. Therefore, each subpopulation has a specific behavior given by the sensitivity level spanning from the diversification to the intensification of the search. The proposed model is engaged in a set of numerical experiments and comparisons for solving various combinatorial optimization problems with very promising results.