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

1、入党积极分子思想汇报模板尊敬的党组织：今天，我怀着无比激动键词：旅行商问题 遗传算 法基因库多重搜索策略论文摘要：t sp是组合优化问题的典型代表，该文在分 析了遗传算法的特点后，提出了一种新的遗传算法(gb mga )，该算法将基因库和多重搜索策略结合起来，利用基因 库指导单亲遗传演化的进化方向，在多重搜索策略的基础上 利用改进的交叉算子又增强了遗传算法的全局搜索能力。通 过对国际tsp库中多个实例的测试，结果表明：算法(gbmga ) 加快了遗传算法的收敛速度，也加强了算法的寻优能力。tsp(trave lingsalesman problem)可以简述为：有 n 个 城市1,2,n, 旅

2、行商从某一城市出发，环游所有城市后 回到原出发地，且各城市只能经过一次，要求找出一条最短 路线。tsp的搜索空间是有限的，如果时间不受限制的话，在 理论上这种问题终会找到最优解，但对于稍大规模的tsp,时 间上的代价往往是无法接受的。这是一个典型的组合最优化 问题，已被证明是np难问题，即很可能不存在确定的算法能 在多项式时间内求到问题的解1。由于tsp在工程领域有 着广泛的应用，如货物运输、加工调度、网络通讯、电气布 线、管道铺设等，因而吸引了众多领域的学者对它进行研究。 ts p的求解方法种类繁多，主要有贪婪法、穷举法、免疫算 法2、蚂蚁算法3、模拟退火算法、遗传算法等。遗传算法是一种借鉴

3、生物界自然选择和遗传机制的随 机化搜索算法，其主要特点是群体搜索策略和群体中个体之 间的信息交换，搜索不依赖于梯度信息4。遗传算法主要包 括选择、交叉和变异3个操作算子，它是一种全局化搜索算 法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。 遗传算法虽然不能保证在有限的时间内获得最优解，但随机 地选择充分多个解验证后，错误的概率会降到可以接受的程 度。用遗传算法求解tsp能得到令人满意的结果，但是其收 敛速度较慢，而且种群在交叉算子作用下，会陷入局部解。采 用局部启发式搜索算法等，虽然能在很短的时间内计算出小 规模城市的高质量解，一旦城市规模稍大就容易陷入局部最 优解。因此，为了能够加快

4、遗传算法的收敛速度，又能得到更 好的近似最优解，该文采纳了文5 中杨辉提出的基因库的 想法，并结合文6中ch eng-fatsai提出的多重搜索策略思 想，使用单亲演化与群体演化相结合的方式来求解tsp问题。 该文根据文7中最小 生成树mst(minimu mcostspannin gtree)的应用，由mst建立tsp的基因库，保存有希望成为最 优解的边，利用基因库提高初始群体的质量进行单亲演化， 然后利用改进后的交叉算子和的多重搜索策略进行群体演 化。1单亲演化过程现有的大多数演化算法在整个演化过程中所涉及的基因，大多来源于个体本身，个体质量的髙低决定了算法的全 局性能，如果群体中初始个体

5、的适应度都较差，肯定要影响 算法的收敛速度，对于规模稍大的tsp尤其明显8。该文为 了克服上述弱点，首先利用普里姆算法求出tsp中最小生成 树，并将各个mst中的每一条边都保存在一个n*(n-l )方阵 里面，就构成了一个基因库，在生成初始群体的时候尽量使 用基因库中的基因片段，来提高整个初始群体的适应度，从 而提高算法的效率。tsp编码表示设n个城市编号为1,2 ，n,为一条可行路 径,pk=vklvk2-v kn为一条可行路径，它是1,2,，n的一个 随机排列，其含意是第k条路径起点城市是vkl,最后一个城 市是vkn,则第k条环路的总长度可以表示为：其中,d(vki ,vkj)表示城市v

6、ki与城市vkj之间的距离。 在算法中环路pk的总长d(pk)用来评价个体的好坏9。适 应度函数取路径长度d (pk)的倒数,f(pk)=l/d(pk)o构建tsp基因库对n个编号为1,2,n的城市，根据它们的坐标计算各 城市之间的欧氏距离d(i, j), i, j=l,2,n,得到一个n*n的 方阵d=d(i, j)o然后利用普里姆算法求得该tsp的一棵mst, 并将这棵mst中的每一条边e (i, j)对应地存储在一个 n*(n-1)的方阵m = e(i, j),即该文的基因库。由于一个ts p可能有多棵mst,操作可以重复多次，这样生成的基因库中 的基因就更多，增强了初始群体的全局性。具

