两阶段遗传算法在求解TSP问题中的应用  

Application of two-stages genetic algorithm to solving TSP

作　　者：张启义[1] 邱国庆[2] 寇学智[1] 陈亮[2] 

机构地区：[1]解放军汽车管理学院,安徽蚌埠233011 [2]解放军理工大学工程兵工程学院,江苏南京210007

出　　处：《解放军理工大学学报（自然科学版）》2011年第1期79-83,共5页Journal of PLA University of Science and Technology(Natural Science Edition)

摘　　要：为了提高利用遗传算法求解TSP(traveling saleman problem)问题的能力,给出了一种种群多样性的定义,提出了一种利用2个阈值在贪婪优化遗传算法和退火单亲遗传算法间切换的两阶段遗传算法,从而可以在保持种群多样性的基础上优化种群。两阶段遗传算法在种群多样性下降到一定程度时,转换遗传方式,在继续寻优的同时,很快提高种群的多样性,当种群多样性上升到一定程度,又转换为原来的算法,如此重复。仿真算例结果表明:两阶段遗传算法收敛速度和全局搜索能力都得到了较大提高,其平均最优解、平均收敛代数和平均耗时优于或与另两种遗传算法相当。To improve the ability to TSP solve using GA,firstly a kind of definition of the population diversity was put forward,and then one kind of two-stage GA,setting two critical values in order to switch between greedy optimization GA and annealing partheno GA,was proposed to optimize the population in a large scale on the basis of keeping the population diversity.In the two-stage genetic algorithm,when the population diversity was degraded to some degree,it switched to the other algorithm searching the best result and improved the population diversity quickly.When the population diversity was ascended to some degree,it changed to the old algorithm,and this process repeated.The simulative result shows that the two-stage GA＇s convergence velocity and the searching capability are greatly improved,and that the average optimal result,the average convergence generations and the average running time are superior to or the same as those of the other two GAs.

关 键 词：TSP 种群多样性 贪婪优化遗传算法 退火单亲遗传算法 两阶段遗传算法 

分 类 号：O221[理学—运筹学与控制论]