基于遗传算法的TSP问题优化方法

来源:用户上传      作者:

　　摘 要：针对传统遗传算法在巡回商旅问题优化计算中存在的弊端——收敛速度慢，迭代次数多。在传统遗传算法基础上，设计出一种加入人工选择和定向突变的优化改进算法。该优化算法通过人工方法保存具有有利变异个体和淘汰具有不利变异个体，有利变异个体进行杂交和变异，从而提高遗传算法的收敛速度，减少遗传算法的迭代次数。同时针对遗传算法易陷入局部最优解的情况，在优化算法中引入自適应参数算法，针对遗传算法的不同阶段，实现杂交概率和变异概率的自适应调节，防止算法陷入局部最优解。最后，采用国际标准的TSP测试集（TSPLIB）对优化算法的优良性进行验证，实验表明，对比其他算法，该优化算法在TSP最优解的质量上提高10%左右。
　　关键词：TSP；遗传算法；人工选择；定向突变；自适应算法
　　中图分类号：TP3-05 文献标识码：A
　　1 绪论
　　旅行商问题（Traveling Salesman Problem，）是路径规划和组合优化领域中著名的NP-hard问题[1，2]，网络路由的大规模优化[3]、超远距离泵送混凝土造价控制技术[4]、车辆路线设计[5]等均是典型的TSP。目前，求解TSP的算法可分为精确算法（exact algorithm）和近似算法（approximation algorithm）两类。Wang等在分析基于智能算法的TSP求解方法优缺点[6，7]的基础上，指出遗传算法受参数选择和数据集分布结构的影响最小，陷入局部最优的概率最小。
　　遗传算法是以适应度[8]为依据的逐代搜索过程。传统的遗传算法，往往存在诸多问题，如收敛速度慢，最优解质量差，容易陷入局部最优等。针对传统遗传算法在旅行商问题求解中存在的弊端，本文对传统遗传算法的几个步骤进行优化，提出改进的遗传算法——在原有的基础上加入新型的进化策略，从而提升最优解的质量，降低最优解的误差率，有效控制遗传算法早熟收敛性。
　　2 遗传算法优化改进
　　2.1 人工选择法
　　传统遗传算法[9]杂交过程的实现往往是从上一代种群中随机选择两个个体进行杂交，对于杂交生成的子代，采取直接替代父代的方法，但是在替代的过程中存在子代的适应度低于父代，出现劣势个体的情况，使整个算法的收敛速度变慢，在遗传代数一定的条件下，最终解的误差率上升。
　　针对上述情况，本文在传统杂交过程和变异基础上进行优化。我们对杂交生成的四个子代个体的适应度进行重新排序，选择其中最优秀的两个个体进入下一代种群，同时在变异过程中也进行人工选择，变异前后的两个个体选择出适应度高的进入下一代群体。人工选择会使种群总体的进化向着适应度不断提高的方向进行，尽可能保证群体中的优势不会在变异过程中淘汰掉，使群体优秀基因能够遗传下去，整个遗传算法的收敛速度得到提高。
　　2.2 定向突变法
　　Fmax代表了群体当中的最大适应度值，Favg代表了群体当中的平均适应度值。由上式可知，群体最大适应度和平均适应度差值越大，Pc和Pm的值相应会越小，而K1和K2在这个过程代表着自适应调节力度的大小。通过自适应参数算法的引入，在遗传过程根据实际情况及时调整Pm和Pc，遗传算法将具有更好的灵活性，收敛速度提高，并且陷入局部最优解的可能性降低。
　　3 性能分析与实验结果
　　基于上述分析，采用C语言对求解TSP问题的改进遗传算法进行设计实现，为了验证算法的正确性和有效性，本文选取了国际标准的TSPLIB测试集中的两组数据，将本文算法求解得到的最优路线与文献[12]中得到的最优解进行比对，结果如下图1，图2所示。
　　由以上两组对比可知，在最优路线的求解上，本文算法相比较于文献[12]中的算法具有一定优势，验证了本文算法的优势性。
　　4 结语
　　本文针对TSP问题的求解在传统遗传算法的基础上引入人工选择，定向突变，和自适应参数算法，设计出一套优化算法。优化算法具有快速的收敛能力，能大幅改善种群的质量，极大程度降低所得解的误差率，并能动态调节杂交概率参数和变异概率参数，防止算法陷入局部最优解。实验结果表明，与其他四种算法进行比较，本文算法在解的误差率上具有很大优势。
　　当然，本文提出的算法还需要做进一步的优化工作。在种群规模迅速扩大的时候，算法的运行时间也会变长，程序会容易陷入局部最优解当中，这些都需要在以后的研究工作中加以改进。
　　参考文献：
　　[1]张芳琴.改进遗传算法在TSP组合优化问题中的应用[J].高师理科学刊，2014，34（05）：1-4.（ZHANG F Q.Application of improved genetic algorithm to TSP combinatorial optimization problem[J].Science of Science，2014，34（05）：1-4.）
　　[2]杜立智，陈和平，符海东.NP完全问题研究及前景剖析[J].武汉工程大学学报，2015，37（10）：73-78.
　　[3]徐津.基于遗传免疫粒群优化的网络拥塞控制方法[D].郑州大学，2012.（XU J.Network congestion control based on genetic immune particle swarm optimization[D].Zhengzhou University，2012.）
　　[4]马行耀.遗传算法用于超远距离泵送混凝土造价控制技术分析[J].混凝土，2018（05）：94-97.
　　[5]李珍萍，胡娩霞，吴凌云.基于遗传算法的成品油二次配送车辆路径问题研究[J].数学的实践与认识，2018，48（09）：189-198.
　　[6]WANGJ，ERSOYO，HEM，et al.Multi-offspring genetic algorithm and its application to the traveling salesman problem[J].Applied Soft Computing，2016，43：415-423. 　　[7]TOBIASM，OLA S.Removing and adding edges for the traveling salesmen problem[J].Journal of theACM，2016，63（1）：2-29.
　　[8]張大科，钱谦.一种新型自适应遗传算法在多峰函数优化中的应用[J].软件导刊，2018，17（06）：85-87+91.
　　[9]邓先习.遗传算法求解 TSP 问题的研究与改进[D].沈阳：东北大学信息科学与工程学院，2008.（DENG X X.Genetic.algorithm to solve TSP research and improvement[D].Shenyang：Northeastern University，School of Information Science and Engineering，2008.）
　　[10]Zu Yun-xiao and Zhou Jie.Multi-user cognitive radio network resource allocation based on the adaptive niche immune genetic algorithm[J].Chinese Physics B，2012，21（1）.
　　[11]Jianfeng Yu，Yuehong Yin.Assembly line balancing based on an adaptive genetic algorithm[J].The International Journal of Advanced Manufacturing Technology，2010，48（1-4）：347-354.
　　[12]于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J].控制策，2014，（8）：1483-1488.（YU Y Y，CHEN Y，LI T Y.An improved genetic algorithm for traveling salesman problem[J].Control Strategy，2014，（8）：1483-1488.
　　作者简介：陈洋卓（1987-），男，硕士，实验师，研究领域为智能优化算法；李青青（1998-），女，本科；罗天扬（1997-），男，本科；朱林丹（1998-），女，本科；肖奇（1996-），男，本科。
转载注明来源:https://www.xzbu.com/1/view-15323993.htm