| 一种求解旅行商问题的高效混合遗传算法 |
| |
| 引用本文： | 姜昌华,胡幼华.一种求解旅行商问题的高效混合遗传算法[J].计算机工程与应用,2004,40(22):67-70. |
| |
| 作者姓名： | 姜昌华 胡幼华 |
| |
| 作者单位： | 1. 华东师范大学计算中心,上海,200062;华东师范大学计算机科学技术系,上海,200062
2. 华东师范大学计算机科学技术系,上海,200062 |
| |
| 摘 要： | 旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。
|
| 关 键 词： | TSP 混合遗传算法 2-opt邻域搜索优化 K近邻点集 |
| 文章编号： | 1002-8331-(2004)22-0067-04 |
An Efficient Hybrid Genetic Algorithms for Traveling Salesman Problem |
| |
| Jiang Changhua , Hu Youhua.An Efficient Hybrid Genetic Algorithms for Traveling Salesman Problem[J].Computer Engineering and Applications,2004,40(22):67-70. |
| |
| Authors: | Jiang Changhua Hu Youhua |
| |
| Affiliation: | Jiang Changhua 1,2 Hu Youhua 21 |
| |
| Abstract: | Travelling Salesman Problem(TSP)is a classic NP-Hard problem in combination.An efficient hybrid genetic algorithms for TSP is presented in this paper.The algorithm combines genetic algorithms and2-opt local search opti-mization,in order to speed up the computation,K Nearest Neighbors Sets is proposed to decrease the search space ac-cording to the characteristic of TSP.The simulations based on typical benchmarks prove that this algorithm is efficient. |
| |
| Keywords: | TSP Hybrid Genetic Algorithms local search optimization K nearest neighbors sets |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
