改进遗传算法在TSP问题中的应用

摘 要：旅行商问题是典型的NP组合优化问题。提出一种旅行商问题求解应用上的改进遗传算法。引入贪心算法优化初始种群，在轮盘赌选择基础上，融入最优保存策略和掺杂算子进行选择操作，以保证群体的多样性；基于两点三段随机交叉算子优化交叉结果，基于启发式倒位变异算子提高算法的收敛速度；给出了求解旅行商问题系统的体系结构。实验结果表明，改进的遗传算法具有更好的寻优能力。

关键词：旅行商问题；遗传算法；贪心算法；组合优化；体系结构

DOIDOI：10.11907/rjdk.162168

中图分类号：TP319

文献标识码：A文章编号：1672-7800（2016）012-0127-03

0 引言

旅行商问题（Traveling Salesman Problem，TSP）是典型的NP组合优化问题，具有重要的理论价值和良好的应用背景，诸如半导体电路设计、公路网络建设、飞机航线安排、连锁店货物配送路线等，通过TSP建模均可解决。求解TSP问题方法包括精确算法、近似算法和智能算法。文献[1]采用遗传算法基础上派生出来的分布估计算法求解TSP问题，并将种群进行分级处理，根据种群级别高低分别采用不同的策略进行交叉和变异操作；文献[2]在基本遗传算法基础上引入外部最优个体集，以增加群体多样性，改善局部搜索能力，采用递归分治策略将遗传算法并行化；文献[3]采用改进的遗传算法，按种群中个体适应度高低采用不同的交叉和变异算子；文献[4]提出一种改进的遗传算法，动态调整交叉和变异概率，以降低染色体近亲繁殖可能，有效控制了进化过程；文献[5]结合遗传算法和模拟退火算法，提出了一种改进的模拟退火遗传算法；文献[6]将蚁群算法和遗传算法融合，经过蚁群算法迭代获得初始种群解集，再采用改进的遗传算法寻优；文献[7]在基本遗传算法基础上，提出改进型多宇宙量子交叉算子，利用不同宇宙间的信息交流提高算法的搜索效率。

上述求解TSP问题的研究效果很好，但都没有提到有关求解系统的设计问题。本文不但对基本遗传算法求解TSP问题进行分析并加以改进，还给出了求解TSP问题系统的体系结构。实验结果表明，改进的遗传算法具有更可靠的寻优能力，求解系统实用性较好。

1 基本问题描述

1.1 TSP问题

TSP问题可描述为：一个旅行商要到n个城市推销商品，从一个城市出发，走一遍余下的n-1个城市再回到起点，要求所走的路程最短，即寻找一条巡回路径C=（c1，c2，...，cn），使得下列目标函数最小[8]：

1.2 遗传算法原理及应用

遗传算法是一种随机并行搜索算法，其基本思想是：首先对个体编码，生成初始种群，然后开始进化，用适应度函数来判断个体优劣，优秀的个体将获得更多的选择、交叉和变异机会，一直进化到满足迭代的终止条件，从而得到最优解。该算法具有全局寻优能力强、计算过程简单、处理并行性、鲁棒性等优点，在组合优化问题、模式识别、图像处理、调度问题等领域得到了广泛应用[9]。

2 应用遗传算法求解TSP问题

遗传算法已经广泛应用于求解组合化问题的近似最优解方面，TSP问题是典型的组合优化问题。应用遗传算法求解TSP问题基本方法如下：（1）确定编码方式。用遗传算法求解TSP问题常用的编码方式有二进制表示、顺序表示、路径表示、边表示等，其中路径表示因自然、直观且易于加入启发式信息，是应用最多的一种表示策略。（2）初始化种群。随机产生初始个体，构成指定规模的初始种群，是应用遗传算法求解TSP问题的常用方法。（3）计算种群中每个个体的适应度值。在TSP问题中，目标函数f（C）=∑n-1i=1d（ci，ci+1）+d（cn，c1）是路径总长度，适应度函数通常取目标函数的倒数，即F（C）=1/f（C）。（4）选择算子。目前常用的选择算子有比例选择、最优保存策略、基于联赛的选择等。（5）交叉算子。按照某一交叉概率pc选择若干父体并进行配对。针对路径表示的TSP遗传算法，常用的交叉算子有部分匹配交叉、贪婪交叉、次序交叉和循环交叉等。（6）变异算子。按照某一变异概率pm随机确定变异个体，常用的变异算子包括倒位变异、插入变异、移位变异和2-opt变异等。（7）迭代终止条件。若算法满足迭代的终止条件，则停止迭代；否则转至第（3）步，利用适应度函数重新计算每个个体的适应度值。基本遗传算法存在易陷入局部最优、收敛速度慢和优化精度低等缺点。改进遗传算法的目标是在提高算法收敛速度的同时确保种群多样性，从而使寻优结果接近最优解[10]。

