关于一种基于基因库和多重搜索策略求解TSP的遗传算法的论文

-本文为网络收集精选范文、公文、论文、和其他应用文档，如需本文，请下载-关于一种基于基因库和多重搜索策略求解TSP的遗传算法的论文本文从网络收集而来，上传到平台为了帮到更多的人，如果您需要使用本文档，请点击下载按钮下载本文档（有偿下载），另外祝您生活愉快，工作顺利，万事如意！论文关键词：旅行商问题 遗传算法 基因库 多重搜索策略论文摘要：tsp是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(gbmga),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际tsp库中多个实例的测试,结果表明:算法(gbmga)加快了遗传算法的收敛速度,也加强了算法的寻优能力。tsp(traveling salesman problem)可以简述为:有n个城市1,2,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。tsp的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的tsp,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是np难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解1。由于tsp在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。tsp的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法2、蚂蚁算法3、模拟退火算法、遗传算法等。遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息4。遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。用遗传算法求解tsp能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内计算出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文5中杨辉提出的基因库的想法,并结合文6中cheng-fa tsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解tsp问题。该文根据文7中最小生成树mst(minimum cost spanning tree)的应用,由mst建立tsp的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。1单亲演化过程现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的tsp尤其明显8。该文为了克服上述弱点,首先利用普里姆算法求出tsp中最小生成树,并将各个mst中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。tsp编码表示设n个城市编号为1,2,n,为一条可行路径,pk=vk1vk2vkn为一条可行路径,它是1,2,n的一个随机排列,其含意是第k条路径起点城市是vk1,最后一个城市是vkn,则第k条环路的总长度可以表示为:其中,d(vki,vkj)表示城市vki与城市vkj之间的距离。在算法中环路pk的总长d(pk)用来评价个体的好坏9。适应度函数取路径长度d(pk)的倒数,f(pk)=1/ d(pk)。构建tsp基因库对n个编号为1,2,n的城市,根据它们的坐标计算各城市之间的欧氏距离d(i,j),i,j=1,2,n,得到一个n*n的方阵d= d(i,j)。然后利用普里姆算法求得该tsp的一棵mst,并将这棵mst中的每一条边e(i,j)对应地存储在一个n*(n-1)的方阵m= e(i,j),即该文的基因库。由于一个tsp可能有多棵mst,操作可以重复多次,这样生成的基因库中的基因就更多,增强了初始群体的全局性。具体算法如下:void minispantreeprim(mgraph g,vertextypeu)struct vertextype adjvex;vrtype lowcost;closedgemaxvertexnum;k=locatevex(g,u);for(j=0;jac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。选择机制和收敛准则为了限制种群的规模13,该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。遗传算法求tsp问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续k1代不再出现更优的染色体;优化解的染色体占种群的个数达k2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。基于多重搜索策略的群体演化算法由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由cheng-fa tsai提出的多重搜索策略6,就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。3实验结果与分析该文的gbmga算法由c#编程实现,所有的结果都是在微机上完成,并进行通用的tsp库实验,选用了具有一定代表性的tsp实例,并把该算法和其他算法做了一个对比。为了减少计算量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图kroa100的示例。为了证明该文提出的gbmga算法的有效性,将该文算法与典型的遗传算法ga、单亲遗传算法pga以及文5中杨辉提出的gega(gene pool genetic algorithm)算法和文12中提出的mmga(modified multiple-searching genetic algorithm)算法都进行了一个对比。实验结果证明,该文算法的求解质量要优于ga、pga、mmga算法,而求解速度方面则优于gega算法,特别是对于大规模城市的tsp问题求解效果尤其明显,具有快速收敛的特性。gega算法对于中等城市规模的tsp实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模tsp问题,那么时间上的代价就让人无法忍受。而该文的gbmga算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。结束语该文在对tsp问题进行分析的基础上,通过对全局最优解和局部最优解中的边关系的分析发现,通过最小生成树的求解保存最有希望成为全局最优解的边,可以提高算法的效率,同时并不降低搜索的性能。在实验中发现,通过生成基因库快速提高种群质量,虽然可以快速收敛,但是tsp问题的求解质量并没有达到一个可以接受的程度,因此在群体演化阶段中又加入了2-opt局部搜索算子和多重搜索策略,对不同类型的染色体以不同几率进行选择交叉操作。用该算法测试tsp库中的典型实例,结果显示,对初始种群运用单亲遗传算法,并引入基因库方法是可行的,有效地提高了算法的效率和收敛速度,在群体演化过程中引入多重搜索策略的方法,提高了算法的并行性和全局寻优性能,即使在较少的寻优步数也能得到适应度不错的局部优化解。gb-mga算法在提高算法求解质量的同时兼顾了算法的效率, 但是其中还有许多有待解决的问题,比如如何构建高质量的基因库,如何对现有基因库进行优化和扩充,以及算法中一些参数的选取问题等,这些方面,还需要进一步的研究。参考文献1 bck t b,hammel u,schwefel h computation:comments on the history and current state j. leee transactions on evolutionary computation,1997,2(6):3172王磊,潘进,焦李成.免疫算法j.电子学报,2000,28(7):74783 dorigo m,gambardella l colony system:a cooperativelearning approach to the traveling salesman problem j. ieeetransactions on evolutionary computation,1997,2(8):53664 holland j h. adaptation in natural and artificial systems m.ann arbor:the university of michigan,155杨辉,康立山,陈毓屏.一种基于构建基因库求解tsp问题的遗传算法j.计算机学报,2003,26(12):175317586 tsai cheng-fa, tsai chun-wei, yang tzer. a modified multiple-searching method to genetic algorithms for solving travelingsalesman problem j.ieee transactions on systems,man andcybernetics,2002,3(10):6127 baraglia r,hidalgo j i, perego r. a hybrid heuristic for thetraveling salesman problem j. ieee transactions on evolutionary computation,2001,5(12):6136228 tsai cheng-fa, tsai chun-wei. a new approach for solvinglarge traveling salesman problem using evolutionary ant rulesc.in: the 2002 international joint neural networks,hawaiian:honolulu,20029 jung s,moon b minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean tsp j.ieee transactions on evolutionary computation,2002,6(12):55756510李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究j.湖南大学学报,1998,25(6):565911陈国良,王煦法,庄镇泉,等.遗传算法及其应用m.徐修存,王晓丹.北京:人民邮电出版社,8112 watson j,ross c,eisele v,et al. the traveling salesrep problem,edge assembly crossover, and 2-opt c.parallel problemsolving from nature v