当前位置:首页 >> 电力/水利 >>

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


最优路径规划算法设计
一、问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线, 由作战空间的一 点向另外一点的位置移动,并带入实体在移动过程中发生变化的状态信息。 兵力机动模型包括行军模型、战斗转移模型、机动能力评估模型。涉及的关 键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、 行军方案评估与优选等。 最优路径问题又称最短路问题。是网络优化中的基本问题,如 TSP 问题等。 下面先举例说明该问题。 最短路问题(SPP-shortest path problem) 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。 从甲地到 乙地的公路网纵横交错, 因此有多种行车路线,这名司机应选择哪条线路呢?假 设货柜车的运行速度是恒定的, 那么这一问题相当于需要找到一条从甲地到乙地 的最短路。 旅行商问题(TSP-traveling salesman problem) 一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅 行路线(从驻地出发,经过每个城市恰好一次,最后返回驻地?) 最短路问题是组合优化中的经典问题, 它是通过数学方法寻找离散时间的最 优编排、分组、次序、或筛选等,这类问题可用数学模型描述为
min

f ( x)

s.t.

g ( x) ? 0
x?D .

其中, f ( x) 为目标函数, g ( x) 为约束函数, x 为决策变量, D 表示有限个点组 成的集合。 一个组合最优化问题可用三个参数 ( D, F , f ) 表示, 其中 D 表示决策变量的定 义域, F 表示可行解区域 F ? {x | x ? D, g ( x) ? 0} , F 中的任何一个元素称为该问
1

题的可行解, f 表示目标函数,满足 f ( x* ) ? min{f ( x) | x ? F} 的可行解 x* 称为该 问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知,只要 将 D 中有限个点逐一判别是否满足 g ( x) ? 0 的约束并比较目标值的大小,就可以 得到该问题的最优解。 以上述 TSP 问题为例,具体阐述组合优化问题: 此模型研究对称 TSP 问题,一个商人欲到 n 个城市推销产品,两个城市 i 和 j 之间的距离 dij ? d ji ,用数学模型描述为

min ? dij xij
i? j

s.t.? xij ? 1
j ?1

n

i ? 1,2,?, n ,

s.t.? xij ? 1
i ?1

n

j ? 1,2,?, n ,

i , j?s

?x

ij

?| s | ?1,2 ?| s |? n ? 2, s ? {1,2,?, n},

xij ?{0,1}, i, j ? 1,2,?, n, i ? j

约束条件决策变量 xij ? 1 表示商人行走的路线包含从城市 i 到 j 的路,而 xij ? 0 表 示商人没有选择走这条路; i ? j 的约束可以减少变量的个数,使得模型中共有

n ? (n ? 1) 个决策变量。
每一个组合优化问题都可以通过完全枚举的方法求得最优解。 枚举是以时间 为代价的,在 TSP 问题中,用 n 个城市的一个排列表示商人按这个排列序推销并 返回起点。若固定一个城市为起终点,则需要 (n ? 1)!个枚举。以计算机 1s 可以完 成 24 个城市所有路径枚举为单位,则 25 个城市的计算时间为:以第 1 个城市为 起点,第 2 个到达城市有可能是第 2 个、第 3 个、……、第 25 个城市。决定前两 个城市的顺序后, 余下是 23 个城市的所有排列, 枚举这 23 个城市的排列需要 1s , 所以, 25 个城市的枚举需要 24 s 。类似地归纳,城市数与计算时间的关系如表 1 所示。

2

表1
城市数 计算时间 24 25

枚举时城市数与计算时间的关系
26 27 28 29 30 31

1s

24 s

10 min

4.3h

4 .9 天

136 .5 天

10.8 年

325 年

