|
|||||
|
|
| 一种求解对称TSP的简单候选集方法 | |
| 引用本文： | 邓苗,林广明,张基宏,梁永生.一种求解对称TSP的简单候选集方法[J].深圳信息职业技术学院学报,2012,10(1):12-17. |
| 作者姓名： | 邓苗 林广明 张基宏 梁永生 |
| 作者单位： | 1. 深圳大学,广东深圳,518060 2. 深圳信息职业技术学院信息技术研究所,广东深圳,518172 3. 深圳大学,广东深圳518060 深圳信息职业技术学院信息技术研究所,广东深圳518172 |
| 基金项目： | 国家自然科学基金项目，广东省自然科学基金项目，深圳市科研项目，深圳信息职业技术学院博士创新项目 |
| 摘 要： | TSP（旅行商问题）作为一种解决组合优化问题的有效方法,在近几十年来受到了广泛的研究。理论证明它是一个典型的NP难问题,为了更快捷地求解,候选集方法在多种求解算法比如LKH算法中都有用到,一般是用于产生一个接近局部最优的初始解,较少用于寻路过程中。本文提出了一种新的简单的候选集方法,它采用一种新的距离度量,更好地符合了对称TSP的寻路规则。将其应用于最大最小蚁群算法（MMAS）的寻路过程中,实验结果表明针对对称TSP问题,该方法能比基本的MMAS取得更好的性能。这种候选集方法也可以用于其他求解对称TSP问题的进化计算。 |
| 关 键 词： | 对称TSP 蚁群优化 最大最小蚁群 候选集 |
A Simple Candidate Set Method for Symmetric TSP |
|
| DENG Miao,LIU Wei,ZHANG Jihong,LIANG Yongsheng.A Simple Candidate Set Method for Symmetric TSP[J].Journal of Shenzhen Institute of Information Technology,2012,10(1):12-17. | |
| Authors: | DENG Miao LIU Wei ZHANG Jihong LIANG Yongsheng |
| Institution: | 1,2(1.School of Information Engineering,Shenzhen University,Guangdong 518060;2.Information Technology Research Center,Shenzhen Institute of Information Technology,Guangdong 518172,China) |
| Abstract: | As a typical NP problem and an effective solution to combinatorial optimization problems,TSP(traveling salesman problem) has been extensively studied in the last few decades.Candidate set is often used in many algorithms to limit the selecting range in the process of choosing a next traveling destination or to initialize a local optimum solution,such as in LKH algorithm.A novel simple generating method of candidate set is proposed in this paper and applied to MAX-MIN Ant System(MMAS) for symmetric TSP problems.Experiment results show that this new method outperforms MMAS.It can also be used in other algorithms for symmetric TSP problems. |
| Keywords: | symmetric TSP ant colony optimization MAX-MIN Ant System candidate set |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |