第1期 彭志红等：基于改进差分进化算法的无人机在线低空突防航迹规划 ·99· 根据图1，将位置在(i,j)的个体表示为Mg,则 和x之间的位置.由此可以得到改进后的变异操 M的邻域为Ng,Ng={MM,M2,Mn},其中 作算子为 i-1,i≠1： j-1,j≠1： 片=ax+(1-a）xims+ i={M,i=1.i={M,j-l. [F+(F-Fa)7]x-x)+ i+l,i≠Me; i+1,j≠Mc: i=M; h={, [F-(F-F) (17) (14) 或 在冯·诺伊曼拓扑结构中，每个个体在进行差分 y片=ax+(1-a）·xam+ 进化操作时，只能随机选择邻居作为基向量和差分 向量，多个子种群同时进化，这样可以有效保持种群 [F+(F-F)·7]小xam-)+ 的多样性，避免算法陷入局部最优.在本文中，种群 进化初期，采用传统的冯·诺伊曼拓扑结构，在进化 [rm-(F-F)·7]。-).(I8) 后期，为了加快算法的收敛性，快速得到最优解，在 2.3编码和初始化 种群进化过程中引入全局最优解，参与子种群的 本文航迹表示采用三维航迹点列表{S,P,P2, 进化 ·,E},列表中S为在线规划航迹片段起始点，E为 2.2.2改进变异操作算子 规划航迹片段终止点，P1,P2,…,P、1为航迹途经 为了提高标准差分进化算法的效率，一些学者 点.每个航迹点由三个坐标点表示，不同的编码方 提出了新的变异操作算子模型，如DE/best/1/bin、 式其意义不同.在航迹片段初始化时采用相对极坐 DE/current-to-best/1/bin,DE/rand-to-best/1/bin, 标，利用其对路径点位置和方位的限制，显著减少搜 不同模式侧重点不同，有的有利于保持群体多样性， 索空间：在变异和交叉操作阶段，使用绝对笛卡儿坐 有的更强调算法的收敛速度.文献0]中提出了一 标，只引起局部改变，克服相对极坐标会引起全局改 种改进变异操作算子，结合了不同策略的优点，如下 变的缺陷.如图2所示，在相对极坐标系下，航迹点 式所示： 用(r,0,z)表示.其中，r为水平投影面中相邻两航 v=ax+(1-a）best+F,·(xim-x）+ 迹点间的距离，0为水平投影面中当前规划航迹点 F2(xn-x). (15) 相对于前一航迹点的变化角，：为当前规划航迹点 通过调整上式的参数可以得到不同的策略模 的高度值.在绝对坐标系下，航迹点用(x,y,z)表 型.若a=1,F,=0,则等价于DE/rand1/bin;若 示，xy和z分别表示航迹点在x轴y轴和z轴的坐 a=0,F,=0,则等价于DE/best/1/bin;若a=0, 标值（图2中z未标出）. F,≠0，则等价于DE/rand-to-best/1bin.在这里，将 此模型做一些改变，根据采用的冯·诺伊曼拓扑结 构，进化初期使用邻域最优解xm代替xa,这里 的，m为冯·诺伊曼拓扑网格中个体M,及其邻域 所构成小种群的局部最优解，进化后期使用整个种 群的全局最优解xa代替x·缩放因子F控制着 差分向量的幅度，较大的F,值可以使解收敛速度较 P: 快，但容易陷入局部最优：较大的F,可以使解在更 图2绝对笛卡儿坐标和相对极坐标下的无人机航迹点 大范围内搜索但收敛速度较慢.为了实现两者之间 Fig.2 UAV path points in absolute Cartesian and relative polar coor- 的折衷，本文设定 dinates [F=Fin+(F-Fai)T 在本文中，因为地形预先未知，故每次规划必须 (16) 在无人机的扫描半径内.为了提高规划效率，设定 F2=F-(Fs-Fa）7 扫描点为规划起点，初始化时规划终点落在扫描半 式中，(Fn,F)为F,和F2的取值范围，T为进化 径R上，中间的航迹点可以根据规划精度在空间内 总代数.式(15)中的参数a决定了基向量介于x, 均匀分布.第 1 期 彭志红等: 基于改进差分进化算法的无人机在线低空突防航迹规划 根据图 1，将位置在( i，j) 的个体表示为 Mij ，则 Mij的邻域为 Nij ，Nij = { Mi1，j ，Mi，j 1 ，Mi2，j ，Mi，j 2 } ，其中 i1 = i － 1， i≠1; {Msize， i = 1． j1 = j － 1， j≠1; {Msize， j = 1． i2 = i + 1， i≠Msize ; {1， i = Msize ; j2 = j + 1， j≠Msize ; {1， j = Msize ． ( 14) 在冯·诺伊曼拓扑结构中，每个个体在进行差分 进化操作时，只能随机选择邻居作为基向量和差分 向量，多个子种群同时进化，这样可以有效保持种群 的多样性，避免算法陷入局部最优． 在本文中，种群 进化初期，采用传统的冯·诺伊曼拓扑结构，在进化 后期，为了加快算法的收敛性，快速得到最优解，在 种群进化过程中引入全局最优解，参与子种群的 进化． 2. 2. 2 改进变异操作算子 为了提高标准差分进化算法的效率，一些学者 提出了新的变异操作算子模型，如 DE /best /1 /bin、 DE /current-to-best /1 /bin、DE /rand-to-best /1 /bin ［9］， 不同模式侧重点不同，有的有利于保持群体多样性， 有的更强调算法的收敛速度． 文献［10］中提出了一 种改进变异操作算子，结合了不同策略的优点，如下 式所示: vt i = a·xt r1 + ( 1 － a)·xt best + F1 ·( xt best － xt r1 ) + F2 ·( xt r2 － xt r3 ) ． ( 15) 通过调整上式的参数可以得到不同的策略模 型． 若 a = 1，F1 = 0，则等价于 DE /rand /1 /bin; 若 a = 0，F1 = 0，则 等 价 于 DE /best /1 /bin; 若 a = 0， F1≠0，则等价于 DE /rand-to-best /1 /bin． 在这里，将 此模型做一些改变，根据采用的冯·诺伊曼拓扑结 构，进化初期使用邻域最优解 xt i，jmax代替 xt best，这里 的 xt i，jmax为冯·诺伊曼拓扑网格中个体 Mij及其邻域 所构成小种群的局部最优解，进化后期使用整个种 群的全局最优解 xt gbest代替 xt best ． 缩放因子 F 控制着 差分向量的幅度，较大的 F1值可以使解收敛速度较 快，但容易陷入局部最优; 较大的 F2可以使解在更 大范围内搜索但收敛速度较慢． 为了实现两者之间 的折衷，本文设定 F1 = Fmin + ( Fmax － Fmin )·t T ， F2 = Fmax － ( Fmax － Fmin )·t T { ． ( 16) 式中，( Fmin，Fmax ) 为 F1和 F2的取值范围，T 为进化 总代数． 式( 15) 中的参数 a 决定了基向量介于 xt r1 和 xt best之间的位置． 由此可以得到改进后的变异操 作算子为 vt i = a·xt r1 + ( 1 － a)·xt i，jmax [ + Fmin + ( Fmax － Fmin )·t ] T ·( xt i，jmax － xt r1 ) [ + Fmax － ( Fmax － Fmin )·t ] T ·( xt r2 － xt r3 ) ( 17) 或 vt i = a·xt r1 + ( 1 － a)·xt gbest [ + Fmin + ( Fmax － Fmin )·t ] T ·( xt gbest － xt r1 ) [ + Fmax － ( Fmax － Fmin )·t ] T ·( xt r2 － xt r3 ) . ( 18) 2. 3 编码和初始化 本文航迹表示采用三维航迹点列表{ S，P1，P2， …，E} ，列表中 S 为在线规划航迹片段起始点，E 为 规划航迹片段终止点，P1，P2，…，PN － 1 为航迹途经 点． 每个航迹点由三个坐标点表示，不同的编码方 式其意义不同． 在航迹片段初始化时采用相对极坐 标，利用其对路径点位置和方位的限制，显著减少搜 索空间; 在变异和交叉操作阶段，使用绝对笛卡儿坐 标，只引起局部改变，克服相对极坐标会引起全局改 变的缺陷． 如图 2 所示，在相对极坐标系下，航迹点 用( r，θ，z) 表示． 其中，r 为水平投影面中相邻两航 迹点间的距离，θ 为水平投影面中当前规划航迹点 相对于前一航迹点的变化角，z 为当前规划航迹点 的高度值． 在绝对坐标系下，航迹点用( x，y，z) 表 示，x、y 和 z 分别表示航迹点在 x 轴、y 轴和 z 轴的坐 标值( 图 2 中 z 未标出) ． 图 2 绝对笛卡儿坐标和相对极坐标下的无人机航迹点 Fig． 2 UAV path points in absolute Cartesian and relative polar coor￾dinates 在本文中，因为地形预先未知，故每次规划必须 在无人机的扫描半径内． 为了提高规划效率，设定 扫描点为规划起点，初始化时规划终点落在扫描半 径 R 上，中间的航迹点可以根据规划精度在空间内 均匀分布． ·99·