通过表 1 可以看出,随着城市数的增加,计算时间增加非常之快,当城市数 增加到 30 时, 计算时间约为 10.8 年, 实际计算中已无法承受。 在城市数较多时, 枚举已不可取,我们可以采用一些别的方法缩短计算时间。 TSP 问题是 NP 难问题,其可能的路径数目与城市数目 n 是成指数型增长的, 所以一般很难求出其最优解, 因而一般是找出其有效的近似求解算法。遗传算法 可以用来解决一些较为复杂的系统问题,显然旅行商问题是需要编码运算的,而 遗传算法本身的特征正好为解决这一问题提供了很好的途径。 NP 问题:是指非确定多项式问题类。若存在一个多项式函数 g ( x) 和一个验 证算法 H ,使得:判定问题 A 的任何一个实例 I 为“是”实例当且仅当存在一个 验证字符串 S , 满足其输入长度 d ( S ) 不超过 g (d ( I )) , 其中 d ( I ) 为 I 的输入长度, 且算法 H 验证实例 I 为“是”实例的计算时间 f ( H ) 不超过 g (d ( I )) ,则称判定问 题 A 是非确定多项式的。对于判定问题 A ,若 NP 中的任何一个问题可在多项式 时间内归约为判定问题 A ,则称 A 为 NP 难问题。 二、知识准备 根据实际需求, 本文拟给出三种算法针对不同的情况做出解答。分别是基于 图论和网络优化的 Dijkstra 和 Floyd—Warshall 算法。这两种算法用来解决起点与 终点不重合的问题。 最后根据现有智能优化计算中的遗传算法计算哈密尔顿回路 问题,即起点与终点重合问题。 1、 图论基本知识 有向图的定义:一个有向图 G 是由一个非空有限集合 V (G ) 和 V (G ) 中某些元 素 的 有 序 对 集 合 E (G ) 构 成 的 二 元 组 , 记 为 G ? (V (G), E (G)) 。 其 中

V (G) ? {v1, v2 , . .v.n } , 称为图 G 的顶点集, V (G ) 中的每一个元素 vi (i ? 1,2,...,n) ,称
3

为该图的一个顶点; E(G) ? {e1 , e2 ,...,em} 称为图 G 的弧集,记为 ek ? (vi , v j ) ,记 有向图 G ? (V , E )

(a) 和(c)是无向图, (b)是有向图 2、 邻接矩阵表示法 图 G ? (V , E ) 的邻接矩阵 C 是如下定义的: C 是一个 n ? n 的 0-1 矩阵,即

?0, (i, j ) ? A ,也就是说,如果两节点之间有一条弧, C ? (cij )n?n ?{0,1}n?n , cij ? ? ?1, (i, j ) ? A
则邻接矩阵中对应元素为 1,否则为 0. 图(a)和图(b)的邻接表矩阵即为
u v w x y u ?0 1 1 0 0? ? ? v ?1 0 0 0 0? w?1 0 0 0 1? ? ? x ?0 0 1 0 0? y ?0 1 0 0 0? ? 3、 ? 在计算机中用二维数组表示,两节点之间有弧相应的元素为 1.

必须指出的是: 目前为止, 一切最短路算法都只对不含负有向圈的网络有效。 实际上,对于含负有向圈的网络,其最短路问题是 NP-hard。因此,除非特别说 明, 一律假定网络不包含负有向圈。此外在实际问题中也会遇到无向网络上的最 短路问题, 这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧 上的权 wij 全为非负数,只需将无向图的一条边代之以两条对称的有向弧即可。 如果弧上的权 wij 有负有正,一般来说问题要复杂得多,要具体问题具体分析。 本文中所要解决的问题都取权值为正,无向图皆采取两条对称的有向弧问题。
4

W ? v0e1v1e2 ...ek vk ,其中 ei ? E(G),1 ? i ? k , v j ?V (G),0 ? j ? k , ei 与 vi ?1, vi 关
联, 称 W 是图 G 的一条道路,k 为路长, 顶点 v0 和 vk 分别称为 W 的起点和终点, 而 v1 , v2 ,...,vk ?1 称为他的内部顶点。 若道路 W 的边互不相同,则 W 称为迹。若道路 W 的顶点互不相同,则 W 称 为轨。 称一条道路是闭的,如果它有正的长且起点和终点相同。起点和终点重合的 轨叫做圈(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 中指定的两个顶点 u0 , v0 间的具最小权的轨。 这条轨叫做 u0 , v0 间的最短 路,它的权叫做 u0 , v0 间的距离,亦记作 d (u0 , v0 ) 。 四、算法设计 1 Dijkstra 算法

1.1 定义预览: Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法, 用于计算一个节点 到其他所有节点的最短路径。 主要特点是以起始点为中心向外层层扩展,直到扩

5

展到终点为止。Dijkstra 算法是很有代表性的最短路径算法,注意该算法要求 图中不存在负权边。 1.2 算法描述 1) 算法思想: 设 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 个节点的赋权无向图

6

图 1 各节点之间的赋权无向图 1 10 2 30 5 50 10 60 100

3

20

4

图 1 中有 5 个节点( v1 , v2 , v3 , v4 , v5 ) ,且是无向图。每条弧有相应的权值。编码 时若两节点之间没有弧,其相应的权值用 99999 表示 其代码如下: int const MAXLENTH=50; int const MAX=99999; void Dijkstra(int n,int v,int *dist,int *prev,int c[MAXLENTH][MAXLENTH])//迪杰斯特 拉算法,计算最短路径 { bool s[MAXLENTH]; int i,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) { int t=MAX; int u=v; for (j=1;j<=n;++j) { if ((!s[j])&&dist[j]<t) { u=j;
7

t=dist[j]; } } s[u]=true; for (j=1;j<=n;++j) if((!s[j])&&c[u][j]<MAX) { int newdist=dist[u]+c[u][j]; if (newdist<dist[j]) { dist[j]=newdist; prev[j]=u; } } } } 输入: 以二维数组的形式表示邻接矩阵,即相应的弧及其权值,数组下标表示 弧。 输出: 最短路径所经过的节点及其距离值 运行实例,得到邻接矩阵和最短路径

2 2.1

Floyd 算法 定义预览 Floyd-Warshall 算法(Floyd-Warshall algorithm)是解决任意两点间的

最短路径的一种算法, 可以正确处理有向图或负权的最短路径问题,同时也被用 于计算有向图的传递闭包。Floyd-Warshall 算法的时间复杂度为 O(N3),空间复 杂度为 O(N2)。 2.2 算法描述 1) 算法思想原理
8

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 的最短路径的距离。
? a11 ?a 21 假设图 G 权的邻接矩阵为 A0 , A0 ? ? ? ? ? ?an1 a12 a22 ? an 2 ? a1n ? ? a2 n ? ? ? ? ? ? ? ann ?

来存放各边长度,其中:

aii ? 0
aij ? ?

i ? 1,2,?, n;
i , j 之间没有边,在程序中以各边都不可能达到的充分大数代替

aij ? wij a ji ? wij

wij 是 i , j 之间边的长度, i, j ? 1,2,?, n 。

递推产生一个矩阵序列 A0 , A1 ,?, Ak ,?, An ,其中 Ak (i, j) 表示从顶点 vi 到顶点 v j 的路径上所经过的顶点序号不大于 k 的最短路径长度。 计算时用迭代公式:

Ak (i, j) ? min(Ak ?1 (i, j), Ak ?1 (i, k ) ? Ak ?1 (k , j))
k 是迭代次数, i, j, k ? 1,2,?, n 。

最后,当 k ? n 时, An 即是各顶点之间的最短通路值。 2) 算法描述

9

a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间 没有边相连,则权为无穷大。 b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再 到 v 比己知的路径更短。如果是更新它。 3) 应用 已知有四点和它们之间的路径如图 2 所示 图2 1 7 3 算法代码实现 void floyd(mgraph *g)//floyd 算法处理矩阵 { int A[ma][ma],path[ma][ma]; int i,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);}
10

赋权无向图 3 4 9999 4 2 9999

10

运行结果如下

3 3、1

遗传算法 算法简介 遗传算法(Genetic Algorithms,简称 GA)是一种基于自然选择原理和自

然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系 统中实现特定目标的优化。 遗传算法的实质是通过群体搜索技术,根据适者生存 的原则逐代进化,最终得到最优解或准最优解。它必须做以下操作:初始群体的 产生、 求每一个体的适应度、 根据适者生存的原则选择优良个体 (评估适应度) 、 被选出的优良个体两两配对, 通过随机交叉其染色体的基因并随机变异某些染色 体的基因后生成下一代群体, 按此方法使群体逐代进化, 直到满足进化终止条件。 其实现方法如下: (1) 根据具体问题确定可行解域,确定一种编码方法,能用数值串或字符串表 示可行解域的每一解。 (2) 对每一解应有一个度量好坏的依据,它用一函数表示,叫做适应度函数, 适应度函数应为非负函数。 (3) 确定进化参数群体规模M 、 交叉概率 pc 、 变异概率 pm 、 进化终止条件。 为便于计算,一般来说,每一代群体的个体数目都取相等。群体规模越大、越容
11

易找到最优解,但由于受到计算机的运算能力的限制,群体规模越大,计算所需 要的时间也相应的增加。 进化终止条件指的是当进化到什么时候结束,它可以设 定到某一代进化结束,也可能根据找出近似最优是否满足精度要求来确定。表1 列出了生物遗传概念在遗传算法中的对应关系。 表1 生物遗传概念 适者生存 个体 染色体 基因 适应性 种群 交配 变异 生物遗传概念在遗传算法中的对应关系 遗传算法中的作用 最优目标值的解有最大的可能被留住 解 解的编码(一条路径包含若干个节点) 解中每一分量的特征 适应度函数值 根据适应度函数值选取的一组解 通过交配原则产生一组新解的过程 编码的某一分量发生变化的过程 (节点)

遗传算法是一种数值求解的方法, 是一个有普适性的方法, 对目标函数的 性质几乎没有要求, 甚至都不一定要显式地写出目标函数, 遗传算法所具有的 特点是记录一个群体, 它可以记录多个解。 遗传算法在给问题的决策变量编码后, 其计算过程是比较简单的,且可以较快得到一个满意解。 3.2 遗传算法的主要构造过程

12

图 3

遗传算法的主要构造过程示意图
最优化问题描述

第一步

确定决策变量、 约束条件

建立优化模型

第二步

个体表现型 X

目标函数 f ( X )

第三步

编码方法

解码方法

第四步

确定适应度转换规则

第五步

个体基因型 X

适应度 F ( X )

设计遗传算子

第六步

确定运行参数

第七步





算 法

3.3 模型与算法 应用举例: 已知100个目标的经度、纬度如表2所示。

13

表2 经度 53.7121 56.5432 20.1050 26.2418 28.2694 8.9586 8.1519 31.9499 43.5474 23.9222 21.5051 17.1168 52.1181 37.5848 14.4703 58.6849 38.4300 13.7909 40.8801 39.9494 8.0831 1.3496 15.7320 6.9909 4.1591 纬度 15.3046 21.4188 15.4562 18.1760 29.0011 24.6635 9.5325 17.6309 3.9061 7.6306 24.0909 20.0354 0.4080 16.8474 13.6368 27.1485 8.4648 1.9510 14.2978 29.5114 27.6705 16.8359 19.5697 23.1804 3.1853 经度 51.1758 10.8198 1.9451 44.0356 32.1910 16.5618 22.1075 0.7732 53.3524 51.9621 15.2548 34.1688 9.5559 35.6619 19.8660 39.5168 51.8181 34.0574 58.8289 9.1556 9.1556 49.9816 11.5118 38.3392 40.1400

目标经度和纬度 经度 46.3253 22.7891 26.4951 28.9836 36.4863 10.5597 0.1215 47.4134 30.8165 12.7938 6.2070 9.4402 24.4509 24.4654 3.1616 56.5089 8.9983 23.0624 18.6635 53.7989 53.7989 19.3635 44.0398 24.6543 23.9876 纬度 28.2753 23.1045 22.1221 25.9879 29.7284 15.1178 18.8726 23.7783 13.4595 15.7307 5.1442 3.9200 6.5634 3.1644 4.2428 13.7090 23.6440 8.4319 6.7436 27.2662 0.2199 17.6622 16.2635 19.6057 9.4030 经度 30.3313 10.1584 31.4847 38.4722 0.9718 50.2111 48.2077 41.8671 27.7133 4.9568 49.2430 11.5812 26.7213 0.7775 18.5245 52.5211 50.1156 19.9857 52.8423 28.7812 33.6490 36.9545 39.7139 36.9980 41.1084 纬度 6.9348 12.4819 8.9640 20.1731 28.1477 10.2944 16.8889 3.5667 5.0706 8.3669 16.7044 14.5677 28.5667 6.9576 14.3598 15.7957 23.7816 5.7902 27.2880 27.6659 0.3980 23.0265 28.4203 24.3992 27.7149

纬度 0.0322 16.2529 0.2057 13.5401 5.8699 23.6143 18.5569 0.4656 26.7526 22.8511 27.2111 22.7571 11.4219 9.9333 15.1224 16.9371 23.1059 23.3960 14.5229 24.0664 14.1304 6.0828 17.3884 19.9950 20.3030

