您现在的位置: 论文资源库 >> 论文资源 >> 理科论文 >> 统计学 >> 正文

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

关于一种基于基因库和多重搜索策略求解TSP的遗传算法
作者:未知 文章来源:网络 点击数: 更新时间:2009-11-24

  论文关键词:旅行商问题  遗传算法  基因库  多重搜索策略

  论文摘要:TSP是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际TSP库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。

  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)方阵里面,就构成了一个基因库,在生成初始群体的时候尽量使用基因库中的基因片段,来提高整个初始群体的适应度,从而提高算法的效率。

  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 群体演化过程

  在单亲演化算法求得的初始群体基础上,再利用多重搜索策略并行地进行群体演化,这样在保证算法的快速收敛的同时也注重了搜索空间的全局性。

...本文来自[论文资源库]lunwen.5151doc.com收集与整理,感谢原作者。
本文版权归原作者所有,如需转载或摘录请注明出处:论文资源库 http://lunwen.5151doc.com

论文录入:5151doc    责任编辑:5151doc 
【字体: 】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
| 设为首页 | 加入收藏 | 联系站长 | 在线投稿 | 版权申明 | 网站登陆 |