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

来源:用户上传      作者:

　　摘 要：TSP問题是一个著名的NP难问题，提出一种改进的遗传算法用来解决该问题。为了处理传统遗传算法中出现的早熟、收敛速度慢、收敛结果不准确等问题，分别在选择、交叉、变异3个阶段对算法进行优化。设计一个动态适应度函数;放弃轮盘赌策略，采用无放回式优良个体多复制原则，防止优良基因被破坏;按照群体适应度值分布，动态改变交叉率及变异率;引入相似度概念，避免出现近亲交配现象，影响种族进化;寻找并记忆优良基因簇，加快收敛过程。实验结果证明，改进遗传算法的优化性能提升了17.04%。
　　关键词：TSP问题;遗传算法;动态适应度函数;优良个体多复制;相似度;优良基因簇
　　DOI：10. 11907/rjdk. 192387
　　中图分类号：TP301   文献标识码：A                 文章编号：1672-7800（2020）003-0116-04
　　Improvement of Genetic Algorithm for Solving TSP Problem
　　LI Qing1， WEI Guang-cun1，2， GAO Lan1， QIU Guo-hua1， XIAO Xin-guang1
　　（1.College of Computer Science and Engineering， Shandong University of Science and Technology，Qingdao 266590，China;
　　2.Department of Informaion Engineering，Shandong University of Science and Technology，Tai’an 271019，China）
　　Abstract：TSP problem is a well-known NP-hard problem. This paper proposes an improved genetic algorithm to solve this problem. In order to solve the problems of premature ripening， slow convergence and inaccurate convergence results in traditional genetic algorithms， the algorithm is optimized in three stages： selection， crossover and mutation. This paper designs a dynamic fitness function， then abandons the roulette strategy and adopts the principle of non-return-type good multiple replication to prevent the destruction of good genes; and then dynamically changes the crossover rate and mutation rate according to the distribution of group fitness values. The concept of similarity is introduced to avoid the phenomenon of inbreeding and affect ethnic evolution. The algorithm finds and memorizes good gene clusters， and accelerates the convergence process to design a dynamic fitness function. It abandons the roulette strategy and adopts the principle of non-return-type good individual multiple replication to prevent good genes from being destroyed. According to the group fitness value distribution， the crossover rate and mutation rate are dynamically changed; the concept of similarity is introduced to avoid inbreeding that affects racial evolution. Finally， find and remember good gene clusters are found and remembered to speed up the convergence process. Experiments show that the optimization performance of the improved genetic algorithm is improved by 17.04%.
　　Key Words： TSP problem; genetic algorithm; dynamic fitness function; excellent individual multiple replication; the concept of similarity; good gene clusters 　　0 引言
　　TSP问题即著名的旅行商问题，是指从多个城市组成的行走路线集合中找到最优城市序列（最优解）。目前，已有很多学者从不同方面对遗传算法进行改进以解决TSP问题，并取得了较好效果。如蒋然[1]给出求解TSP问题系统的体系结构;孙文彬等[2]借助去交叉和小角操作进一步优化TSP解路径;肖世昌等[3]在遗传算法中加入灾变算子，可以使算法跳出局部最优;谢艳丽等引入拉普拉斯算子用来改进交叉算子，并结合黄金分割法对变异算子作进一步改进，提高了算法收敛速度。针对遗传算法在搜索过程中收敛过慢和容易早熟的问题[4]，杨文等[5]对种群进化中被淘汰的个体进行二次进化，将可能影响全局最优解的基因尽可能提取出来;杨玉等[6]在基本遗传算法基础上，提出改进型多宇宙量子交叉算子，利用不同宇宙间的信息交流提高算法搜索效率。
　　但以上遗传算法改进方法仍然存在缺陷，本文在原始遗传算法基础上，对适应度函数、选择算子、交叉算子、变异算子加以改造，标定适应度值，采用优良基因多复制原则选择个体，动态改变交叉、变异算子;通过个体相似度计算，避免出现近亲“交配”现象;引入基因簇概念，防止优良基因被破坏。实验结果证明，改进遗传算法具有更好的优化性能，收敛精度也得到了提高。
　　1 TSP數学模型
　　TSP问题是一个NP难问题[7-8]，问题一般描述为：现有n个城市，一个推销员从某城市启程，走完这n个城市，每个城市只可走一次，求选择何种行程才能使总路程最短[9-10]。
　　现将上述问题转换为数学模型：设G = （V，E）为赋权无向图，V = {1，2，3，…，n}为顶点集，E为边集，各顶点间距离为[Cij]，已知[Cij][∈]（0，+∞），i，j[∈]V），[Wij]（i，j∈V）是节点i和节点j对应边的权值。TSP可描述为求T={[t1]，[t2]，[t3]，…，[tn]}，[ti∈]V（i = 1，2，3，…，n）的一个排序，求解式（1），其中[tn+1]= [t1]。
　　2 传统遗传算法及不足
　　2.1 传统遗传算法
　　遗传算法（Genetic Algorithm，GA）是一种通过模仿自然进化过程搜索最优解的方法[13]。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定，不需要确定规则就能自动获取与指导优化搜索空间，自适应地调整搜索方向。
　　选择算子、交叉算子和变异算子构成遗传算法中的基本算子，传统遗传算法计算过程如下：首先对个体进行编码，初始化种群，计算每个个体适应度值，通过轮盘赌方法[11]挑选下一代种群初始个体，然后通过个体间的交叉操作及个体自身变异操作形成新一代种群。按照该方法不断迭代，直到达到终止条件为止。算法流程如图1所示。
　　2.2 传统遗传算法的不足
　　传统遗传算法存在一些自身的局限性：①容易在未得到最优解或满意解之前收敛，即出现“早熟”现象[12];②优良个体基因遭到破坏，有用的模板消失;③在接近最优解时，收敛缓慢;④无法自适应不断进化的种群[13-16]。
　　3 传统遗传算法改进
　　3.1 适应度函数改造
　　在种群进化初期，如果出现一个适应度很高的个体，种群会往该个体方向进化，从而破坏了种群的多样性，容易出现“早熟”现象。
　　在种群进化后期，种群个体间相似度较高，如果仍用种群进化初期的适应度函数尺度进行优良个体选择，选取的优良个体则不具备代表性，收敛会变得缓慢。
　　为了解决上述问题，设计一个能够根据种群进化过程动态改变适应度值变化尺度的适应度函数，如式（2）所示。f是某一个体适应度值，[fmin]是本代种群中的最小适应度值，[fmax]是本代种群中的最大适应度值，[α]是一个常数，是为了防止出现分母为0的情况。
　　当种群个体间相似度较高时，即种群中的最大适应度值和最小适应度值差别较小时，相应个体F值变大，群体适应度值范围扩大，提高了选择能力;当种群个体间相似度较低时，即种群中的最大适应度值和最小适应度值差别较大时，相应个体F值变小，群体适应度值范围缩小，降低了选择能力，从而可以在种群进化各个阶段，自适应地改变适应度函数，以改变选择能力。
　　3.2 无放回式优良个体多复制
　　传统遗传算法在选择父代个体时，一般采用轮盘赌选择（Roulete Wheel Selection）算法。该算法根据个体适应度值占种群个体适应度值和的比值进行父代个体选取，并且是一种有放回的选择算法。该选取策略会极大地提高适应度值高个体的被选择概率，容易导致适应度值高的个体迅速占领整个种群，无法跳出局部最优。
　　为了解决该问题，在选择个体时，采用无放回式优良个体多复制选择策略：①设定需要选取的个体数n;②根据轮盘赌选择（Roulete Wheel Selection）算法，无放回地选取n个个体;③将n个个体按照适应度值由大到小进行排序，分别将前1/3的优良个体复制两份，中间1/3的个体复制一份;④父代交配种群经过交叉、变异，再次沿用无放回式优良个体多复制原则，小概率地保留种群中适应度值较小的个体。
　　3.3 相似度概念
　　在交叉算子选择待交叉个体时，首先计算两个待交叉个体的相似度，将待交叉个体1表示为 T1 ={[t1]，[t2]，[t3]，…，[tn]}，待交叉个体2表示为 T2={[t1]，[t2]，[t3]，…，[tn]}，D（T1， T2）表示两个体之间的相似度，这里相似度用汉明距离（Hamming Distance）表示。若两个体相似度大于设定阈值，则将其中一个个体舍弃，引用相似度概念，可很大程度上避免“近亲交配”现象的发生，维持种群多样性。
　　3.4 自适应交叉、变异算子
　　根据种群进化的不同阶段，动态改变交叉、变异算子。在种群进化初始阶段，采用强交叉，弱变异;当种群进化缓慢，陷入局部最优解时，则采用弱交叉，强变异。 　　[Fmax]为该代种群中最高的个体适应度值，[F]为该代种群所有个体平均适应度值，f为种群中最高的个体适应度值与种群所有个体平均适应度值的差值，如式（3）所示。
　　σ为Sigmod函数，将适应度值映射到0～1概率区间，如式（4）所示。
　　α为交叉率自适应参数，表示为[α=σ]，根据种群进化中个体适应度值分布自适应改变交叉率。β为变异率自适应参数，表示为[β=1-σ]，根据种群进化中个体适应度值分布自适应地改变变异率。a为交叉率基，b为变异率基，[P]为交叉率，表示为[Pc=αa]，[Pv]为变异率，表示为[Pv=βb]。
　　3.5 优良基因簇
　　在适应度值高的个体中，往往有相同或相似的基因组合区间，可将这些基因组合成为优良基因簇。记忆优良基因簇可以防止优良基因被破坏，加速收敛过程。
　　个体基因中有正向基因与反向基因，正向基因促进个体成长，反向基因则阻碍个体成长，多个基因构成基因簇。在求解TSP问题中，要想搜索到行走最短路径，并且尽量减少搜索时间，可以将线路中部分未交叉的较短路径提取出来，该部分路径中的城市有序集合即为一个基因簇。至此，一个基因簇可以看作一个城市，从而减少总城市数量，加快收敛速度。
　　本文采用代际子空间寻优基因簇策略。
　　（1）划分寻优空间。找出个体中所有连续未交叉路径中的城市有序集合，集合数量为n，将这些集合称为基因簇。据此，个体被n个基因簇所划分。所有个体按该方法进行寻优空间划分，所有m个个体根据适应度值降序排列为：
　　将排序后的个体放到集合[S]中。
　　（2）基因簇寻优。选取排序后的前[ηm]个个体，[η]为设定好的选取比例。
　　[ηm]个个体按照排序在前权重高的原则，分别给予一个权重[λi]，找出个体间的相同基因簇记录下来。对于个体间的相似基因簇，根据基因簇适应度值[g.]与权重[λi]乘积的值，保留具有较大值的基因簇。
　　（3）父代交叉，子代基因簇生成。将每个基因簇看作一个基因，交叉时两个个体互换部分基因簇，除基因簇外的基因进行自由交叉。生成子代个体后，寻找新的基因簇。
　　3.6 算法总结
　　通过重新设计适应度函数和自适应的交叉、变异算子，引入相似度、优良基因簇概念等对遗传算法进行改进，具体算法流程如图2所示。
　　4 实验及结果
　　4.1 实验
　　为了验证改进遗传算法的性能，以34个中国城市的经纬度坐标为测试数据集，分别采用标准遗传算法（Standard GA）和改进遗传算法（Improved GA）随机计算20次。种群规模N=100，交叉率[Pc]=0.7，变异率[Pv]=0.06，进化代数（迭代次数）G=10 000。基本遗传算法和改进遗传算法所求最短距离如表1所示，进化曲线分别如图3、图5所示，TSP问题最优解路线分别如图4、图6所示。
　　4.2 结果
　　改进遗传算法相比基本遗传算法，在迭代次数、交叉率、变异率等参数相同的情况下，获得了较好的最优解，加快了收敛速度，可以更好地跳出局部最优，降低了“早熟”现象发生率。
　　5 结语
　　标准遗传算法采用固定的交叉率、变化率，适应度函数无法适应不断进化的种群，采用“轮盘赌”算法容易让部分较优良个体迅速占领种群，从而产生“早熟”现象。本文通过重新设计适应度函数和自适应的交叉、变异算子，引入相似度概念、优良基因簇等方法对遗传算法进行改进，可一定程度上避免“早熟”现象的发生，加快收敛速度，并能够跳出局部最优解，算法性能得到较大提升。
　　通过研究“早熟”、容易陷入局部最优、收敛速度慢等问题，发现在种群进化过程中，在保留适应度值较高个体的同时，需加入部分适应度值较低的个体，缓解“早熟”现象。适应度函数需随种群个体适应度值分布的变化而动态改变，从而使种群进化跳出局部最优，并且提高收敛速度。
　　本文对传统遗传算法进行改进后，虽然使算法性能得到了较大提升，但在解决种群进化容易陷入局部最优解问题方面效果还不理想，接下来会引入Alopex算法，对遗传算法作更深入的研究。
　　参考文献：
　　[1]蒋然. 改进遗传算法在TSP问题中的应用[J]. 软件导刊，2016，15（12）：127-129.
　　[2]孙文彬，王江. 一种基于遗传算法的 TSP问题多策略优化求解方法[J]. 地理与地理信息科学，2016，32（4）：1-4.
　　[3]肖世昌，孙树栋，国欢. 灾变遗传算法求解带时间窗的车辆调度问题[J]. 计算机应用研究，2014，31（12）：3568-3571.
　　[4]谢燕丽，许春林，姜文超. 一种基于交叉和变异算子改进的遗传算法研究 [J]. 计算机应用与发展，2014，24（14）：80-83.
　　[5]杨文，顾保磊，戴光耀. 一种避免早熟收敛的改进遗传算法[J]. 软件导刊，2009，8（3）：53-55.
　　[6]杨玉，李慧，戴红伟. 改进量子交叉遗传算法在TSP问题中的应用[J]. 南京师范大学学报（工程技術版），2012，12（3）：43-48.
　　[7]杨华芬，魏延. 一种求解TSP问题的改进遗传算法[J]. 重庆工学院学报（自然科学版），2007，21（5）：86-90.
　　[8]孙文彬，王江. 一种基于遗传算法的TSP问题多策略优化求解方法[J]. 地理与地理信息科学，2016（4）：1-4.
　　[9]于莹莹，陈燕，李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策，2014，29（8）：1483-1488.
　　[10]佘智勇，庄健敏，翟旭平. 基于改进的 TSP 模型和模拟退火算法路径规划研究[J]. 工业控制计算机，2018（2）：56-57.
　　[11]刘青凤，李敏. 基于遗传算法的 TSP 问题优化求解[J]. 计算机与现代化，2008（2）：43-44，56.
　　[12]蒋腾旭，谢枫. 遗传算法中防止早熟收敛的几种措施[J]. 计算机与现代化，2006（12）：58-60.
　　[13]曲志坚，张先伟，曹雁锋，等. 基于自适应机制的遗传算法研究[J]. 计算机应用研究，2015，32（11）：3222-3225，3229.
　　[14]于光帅，于宪伟. 一种改进的自适应遗传算法[J]. 数学的实践与认识，2015，45（19）：259-264.
　　[15]杨从锐，钱谦，王锋，等. 改进的自适应遗传算法在函数优化中的应用[J].  计算机应用研究，2018，35（4）：1042-1045.
　　[16]刘荷花，崔超，陈晶. 一种改进的遗传算法求解旅行商问题[J]. 北京理工大学学报，2013，33（4）：390-393.
　　（责任编辑：黄 健）
　　收稿日期：2019-10-06
　　基金项目：山东省自然科学基金项目（ZR2018BF005）;山东省重点研发计划项目（2018GGX101011）
　　作者简介：李庆（1995-），男，山东科技大学计算机科学与工程学院硕士研究生，研究方向为云计算与大数据处理;魏光村（1971-），男，博士，山东科技大学计算机科学与工程学院副教授、硕士生导师，研究方向为人工智能与物联网工程;高兰（1994-），女，山东科技大学计算机科学与工程学院硕士研究生，研究方向为计算机控制与嵌入式系统;仇国华（1994-），女，山东科技大学计算机科学与工程学院硕士研究生，研究方向为云计算与大数据处理;肖新光（1995-），男，山东科技大学计算机科学与工程学院硕士研究生，研究方向为人工智能。本文通讯作者：魏光村。
转载注明来源:https://www.xzbu.com/8/view-15217537.htm