我方有一个基地,经度和纬度为(70,40),假设我方有一部队乘坐飞机从 基地出发,侦察完所有目标,再返回原来的基地。假设飞机的速度为1000公里/
14

小时,到达每一目标之后不做停留,求侦察完所有目标之后花费的时间。 显然这是一个旅行商问题。我们依次给基地编号为1,目标依次编号为2, 3,?101,最后我方基地再重复编号为102。距离矩阵 D ? (dij )102?102 ,其中 dij 表示

102,这里 D 为实对称矩阵。则问题就是,求一个从 i , j 两点的距离, i, j ? 1,2,...,
点1出发,走遍所有中间点,到达点102的一个最短路径。 上面问题中给定的是地理坐标(经度和纬度) ,我们必须要求两点间的实际 距离。设 A, B 两点的地理坐标为 ( x1 , y1 ), ( x2 , y2 ) ,过 A, B 两点的大圆的劣弧长即 为两点的实际距离。以地心为坐标原点 O ,以赤道平面为 XOY 平面,以0度经线 圈所在的平面为 XOZ 平面建立三维直角坐标系。 则 A, B 两点的直角坐标分别为:

A( R cos x1 cos y1 , R sin x1 cos y1 , R sin y1 ) B( R cos x2 cos y2 , R sin x2 cos y2 , R sin y2 )
其中 R ? 6370 为地球半径。

A, B 两点的实际距离
? ? ? OA.OB ? d ? R arccos ? ?, ? OA. OB ? ? ?

化简得

d ? R arccos[cos ( x1 ? x2 ) cos y1 cos y2 ? sin y1 sin y2 ] 。
求解的遗传算法的参数设定如下: 种群大小: M ? 50 最大代数: G ? 1000 交叉率: pc ? 1 ,交叉概率为1能保证种群的充分进化。 变异率: pm ? 0.1 ,一般而言,变异发生的可能性较小。 (1) 编码策略 采 用 十 进 制 编 码 , 用 随 机 数 列 ?1?2 ...?102 作 为 染 色 体 , 其 中 0 ? ?i ? 1

(i ? 2,3,...101 ),?1 ? 0, ?102 ? 1; 每一个随机序列都和种群中的一个个体相对应,例
15

如一个9城市问题的一个染色体为

[0.23,0.82,0.45,0.74,0.87,0.11,0.56,0.69,0.78]
其中编码位置 i 代表城市 i ,位置 i 的随机数表示城市 i 在巡回中的顺序,我们将 这些随机数按升序排列得到如下巡回:
6 ?1 ? 3 ? 7 ? 8 ? 4 ? 9 ? 2 ? 5

(2) 初始种群 本文中我们先利用经典的近似算法—改良圈算法求得一个较好的初始种群。

, 2 ? ? u ? ? v ? 101, 即对于初始圈 C ? ?1...? u ?1? u? u ?1...? v?1? v? v?1...?102 ,2 ? u ? v ? 101
交换 u 与 v 之间的顺序,此时的新路径为:

?1...? u?1? v? v?1...? u ?1? u? v?1...?102
记 ?f ? (d? u?1? v ? d? u? v?1 ) ? (d? u?1? u ? d? v? v?1 ),?f ? 0 ,则以新的路径修改旧的路径,直 到不能修改为止。 (3) 目标函数 目标函数为侦察所有目标的路径长度,适应度函数就取为目标函数,我们要 求
min f (? 1 , ? 2 ,...,? 102 ) ? ? d? i? i?1
i ?1 101

(4) 交叉操作 我们的交叉操作采用单点交叉。设计如下,对于选定的两个父代个体
' f1 ? ?1?2 . .. ?1 02, f 2 ? ?1'?2 . .. ?1' 02 ,我们随机地选取第 t 个基因处为交叉点,则经过

交叉运算后得到的子代编码为 s1 和 s 2 , s1 的基因由 f1 的前 t 个基因和 f 2 的后
102 ? t 个基因构成, s 2 的基因由 f 2 的前 t 个基因和 f1 的后 102 ? t 个基因构成,例

如:

f1 ? [0,0.14,0.25,0.27,| 0.29,0.54,...,0.19,1] f 2 ? [0,0.23,0.44,0.56, | 0.74,0.21,...,0.24,1]
设交叉点为第四个基因处,则

