内容发布更新时间 : 2024/11/17 23:37:12星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

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

作者：蒋然

来源：《软件导刊》2016年第12期

摘 要：旅行商问题是典型的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问题

龙源期刊网 http://www.qikan.com.cn

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 贪心算法优化初始种群

龙源期刊网 http://www.qikan.com.cn

针对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。