1、 1 遗传模拟退火算法 遗传模拟退火算法 黑龙江 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问题，通过对实验数据的分析，得出了遗传模拟退火算法在求解精度上优于遗传算法或模拟退火算法。遗传模拟退火算法利
2、用了模拟退火算法局部精确的求解能力补充了遗传算法在局部求解不够精确的弊端，从而加快了求解 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
3、genetic algorithm or simulated annealing algorithm in solving the precision. Genetic Simulated Annealing Algorithm （ GA）， which 2 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 t
4、he 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 引言 传统的遗传算法容易过早收敛，而且在搜索过程中有可能搜索到最优解然后又发散出去的现象。
5、模拟退火算法在解的质量与求解时间长之间存在矛盾，为得到一个好的近似最优解，需要进行反复迭代运算，当问题的规模不可避免地增大 时，缺乏可行的解决途径。遗传算法和模拟退火算法的直接互补性体现在：遗传算法虽把握总体的能力较强，但局部搜索能力较差；模拟退火算法具有较强的局部搜索能力，为了克服遗传算法和模拟退火算法各自的缺点，将遗传算法和模拟退火算法相互结合，取长补短，这就形成了模拟退火遗传算法，简称 GASA。 1 黑龙江旅行商问题 TSP问题是比较典型的组合优化问题，因其应用范围广，研究价值高，所以成为学者们研究重点，求解方法也有许多。但是一些常规的算法往往存在一些弊端，如后期计算不够精确，容易造成
6、过早收敛等。 TSP 问题是3 研 究算法性能的经典问题，具有广泛的应用背景。 选取黑龙江省 29个城市构造 TSP问题，即求得一条将黑龙江省 29个城市旅行一遍，且每个城市有且仅经过一次的最短路线。表 1 是黑龙江省29个城市的坐标。 2 算法比较 实验过程中，染色体的长度 L 等于城市个数，即： 29。种群的规模pop-size 定为 100，各个参数确定如下：将退火过程参数 a=0.9，交叉概率和变异概率 Pc=0.5， Pm=0.1，迭代结束的依据是 q=100。单个的遗传算法和模拟退火法里用到的参数也这样设定。 首先将黑龙江省 29 个城市 的坐标放入一个数组中，记为： citys=
7、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
8、455 711； 27 838 607； 28 742 856； 29 604 558。 2.1 运用遗传算法 遗传算法，简称 GA，是以自然选择理论和遗传变异理论为基础的仿生学的概率性搜索迭代算法。 遗传算法求解 TSP的算法描述如下： 步骤 1 设定种群的规模、遗传变异概率 pm、遗传交叉概率 pc，初始化当前代数 g=0； 4 步骤 2 使用算法，随机产生一个初代种群，在将种群中所有个体的适应度计算出来； 步骤 3 根据轮盘赌策略选择父代 1 和父代 2； 步骤 4 产生两个 0 1 的随机数 p1和 p2； 步骤 5 若 p1pc，则对父代 1 和父代 2 进行杂交操作，生成新的子代1 和子代 2，否则，父代 1 和父代 2 不进行任何操作直接成为新的子代 1和子代 2；
