解决tsp的遗传算法初始种群改进方法研究new

《解决tsp的遗传算法初始种群改进方法研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn1解决TSP的遗传算法初始种群改进方法研究贾海鹏，郑丽英，何天斌，徐顼兰州交通大学电子与信息工程学院，甘肃兰州（730070）E-mail：jiahaipg@yahoo.com.cn摘要：遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择成为算法成败的一个至关重要的因素，直接影响到算法的寻优效率和效果。遗传算法初始种群的构造普遍采用均匀取种法或随机取种法，但这两种策略的搜索效率都难以保证。针对这类算法的缺陷，本文结合图论中相关理论提出了三种基于最小生成树原理的初始种群改进方法。关键词：遗传算法；初始种群；最小生成树；旅

2、行商问题；普里姆算法；奇偶点图上作业法中图分类号：TP301文献标识码：A1.引言旅行商问题（TravelingSalesmanProblem,TSP）是运筹学，图论，组合优化以及计算机算法设计中的精典课题，由于它有着广泛的应用背景，所以引起了大量学者的关注。同时TSP问题也属于NP-Hard题，求准确的最优解实际意义不大，因此启发式算法的研究就越发显示出其魅力。从图论的角度分析，TSP问题实质上是寻找一条权值最小的哈密顿（Hamilton）回路的问题。遗传算法（GeneticAlgorithm,GA）是一种基于生物自然选择和基因遗传原理的随机搜索启发式算法[1]。算法自提出以来对它的理论

3、和应用的研究就从未停止过，出现了相当多别具特色的改进形式，但是这些改进几乎全都集中在编码方式和遗传算子操作上，对初始种群的研究目前非常匮乏。遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择就成为算法中一个至关重要的因素，直接影响到算法的寻优效率和效果[2]。2.当前遗传算法初始种群的构造算法初始种群（第一代种群）的获取一般采用均匀取种法或随机取种法，这是两种现阶段比较普遍采用的算法，但是这两种算法构造出的初始种群具有很大的随机性，种群的平均适应度较低。2.1均匀取种法首先它将搜索域的解空间分成n个大小相等的子空间（n为种群的规模），然后等概率的在每个子空间中选取

4、一个种子，把选出的这n个种子合并成第一代种群。算法的搜索过程是：先经过前M次遗传迭代，算法并行搜索到各个局部最大值附近（如图1中的A,B,C），再经过N次迭代，收敛到全局极大值(图1中的B点)。2.2随机取种法在搜索域的解空间中每个种子被选择的机会是相等的。随机取种算法实际操作首先是1本课题得到教育部春晖计划（Z2004-1-62018）和甘肃省自然科学基金项目（3ZS042-B25-038）的资助。-1-http://www.paper.edu.cn选择一个种子，然后再对该种子在解空间内进行基因位重组。选出n个种子后，就形成了第一代种群。算法的搜索过程与均匀取种法相似。图1搜索解空间Fi

5、g1.SearchSolutionSpace3.基于TSP问题的初始种群改进算法初始种群中一个染色体的有效基因概率越大，它的适应度就越高。如果采用有效的初始化方法，使初始种群本身就能集中到最优解邻近区域，显然要收敛到同样的结果，采用有效初始化方法的GA所需的迭代次数比随机或均匀取种法要少的多，因而搜索速度也就提高了。一个完全图的最小生成树,是所有经过n个结点生成树中代价最小的一棵树。TSP也是求经过n个结点最小代价的问题，因此两者之间有许多的相似之处[3]。所以TSP的求解,可以通过对最小生成树部分有效信息的改造来完成。下面我们分别对对称和非对称的TSP问题初始种群进行重新构造。3.1对称

6、TSP问题对称TSP是指一个旅行商从驻地出发去某些城镇旅行，然后再回到出发地。各城镇之间的路程是已知的，并且城镇甲到乙的路程与城镇乙到甲路的相等，求如何安排他的旅行路线，才能使经过每个城镇恰好一次，且总的旅行路程最短[4]。3.1.1最小生成树连续出度法这是一种DNA和RNA的嫁接算法。在这里我们把一条完整的染色体分为二部分：前部和后部。前部动态生成，用来存储最小生成树中的局部有效信息可近似理解为生物体中基因相对稳定的DNA；染色体后部采用随机优化方式排列产生，其基因位相对前部不够稳定，这尤其生物体中的RNA。再由这两部分嫁接构成一条完整的染色体。连续出度法解决TSP问题：1）利用普里姆（

7、Prim）算法产生最小生成树;2）遍历最小生成树，判断结点的出度，当出度大于1时停止遍历。并记录经过的路径，把该路径上的i个结点作为初始种群中染色体前部，并且基因相对固定，不参与交叉和变异操作。3）剩余n-i个结点采用随机组合的方式产生染色体后部，进而形成改进后的初始种群。3.1.2奇偶点图上作业法定理1：一个非平凡连通图G是Euler图当且仅当图G没有奇点[5]。定理2：（管梅谷，1960）设G是一个连通的赋权图，&&