s1 ? [0,0.14,0.25,0.27, | 0.74,0.21,...,0.24,1]
16

s2 ? [0,0.23,0.44,0.56, | 0.29,0.54,...,0.19,1]
交叉操作的方式有很多种选择,我们应该尽可能选取好的交叉方式,保证子 代能继承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。 (5) 变异操作 变异也是实现群体多样性的一种手段,同时也是全局寻优的保证。具体设计 如下,按照给定的变异率,对选定变异的个体,随机地取三个整数,满足
1 ? u ? v ? w ? 102 ,把 u , v 之间(包括 u 和 v )的基因段插到 w 后面。

(6) 选择 采用确定性的选择策略,也就是说选择目标函数值最小的 M 个个体进化到 下一代,这样可以保证父代的优良特性被保存下来。 3.3 模型求解与结论 经由matlab编程可得 path = Columns 1 through 16 1 92 87 17 83 3 74 45 30 67 72 14 27 48 82 2

Columns 17 through 32 20 84 97 42 31 15 79 51 77 80 50 9 60 40 18 10

Columns 33 through 48 85 26 29 65 34 64 66 11 90 76 69 94 70 19 63 62

Columns 49 through 64 86 58 81 8 25 39 68 78 7 88 61 49 28 57 47 23

Columns 65 through 80 22 33 75 71 5 37 54 32 53
17

13

24

16

91

41

4

73

Columns 81 through 96 12 99 101 89 52 6 46 96 59 55 44 38 98 100 56 21

Columns 97 through 102 93 long = 4.0054e+04 所花时间为40小时左右,其中一个侦察路径图如图2所示 图2
40 35 30 25 20 15 10 5 0

43

36

35

95

102

侦察路径图

0

10

20

30

40

50

60

70

算法说明:输入为各个目标的地理坐标,以文件的形式导入。
load sj.txt %加载敌方100个目标数据

输出为最优路径所经过的各节点及其路径图 五、 模型扩展 遗传算法作为现代优化算法之一, 其主要特点是对非线性极值问题能以概率 1跳出局部最优解,找到全局最优解。而遗传算法这种跳出局部最优寻找全局最 优特性都基于算法中的交叉和变异。在传统遗传算法的结构中,变异操作在交叉
18

操作基础上进行,强调的是交叉作用,认为变异只是一个生物学背景机制。在具 体交叉操作中,通常采用断点交叉法(段交叉)多点交叉与均匀交叉,其中断点 交叉是指随机地在基因序列中选择一个断点, 然后交换双亲上断点右端的所有染 色体。在变异操作中,变异算子一般是用Guassian分布的随机变异来实现。本文 根据以上特点对基于求解最优路径规划的遗传算法进行改进, 首先将变异操作从 交叉操作中分离出来, 使其成为独立的并列于交叉的寻优操作,在具体遗传操作 中,混沌与遗传操作联系在一起,在交叉操作中,以“门当户对”原则进行个体 配对,利用混沌序列确定交叉点,实行强度最弱的单点交叉,以确保算法收敛精 度,削弱和避免寻优抖振问题:在变异操作中,利用混沌序列对染色体中多个基 因进行变异,以避免算法早熟(过早收敛于局部的最优解,其原因为群体的规模 是有限的, 可以预见当群体经过若干代的进化后,以指数级增长的具有较高平均 适应度的模式将在种群中占绝大多数,而其他的模式将迅速消失。) 1、 模型及算法 对交叉算子和变异算子做了如下两点改进。 (1) 交叉操作 交叉操作设计如下:首先以“门当户对”原则,对父代个体进行配对,即对 父代以适应度函数(目标函数)值进行排序,目标函数小的与小的配对,目标函 数大的与大的配对。 然后利用混沌序列确定交叉点的位置,最后对确定的交叉项
1 1 1 进 行 交 叉 。 例 如 (?1 , ?2 ) 配 对 , 他 们 的 染 色 体 分 别 是 ?1 ? ?1 , ?2 ??102 2 2 , 采用 Logistic 混沌序列 x(n ? 1) ? 4 x(n)(1 ? x(n)) 产生一个 2 到 ?2 ? ?12?2 ??102

