求解TSP问题的自适应邻域遗传算法
Computer Engineering and Applications计算机工程与应用2010，46（27）
1引言
TSP是典型的组合优化问题，给定n个城市以及各城市之间的距离，要求找到一条遍历所有城市且每个城市只被访问一次的路线，并使得总路线距离最短，或表述为在有n个结点的完全图中找出最短的Hamilton回路。TSP问题的求解主要有两类算法，一类是保证得到最优解的完全算法，典型例子如枚举法，但这种算法必须考虑（n-1）!个不同的路径，规模稍大的实例，在时间上是不可行的。另一类是近似算法，如最近邻法[1]和智能算法（蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、Hopfield神经网络、粒子群优化算法、免疫算法等[2-5]）。最近邻法的优点是算法简单，直观可行，实现方便，但缺点是容易陷入局部最优解，而得不到全局最优解[1，5]。智能算法虽然不能保证在有限时间内获得最优解，但选择充分的多个解验证后，错误概率可以降到可以接受的程度。
遗传算法（Genetic Algorithm）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。Goldberg等首次应用GA求解TSP问题[6]。文献[2]指出将GA应用求解TSP问题时的主要缺点是：对初始种群很敏感，初始种群的选择常常直接影响解的质量和算法效率；对于结构复杂的组合优化问题，搜索空间大，搜索时间比较长，往往会出现早熟收敛的情况。
一些学者对求解TSP的遗传算法进行了改进。魏英姿等采用贪婪初始化法形成初始解（实质是最近邻法），为了克服早熟收敛引入了移民操作的概念，取得了比较好的效果[7]。莫海芳等提出混合遗传算法，在初始化种群中20％的个体是随机生成的，另外80％基于最近邻域生成部分个体；该方法既保证了群体的多样性，又充分利用城市路径的特征信息[8]。谢胜利采用了贪婪交叉算法，在交叉时考虑边的邻接关系，提高了算法的收敛速度[9]。
本文将自适应邻域法作为优化路径信息提取的手段结合
求解TSP问题的自适应邻域遗传算法
汪金刚，罗辞勇
WANG Jin-gang，LUO Ci-yong
重庆大学输配电装备及系统安全与新技术国家重点实验室，重庆400044
State Key Laboratory of Power Transmission Equipment&System Security and New Technology，Chongqing University，Chongqing400044，China
E-mail:jingang_023@https://www.wendangku.net/doc/c77178393.html,
WANG Jin-gang，LUO Ci-yong.Adaptive neighborhood method&Genetic Algorithm for solving Travelling Salesman https://www.wendangku.net/doc/c77178393.html,puter Engineering and Applications，2010，46（27）：20-24.
Abstract：In this paper，the travelling salesman problem（TSP）is solved by using the adaptive neighborhood method&ge-netic algorithm.In adaptive neighborhood method（ANM）one mimics the traveller whose rule shows that the next city is not always the nearest as-yet-unvisited location but it’s randomly selected from the unvisited cities which are further than the nearest city in adaptive neighborhood.While solving the TSP，ANM is used to create the initial population at first，then itera-tions are done through selection，cross and mutation operation.In selection，the proposed algorithm only keeps90%samples from the previous generation；the remaining is supplied by the new samples created by ANM.The results of simulation show that this approach is more competitive than other algorithms.
Key words：Genetic Algorithm（GA）；Travelling Salesman Problem（TSP）；nearest neighbor；adaptive neighborhood method
摘要：提出结合自适应邻域法与遗传算法来求解TSP问题。在自适应邻域法中，从某个城市出发，下一城市不一定是其最近城市，而是在比其最近城市稍远的邻域范围进行动态随机选取。在求解TSP时，采用自适应邻域法对种群初始化，然后采用选择、交叉、变异进行迭代，在选择中仅保留父代90％的样本，剩下的采用自适应邻域法产生新样本进行补充。仿真实验结果表明所提算法与其他算法相比具有竞争能力。
关键词：遗传算法；旅行商问题；最近邻法；自适应邻域法
DOI：10.3778/j.issn.1002-8331.2010.27.005文章编号：1002-8331（2010）27-0020-05文献标识码：Ａ中图分类号：TP301
基金项目：国家高技术研究发展计划（863）（the National High-Tech Research and Development Plan of China under Grant No.2006AA02Z4B7）；
中俄国际合作项目（No.ISCP2007DFR30080）。
作者简介：汪金刚（1979-），男，讲师，博士，主要研究方向为信号处理与计算机应用等；罗辞勇（1973-），男，副教授，主要研究方向为图像处理等。收稿日期：2010-07-16修回日期：2010-08-26
20