| 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 |
| |
| 摘 要： | 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.
|
| 关 键 词： | “货郎担” 问题 多主体逼近 遗传算法 蚁群算法 |
| 文章编号： | 1007-1202（2006）05-1104-05 |
| 收稿时间： | 2006-03-23 |
A multi-agent approach for solving traveling salesman problem |
| |
| ZHOU Tiejun TAN Yihong XING Lining.A Multi-Agent Approach for Solving Traveling Salesman Problem[J].Wuhan University Journal of Natural Sciences,2006,11(5):1104-1108. |
| |
| Authors: | Zhou Tiejun Tan Yihong Xing Lining |
| |
| Institution: | (1) School of Computer and Communication, Hunan University, 410082 Changsha, Hunan, China;(2) Department of Information and Computer Science, Changsha University, 410003 Changsha, Hunan, China;(3) School of Management, National University of Defense Technology, 410073 Changsha, Hunan, China |
| |
| Abstract: | 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 multi- agent 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 approach has good performance with respect to the quality of solution and the speed of computation. |
| |
| Keywords: | traveling salesman problem multi-agent approach genetic algorithm ant colony system |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
|
