改进的遗传算法求解TSP  

Solving TSP Based on Improved Genetic Algorithm

作　　者：程孝庆[1] 田妙苗[2] 邵克勇[2] 李飞[2] 谢维志 易江 张新刚[4] 

机构地区：[1]大庆油田有限责任公司第一采油厂,大庆163453 [2]东北石油大学电气信息工程学院,大庆163318 [3]中国石油辽河石化公司电工车间,盘锦124022 [4]青海油田公司冷湖油田管理处,冷湖810000

出　　处：《科学技术与工程》2011年第9期1995-1998,共4页Science Technology and Engineering

基　　金：黑龙江省博士后科研启动基金项目(LBH-Q08159)资助

摘　　要：阐述了一种针对TSP问题的改进遗传算法。引入了局部优化搜索算法。加快了算法的收敛速度。减轻了初值对结果的影响。加入了改进的OX交叉算法,在交叉中合理保留了优秀个体基因的排列顺序。利用精英复制保留了优秀基因。维持了种群个体数目稳定。提出了一种新的变异算法,有效避免了路径重复,减小了运算量,提高了运算速度。An improved genetic algorithm for TSP problem was provided.A local optimization search algorithm was introduced to accelerate the convergence velocity and mitigated the influence of the initial value.An improved OX cross algorithm was added and the genes sequence of excellent individuals were reasonably preserved.The elite reproduction retaines good genes and guarantees the number stability of the population.A new variation algorithm is described,which avoides the duplication of the paths,reduces the computation and improved the operation speed.

关 键 词：遗传算法 TSP 局部优化 OX交叉 

分 类 号：TP273.23[自动化与计算机技术—检测技术与自动化装置]