一种求解旅行商问题的高效混合遗传算法  

An Efficient Hybrid Genetic Algorithms for Traveling Salesman Prob lem

作　　者：姜昌华[1] 胡幼华[2] 

机构地区：[1]华东师范大学计算中心,上海200062 [2]华东师范大学计算机科学技术系,上海200062

出　　处：《计算机工程与应用》2004年第22期67-70,共4页Computer Engineering and Applications

摘　　要：旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。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.

关 键 词：TSP 混合遗传算法 2-opt邻域搜索优化 K近邻点集 

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