An agent-based approach to combinatorial optimization
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 properties 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 sensitivity level according to environment characteristics and previous experience. The resulting computational metaheuristic combines sensitive stigmergic behaviour with direct agent communication and learning to better addressing combinatorial optimization problems. The proposed model has been tested for solving various instances of NP-hard problems indicating the robustness and potential of the new metaheuristic.
agent communication sensitivity stigmergy multi-agent system ant colony optimization