101 之间的正整数,具体步骤如下: 取一个(0,1 )随机初始值,然后利用 x(n ? 1) ? 4 x(n)(1 ? x(n)) 迭代一次产生 1 个 (0, 1) 上的混沌值, 保存以上混沌值作为产生下一代交叉项的混沌迭代初值, 再把这个值分别乘以 100 并加上 2,最后取整即可。假如这个数为 33,那么我们
' 对 (?1 , ?2 ) 染色体中相应的基因进行交叉,得到新的染色体 (?1 , ?'2 )
' 1 1 1 1 1 2 1 1 1 ?1 ? ?1 ?2?3?4?5 ??33 ?34 ??60 ?61 ? 2 2 2 2 1 2 2 2 ?'2 ? ?12?2 ?3 ?4 ?5 ??33 ?34 ??60 ?61 ?

19

(2) 变异操作 变异也是实现群体多样性的一种手段,是跳出局部最优,全局最优的重要保 证。在本文具体变异算子设计如下,首先根据给定的变异率,随机地取两个在 2 到 101 之间的整数, 对这两个数对应位置的基因进行变异,具体变异以当前的基 因值,从而得到新的染色体。 2、 改进的交叉算子和变异算子 (1) 算法代码如下
A=J; for k=1:dai %产生0~1之间随机数列进行编码 B=A; %交配产生子代B for i=1:2:w ch0=rand;ch(1)=4*ch0*(1-ch0); for j=2:50 ch(j)=4*ch(j-1)*(1-ch(j-1)); end ch=2+floor(100*ch); temp=B(i,ch); B(i,ch)=B(i+1,ch); B(i+1,ch)=temp; end %变异产生子代C by=find(rand(1,w)<0.1); if length(by)==0 by=floor(w*rand(1))+1; end C=A(by,:); L3=length(by); for j=1:L3 bw=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]); end G=[A;B;C]; TL=size(G,1);

其运行结果

20

图 2 基于改进的遗传算法优化路径图

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.2

0.4

0.6

0.8

1

1.2

1.4

path = Columns 1 through 18 1 84 18 17 40 3 60 45 79 67 31 82 97 48 72 14 27 10

Columns 19 through 36 77 62 26 85 29 65 34 64 66 11 90 76 86 69 94 70 19 63

Columns 37 through 54 8 71 37 39 32 78 13 47 24 23 49 58 28 81 25 68 7 22

Columns 55 through 72 57 54 53 88 12 61 89 16 6 91 96 41 55 4 73 33 75 5

Columns 73 through 90 44 38 9 80 50
21

15

42

20

30

74

83

87

92

2

36

43

93

46

Columns 91 through 102 59 102 long = 4.0886e+04 六、 算法性能比较 最优路径规划问题是组合最优化问题,但它不是多项式可解问题,即其目标 函数并不能用一个多项式函数表示。 所以此类问题还没有一个有能求得最优解的 多项式时间算法, 它是 NP-hard 问题。但是我们可以通过一些算法找到它的近似 最优解。 本文中的 Dijkstra 算法和 Floyd-Warshall 算法以及智能优化遗传算法 都为解决这一类问题提供了很好的途径。 1)Dijkstra 算法 局限性:该算法只适合求两个指定顶点的最短路径,且要求权值为正。 时间复杂度:O( n 2 ) 2)Floyd-Warshall 算法 局限性: 时间效率低, 对于多个节点之间的算法实现所需要的空间复杂度高。 时间复杂度:O( n3 ) 3)遗传算法 遗传算法适合数值求解那些带有多参数、多变量、多目标和在多区域但连通 性较差的 NP -hard 优化问题. 对多参数、多变量的 NP-hard 优化问题, 通过解 析求解或是计算求最优解的可能性很小, 主要依赖于数值求解. 遗传算法是一 种数值求解的方法, 是一个有普适性的方法, 对目标函数的性质几乎没有要求, 甚至都不一定要显式地写出目标函数, 因此用遗传算法求解优化问题不足 为奇. 遗传算法的实现效率依赖于算子的操作和编码操作。时间复杂度则依赖于代 数和种群大小。 所以求解时对于算法的收敛性和收敛速度都要以依具体问题计算。 51 98 100 56 21 99 101 52 95 35

22

