拉丁超立方体抽样混合遗传算法求解TSP问题  

SOLVING TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHM BASED ON LATIN HYPERCUBE SAMPLING

作　　者：陈明华[1] 周本达[1] 任哲[2] 

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

出　　处：《高等学校计算数学学报》2011年第2期138-144,共7页Numerical Mathematics A Journal of Chinese Universities

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

摘　　要：0引言 旅行商问题（TravelingSalesmanProblem：TSP）是十分重要的组合优化问题，它在计算机科学、运筹学及工程等领域都有着广泛的应用．巡回旅行商问题即给定一组N个城市和它们两两之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短．It is well known that the GA is a guided random search and the guid- ing direction always aims at the family whose ancestors have schemata with high fitness. Based on the results, the crossover operation in GA is redesigned by using the principle of Latin Hypercube Sampling and combining the 2-opt locale search strategy. Then a new GA called Genetic Algorithm based on Latin Hypercube Sampling is presented. The new GA is applied to solving 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.

关 键 词：拉丁超立方体抽样 混合遗传算法 TSP问题 旅行商问题 求解 组合优化问题 计算机科学 运筹学 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]