遗传模拟退火算法

遗传模拟退火算法

——黑龙江TSP问题

Genetic Simulated Annealing Algorithm： Heilongjiang TSP Problem

姚君 YAO Jun

（黑龙江科技大学理学院，哈尔滨150022）

（College of Science，Heilongjiang University of Science and Technology，Harbin 150022，China）

摘要：以黑龙江省29个城市构造TSP问题，通过对实验数据的分析，得出了遗传模拟退火算法在求解精度上优于遗传算法或模拟退火算法。遗传模拟退火算法利用了模拟退火算法局部精确的求解能力补充了遗传算法在局部求解不够精确的弊端，从而加快了求解TSP问题的效率，同时，又将蚁群算法和遗传模拟退火算法做比较，从结果可以看出遗传模拟退火算法求解效果较好。

Abstract： Based on the analysis of experimental data of the urban structure TSP problem of 29 cities in Heilongjiang Province， it is concluded that genetic simulated annealing algorithm is better than genetic algorithm or simulated annealing algorithm in solving the precision. Genetic Simulated Annealing Algorithm （GA）， which utilizes the local exact solution ability of the simulated annealing algorithm，complements the drawbacks of the genetic algorithm which is not accurate enough to solve the problem. The results show that the genetic simulated annealing algorithm is effective.

关键词：遗传模拟退火算法；TSP问题；蚁群算法

Key words： genetic simulated annealing algorithm；TSP problem；ant colony algorithm

中图分类号：O1-0 文献标识码：A 文章编号：1006-4311（2016）36-0206-03

0 引言

传统的遗传算法容易过早收敛，而且在搜索过程中有可能搜索到最优解然后又发散出去的现象。模拟退火算法在解的质量与求解时间长之间存在矛盾，为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大时，缺乏可行的解决途径。遗传算法和模拟退火算法的直接互补性体现在：遗传算法虽把握总体的能力较强，但局部搜索能力较差；模拟退火算法具有较强的局部搜索能力，为了克服遗传算法和模拟退火算法各自的缺点，将遗传算法和模拟退火算法相互结合，取长补短，这就形成了模拟退火遗传算法，简称GASA。

1 黑龙江旅行商问题

TSP问题是比较典型的组合优化问题，因其应用范围广，研究价值高，所以成为学者们研究重点，求解方法也有许多。但是一些常规的算法往往存在一些弊端，如后期计算不够精确，容易造成过早收敛等。TSP问题是研究算法性能的经典问题，具有广泛的应用背景。

选取黑龙江省29个城市构造TSP问题，即求得一条将黑龙江省29个城市旅行一遍，且每个城市有且仅经过一次的最短路线。表1是黑龙江省29个城市的坐标。

2 算法比较

实验过程中，染色体的长度L等于城市个数，即：29。种群的规模pop-size定为100，各个参数确定如下：将退火过程参数a=0.9，交叉概率和变异概率Pc=0.5，Pm=0.1，迭代结束的依据是q=100。单个的遗传算法和模拟退火法里用到的参数也这样设定。

首先将黑龙江省29个城市的坐标放入一个数组中，记为：citys=[1 544 636；2 532 658；3 624 518；4 815 631；5 636 501；6 715 202；7 435 912；8 728 657；9 720 1016；10 1014 729；11 647 1022；12 517 1057；13 532 1150；14 435 936；15 829 451；16 421 928；17 720 357；18 548 1049；19 522 615；20 514 755；21 638 1111；22 425 1111；23 638 659；24 659 801；25 739 1230；26 455 711；27 838 607；28 742 856；29 604 558]。

2.1 运用遗传算法

遗传算法，简称GA，是以自然选择理论和遗传变异理论为基础的仿生学的概率性搜索迭代算法。

遗传算法求解TSP的算法描述如下：

步骤1 设定种群的规模、遗传变异概率pm、遗传交叉概率pc，初始化当前代数g=0；

步骤2 使用算法，随机产生一个初代种群，在将种群中所有个体的适应度计算出来；

步骤3 根据轮盘赌策略选择父代1和父代2；

步骤4 产生两个0～1的随机数p1和p2；

步骤5 若p1

步骤6 若p2

步骤7 若产生子代种群总数等于规定最大总群个体量，就向下顺序执行步骤8，不然就跳到步骤3；

步骤8 计算新产生种群的适应度（遍历的距离），并用新产生的子代作为新的父代；

步骤9 check目前状态是否达到结束条件，如果达到，则结束迭代计算并输出得到的最优解，并跳转到步骤3；

最优解为：R1=[1 19 2 26 20 16 7 14 22 12 18 13 25 21 11 9 28 24 8 4 10 27 15 6 17 5 3 29 23]；

程序求解结果如图1。

即最佳路线为：哈尔滨—双城—阿城—五常—尚志—宁安—海林—牡丹江—绥芬河—鸡西—七台河—密山—同江—双鸭山—佳木斯—鹤岗—伊春—铁力—海伦—北安—黑河—五大连池—讷河—富锦—齐齐哈尔—大庆—安达—肇东—绥化—哈尔滨；

最短路径为：3408.6。

2.2 运用模拟退火算法

模拟退火算法，简称SA，通常能够求得局部的最优解，它的根本思想源自固态物体降温过程，将该过程引入到求解组合的优化问题从而出现这个算法。

模拟退火算法的伪代码如下：

①随机生成一个初始解X0，令Xbest=X0，并计算目标函数值E（X0）；

②设置初始的温度T（0）=T0，迭代次数 i=l：

Do whileT（i）>Tmin

for j=1 to k （k为循环次数和城市规模有关）