tic clc,clear load sj.txt %加载敌方100个目标数据 x=sj(:,1:2:8);x=x(:);%每隔一列取一个数 y=sj(:,2:2:8);y=y(:); sj=[x y]; d1=[70,40]; sj0=[d1;sj;d1]; %距离矩阵d sj=sj0*pi/180; d=zeros(102);%产生102行1列的全零数据 for i=1:101 for j=i+1:102 temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin( sj(j,2)); d(i,j)=6370*acos(temp);%任取两点的实际距离 end end d=d+d';L=102;w=50;dai=100;%选取种群数为50,迭代100代 %通过改良圈算法选取优良父代A for k=1:w c=randperm(100);%产生随机排列的数组(100个0~1之间的数) c1=[1,c+1,102]; flag=1; while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1)) flag=1; c1(m+1:n)=c1(n:-1:m+1);%交换基因 end end end end J(k,c1)=1:102; end J=J/102;%遗传概率 J(:,1)=0;J(:,102)=1;%染色体1列为0,102列为1 rand('state',sum(clock)); %遗传算法实现过程 A=J; for k=1:dai %产生0~1间随机数列进行编码
23

B=A; c=randperm(w); %交配产生子代B for i=1:2:w F=2+floor(100*rand(1));%向负无穷舍入取整 temp=B(c(i),F:102); B(c(i),F:102)=B(c(i+1),F:102); B(c(i+1),F:102)=temp; end %变异产生子代C by=find(rand(1,w)<0.1);%找到随机数小于0.1的个体 if length(by)==0 by=floor(w*rand(1))+1; end C=A(by,:);%取by行 L3=length(by); for j=1:L3 bw=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]); end G=[A;B;C]; TL=size(G,1); %在父代和子代中选择优良品种作为新的父代 [dd,IX]=sort(G,2);temp(1:TL)=0; for j=1:TL for i=1:101 temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));%适应度距离函数 end end [DZ,IZ]=sort(temp); A=G(IZ(1:w),:); end path=IX(IZ(1),:) long=DZ(1) toc xx=sj0(path,1);yy=sj0(path,2); plot(xx,yy,'-o')

24


相关文章:
一种路径规划算法的改进与设计
这里主要介绍了用一种新的算法选择最优路径。这是...法,运用路径规划的思想,设计一套方便人们出行时所需...该阶段结束应交付测试报告,说明测试数据的选择,测试...
数学建模最优路径设计
2.根据第一问的定义, 设计算法搜索最优路径,并将该算法应用到具体交通 网络中...f (d ) 6、模型的分析、推广与改进路线选择问题是一个多目标规划问题, 其中...
最短路径问题设计报告
最短路径问题设计报告_计算机软件及应用_IT/计算机_专业资料。两个星期关于数据...性能等等,掌握了编程的方法和技术,通 过查询资料,也了解了遗传算法,退火算法...
路径规划算法
路径规划算法_IT/计算机_专业资料。路径规划[选取日期] NUAA 未知环境的动态路径...(n) <= C*. 这个性质可以这样理解,因为最短路径存在,我们不妨设它为 : ...
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、...[1]总结出“延续现有模式,改变传统 思维;优化送货...设计求解问 题的算法,然后用计算机求得合理可行的...
基于遗传算法的TSP路径规划算法设计
2. TSP问题的数学模型 TSP 问题即寻找一条最短的遍历n个城市的最短路径, ...总结本文针对TSP问题,首先给出了基于遗传算法求解TSP问题的一般性流程,设计了基于...
课程设计报告《导航路径规划》
自定义,要求城市个数>=20),根据导航策略(时间 最短,里程最短)给出路径规划...[j]; } "<<"路费 1.3.2 算法分析及程序流程图 1 浏览城市名字和编号 2...
最短路径算法的研究与应用 开题报告_图文
集美大学毕业设计(论文)开题报告理 学院 数学与应用数学 专业 最短路径算法的...算法 (3)补充其他最短路径算法,例如遗传算法、动态规划算法等 (4)最短路径的...
c语言公交最优路径查询数据结构(附设计报告,完整代码)
《 数据结构 》 课程设计报告 题年专 目级业 公交路线上优化路径的查询 2008...利用 Floyd 算法找出按时间的所有两站之间的最优路径 ④,编写时间最优的路线...
最短路径实验报告
最短路径实验报告_调查/报告_表格/模板_实用文档。...(i,j)∈E 都有 Wij≥0); 2)算法描述: a)...最短路径规划实验报告 7页 1下载券 喜欢此文档的还...
更多相关标签: