A Multi-Agent Approach for Solving Traveling Salesman Problem  

作　　者：ZHOU Tiejun TAN Yihong XING Lining 

机构地区：[1]School of Computer and Communication, HunanUniversity, Changsha 410082, Hunan, China [2]Department of Information and Computer Science,Changsha University, Changsha 410003, Hunan, China [3]School of Management, National University ofDefense Technology, Changsha 410073, Hunan, China

出　　处：《Wuhan University Journal of Natural Sciences》2006年第5期1104-1108,共5页武汉大学学报（自然科学英文版）

基　　金：Supported by the National Natural Science Foun-dation of China (69973016)

摘　　要：The traveling salesman problem （TSP） is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony system to solve the TSP. Three kinds of agents with different function were designed in the multi-agent architecture proposed by this paper. The first kind of agent is ant colony optimization agent and its function is generating the new solution continuously. The second kind of agent is selection agent, crossover agent and mutation agent, their function is optimizing the current solutions group. The third kind of agent is fast local searching agent and its function is optimizing the best solution from the beginning of the trial. At the end of this paper, the experimental results have shown that the proposed hybrid ap proach has good performance with respect to the quality of solution and the speed of computation.The traveling salesman problem （TSP） is a classical optimization problem and it is one of a class of NP- Problem. This paper presents a new method named multiagent approach based genetic algorithm and ant colony system to solve the TSP. Three kinds of agents with different function were designed in the multi-agent architecture proposed by this paper. The first kind of agent is ant colony optimization agent and its function is generating the new solution continuously. The second kind of agent is selection agent, crossover agent and mutation agent, their function is optimizing the current solutions group. The third kind of agent is fast local searching agent and its function is optimizing the best solution from the beginning of the trial. At the end of this paper, the experimental results have shown that the proposed hybrid ap proach has good performance with respect to the quality of solution and the speed of computation.

关 键 词：traveling salesman problem multi-agent approach genetic algorithm ant colony system 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]