An Agent-Based Approach to Combinatorial Optimization
Camelia Chira, Camelia-M. Pintea, Dan Andrei Dumitrescu · 2008
Abstract: Systems composed of several interacting autonomous agents are investigated for their potential to efficiently address complex real-world problems. Agents communicate by directly exchanging information and knowledge about the environment. Typical agent prop-erties include autonomy, communication, learning, reactivity and mobility. It is proposed to further endow agents with stigmergic behaviour in order to cope with complex combinatorial problems. This means that agents are able to indirectly communicate by producing and being influenced by pheromone trails. Furthermore, each stigmergic agent has a certain level of sensitivity to the pheromone allowing various types of reactions to a changing environment. For better search diversification and intensification, agents can learn to modify their sensi-tivity level according to environment characteristics and previous experience. The resulting computational metaheuristic combines sensitive stigmergic behaviour with direct agent com-munication and learning to better addressing combinatorial optimization problems. The pro-posed model has been tested for solving various instances of NP-hard problems indicating the robustness and potential of the new metaheuristic.