文献类型：会议论文

英文题名：A clustering-based evolutionary algorithm for traveling salesman problem

作者：Liu, Dalian[1]; Wang, Xinfeng[1]; Du, Jinling[2]

通讯作者：Liu, D.|[1141727023d67399c6aa8]刘丹;

机构：[1] Department of Basic Course Teaching, Beijing Union University, Beijing, China; [2] School of Management Engineering, Shan Dong Jianzhu University, Ji Nan, China

第一机构：北京联合大学基础教学部

通讯机构：[1]Department of Basic Course Teaching, Beijing Union University, Beijing, China|[1141788]北京联合大学基础教学部;[11417]北京联合大学;

会议论文集：CIS 2009 - 2009 International Conference on Computational Intelligence and Security

会议日期：December 11, 2009 - December 14, 2009

会议地点：Beijing, China

语种：英文

外文关键词：Artificial intelligence - Evolutionary algorithms - Traveling salesman problem

摘要：The traveling salesman problem (TSP) is widely used in many real world problems. It is very important to design efficient algorithms for this problem. The key issue in TSP is that the computation cost will increase rapidly with the increasing of the size of the problem. To overcome the shortcoming, in this paper a novel evolutionary algorithm based on a clustering algorithm is proposed for TSP. The proposed algorithm consists of three phases. In the first phase, the cities are divided into several group by a clustering algorithm. In the second phase, each group of cities are considered as a smaller scale TSP problem and this smaller size TSP problem is solved by a new evolutionary algorithm and get a sub-tour of the cities of this group. In the third phase, a connection scheme is proposed to connect these sub-tours into a feasible tour of whole cities. Furthermore, this feasible tour is improved by a local search scheme. At last, the simulations on some standard test problems are made, and the results indicate the proposed algorithm is efficient. ? 2009 IEEE.