基于遗传算法的最短路径探索

基于遗传算法的最短路径探索摘要：最短路径问题是图论中的典型问题，它在生产和生活中具有广泛的实例。本文对遗传算法求解最短路径问题作了有益的尝试，详细分析了求解最佳路径的遗传算法的构成要素，着重探讨遗传算法求解最短路径问题的可行性。关键词：遗传算法；最短路径；适应函数；选择；交叉；变异；可行性研究exploringtheshortestpathBasedongeneticalgorithmsAbstract：Asthedevelopmentofhumansociety,peoplearefortherequestonproblemsolvingdoesnotmerelystopatthepointoffeasibility,butturnstoconcision,efficiencyandspeediness.Itnotonlymeetspeople’sneedsforthegeneralstudyandlife,butalsorequiresusingtheleastresources,suchastimeandspace,toachievethebestresult.Thisarticletriestoworkouttheshortestpathofgeneticalgorithm,andparticularlyanalysestheconstituentelementsofthebestpathofgeneticalgorithm,andmainlydiscussesthefeasibilityoftheshortestpathofgeneticalgorithm.KeyWords：geneticalgorithm;shortestpath;feasibility1引言遗传算法（geneticalgorithm，下面简称GA）是基于生物进化原理的一种全局性优化算法，是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法，是生物遗传技术和计算机技术结合的产物。它采用的是启发性知识的智能搜索算法，在高空间复杂问题上比以往有更好的结果。它提供给我们的是一种通用的算法框架，具有很强的适应性，对特殊问题提供了极大的灵活性。GIS领域中所涉及的很多有关最优化问题的算法具备了遗传算法的结构特征，这些问题包括最佳路径分析、资源分配、连通分析、流分析以及决策支持系统中的决策理论等。本文选择了其中最富有代表性的最短路径问题，着重探讨遗传算法求解最短路径问题的可行性。最短路径问题是图论中的一个典范问题。从网络模型的角度看最短路径分析就是在指定网络的两节点间找一条阻碍强度最小的路径。但最短路径的含义并不是地理位置的最短距离，还可以引申到其它的度量，如:时间、费用、容量等，实际中常用于车载导航系统及各种城市应急系统中。最短路径问题通常有两类:一类是求取从某一源点到其余各点的最短路径，另一类是求取每一对顶点之间的最短路径。目前的研究工作主要集中于算法实现的优化改进与应用方面。最短路径计算分静态最短路计算和动态最短路计算。静态路径最短路是外界环境不变，计算最短路径。主要有Dijkstra算法，A*算法。动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路径。最短路径问题，用图论术语描述如下:在图G(V,A)中.V表示顶点集合.V=(v1，v2,…,vn)对G中的某一条边(vi,vj).相应地有一个数d(vi,vj)。如果G中不存在边(vi,vj),则令d(vi,vj)=∞，如把d(vi,vj)认为是边(vi,vj)的长度(也可认为是边(vi,vj)的费用或权)，则路的长度定义为组成路的各条边的长度的总和。顶点vi,vj之间是否有边相连，由邻接矩阵来决定。邻接矩阵A:对一个具有V个顶点，e条边的图G的邻接矩阵A=[aij]是一个v*v阶方阵，其中aij=1，表示vi和vj邻接，aij=0，表示vi和vj不相邻接(或i=j)。2最短路径问题的遗传算法的表示与实现用遗传算法求解一个优化问题.就是对该优化问题存在许多解xi，计算每个xi对应的适应函数fi.优化的过程就是要寻找这样的xm。，使得与之对应的f(xm)最大或最小。用遗传算法求解的过程是根据待解问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足迭代收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交又、变异、操作，循环往复直到满足条件。遗传算法的算法表示如下：ProcedureevolutionprogramBegint←0初始化P(t)评估P(t)While(不满足终止条件)do重组P(t)获得c(t)从P(t)和C(t)中选择P(t+1)t←t+1endend其中，P(t)为第t代的双亲；C(t)为第t代的后代;t为进化代数。对于一个给定的图模型，将图中各顶点按顶点号自然排序，然后按此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选人该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在此条通路中出现的先后顺序，染色体的长度应等于该图中的顶点个数。2.1适应函数f(i)为了指导遗传算法的进化方向，需要为它设定一个优良的向导——适应度函数。对具有二个顶点的图，已知各顶点(vi,vj)的边长度d(vi,vj)，把vi1到vjn间的一条通路vi1,vjn,…,vin的路径长度定义为适应函数:111),()(nririrvvdif对该优化问题，就是要寻找解xm，使f(xm)值最小。用适应度函数的值来评价个体的优劣，个体的适应度越大，则其性能就越优；否则就越差。由于VRPHTW属于最小化问题，其优化目标是在给定的约束条件下，使车辆调度的总成本最小，即目标函数的值越小，对应个体的适应度就越大，该个体就越优良，其相应的解的性能就越优。通常，对于求目标函数最小值的优化问题，变换方法为：maxmaxmax)()(0)()(CXfCXfififxfCXF其中，Cmax是一个适当的相对比较大的数，它可用下面几种方法求得：1、预先指定的一个较大的数。2、进化到当前代为止的最大目标函数值。3、当前代或最近几代种群中的最大目标函数值。还有一种针对最小化问题的适应度函数设定方式就是使用倒数法，同时加上可以根据经验调节的参数，例如对第i个个体目标函数f(x)的总成本为Zi，则可以通过下式将其转化为适应度函数：iZZXF*)(其中ξ为一常数，可以根据经验设定，Z'为当前种群中最好个体对应的总成本。研究结果表明，仅仅使用上式来确定适应度函数，常常使得有些GA收敛得很慢，而有些则收敛的很快。由此可见，适应度函数的选择也是影响遗传算法性能的一种重要的因素。2.2交叉与变异操作将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点，位于染色体的第几位基因上.然后在此位置进行部分基因交换。变异操作是将染色体中某位基因逆变，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点.但这样做的结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。为了使算法尽可能快地获得更好的解。改善遗传算法的收敛性，在变异操作时，增加了个体求优的自学习过程。即在某位基因变异后.计算新产生的染色体的适应函数值，若适应函数值更小，即获得的路径更短，则保留;否则一保持原来的解不变。如果有连续N/3次没有得到更好的解，则该过程结束。其中N表示从起点到终点的顶点数。解最短路径问题的遗传算法如下:generate[p(c)];evaluate[p(n)];repeatnoofGenerationstimes:Selectp(n)fromp(n-1):Crossoverandmutationp(n);learning[p(n)];evaluate[p(n)];end;其中:selectp(n)fromp(n-1)表示从前一代群体中选择一对双亲，用于交叉，变异操作。p(n)代表第n代群体。generate[p(n)]表示在程序开始时要首先产生一个群体。evaluate[p(n)]表示计算每个个体适应度。3算法实现与结果3.1原始数据对解的影响交叉率pt不可选择过小，否则，延缓获得最优解的过程，本题选择pt=0.9。变异率(pm)的选择对规模大的优化问题影响很大，本题选pm=0.009。群体中的个体数的选取是算法中一个很重要的参数，群体中的个体数目越大，算法就越能找到更好的解。个体数目过小，有可能找不到最优解。3.2算例(1)求图中从1点到15点间的最短路径。图中vi到vj的数值代表两点间的路径长度。对该例用本算法求得的最短路径集为:1→3→4→6→12→15;1→2→11→13→15;1→2→11→13→14→15;1→3→4→13→15;1→3→4→13→14→15.最短路径的长度为140(2)小图给出了60个顶点的例子上图用坐标给出了60个顶点的位置，若两点vi,vj之间有连线，则权值d(vi,vj)取两点间的距离;否则d(vi,vj)取一个大数。求解过程中，迭代次数与计算结果关系见表l。对图2，求得的最短路径为:1→4→14→35→49→57→60最短路径长度为12.936。遗传算法在最初几次迭代中，个体的出现是良莠并存的，个体的适应度也不高，随着迭代次数的增加，适应度高的个体将被遗传出来。参考文献[1]施益强，伍良，陈玲等.海上溢油事故应急反应系统的框架研究[J].灾害学，2002，12:87-91.[2]黄晓霞，萧蕴诗.基于多智能体的新型智能决策支持系统体系结构的产生和发展[J]，微型电脑应用，2002,5:8,10,17.[3]于跃海，何建敏，郑瑞强，邱海波.基于案例推理的ICU应急诊断方案生成系统[M].东南大学学报(自然科学版)，2001,3:6-9.[4]张春平，关志超，杨东援.深圳应急指挥中心的最优路径规划技术研究[M].中山大学学报(自然科学版)，2003，12:160-164.[5]GoldbergDE.GeneticAlgorithmsinsearch,optimizationandmachinelearning,NewYork:Addison_Wesley,1999.[6]陈国良，吴俊敏，章锋，章隆兵.并行计算机体系结构[M].北京:高等教育出版社，2002年.[7]都志辉.高性能计算并行编程技术一MPI并行程序设计[M].北京:清华大学出版社，2001年.[8]RichardSMorrison,ClusterComputing-Architectures,OperatingSystems,ParallelProcessing&ProgrammingLanguages,SydneyUniversityofTechnology,Australia,2002.[9]高淑萍，刘三阳.应急系统调度问题的最优决策[J].系统工程与电子技术,2003,10:1022-1024.[10]戴更新，达庆利.多资源组合应急调度问题的研究[J].系统工程理论与实践，2000,20(9):52-55.[11]高经纬，张煦.求解TSP问题的遗传算法实现[M].计算机时代，2004,2:19-21.[12]李士勇.模糊控制#神级控制和智能控制论[M].哈尔滨:哈尔滨工业大学出版社,1998,1.[13]冯春,李柏林.解TSP的有序遗传算法[J].西南交通大学学报,1997,32(5):528-532.[14]尹德春.多线程技术在串口通信中的应用[J].微计算机信息,2005(8-3).[15]陈根社，陈新海.遗传算法的研究与进展[M].信息与控制，1994,23(4)