遗传算法的TSP问题优化方法分析范文

摘要:针对传统遗传算法在巡回商旅问题优化计算中存在的弊端———收敛速度慢，迭代次数多。在传统遗传算法基础上，设计出一种加入人工选择和定向突变的优化改进算法。该优化算法通过人工方法保存具有有利变异个体和淘汰具有不利变异个体，有利变异个体进行杂交和变异，从而提高遗传算法的收敛速度，减少遗传算法的迭代次数。同时针对遗传算法易陷入局部最优解的情况，在优化算法中引入自适应参数算法，针对遗传算法的不同阶段，实现杂交概率和变异概率的自适应调节，防止算法陷入局部最优解。最后，采用国际标准的TSP测试集(TSPLIB)对优化算法的优良性进行验证，实验表明，对比其他算法，该优化算法在TSP最优解的质量上提高10%左右。

关键词:TSP;遗传算法;人工选择;定向突变;自适应算法

1绪论

旅行商问题(TravelingSalesmanProblem，)是路径规划和组合优化领域中著名的NP-hard问题［1，2］，网络路由的大规模优化［3］、超远距离泵送混凝土造价控制技术［4］、车辆路线设计［5］等均是典型的TSP。目前，求解TSP的算法可分为精确算法(exactalgorithm)和近似算法(approximationalgorithm)两类。Wang等在分析基于智能算法的TSP求解方法优缺点［6，7］的基础上，指出遗传算法受参数选择和数据集分布结构的影响最小，陷入局部最优的概率最小。遗传算法是以适应度［8］为依据的逐代搜索过程。传统的遗传算法，往往存在诸多问题，如收敛速度慢，最优解质量差，容易陷入局部最优等。针对传统遗传算法在旅行商问题求解中存在的弊端，本文对传统遗传算法的几个步骤进行优化，提出改进的遗传算法———在原有的基础上加入新型的进化策略，从而提升最优解的质量，降低最优解的误差率，有效控制遗传算法早熟收敛性。

2遗传算法优化改进

2．1人工选择法传统遗传算法［9］杂交过程的实现往往是从上一代种群中随机选择两个个体进行杂交，对于杂交生成的子代，采取直接替代父代的方法，但是在替代的过程中存在子代的适应度低于父代，出现劣势个体的情况，使整个算法的收敛速度变慢，在遗传代数一定的条件下，最终解的误差率上升。针对上述情况，本文在传统杂交过程和变异基础上进行优化。我们对杂交生成的四个子代个体的适应度进行重新排序，选择其中最优秀的两个个体进入下一代种群，同时在变异过程中也进行人工选择，变异前后的两个个体选择出适应度高的进入下一代群体。人工选择会使种群总体的进化向着适应度不断提高的方向进行，尽可能保证群体中的优势不会在变异过程中淘汰掉，使群体优秀基因能够遗传下去，整个遗传算法的收敛速度得到提高。

2．2定向突变法基因突变是生物产生新基因的根本途径，是生物遗传变异的根本来源。优势个体发生基因突变往往是有害的，它们所携带的优势基因往往会突变成劣势基因，导致个体在遗传过程失去了竞争优势，从而被淘汰掉。相反，劣势个体发生基因突变带来的是利多害少，突变之后的个体适应度将会得到提高，使得个体具有更强的竞争力，整个群体的进化也因此向着适应度增加的方向进行。因此，针对基因突变的特点，本文提出了一种新型的突变策略，即定向突变法。假设在初始群体遗传到第X代的时候，此时群体的个体最大适应度是F(x)max，最小适应度是F(x)min，于是取整个群体的平均适应度:在一定的突变概率P下，对于在第X代的任意个体的适应度F(xi)来讲，满足下列公式:上述公式是定向突变法的核心，定向突变的实质在于保护优势个体的优势基因，同时促进劣势个体进行主动突变。在整个突变的过程中，群体的基因多样性不会因为优势个体的保留而减少，因为存在劣势个体的突变，保证遗传算子正常发挥进化和重组效应，从而提高群体的多样性。

2．3自适应参数算法传统遗传算法在遗传过程当中，杂交概率Pc和变异概率Pm是始终不变的。通过理论分析可知，当处在种群迭代的早期，个体之间的差异性很大，种群的多样性非常丰富，因此对于此时的交叉概率和变异概率来说，其取值可以变得相对小一些。随着迭代次数的增多，种群之间的差异性减少，多样性也随之减少，将会导致算法的结果会陷入局部最优解，并且影响到算法的收敛速度，此时本文需要增大变异概率Pm和交叉概率Pc。因此本文引入自适应［10，11］参数K1和K2，通常自适应参数算法写成: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．

［2］杜立智，陈和平，符海东．NP完全问题研究及前景剖析［J］．武汉工程大学学报，2015，37(10):73-78．

［3］徐津．基于遗传免疫粒群优化的网络拥塞控制方法［D］．郑州大学，2012．

［4］马行耀．遗传算法用于超远距离泵送混凝土造价控制技术分析［J］．混凝土，2018(05):94-97．

［5］李珍萍，胡娩霞，吴凌云．基于遗传算法的成品油二次配送车辆路径问题研究［J］．数学的实践与认识，2018，48(09):189-198．

［8］张大科，钱谦．一种新型自适应遗传算法在多峰函数优化中的应用［J］．软件导刊，2018，17(06):85-87+91．

［9］邓先习．遗传算法求解TSP问题的研究与改进［D］．沈阳:东北大学信息科学与工程学院，2008．

［12］于莹莹，陈燕，李桃迎．改进的遗传算法求解旅行商问题［J］．控制策，2014，(8):1483-1488．

作者：陈洋卓 李青青 罗天扬 朱林丹 肖奇 单位：湘潭大学信息工程学院