7、体算法如下：voidm inispantree一prim(mgraphg , vertextypeu ) struct v ertextypeadj vex；vrtypel owcost； clo sedge maxve rtexnum；k =locatevex(g,u)；for (j=0 ； jif (j!=k)cl osedgej = u , k j. adj； closedgek . lowcost二0；for (i=0； ik=m inimum(close dge)；printf (closedgekadjvex,k)；closedgek . lowcost二0；for (j=0； j

8、if (k j. adjc losedgej = k, k j. a dj;单亲演化算法单亲演化算法是利用遗传算法的优胜劣汰的遗传特性,在单个染色体内以基因重组的方式，使子代在满足tsp问题 的限定条件下进行繁衍，然后保留适应度高的染色体种群， 达到优化的目的。单亲演化算法的基因重组操作包括基因换 位、基因段错位和基因段倒转三种操作来实现。基因换位操 作是将亲代的染色体基因进行对换后，形成子代，其换位又 分为单基因换位和基因段换位两种方式。基因段错位操作是 随机确定基因段，也随机选定错位位置，整段错移。基因段倒 转操作则是随机地确定倒转基因段的起止位置，倒转操作是 对该段内基因按中垂线作镜面反

9、射，若段内基因数为奇数时, 则中位基因不变。单亲演化时可以是单个操作用于单个父代, 也可以是几种操作同时采用。为了编程方便，文中采用基因 段倒转操作。2群体演化过程在单亲演化算法求得的初始群体基础上，再利用多重搜 索策略并行地进行群体演化，这样在保证算法的快速收敛的 同时也注重了搜索空间的全局性。交叉算子该文算子采用一种与顺序交叉ox(ordercrossov er)法 类似的交叉方法11,即随机在串中选择一个交配区域，例 如以下两个父串及交配区域选定为：pl=(12|3456 |789)p2=(98|7654|321)将p2的交配区域加到p1的前面或后面,p1的交配区域加到p2的前面或后面，

10、得ml=(7654| 12 3456789)m2= (34561987654 321)在ml中自交配区域后依次删除与交配区域相同的城市 码，得到最终的两个子串：sl=(76 5412389)s2= (345698721)同时为了能更好地增强算子的全局搜索能力，对该算子 作了如下的改进。子代个体的新边来自：随机生成和群体中 其他个体,其选择比例由随机数p和阈值p来决定。如果随 机数p小于阈值p,则子代个体的新边来自随机生成，否则就 来自群体中的其他个体。这种改进后的交叉算子在父串相同的情况下仍能产生 一定程度的变异效果，这对维持群体的多样化特性有一定的 作用。实验结果也证实了这种改进算子对于种群

11、的全局搜索 能力有一定的提高，避免搜索陷入局部解。局部启发式算子为了增强遗传算法的局部搜索性能，在算法中引入2- opt局部搜索算子12。该算子通过比较两条边并交换路径 以提升算法的局部搜索性能，示例见图2。比较子路径ab+cd和a c+bd,如果ab+cd >ac+bd则交换, 否则就不交换。考虑到程序的运行效率，不可能对每对边都 做检查，所以选取染色体中的一定数量的边进行比较。2-opt 搜索算子实际上进行的相当于变异操作，同时又不仅仅是简 单的变异，而是提高算法的局部搜索性能的变异操作。选择机制和收敛准则为了限制种群的规模13,该文采用了联赛选择法的淘 汰规则。联赛选择法就是以各染

12、色体的适应度作为评定标准, 从群体中任意选择一定数目的个体，称为联赛规模，其中适 应度最高的个体保存到下一代。这个过程反复执行，直到保 存到下一代的个体数达到预先设定的数目为止。这样做可能 导致种群过早收敛，因此在收敛准则上要采取苛刻的要求来 保证搜索的全局性。遗传算法求ts p问题如果不设定终止条件，其演化过程 将会无限制地进行下去。终止条件也称收敛准则，因为多数 最优化问题事先并不了解最优的目标函数值，故无法判断寻 优的精度。该文采用如下两条收敛准则：在连续k1代不再出 现更优的染色体;优化解的染色体占种群的个数达k2的比例 以上。当两准则均满足时，则终止运算，输出优化结果和对应 的目标函

13、数值。由数值实验表明，添加第2条准则之后，全局 最优解的出现频率将大为提高。基于多重搜索策略的群体演化算法由于基因库的引入， 可能降低初始种群的多样性，为避免算法陷入局部最优解， 因此在群体演化中采取多重搜索策略。由che ng-fatsai提 出的多重搜索策略6,就是把染色体集中的染色体分成保 守型和探索型两种不同类型的集合，然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作, 对保守型染色体集合就采用比较低的交叉变异概率，而对探 索型染色体集合就采用比较高的交叉变异概率。这种策略对 保守型染色体集合的操作最大限度地保留了父代的优秀基 因片段，另一方面对探索型染色体集合

14、的操作又尽可能地提 高了算法的全局搜索能力。为了提髙算法的收敛速度，初始 染色体集合该文采用了前面单亲演化的结果中的染色体集 合，交叉算子则利用的是前面介绍的改进后的算子，改进后 的多重搜索策略见下。3实验结果与分析该文的gbmga算法由c#编程实现，所有的结果都是在 微机上完成，并进行通用的tsp库实验，选用了具有一定代表 性的tsp实例，并把该算法和其他算法做了一个对比。为了减 少计算量，程序中的数据经过四舍五入整数化处理，与实数 解有一定的偏差，下面给出图kroaloo的示例。为了证明该文提出的gbmga算法的有效性，将该文算 法与典型的遗传算法ga、单亲遗传算法pga以及文5中杨 辉提

15、出的 gega (gen epoolgenetic algorithm)算法和文12 中提出的 mm ga (modi fi edm ultiplesear chinggenetic algorithm)算法都进行了 一个对比。实验结果证明，该文算法的求解质量要优于ga、pga、 mmga算法，而求解速度方面则优于ge-ga算法，特别是对于 大规模城市的tsp问题求解效果尤其明显，具有快速收敛的 特性。gega算法对于中等城市规模的tsp实例求解，其运 算时间就大幅度增加，如果把该算法用于求解大规模和超大 规模tsp问题，那么时间上的代价就让人无法忍受。而该文 的gb-m ga算法在单亲遗传演

16、化中就使用了基因库中的优质 基因，使得单个个体的进化速度大大提高，从而为进一步的 演化提供了条件,群体演化过程的选择机制和收敛准则的恰 当选取使得算法在注重了求解质量的同时兼顾了算法的效 率。结束语该文在对tsp问题进行分析的基础上，通过对全 局最优解和局部最优解中的边关系的分析发现，通过最小生 成树的求解保存最有希望成为全局最优解的边，可以提高算 法的效率，同时并不降低搜索的性能。在实验中发现，通过生 成基因库快速提高种群质量，虽然可以快速收敛，但是tsp问 题的求解质量并没有达到一个可以接受的程度，因此在群体 演化阶段中又加入了 2-opt局部搜索算子和多重搜索策略, 对不同类型的染色体以

17、不同几率进行选择交叉操作。用该算法测试tsp库中的典型实例，结果显示，对初始种群运用单亲遗传算法，并引入基因库方法是可行的，有效地 提高了算法的效率和收敛速度，在群体演化过程中引入多重 搜索策略的方法，提高了算法的并行性和全局寻优性能，即 使在较少的寻优步数也能得到适应度不错的局部优化解。 gb-mga算法在提高算法求解质量的同时兼顾了算法的效率, 但是其中还有许多有待解决的问题，比如如何构建高质量的 基因库，如何对现有基因库进行优化和扩充，以及算法中一 些参数的选取问题等，这些方面，还需要进一步的研究。参考文献ibektb,hammelu,schwefelhcomputation :comm

18、entsont hehistoryand currentstate j.leeetran sactionsonev olutionaryco mputation,19 97,2(6):3172王磊，潘进，焦李成.免疫算法j1.电子学 报，2000,28 (7)：74783dorig om,gambardel lalcolonysys tem：acoopera tivelearning approachtoth etravelingsa lesmanproble mjieeetra nsactionsone volutionaryc omputation,1 997,2(8):53664holl

19、andj h. adaptation innaturaland artificialsy stems m. ann arbor： theuni versityofmic higan, 155杨辉，康立山，陈毓屏一种基于构建基因库求解tsp问 题的遗传算法j.计算机学报,xx,26(1 2): 175317586tsaicheng-fa, tsaichun-wei, yangtzer . amodif iedmu ltiple-searc hingmethodto geneticalgor ithmsforsolv ingtraveling salesmanprob lemj ieeet ransactionso nsystems,man andcybernetics, 2002, 3 (10 ): 6127bara gliar,hidalg oji,peregor. ahybridheuri sticforthetr avelingsales manproblemj .ieeetransa ctionsonevol utionarycomp utation, 2001 , 5 (12): 6136 228tsaichen gfa, tsaichu nwei. anewap proachforsol vinglargetra velingsalesm anproblemusi