资源描述：
《用遗传算法求解GTSP的编码改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第7卷第12期2007年6月科学技术与工程Vol17No112June20071671-1819(2007)12-2981-03ScieTechnologyandEngineering2007Sci1Tech1Engng.计算机技术用遗传算法求解GTSP的编码改进赵曦曾庆斌(广东科学技术职业学院计算机工程技术学院,珠海519090)摘要在遗传算法的过程中,变异概率是很低的,相对交叉算子对于影响染色体的多样性更为重要。针对基于广义染色体求解GTSP的遗传算法,提出一种二进制与十进制混合编码,改进了交叉算子,具有更强的搜
2、索能力。测试证明算法改进是有效的。关键词广义旅行商遗传算法广义染色体中图法分类号TP18;文献标识码B[1-3]GTSP定义如下:设G=(V,A,W)是一个赋权有向图,其中V={v1,v2,,,vn}为顶点集,A={(vi,vj):vi,vjIV}为弧集。令W=wij是定义在弧集A上的赋权矩阵,其中wij为弧(vi,vj)的费用。图1广义染色体模型TSP即为在赋权图G上找一条费用最小的Hamilton回路,即一条能够遍历图中的一切顶点,而且起点与广义染色体的长度为2m^+m,左边含有m^个终点重合的路。在GTSP中,
3、顶点集V变为p个点基因的部分称为染色体的头部,右边含有m^+m个群的并集,V=V1GV2G,Vp,目标是要找到一条基因的部分称为身体。能够遍历p个点群的、费用最小的Hamilton回路。当i[m^时,此广义染色体的第i个基因在头解决GTSP就要考虑以下两点:第一,点群内代表顶部,这个基因包含的信息为参数l(l[
4、Vi
5、),其中点的选取;第二,把每个点群看作一个点后再把问题
6、Vi
7、为第i个点群内所含顶点的个数。它表示当简化为这些点的TSP问题。用遗传算法求解TSP前路径到达点群ui时,只要经过这个点群的第l个时,使用十
8、进制编码易读懂,易操作。对GTSP,关键顶点即可。头部解释了可行解在经过一个点群时,在于怎样编码才能把点群内顶点选取与点群遍历顺应该经过该点群的哪个顶点。序的信息结合起来放到染色体中。身体编码与用GA求解TSP的染色体一致,解释了点群和散点的遍历顺序。1广义染色体2编码改进[4]WuChunguo等定义了一种分为两部分的广义染色体(见图1),考虑到TSP是GTSP的一种特在遗传算法的过程中的,变异概率是很低的。例,把只含有一个顶点的点群称为散点。不妨设一变异概率取大些,传统的变异算子将导致算法随机个GTSP问题中有m
9、^个点群,m个散点,则最优解要性很大,使搜索过程过于盲目;而较小的变异概率使经过m^+m个顶点。变异算子引入新染色体的机会少。相对来说,交叉算子是影响头部染色体的最关键算子。2007年2月8日收到第一作者简介:赵曦(1979)),男,湖南湘潭人,助教,硕士,研文献[4]提出的遗传算法的、头部的交叉过程究方向:组合优化,仿生算法。E-mai:lzhccc20@126.com。中,父辈的两个染色体只是交换了原有的基因段,并2982科学技术与工程7卷没有产生新的信息,所以头部染色体在初始化后只能通过变异来产生新的信息。但是
10、,变异概率太小,3实验结果引入新染色体的机会少。所以在迭代过程中,染色体初始化后,头部染色体内的原始顶点只能通过变假设GTSP实例含有4个点群,点群内顶点个异算子来产生不同于初始化种群的新的头部。因数分别为10,20,30,40。则染色体头部的四个基因此,搜索的范围有局限性,最后很有可能找不到全局位的取值分别为1~10,1~20,1~30,1~40。表1最优解。给出了改进算法与原算法在不同的迭代次数对于头为了解决上述提到的,交叉算子不能产生新的部的不同搜索范围,表1中的数据为当前迭代次数头部信息的问题,本文提出一种新
11、的混合编码(见可以取到的值的个数。其中,种群规模为50,迭代图2),和新的交叉算子。头部为二进制的编码,身中没有进行变异操作。体和原编码一样。表1改进算法与原算法的搜索范围比较改进算法1-101-201-301-40原算法1-101-201-301-40第1代961818第1代961818第5代9172324第5代961818图2混合编码模型第10代10182425第10代961818H={h
12、h=[h(1),h(2),,,h(m^)],h(i)=[a1,a2,,.aN]},i(ajI{0,1},1[j[Ni,Ni=
13、[log2
14、ui
15、,i[4结论m^])。头部解码过程:基于广义染色体的遗传算法可以有效求解h=[h(1),h(2),,,h(m^)][h(1)modGTSP,本文提出一种二进制与十进制混合编码,改
16、u1
17、,h(2)mod
18、u2
19、,,,h(m^)mod
20、um^
21、]。进了交叉算子。测试证明了改进后的交叉算子具有由上述解码过程,通过取模运算,头部基因