3 求解TSP问题的改进遗传算法

3.1 个体路径编码表示

路径表示法是TSP问题最直接的表示方法，本文算法采用此方法进行个体编码，每个个体就是一次访问城市的顺序排列。编码串（x1，x2，...，xn）表示从城市x1出发，依次经过城市x2，x3，...，xn，最后回到x1。

3.2 贪心算法优化初始种群

针对n个城市的TSP问题，假定种群规模为N，其中N*0.3个初始个体由贪心算法生成，N*0.7个初始个体随机产生。N*0.3个初始个体中，每个个体生成的基本思想是：首先随机地从n个城市中选取一个城市ccurrent作为第1个基因，然后从余下的n-1个城市中找到城市cnext（cnext是距离ccurrent最近的城市）作为第2个基因，再从余下的n-2个城市中找到城市cnext+1（cnext+1是距离cnext最近的城市）作为第3个基因，依次类推，直到遍历n个城市为止。贪心算法生成的部分种群占比不大，在提高初始种群整体质量的同时，不会影响初始种群的多样性，有助于加速寻优速度[11]。

3.3 适应度函数

适应度函数通常直接由目标函数得出，本文用目标函数的倒数来表示适应度函数。实际情况中，多个城市间的路径长度∑n-1i=1d（ci，ci+1）+d（cn，c1）会比较大，倒数后数据将会有3～5位小数，不利于计算，所以将适应度值放大D倍（D∈[10000，1000000]为常量），即适应度函数表达式为：F（C）=D/f（C），其中f（C）为公式（1）表示的目标函数。

3.4 选择算子

本文改进的选择算子是基于轮盘赌选择，融入最优保存策略和掺杂算子。最优保存策略是直接复制群体中适应度最高的个体到下一代，即个体不进行交叉、变异等操作[11]。掺杂算子是指在每代种群中随机产生不大于N*0.1（N为种群规模）个新个体参与遗传操作[12]。通过改进的选择算子，在保留最优个体的同时引入新个体，提高了算法收敛于全局最优的可能性。

3.5 交叉算子

基本遗传算法常用的双点交叉算子，是指在要配对的两个个体中随机选择两个交叉点，将介于两点之间的部分基因进行交换，对交换后两点区域外出现的重复节点，按照原有位置对应关系进行替换，从而得到两个新染色体。这种交叉方式只是对父个体两点之间的基因进行交叉，两点区域外的基因要么不变，要么由于节点重复而盲目地改变，父个体的优良基因得不到有效继承。在两点交叉基础上，本文改进的交叉算子采用两点三段随机交叉，基本思想是对相互配对的父个体P1、P2随机产生两个交叉点，将父个体分成三段，再随机产生一个介于0～2之间的整数X，X∪{0，1，2}，交叉操作按照公式（2）进行。

P1，P2前半部分进行交叉，X=0P1，P2中间部分进行交叉，X=1P1，P2后半部分进行交叉，X=2 （2）

假设父个体为P1=5714236，P2=1435726，交叉过程为：（1）随机选择两个交叉点。假设P1=57|142|36，P2=14|357|26。（2）确定交叉区域。假设X=1，根据公式（2）中间部分进行交叉。

（3）将P2的中间部分加到P1前面，P1的中间部分加到P2前面，即得到P′1=3575714236，P′2=1421435726。

（4）删除重复节点。P′1的重复节点为3、5、7，对于节点3，比较2-3-6和6-3-5之间的路程d（2-3-6）和d（6-3-5），如果d（2-3-6） >d （6-3-5），就删除P′1后面的3，否则删除前面的3。以同样的方法处理P′1节点5和7，以及P′2的重复节点1、4、2。重复节点删除完成后，得到交叉后的新个体P*1和P*2。改进的交叉算子克服了传统两点交叉中父个体两端的基因要么不改变，要么由于节点重复而被盲目改变的缺陷，染色体变化能力得到提高，保证了种群多样性，同时通过重复节点邻接路径长度比较，将路程长的重复节点删除，提高了个体质量和算法的收敛性。

3.6 变异算子

