一种求解TSP问题的均匀设计抽样混合遗传算法  

A Hybrid Genetic Algorithm based on Uniform Design Sampling for Solving Traveling Salesman Problem Using

作　　者：赵义超[1,2] 周本达[2] 

机构地区：[1]安徽大学数学科学学院,安徽合肥230039 [2]皖西学院数理系,安徽六安237012

出　　处：《皖西学院学报》2009年第2期10-13,共4页Journal of West Anhui University

基　　金：安徽省高校省级自然科学研究项目(KJ2007B152);安徽省高校青年教师资助计划项目(2007jql180)

摘　　要：旅行商问题是经典的NP-hard组合优化问题,在许多领域有着重要应用。近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想。基于理想浓度模型的机理分析,利用均匀设计抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在旅行商问题特点的基础上,结合2-opt局部搜索策略,给出了一个解决旅行商问题的新的遗传算法。通过将该算法与简单遗传算法和佳点集遗传算法进行实例仿真比较,可以看出新算法在求解旅行商问题上提高了求解的质量、速度和精度,而且避免了其它方法常有的早期收敛现象。The Traveling Salesman Problem is a typical NP-hard combination optimization question,has the important application in many domains. In recent years, the tradition genetic algorithm and so on each intelligent optimization method is introduced to solve this question, but the effect is not ideal Based on the mechanism of ideal density model and characteristic of the Traveling Salesman Problem, the crossover operation in GA is redesigned by using the principle of Uniform Design Sampling and combining the 2-opt locale search strategy. Then a new GA is presented. The new GA is applied to solve the Traveling Salesman Problem. Compared to simple GA and Good Point GA for solving this problem, the simulation results show that the new GA has superiority in speed,accuracy and overcoming premature.

关 键 词：遗传算法 均匀设计抽样 均匀设计抽样遗传算法 

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