求解超大规模旅行商问题的纵深遗传算法  

Depth genetic algorithm solve ultra-large-scale Traveling Salesman Problem

作　　者：赵连朋[1,2] 金喜子[2,3] 王娜[2] 姚明海[1,2] 

机构地区：[1]渤海大学公共计算机教研部,辽宁锦州121000 [2]东北师范大学计算机学院,长春130117 [3]吉林大学计算机科学与技术学院,长春130117

出　　处：《计算机工程与应用》2009年第4期56-58,101,共4页Computer Engineering and Applications

基　　金：国家自然科学基金No.60573067;辽宁省教育厅A类基金资助项目~~

摘　　要：很多演化算法对初始参数设计都敏感,针对于不同的旅行商问题(Traveling Salesman Problem,TSP)实例需要进行相应的初始参数调整。并且,在求解超大规模TSP问题时容易陷于局部最优解。提出了一种纵深遗传算法的TSP问题求解方案,以及新的改良函数、变异函数和交叉函数。对pr1002(259269.09)、pla85900(152394182.43)和brd14051(489842.93)等实例都获得了比较好的优化解。实验表明该方案在求解TSP问题方面具有优势。Many evolutionary algorithms are sensitive for initial parameters design,the different Traveling Salesman Problem（TSP） need for corresponding adjustment for the initial parameters.And the local optimal solution is easy when you solve the issue of ultra-large-scale TSP problem.Therefore,this paper presents a programme about depth genetic algorithms to solve TSP problems and improved function,variation function,cross-function in order to resolve the question.For example,pr1002（259 269.09）,pla85900（152 394 182.43） and brd14051（489 842.93） have a relatively good optimal solution.Experimental results show that the algorithm has great advantages.

关 键 词：旅行商问题 演化算法 纵深遗传算法 最优解 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301[自动化与计算机技术—控制科学与工程]