最优路径规划算法设计报告

...wd......wd......wd...最优路径规划算法设计问题概述兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。兵力机动模型包括行军模型、战斗转移模型、机动能力评估模型。涉及的关键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、行军方案评估与优选等。最优路径问题又称最短路问题。是网络优化中的基本问题，如TSP问题等。下面先举例说明该问题。最短路问题〔SPP－shortestpathproblem〕一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交织，因此有多种行车路线，这名司机应选择哪条线路呢假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。旅行商问题〔TSP－travelingsalesmanproblem〕一名推销员准备前往假设干城市推销产品。如何为他〔她〕设计一条最短的旅行路线〔从驻地出发，经过每个城市恰好一次，最后返回驻地〕最短路问题是组合优化中的经典问题，它是通过数学方法寻找离散时间的最优编排、分组、次序、或筛选等，这类问题可用数学模型描述为.其中，为目标函数，为约束函数，为决策变量，表示有限个点组成的集合。一个组合最优化问题可用三个参数表示，其中表示决策变量的定义域，表示可行解区域，中的任何一个元素称为该问题的可行解，表示目标函数，满足的可行解称为该问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知，只要将中有限个点逐一判别是否满足的约束并比较目标值的大小，就可以得到该问题的最优解。以上述TSP问题为例，具体阐述组合优化问题：此模型研究对称TSP问题,一个商人欲到个城市推销产品，两个城市和之间的距离，用数学模型描述为，，约束条件决策变量表示商人行走的路线包含从城市到的路，而表示商人没有选择走这条路；的约束可以减少变量的个数，使得模型中共有个决策变量。每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时间为代价的，在TSP问题中，用个城市的一个排列表示商人按这个排列序推销并返回起点。假设固定一个城市为起终点，那么需要个枚举。以计算机可以完成个城市所有路径枚举为单位，那么个城市的计算时间为：以第个城市为起点，第个到达城市有可能是第个、第个、……、第个城市。决定前两个城市的顺序后，余下是个城市的所有排列，枚举这个城市的排列需要，所以，个城市的枚举需要。类似地归纳，城市数与计算时间的关系如表1所示。表1枚举时城市数与计算时间的关系城市数2425262728293031计算时间天天年年通过表1可以看出，随着城市数的增加，计算时间增加非常之快，当城市数增加到30时，计算时间约为10.8年，实际计算中已无法承受。在城市数较多时，枚举已不可取，我们可以采用一些别的方法缩短计算时间。TSP问题是NP难问题，其可能的路径数目与城市数目是成指数型增长的，所以一般很难求出其最优解，因而一般是找出其有效的近似求解算法。遗传算法可以用来解决一些较为复杂的系统问题，显然旅行商问题是需要编码运算的，而遗传算法本身的特征正好为解决这一问题提供了很好的途径。NP问题：是指非确定多项式问题类。假设存在一个多项式函数和一个验证算法，使得：判定问题的任何一个实例为“是〞实例当且仅当存在一个验证字符串，满足其输入长度不超过，其中为的输入长度，且算法验证实例为“是〞实例的计算时间不超过,那么称判定问题是非确定多项式的。对于判定问题，假设NP中的任何一个问题可在多项式时间内归约为判定问题，那么称为NP难问题。知识准备根据实际需求，本文拟给出三种算法针对不同的情况做出解答。分别是基于图论和网络优化的Dijkstra和Floyd—Warshall算法。这两种算法用来解决起点与终点不重合的问题。最后根据现有智能优化计算中的遗传算法计算哈密尔顿回路问题，即起点与终点重合问题。图论基本知识有向图的定义：一个有向图是由一个非空有限集合和中某些元素的有序对集合构成的二元组，记为。其中称为图的顶点集，中的每一个元素，称为该图的一个顶点；称为图的弧集，记为，记有向图和〔c〕是无向图，〔b〕是有向图邻接矩阵表示法图的邻接矩阵是如下定义的：是一个的0-1矩阵，即，，也就是说，如果两节点之间有一条弧，那么邻接矩阵中对应元素为1，否那么为0.图〔a〕和图〔b〕的邻接表矩阵即为在计算机中用二维数组表示，两节点之间有弧相应的元素为1.必须指出的是：目前为止，一切最短路算法都只对不含负有向圈的网络有效。实际上，对于含负有向圈的网络，其最短路问题是NP-hard。因此，除非特别说明，一律假定网络不包含负有向圈。此外在实际问题中也会遇到无向网络上的最短路问题，这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧上的权全为非负数，只需将无向图的一条边代之以两条对称的有向弧即可。如果弧上的权有负有正，一般来说问题要复杂得多，要具体问题具体分析。本文中所要解决的问题都取权值为正，无向图皆采取两条对称的有向弧问题。，其中，与关联，称是图的一条道路，为路长，顶点和分别称为的起点和终点，而称为他的内部顶点。假设道路的边互不一样，那么称为迹。假设道路的顶点互不一样，那么称为轨。称一条道路是闭的，如果它有正的长且起点和终点一样。起点和终点重合的轨叫做圈(cycle)。假设图G的两个顶点u,v间存在道路，那么称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d(u,v)。假设图G的任二顶点均连通，那么称G是连通图。显然有：(i)图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2；(ii)图C是一个圈的充要条件是C是各顶点的度均为2的连通图应用以行军途中各目标为图G的顶点，两目标之间的连线为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)—两目标之间的距离长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作。算法设计Dijkstra算法1.1定义预览：Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，注意该算法要求图中不存在负权边。算法描述算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合〔用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将参加到集合S中，直到全部顶点都参加到S中，算法就完毕了〕，第二组为其余未确定最短路径的顶点集合〔用U表示〕，按最短路径长度的递增次序依次把第二组的顶点参加S中。在参加的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。2〕算法步骤：a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，假设v与U中顶点u有边，那么<u,v>正常有权值，假设u不是v的出边邻接点，那么<u,v>权值为∞。b.从U中选取一个距离v最小的顶点k，把k参加S中〔该选定的距离就是v到k的最短路径长度〕。c.以k为新考虑的中间点，修改U中各顶点的距离；假设从源点v到顶点u的距离〔经过顶点k〕比原来距离〔不经过顶点k〕短，那么修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。d.重复步骤b和c直到所有顶点都包含在S中。3〕算法实例图1是5个节点的赋权无向图图1各节点之间的赋权无向图11010023055010603204图1中有5个节点〔〕，且是无向图。每条弧有相应的权值。编码时假设两节点之间没有弧，其相应的权值用99999表示其代码如下：intconstMAXLENTH=50;intconstMAX=99999;voidDijkstra(intn,intv,int*dist,int*prev,intc[MAXLENTH][MAXLENTH])//迪杰斯特拉算法，计算最短路径{ bools[MAXLENTH]; inti,j; for(i=1;i<=n;++i) { dist[i]=c[v][i]; s[i]=false; if(dist[i]==MAX) prev[i]=0; else prev[i]=v; } dist[v]=0; s[v]=true; for(i=2;i<=n;++i) { intt=MAX; intu=v; for(j=1;j<=n;++j) { if((!s[j])&&dist[j]<t) { u=j; t=dist[j]; } } s[u]=true; for(j=1;j<=n;++j) if((!s[j])&&c[u][j]<MAX) { intnewdist=dist[u]+c[u][j]; if(newdist<dist[j]) { dist[j]=newdist; prev[j]=u; } }}}输入：以二维数组的形式表示邻接矩阵，即相应的弧及其权值，数组下标表示弧。输出：最短路径所经过的节点及其距离值运行实例，得到邻接矩阵和最短路径Floyd算法2.1定义预览Floyd-Warshall算法〔Floyd-Warshallalgorithm〕是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。2.2算法描述1〕算法思想原理Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释〔这个诠释正是动态规划最富创造力的精华所在〕从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过假设干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。假设图权的邻接矩阵为，来存放各边长度，其中：之间没有边，在程序中以各边都不可能到达的充分大数代替是之间边的长度，。递推产生一个矩阵序列，其中表示从顶点到顶点的路径上所经过的顶点序号不大于的最短路径长度。计算时用迭代公式：是迭代次数，。最后，当时，即是各顶点之间的最短通路值。2〕算法描述a.从任意一条单边路径开场。所有两点之间的距离是边的权，如果两点之间没有边相连，那么权为无穷大。b.对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。3〕应用有四点和它们之间的路径如图2所示图2赋权无向图11032749999399994算法代码实现voidfloyd(mgraph*g)//floyd算法处理矩阵{ intA[ma][ma],path[ma][ma]; inti,j,k; for(i=1;i<=g->n;i++) for(j=1;j<=g->n;j++) { A[i][j]=g->edges[i][j]; path[i][j]=-1; } for(k=1;k<=g->n;k++)//先确定k点，找寻经过k点的最短路径的节点 { for(i=1;i<=g->n;i++) for(j=1;j<=g->n;j++)if(A[i][k]!=0&&A[k][j]!=0&&A[i][j]>(A[i][k]+A[k][j])) { A[i][j]=A[i][k]+A[k][j]; path[i][j]=k; } } cout<<endl; cout<<"输出最短路径"<<endl; i=g->n; dispath(A,path,i);}运行结果如下遗传算法3、1算法简介遗传算法〔GeneticAlgorithms，简称GA〕是一种基于自然选择原理和自然遗传机制的搜索〔寻优〕算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原那么逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原那么选择优良个体〔评估适应度〕、被选出的优良个体两两配对，通过随机穿插其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：〔1〕根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。〔2〕对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。〔3〕确定进化参数群体规模M、穿插概率、变异概率、进化终止条件。为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候完毕，它可以设定到某一代进化完毕，也可能根据找出近似最优是否满足精度要求来确定。表1列出了生物遗传概念在遗传算法中的对应关系。表1生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存最优目标值的解有最大的可能被留住个体解染色体解的编码〔一条路径包含假设干个节点〕基因解中每一分量的特征〔节点〕适应性适应度函数值种群根据适应度函数值选取的一组解交配通过交配原那么产生一组新解的过程变异编码的某一分量发生变化的过程遗传算法是一种数值求解的方法,是一个有普适性的方法,对目标函数的性质几乎没有要求,甚至都不一定要显式地写出目标函数,遗传算法所具有的特点是记录一个群体,它可以记录多个解。遗传算法在给问题的决策变量编码后,其计算过程是比较简单的，且可以较快得到一个满意解。3.2遗传算法的主要构造过程图3遗传算法的主要构造过程示意图最优化问题描述最优化问题描述第一步第二步确定决策变量、约束条件建设优化模型第一步第二步确定决策变量、约束条件建设优化模型目标函数个体表现型X目标函数个体表现型X第五步第三步第四步确定适应度转换规那么编码方法解码方法第五步第三步第四步确定适应度转换规那么编码方法解码方法适应度个体基因型X适应度个体基因型X设计遗传算子设计遗传算子第六步第六步确定运行参数第七步确定运行参数第七步遗传算法遗传算法3.3模型与算法应用举例：100个目标的经度、纬度如表2所示。表2目标经度和纬度经度纬度经度纬度经度纬度经度纬度53.712115.304651.17580.032246.325328.275330.33136.934856.543221.418810.819816.252922.789123.104510.158412.481920.105015.45621.94510.205726.495122.122131.48478.964026.241818.176044.035613.540128.983625.987938.472220.173128.269429.001132.19105.869936.486329.72840.971828.14778.958624.663516.561823.614310.559715.117850.211110.29448.15199.532522.107518.55690.121518.872648.207716.888931.949917.63090.77320.465647.413423.778341.86713.566743.54743.906153.352426.752630.816513.459527.71335.070623.92227.630651.962122.851112.793815.73074.95688.366921.505124.090915.254827.21116.20705.144249.243016.704417.116820.035434.168822.75719.44023.920011.581214.567752.11810.40809.555911.421924.45096.563426.721328.566737.584816.847435.66199.933324.46543.16440.77756.957614.470313.636819.866015.12243.16164.242818.524514.359858.684927.148539.516816.937156.508913.709052.521115.795738.43008.464851.818123.10598.998323.644050.115623.781613.79091.951034.057423.396023.06248.431919.98575.790240.880114.297858.828914.522918.66356.743652.842327.288039.949429.51149.155624.066453.798927.266228.781227.66598.083127.67059.155614.130453.79890.219933.64900.39801.349616.835949.98166.082819.363517.662236.954523.026515.732019.569711.511817.388444.039816.263539.713928.42036.990923.180438.339219.995024.654319.605736.998024.39924.15913.185340.140020.303023.98769.403041.108427.7149我方有一个基地，经度和纬度为〔70，40〕，假设我方有一部队乘坐飞机从基地出发，侦察完所有目标，再返回原来的基地。假设飞机的速度为1000公里/小时，到达每一目标之后不做停留，求侦察完所有目标之后花费的时间。显然这是一个旅行商问题。我们依次给基地编号为1，目标依次编号为2，3，…101,最后我方基地再重复编号为102。距离矩阵，其中表示两点的距离，，这里为实对称矩阵。那么问题就是，求一个从点1出发，走遍所有中间点，到达点102的一个最短路径。上面问题中给定的是地理坐标〔经度和纬度〕，我们必须要求两点间的实际距离。设两点的地理坐标为，过两点的大圆的劣弧长即为两点的实际距离。以地心为坐标原点，以赤道平面为平面，以0度经线圈所在的平面为平面建设三维直角坐标系。那么两点的直角坐标分别为：其中为地球半径。两点的实际距离，化简得。求解的遗传算法的参数设定如下：种群大小：最大代数：穿插率：，穿插概率为1能保证种群的充分进化。变异率：，一般而言，变异发生的可能性较小。编码策略采用十进制编码，用随机数列作为染色体，其中每一个随机序列都和种群中的一个个体相对应，例如一个9城市问题的一个染色体为其中编码位置代表城市，位置的随机数表示城市在巡回中的顺序，我们将这些随机数按升序排列得到如下巡回：初始种群本文中我们先利用经典的近似算法—改良圈算法求得一个较好的初始种群。即对于初始圈，交换与之间的顺序，此时的新路径为：记，那么以新的路径修改旧的路径，直到不能修改为止。目标函数目标函数为侦察所有目标的路径长度，适应度函数就取为目标函数，我们要求穿插操作我们的穿插操作采用单点穿插。设计如下，对于选定的两个父代个体，我们随机地选取第个基因处为穿插点，那么经过穿插运算后得到的子代编码为和，的基因由的前个基因和的后个基因构成，的基因由的前个基因和的后个基因构成，例如:设穿插点为第四个基因处，那么穿插操作的方式有很多种选择，我们应该尽可能选取好的穿插方式，保证子代能继承父代的优良特性。同时这里的穿插操作也蕴含了变异操作。变异操作变异也是实现群体多样性的一种手段，同时也是全局寻优的保证。具体设计如下，按照给定的变异率，对选定变异的个体，随机地取三个整数，满足，把，之间〔包括和〕的基因段插到后面。选择采用确定性的选择策略，也就是说选择目标函数值最小的个个体进化到下一代，这样可以保证父代的优良特性被保存下来。模型求解与结论经由matlab编程可得path=Columns1through1611734567721427488229287837430Columns17through322042155180509604018108497317977Columns33through4885656411766994701963622629346690Columns49through64868397888614928574723588125687Columns65through80227137321324169141473337555453Columns81through96128969655443898100562199101524659Columns97through1029343363595102long=4.0054e+04所花时间为40小时左右，其中一个侦察路径图如图2所示图2侦察路径图算法说明：输入为各个目标的地理坐标，以文件的形式导入。loadsj.txt%加载敌方100个目标数据输出为最优路径所经过的各节点及其路径图五、模型扩展遗传算法作为现代优化算法之一，其主要特点是对非线性极值问题能以概率1跳出局部最优解，找到全局最优解。而遗传算法这种跳出局部最优寻找全局最优特性都基于算法中的穿插和变异。在传统遗传算法的构造中，变异操作在穿插操作根基上进展，强调的是穿插作用，认为变异只是一个生物学背景机制。在具体穿插操作中，通常采用断点穿插法〔段穿插〕多点穿插与均匀穿插，其中断点穿插是指随机地在基因序列中选择一个断点，然后交换双亲上断点右端的所有染色体。在变异操作中，变异算子一般是用Guassian分布的随机变异来实现。本文根据以上特点对基于求解最优路径规划的遗传算法进展改良，首先将变异操作从穿插操作中别离出来，使其成为独立的并列于穿插的寻优操作，在具体遗传操作中，混沌与遗传操作联系在一起，在穿插操作中，以“门当户对〞原那么进展个体配对，利用混沌序列确定穿插点，实行强度最弱的单点穿插，以确保算法收敛精度，削弱和防止寻优抖振问题：在变异操作中，利用混沌序列对染色体中多个基因进展变异，以防止算法早熟〔过早收敛于局部的最优解，其原因为群体的规模是有限的，可以预见当群体经过假设干代的进化后，以指数级增长的具有较高平均适应度的模式将在种群中占绝大多数，而其他的模式将迅速消失。〕1、模型及算法对穿插算子和变异算子做了如下两点改良。穿插操作穿插操作设计如下：首先以“门当户对〞原那么，对父代个体进展配对，即对父代以适应度函数〔目标函数〕值进展排序，目标函数小的与小的配对，目标函数大的与大的配对。然后利用混沌序列确定穿插点的位置，最后对确定的穿插项进展穿插。例如配对，他们的染色体分别是，，采用Logistic混沌序列产生一个2到101之间的正整数，具体步骤如下：取一个〔0，1〕随机初始值，然后利用迭代一次产生1个〔0，1〕上的混沌值，保存以上混沌值作为产生下一代穿插项的混沌迭代初值，再把这个值分别乘以100并加上2，最后取整即可。假设这个数为33，那么我们对染色体中相应的基因进展穿插，得到新的染色体变异操作变异也是实现群体多样性的一种手段，是跳出局部最优，全局最优的重要保证。在本文具体变异算子设计如下，首先根据给定的变异率，随机地取两个在2到101之间的整数，对这两个数对应位置的基因进展变异，具体变异以当前的基因值，从而得到新的染色体。2、改良的穿插算子和变异算子〔1〕算法代码如下A=J;fork=1:dai%产生0~1之间随机数列进展编码B=A;%交配产生子代Bfori=1:2:wch0=rand;ch(1)=4*ch0*(1-ch0);forj=2:50ch(j)=4*ch(j-1)*(1-ch(j-1));endch=2+floor(100*ch);temp=B(i,ch);B(i,ch)=B(i+1,ch);B(i+1,ch)=temp;end%变异产生子代Cby=find(rand(1,w)<0.1);iflength(by)==0by=floor(w*rand(1))+1;endC=A(by,:);L3=length(by);forj=1:L3bw=2+floor(100*rand(1,3));bw=sort(bw);C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);endG=[A;B;C];TL=size(G,1);其运行结果图2基于改良的遗传算法优化路径图path=Columns1through181173456782487214271084184060793197Columns19through36778565641176699470196362262934669086Columns37through548397847235881256872271373213244928Columns55through72578861169141473337555453128969655Columns73through904438980501542203074838792236439346Columns91through102595198100562199101529535102long=4.0886e+04六、算法性能比较最优路径规划问题是组合最优化问题，但它不是多项式可解问题，即其目标函数并不能用一个多项式函数表示。所以此类问题还没有一个有能求得最优解的多项式时间算法，它是NP-hard问题。但是我们可以通过一些算法找到它的近似最优解。本文中的Dijkstra算法和Floyd-Warshall算法以及智能优化遗传算法都为解决这一类问题提供了很好的途径。1〕Dijkstra算法局限性：该算法只适合求两个指定顶点的最短路径，且要求权值为正。时间复杂度：O()2〕Floyd-Warshall算法局限性：时间效率低，对于多个节点之间的算法实现所需要的空间复杂度高。时间复杂度：O()3〕遗传算法遗传算法适合数值求解那些带有多参数、多变量、多目标和在多区域但连通性较差的NP-hard优化问题.对多参数、多变量的NP-hard优化问题,通过解析求解或是计算求最优解的可能性很小,主要依赖于数值求解.遗传算法是一种数值求解的方法,是一个有普适性的方法,对目标函数的性质几乎没有要求,甚至都不一定要显式地写出目标函数,因此用遗传算法