Learning Sensitive Stigmergic Agents for Solving Complex Problems

Abstract

Systems composed of several interacting autonomous agents have a huge potential to efficiently address complex real-world problems. Usually agents communicate by directly exchanging information and knowledge about the environment. The aim of the paper is to develop a new computational model that endows agents with a supplementary interaction/search mechanism of stigmergic nature. Multi-agent systems can therefore become powerful techniques for addressing NP-hard combinatorial optimization problems. In the proposed approach, agents are able to indirectly communicate by producing and being influenced by pheromone trails. Each stigmergic agent is characterized by a certain level of sensitivity to the pheromone trails. The non-uniform pheromone sensitivity allows various types of reactions to a changing environment. For efficient search diversification and intensification, agents can learn to modify their sensitivity level according to environment characteristics and previous experience. The resulting system for solving complex problems is called Learning Sensitive Agent System (LSAS). The proposed LSAS model is used for solving several NP-hard problems such as the Asymmetric and Generalized Traveling Salesman Problems. Numerical experiments indicate the robustness and the potential of the new metaheuristic.