倒位变异算子是指在父个体中随机顺序地选取两个城市并记为c*和c#，使c*和c#之间的编码倒序排列，并将c*和c#相邻排列，产生一个新个体[13-14]。假设有父个体P=1 732 564，随机选择的两城市为3和6，则产生的新个体P*=1 736 524。本文改进的变异算子采用启发式倒位变异算子，其基本思想是：首先随机选择一个城市c，除去c、cRight、cLeft节点，在剩余节点中选择距离c最近的城市c′，再将cRight到c′之间的城市编码倒位产生新个体。例如上述父个体P=1732564，随机选择一个城市7，城市2和4是离城市7最近的两个城市，若c′选城市2，则倒位后产生的新个体P*=1723564，若c′选城市4，则倒位后产生的新个体P*=1746523。

3.7 改进的遗传算法流程

为了更加清晰地表述本文提出的算法求解TSP问题流程，用图1所示流程图来描述算法。

4 TSP问题求解系统体系结构

求解TSP问题系统包括界面模块和改进遗传算法应用模块，系统体系结构如图2所示。

界面模块主要由城市布局选择和优化结果显示两部分组成。本文提出的改进遗传算法用改进遗传算法应用模块来实现，此模块主要由路径编码、贪心优化初始种群、适应度函数、最优保存策略和掺杂算子选择、两点三段随机交叉算子和启发式倒位变异算子实现等几部分组成。

5 实验及结果分析

依据标准的CHN144城市坐标数据，分别用基本遗传算法（SGA）和本文改进的遗传算法（IGA）对CHN144中的城市进行20次随机实验。采用C语言编程，实验控制参数设置如下：种群规模N=150，交叉概率pc=0.9，变异概率pm=0.2，终止条件中最优个体保持代数M=200，实验结果见表1。

实验结果表明，本文IGA算法在收敛性上要明显好于SGA算法，且IGA算法的最优解和平均解都优于SGA算法，进一步说明了用贪心算法优化初始种群和用最优保存策略及在选择操作中引入掺杂算子，在利用局部寻优能力改善种群质量、加速寻优速度、提高算法搜索效率方面有着重要作用。IGA算法采用的两点三段随机交叉操作及启发式倒位变异操作，较好解决了群体多样性和收敛速度的矛盾，使算法具有较强的鲁棒性。

6 结语

TSP问题是计算机、物流等领域许多复杂问题的抽象模型，具有良好的应用前景，对TSP问题进行研究具有重要意义。本文针对TSP问题提出了改进的遗传算法，并给出了求解系统的体系结构。仿真实验表明，对144个城市求解TSP问题得到的结果优于基本遗传算法。本文改进的遗传算法可应用于任何类型的优化操作中，通用性好、实用价值高。

参考文献：

[1] 晏雨.改进的遗传算法和分布估计算法求解TSP问题[D].重庆：重庆理工大学，2013.

[2] 王建忠，唐红.TSP问题的一种快速求解算法[J].微电子学与计算机，2011，28（1）：7-10.

[3] 张芳琴.改进遗传算法在TSP组合优化问题中的应用[J].高师理科学刊，2014，34（5）：1-4.

[4] 姜群，晏雨.改进的遗传算法在TSP问题中的应用[J].重庆理工大学学报：自然科学版，2012，26（9）：96-99.

[5] 姚明海，王娜，赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用，2013，49（14）：60-65.

[6] 于莹莹，陈燕，李桃迎.改进的蚁群遗传算法求解旅行商问题[J].计算机仿真，2013，30（11）：317-320.

[7] 杨玉，李慧，戴红伟.改进量子交叉遗传算法在TSP问题中的应用[J].南京师范大学学报：工程技术版，2012，12（3）：43-48.

[8] 候建花.TSP遗传算法的改进及其并行化研究[D].成都：成都理工大学，2004.

[9] 蒋然，张光桃.基于预分类的逆变异分类器算法[J].软件， 2015， 36（2）： 39-44.

[10] 于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策，2014，29（8）：1483-1488.

[11] 周泽岩，张喜.基于改进遗传算法的TSP问题求解的研究[J].物流技术，2012，31（9）：220-223.

[12] 陈智军.一种改进的求解TSP问题的遗传算法[J].软件导刊，2011，10（2）：52-54.

[13] 谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用，2002（8）：58-60，245.

[14] 杜宗宗.基于遗传算法的移动机器人路径规划研究[D].无锡：江南大学，2009.

（责任编辑：杜能钢）