论文 关键词：旅行商问题 遗传算法 基因库 多重搜索策略
论文摘要：tsp是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(gb—mga),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际tsp库中多个实例的测试,结果表明:算法(gb—mga)加快了遗传算法的收敛速度,也加强了算法的寻优能力。
tsp(traveling salesman problem)可以简述为:有n个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。tsp的搜索空间是有限的,如果时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的tsp,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是np难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于tsp在工程领域有着广泛的应用,如货物运输、加工调度、 网络 通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行研究。tsp的求解方法种类繁多,主要有贪婪法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。
遗传算法是一种借鉴生物界 自然 选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。wWw.133229.COM遗传算法主要包括选择、交叉和变异3个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的程度。
用遗传算法求解tsp能得到令人满意的结果,但是其收敛速度较慢,而且种群在交叉算子作用下,会陷入局部解。采用局部启发式搜索算法等,虽然能在很短的时间内 计算 出小规模城市的高质量解,一旦城市规模稍大就容易陷入局部最优解。因此,为了能够加快遗传算法的收敛速度,又能得到更好的近似最优解,该文采纳了文[5]中杨辉提出的基因库的想法,并结合文[6]中cheng-fa tsai提出的多重搜索策略思想,使用单亲演化与群体演化相结合的方式来求解tsp问题。该文根据文[7]中最小生成树mst(minimum cost spanning tree)的应用,由mst建立tsp的基因库,保存有希望成为最优解的边,利用基因库提高初始群体的质量进行单亲演化,然后利用改进后的交叉算子和的多重搜索策略进行群体演化。
1 单亲演化过程
现有的大多数演化算法在整个演化过程中所涉及的基因,大多来源于个体本身,个体质量的高低决定了算法的全局性能,如果群体中初始个体的适应度都较差,肯定要影响算法的收敛速度,对于规模稍大的tsp尤其明显[8]。该文为了克服上述弱点,首先利用普里姆算法求出tsp中最小生成树,并将各个mst中的每一条边都保存在一个n*(n-1)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。
1.1 tsp编码表示
设n个城市编号为1,2,…,n,为一条可行路径,pk=vk1vk2…vkn为一条可行路径,它是1,2,…,n的一个随机排列,其含意是第k条路径起点城市是vk1,最后一个城市是vkn,则第k条环路的总长度可以表示为:
其中,d(vki,vkj)表示城市vki与城市vkj之间的距离。在算法中环路pk的总长d(pk)用来评价个体的好坏[9]。适应度函数取路径长度d(pk)的倒数,f(pk)=1/ d(pk)。
1.2 构建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 minispantree—prim(mgraph g,vertextypeu){
struct {
vertextype adjvex;
vrtype lowcost;
}closedge[max—vertex—num];
k=locatevex(g,u);
for(j=0;j<g.vexnum;++j)
if(j!=k)closedge[j]={u,g.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=0;i<g.vexnum;++i){
k=minimum(closedge);
printf(closedge[k].adjvex,g.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<g.vexnum;++j)
if(g.arcs [k][j].adj<closedge[j].lowcost)
closedge[j]={g.vexs[k],g.arcs[k][j].adj};
}
}
1.3 单亲演化算法
单亲演化算法是利用遗传算法的优胜劣汰的遗传特性,在单个染色体内以基因重组的方式,使子代在满足tsp问题的限定条件下进行繁衍,然后保留适应度高的染色体种群,达到优化的目的。单亲演化算法的基因重组操作包括基因换位、基因段错位和基因段倒转三种操作来实现。基因换位操作是将亲代的染色体基因进行对换后,形成子代,其换位又分为单基因换位和基因段换位两种方式。基因段错位操作是随机确定基因段,也随机选定错位位置,整段错移。基因段倒转操作则是随机地确定倒转基因段的起止位置,倒转操作是对该段内基因按中垂线作镜面反射,若段内基因数为奇数时,则中位基因不变。单亲演化时可以是单个操作用于单个父代,也可以是几种操作同时采用。为了编程方便,文中采用基因段倒转操作。
2 群体演化过程
在单亲演化算法求得的初始群体基础上,再利用多重搜索策略并行地进行群体演化,这样在保证算法的快速收敛的同时也注重了搜索空间的全局性。
2.1 交叉算子
该文算子采用一种与顺序交叉ox(order crossover)法类似的交叉方法[11],即随机在串中选择一个交配区域,例如以下两个父串及交配区域选定为:
p1=(12|3456|789) p2=(98|7654|321)
将p2的交配区域加到p1的前面或后面,p1的交配区域加到p2的前面或后面,得
m1=(7654|123456789)
m2=(3456|987654321)
在m1中自交配区域后依次删除与交配区域相同的城市码,得到最终的两个子串:
s1=(765412389) s2=(345698721)
同时为了能更好地增强算子的全局搜索能力,对该算子作了如下的改进。子代个体的新边来自:随机生成和群体中其他个体,其选择比例由随机数p和阈值p来决定。如果随机数p小于阈值p,则子代个体的新边来自随机生成,否则就来自群体中的其他个体。
这种改进后的交叉算子在父串相同的情况下仍能产生一定程度的变异效果,这对维持群体的多样化特性有一定的作用。实验结果也证实了这种改进算子对于种群的全局搜索能力有一定的提高,避免搜索陷入局部解。
2.2 局部启发式算子
为了增强遗传算法的局部搜索性能,在算法中引入2-opt局部搜索算子[12]。该算子通过比较两条边并交换路径以提升算法的局部搜索性能,示例见图2。
比较子路径ab+cd和ac+bd,如果ab+cd>ac+bd则交换,否则就不交换。考虑到程序的运行效率,不可能对每对边都做检查,所以选取染色体中的一定数量的边进行比较。2-opt搜索算子实际上进行的相当于变异操作,同时又不仅仅是简单的变异,而是提高算法的局部搜索性能的变异操作。
2.3 选择机制和收敛准则
为了限制种群的规模[13],该文采用了联赛选择法的淘汰规则。联赛选择法就是以各染色体的适应度作为评定标准,从群体中任意选择一定数目的个体,称为联赛规模,其中适应度最高的个体保存到下一代。这个过程反复执行,直到保存到下一代的个体数达到预先设定的数目为止。这样做可能导致种群过早收敛,因此在收敛准则上要采取苛刻的要求来保证搜索的全局性。
遗传算法求tsp问题如果不设定终止条件,其演化过程将会无限制地进行下去。终止条件也称收敛准则,因为多数最优化问题事先并不了解最优的目标函数值,故无法判断寻优的精度。该文采用如下两条收敛准则:在连续k1代不再出现更优的染色体;优化解的染色体占种群的个数达k2的比例以上。当两准则均满足时,则终止运算,输出优化结果和对应的目标函数值。由数值实验表明,添加第2条准则之后,全局最优解的出现频率将大为提高。
由于基因库的引入,可能降低初始种群的多样性,为避免算法陷入局部最优解,因此在群体演化中采取多重搜索策略。由cheng-fa tsai提出的多重搜索策略[6],就是把染色体集中的染色体分成保守型和探索型两种不同类型的集合,然后针对不同类型的染色体集合根据不同的交叉、变异概率分别进行交叉变异操作,对保守型染色体集合就采用比较低的交叉变异概率,而对探索型染色体集合就采用比较高的交叉变异概率。这种策略对保守型染色体集合的操作最大限度地保留了父代的优秀基因片段,另一方面对探索型染色体集合的操作又尽可能地提高了算法的全局搜索能力。为了提高算法的收敛速度,初始染色体集合该文采用了前面单亲演化的结果中的染色体集合,交叉算子则利用的是前面介绍的改进后的算子,改进后的多重搜索策略见下。
3 实验结果与分析
该文的gb—mga算法由c#编程实现,所有的结果都是在p42.0g微机上完成,并进行通用的tsp库实验,选用了具有一定代表性的tsp实例,并把该算法和其他算法做了一个对比。为了减少 计算 量,程序中的数据经过四舍五入整数化处理,与实数解有一定的偏差,下面给出图kroa100的示例。
为了证明该文提出的gb—mga算法的有效性,将该文算法与典型的遗传算法ga、单亲遗传算法pga以及文[5]中杨辉提出的ge—ga(gene pool genetic algorithm)算法和文[12]中提出的mmga(modified multiple-searching genetic algorithm)算法都进行了一个对比。
实验结果证明,该文算法的求解质量要优于ga、pga、mmga算法,而求解速度方面则优于ge—ga算法,特别是对于大规模城市的tsp问题求解效果尤其明显,具有快速收敛的特性。ge—ga算法对于中等城市规模的tsp实例求解,其运算时间就大幅度增加,如果把该算法用于求解大规模和超大规模tsp问题,那么时间上的代价就让人无法忍受。而该文的gb—mga算法在单亲遗传演化中就使用了基因库中的优质基因,使得单个个体的进化速度大大提高,从而为进一步的演化提供了条件,群体演化过程的选择机制和收敛准则的恰当选取使得算法在注重了求解质量的同时兼顾了算法的效率。
结束语 该文在对tsp问题进行分析的基础上,通过对全局最优解和局部最优解中的边关系的分析发现,通过最小生成树的求解保存最有希望成为全局最优解的边,可以提高算法的效率,同时并不降低搜索的性能。在实验中发现,通过生成基因库快速提高种群质量,虽然可以快速收敛,但是tsp问题的求解质量并没有达到一个可以接受的程度,因此在群体演化阶段中又加入了2-opt局部搜索算子和多重搜索策略,对不同类型的染色体以不同几率进行选择交叉操作。
用该算法测试tsp库中的典型实例,结果显示,对初始种群运用单亲遗传算法,并引入基因库方法是可行的,有效地提高了算法的效率和收敛速度,在群体演化过程中引入多重搜索策略的方法,提高了算法的并行性和全局寻优性能,即使在较少的寻优步数也能得到适应度不错的局部优化解。gb-mga算法在提高算法求解质量的同时兼顾了算法的效率, 但是其中还有许多有待解决的问题,比如如何构建高质量的基因库,如何对现有基因库进行优化和扩充,以及算法中一些参数的选取问题等,这些方面,还需要进一步的研究。
参考 文献
1 bck t b,hammel u,schwefel h p.evolutionary computation:comments on the history and current state [j]. leee transactions on evolutionary computation,1997,2(6):3~17
2王磊,潘进,焦李成.免疫算法[j]. 电子 学报,2000,28(7):74~78
3 dorigo m,gambardella l m.ant colony system:a cooperativelearning approach to the traveling salesman problem [j]. ieeetransactions on evolutionary computation,1997,2(8):53~66
4 holland j h. adaptation in natural and artificial systems [m].ann arbor:the university of michigan,1975.10~15
5杨辉,康立山,陈毓屏.一种基于构建基因库求解tsp问题的遗传算法[j].计算机学报,2003,26(12):1753~1758
6 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):6~12
7 baraglia r,hidalgo j i, perego r. a hybrid heuristic for thetraveling salesman problem [j]. ieee transactions on evolutionary computation,2001,5(12):613~622
8 tsai cheng-fa, tsai chun-wei. a new approach for solvinglarge traveling salesman problem using evolutionary ant rules[c].in:proc.of the 2002 international joint conf.on neural networks,hawaiian:honolulu,2002
9 jung s,moon b r.toward minimal restriction of genetic encoding and crossovers for the two-dimensional euclidean tsp [j].ieee transactions on evolutionary computation,2002,6(12):557~565
10李茂军,童调生,罗隆诵.单亲遗传算法及其应用研究[j].湖南大学学报,1998,25(6):56~59
11陈国良,王煦法,庄镇泉,等.遗传算法及其应用[m].徐修存,王晓丹.北京:人民邮电出版社,1996.75~81
12 watson j,ross c,eisele v,et al. the traveling salesrep problem,edge assembly crossover, and 2-opt [c].parallel problemsolving from nature v,netherlands: amsterdam,1998
13 burkowski f j.proximity and priority: applying a gene expressionalgorithm to the traveling salesperson problem [j]. parallelcomputing,2004,30(5-6):803~816
