Question

自适应遗传算法在求解TSP问题中的应用研究

求自适应遗传算法在求解TSP问题中的应用研究论文一篇

Answer 1

利用基于分区搜索的自适应遗传算法求解TSP问题
江金龙,薛云灿,冯骏
　　为了提高用遗传算法求解旅行商问题(TSP)的收敛速度,结合自适应算子和父子竞争策略等优化思想,提出了基于分区搜索的自适应遗传算法.该算法将整个搜索区域分成若干个较小的搜索区域,先进行局部搜索,在得到局部较优的基因组合后,再进行全区域搜索,不但提高了遗传算法的收敛速度,而且改进了变异算子的操作性能.通过TSP问题的求解表明,基于分区搜索的自适应遗传算法是一种稳定、高效的优化算法.
【作者单位】：河海大学计算机及信息工程学院;河海大学计算机及信息工程学院;河海大学计算机及信息工程学院 江苏常州213022九江学院电子工程学院;江西九江332005;江苏常州213022;江苏常州213022
【关键词】：遗传算法;分区搜索;旅行商问题
【基金】：湖北省自然科学基金资助项目(2004ABA018);河海大学常州校区创新基金资助项目(2005B002-01)
【分类号】：TP18
【DOI】：cnki:ISSN:1009-1130.0.2005-03-001
【正文快照】：
　　1分区搜索自适应遗传算法的基本思想旅行商问题(Traveling Salesm an Problem,TSP)是指旅行商从某城市出发,在遍历N个城市后又回到出发点,且每个城市只经过一次,求旅行商行程最短的问题[1].TSP是一个N P难题,其可能的路径数目随城市数N的增加呈指数型增长.如果是对称TSP问题,则共有0.5(N-1)!种可能路线,如果是非对称TSP问题,可能的路线还会加倍.许多学者运用遗传算法的不同控制方法来求解TSP的最优解[2-3],但简单遗传算法(Sim ple G enetic A lgorithm,SG A)的收敛速度慢,且易陷入局部最优解.如果能找到某些局部优良的基因组合(…
推荐 CAJ下载 PDF下载
CAJViewer7.0阅读器支持所有CNKI文件格式，AdobeReader仅支持PDF格式

Solving Traveling Salesman Problem by the Adaptive Genetic Algorithm Based on the Regional Search
JIANG Jin-long1;2;XUE Yun-can1;FENG Jun1(1.College of Computer & Information Engineering;Hohai Univ.;Changzhou 213022;China;2.College of Electronic Engineering;Jiujiang Univ.;Jiujiang 332005;China)
　To increase the convergence speed of the genetic algorithm in solving the traveling salesman problem(TSP),combined with adaptive operators and competitive strategy between parents and their children,an adaptive genetic algorithm based on the regional search is proposed. This algorithm divides the global space into regional space and makes the regional search first. The global space search is carried out based on the better local gene sequences obtained from the regional search,so as to improve the search speed. Moreover,this algorithm improves the mutation performance at the same time. The TSP simulations show that the improved algorithm is a steady and efficient optimal search method.
【Keyword】：genetic algorithms;regional search;traveling salesman problem(TSP)