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

基于遗传算法的最短路径探索摘要：最短路径问题是图论中的典型问题，它在生产和生活中具有广泛的实例。本文对遗传算法求解最短路径问题作了有益的尝试，详细分析了求解最正确路径的遗传算法的构成要素，着重探讨遗传算法求解最短路径问题的可行性。关键词：遗传算法；最短路径；适应函数；选择；交叉；变异；可行性研究exploringtheshortestpathBasedongeneticalgorithmsAbstract：Asthedevelopmentofhumansociety,peoplearefortherequestonproblemsolvingdoesnotmerelystopatthepointoffeasibility,butturnstoconcision,efficiencyandspeediness.Itnotonlymeetspeople’sneedsforthegeneralstudyandlife,butalsorequiresusingchtheasleastresources,sutimeandspace,toachievethebestresult.Thisarticletriestoworkouttheshortestpathofgeneticalgorithm,andparticularlyanalysestheconstituentelementsofthebestpathofgeneticalgorithm,andmainlydiscussesthefeasibilityoftheshortestpathofgeneticalgorithm.KeyWords：geneticalgorithm;shortestpath;feasibility1引言遗传算法〔geneticalgorithm，下面简称GA〕是基于生物进化原理的一种全局性优化算法，是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法，是生物遗传技术和电脑技术结合的产物。它采用的是启发性知识的智能搜索算法，在高空间复杂问题上比以往有更好的结果。它提供应我们的是一种通用的算法框架，具有很强的适应性，对特殊问题提供了极大的灵活性。GIS领域中所涉及的很多有关最优化问题的算法具备了遗传算法的结构特征，这些问题包括最正确路径分析、资源分配、连通分析、流分析以及决策支持系统中的决策理论等。本文选择了其中最富有代表性的最短路径问题，着重探讨遗传算法求解最短路径问题的可行性。最短路径问题是图论中的一个典范问题。从网络模型的角度看最短路径分析就是在指定网络的两节点间找一条阻碍强度最小的路径。但最短路径的含义并不是地理位置的最短距离，还可以引申到其它的度量，如:时间、费用、容量等，实际中常用于车载导航系统及各种城市应急系统中。最短路径问题通常有两类:一类是求取从某一源点到其余各点的最短路径，另一类是求取每一对顶点之间的最短路径。目前的研究工作主要集中于算法实现的优化改良与应用方面。最短路径计算分静态最短路计算和动态最短路计算。静态路径最短路是外界环境不变，计算最短路径。主要有Dijkstra算法，A*算法。动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路径。最短路径问题，用图论术语描述如下:在图G(V,A)中.V表示顶点集合.V=(v，v,…,v)对G中的某一12n条边(v,v).相应地有一个数d(v,v)。如果G中不存在边(v,v),则令d(v,v)=∞，如把d(v,v)认为是边(v,v)ijijijijijij的长度(也可认为是边(v,v)的费用或权)，则路的长度定义为组成路的各条边的长度的总和。顶点v,v之间ijij是否有边相连，由邻接矩阵来决定。邻接矩阵A:对一个具有V个顶点，e条边的图G的邻接矩阵A=[a]是一ij个v*v阶方阵，其中a=1，表示v和v邻接，a=0，表示v和v不相邻接(或i=j)。ijijijij2最短路径问题的遗传算法的表示与实现用遗传算法求解一个优化问题.就是对该优化问题存在许多解x，计算每个x对应的适应函数f.优化的过iii程就是要寻找这样的x。，使得与之对应的f(x)最大或最小。用遗传算法求解的过程是根据待解问题的参数集mm进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足迭代收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交又、变异、操作，循环往复直到满足条件。遗传算法的算法表示如下：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)为