对当前最优解Xbest邻域函数，产生一新的解Xnew，计算新得到的目标函数值E（Xnew），并计算判定函数的增量ΔE=E（Xnew）-E（Xbest）。

如果ΔE<0，则Xbest=Xnew。

③输出当前最优点，计算结束。

最优解为：R2=[1 23 29 3 5 17 6 15 10 27 4 8 24 28 9 11 21 25 13 22 12 18 14 16 7 20 26 2 19]；

程序求解结果如图2。

即最佳路线为：哈尔滨—绥化—肇东—安达—大庆—齐齐哈尔—富锦—讷河—黑河—五大连池—北安—海伦—铁力—伊春—鹤岗—佳木斯—双鸭山—同江—密山—绥芬河—鸡西—七台山—牡丹江—宁安—海林—尚志—五常—阿城—双城—哈尔滨；

最短路程为：3365.3。

2.3 运用遗传模拟退火算法

遗传算法虽把握总体的能力较强，但局部搜索能力较差；模拟退火算法具有较强的局部搜索能力，因此可以将遗传算法和模拟退火算法相互结合，取长补短。为了克服遗传算法和模拟退火算法各自的缺点，发挥它们的优势，将遗传算法和模拟退火算法结合起来，形成了模拟退火遗传算法，简称GASA。

GASA算法求解TSP问题流程：

Step1.给定算法参数：初始温度t0，终止温度tf，温度衰减因子α，种群规模Nc，交叉概率Pc，变异概率p，并初始化种群S；

Step2.在当前温度tk下，执行以下操作：

①对种群中各个个体进行评价，即计算所有个体的适应度vali；e（i，1：n）=s（i），e（i，n+1）=val（i）；

②执行GA算法的选择处理，采用淘汰算法判定是否淘汰恶性解，对当前种群进行选择；

③运行算法中的交叉流程，采用部分匹配交叉算子，附带保优操作，即执行交叉操作后所有个体的适应度val（i），如果val（i）>e（i，n+1），则令e（i，n+1）=val（i）；

④执行算法中的变异流程，采用倒位变异算子，附带保优操作；

⑤由上一步得到初代群体，然后对群体中的个体使用模拟退火操作，获得子代个体；

⑥利用SA算法的状态产生函数获取新的个体；

⑦依据概率exp（-Δf/tk）>random[0，1]接受新个体；重复⑥和⑦直至系统达到温度的平衡状态；

Step3.按一定方式降温，tk=αtk-1；

Step4.若tk

最优解为：R4 = [1 2 26 20 7 16 14 18 12 22 13 25 21 11 9 28 24 23 8 4 27 10 15 6 17 5 3 29 19]；

程序求解结果如图3。

即最佳路线为：哈尔滨—阿城—五常—尚志—海林—安宁—牡丹江—七台河—鸡西—绥芬河—密山—同江—双鸭山—佳木斯—鹤岗—阿城—铁力—绥化—海伦—北安—五大连池—黑河—讷河—富锦—齐齐哈尔—大庆—安达—肇东—双城—哈尔滨；

最短路程为：3316.6。

可以看出，将模拟退火算法优良的局部求解能力和遗传算法优良的全局求解能力进行有机结合的遗传模拟退火算法的结果优于单独使用遗传算法和模拟退火算法的结果。

3 蚁群算法与遗传模拟退火算法对比

运用蚁群算法求解此问题的结果如下：

最优解为： R3= [1 19 29 3 5 17 6 15 10 27 4 8 23 24 28 9 25 21 11 18 12 13 22 14 16 7 20 26 2]；

程序求解结果如图4。

即最优路线为：哈尔滨—双城—肇东—安达—大庆—齐齐哈尔—富锦—讷河—黑河—五大连池—北安—海伦—绥化—铁力—伊春—鹤岗—同江—双鸭山—佳木斯—七里河—鸡西—密山—绥芬河—牡丹江—安宁—海林—尚志—五常—阿城—哈尔滨；

最短路程为：3341.9。

由实验结果可以看出，在该问题的求解过程中，蚁群算法的求解结果优于遗传算法和模拟退火算法的求解结果，但还是不如遗传模拟退火算法的求解效果。

将四种算法结果进行对比，如表2。

通过对比四种算法求解黑龙江省29城市的问题的结果可以看出：

虽然GA算法、SA算法，单独求解已经可以得到很好的结果。但从结果中可以看到，蚁群算法的求解结果却优于GA和SA，将遗传算法和模拟退火算法两种算法的结合而成的GASA算法，在求解该问题时，得到的结果又优于蚁群算法，是最好的。可见将遗传算法和模拟退火算法结合起来使用可以有效提高解的质量，可以更有效的求解TSP问题。但是在求解过程中参数的给定，会很大程度上影响求解结果；遗传算法的交叉、变异过程也有很大的改进空间；所以，在接下来的主要研究中，应该对这些问题进行思考，从而进一步提高遗传模拟退火算法的性能。

参考文献：

[1]刘锦.混合遗传算法和模拟退火算法在TSP中的应用研究[D].广东省：华南理工大学，2014.

[2]朱成娟.遗传算法的改进及其若干应用[D].河北省：燕山大学，2006.

[3]刘晓路.改进的遗传算法及其在TSP问题中的应用与研究[D].黑龙江：哈尔滨理工大学，2011.

[4]庞峰.模拟退火算法的原理及算法在优化问题上的应用[D].吉林：吉林大学，2005.

[5]张文修.遗传算法的数学基础[M].西安：西安交通大学出版社，2003：90-157.

[6]王凌著.智能优化算法及其应用[M].北京：清华大学出版社，2001：66-120.