CN102436604B - 一种基于多目标进化方法的多弹协同航路计算方法 - Google Patents

Abstract

本发明提出一种基于多目标进化方法的多弹协同航路计算方法，属于任务规划技术领域，具体包括：对导弹航路进行编码并定义导弹的机动特性、对规划区域进行建模、生成航路初始种群、对航路初始种群进行进化操作产生新一代航路种群、对新一代航路种群进行评价，航路集合Q、对种群间的航路集合Q进行进化操作得到新一代航路集合Q′、得到新一代航路集合Q′进行评价、判断是否满足协同条件等几个步骤。本发明摒弃了传统针对单一的一枚导弹进行航路规划模式，而是对多弹进行协同规划。在规划中充分考虑多弹之间的空间冲突关系和攻击到达时间关系，有利于实现同时对多个敌方目标进行设定时间攻击、对某个敌方目标进行饱和攻击等，提高攻击效率。

Description

一种基于多目标进化方法的多弹协同航路计算方法

技术领域

本发明属于任务规划技术领域，具体涉及一种基于多目标进化方法的多弹协同航路计算方法。 

背景技术

航路规划是任务规划系统的核心之一，其核心内容是在初始点和目标点之间选择满足一系列约束条件的点，并且在约束条件下对其优化，得到一条优化航路，从某种意义上讲，就是使明确的目标与各种限制函数相匹配的优化问题。导弹航路规划的目的是利用地理信息和战场环境信息，在满足各种约束条件的前提下，规划导弹的飞行航路，使得导弹的特定评价指标达到最优，从而提高导弹的作战效能。 

在针对导弹的航路规划过程中，需要了解和掌握诸如规划区域的地理信息、敌我双方的位置坐标和运动情况、敌方的防空火力分布、武器的性能等多方面的信息。将这些信息结合导弹自身的约束进行航路规划，是一个复杂的多目标非线性寻优问题，其计算量大，计算过程非常复杂。另外，现代战争的防空技术日益发展，要出色完成作战任务，进行可靠性打击，还需要对同一具有防空设施的目标实施多波次攻击、饱和攻击等等。在多波次攻击中，航路规划必须协调各波次之间的攻击时差；在饱和攻击中，航路规划必须协调各枚导弹设定的攻击时间。如何为每一枚导弹生成有效的航路，并调整各枚导弹的航路航程以协调其打击目标的时间，是完成攻击任务的前提条件之一。 

目前，常用的航路规划方法有Voronoi图法、栅格法、数学规划方法、人工势场法和遗传算法等等。 

Voronoi图法其基本原理是将环境空间划分为若干个区域，每个区域内只包含一个障碍物的边界，并且环境空间任意一点到本区域内障碍物边界的距离比到其它区域内障碍物边界都短，在由区域边界组成的从起始点到目标点之间的集合当中搜索出一条最短路径，这条路径的优点在于即使产生位置误差，移动机器人也不会碰撞障碍物，相对比较安全。其缺点是规划出来的航路过于接近障碍物，而且误差较大。 

栅格法的主要思想是将飞行器的环境空间分解成一系列具有二进制信息的栅格单元，多数使用四叉树或八叉树方法。其中主要的划分方法是：每个栅格单元都记录了环境空间信息，有障碍物的地方累积值比较高，因此环境空间信息可被量化为具有一定分辨率的栅格。通过优化搜索策略，飞行器就会在这些栅格当中避开障碍并完成航路规划。栅格法在环境空间的 表达上具有一致性、规范性和简单性，但是没有考虑到环境本身的分布特点，依赖于对精度的要求，搜索具有盲目性，当环境复杂时，搜索空间会相当的大，算法效率很低。 

数学规划方法通常将避障问题表示成一系列不等式约束，这样，路径规划问题就可以表示成带有约束条件的最优化问题。这类方法的一大优点就是除了距离和障碍之外，还可以综合考虑多种与路径相关的其他要素，如路径的安全性、可执行性等。由于该最优化问题通常是非线性的，并且带有多个不等式约束，一般需用数字方法进行求解。数学规划方法用于求解路径规划一般计算量都很大，而且受局部最小值的影响，通常只用于局部路径规划。 

人工势场法的基本思想是将移动机器人在环境空间中的运动视为一种虚拟人工受力场中的运动。目标点对机器人产生引力，而障碍物对其产生斥力。由引力和斥力产生势场，机器人在势场中受到抽象力的作用下，能够规避障碍物。该方法结构简单，易于实现，在处理未知环境信息下的动态路径规划方面得到了广泛应用，但是这种方法容易陷入局部最优，产生死锁现象，即在相近障碍物之间不能发现路径，在障碍物前面容易发生震荡。 

遗传算法是以遗传机制和自然选择等生物进化理论为基础，通过数学和计算机模拟生物进化的过程。其基本思想是：将路径规划中的各个路径点构建为以编码形式存在的个体，这些个体组成了一个种群。通过建立适应度函数，在种群当中进行选择、交叉和变异等遗传操作，经过若干代的进化，直到最后产生满足期望的子代，然后输出最优良的个体。遗传算法的优势在于它采用并行方式处理多点搜索问题，克服了其他单点搜索算法容易陷入局部最优的缺陷，适用于全局路径规划，容易搜索到全局最优解。其缺点是遗传因子和控制参数难以决策，算法可能容易出现过早收敛和停滞现象。 

因此，以上这些算法应用于导弹航路规划仍有很多有待解决的问题。且其大都是针对单一一枚导弹的规划，没有从多弹协同的角度考虑。因此，以上这些算法均不能有效地从实际意义上解决针对多弹协同航路规划的问题。 

发明内容

针对现有技术中存在的问题，本发明提出一种基于多目标进化方法的多弹协同航路计算方法，针对多目标进化算法采用群体搜索策略，仅使用基于目标函数值评价信息，具有隐并行性、并行计算的特点；结合规划区域的地理信息、敌我双方的位置坐标和运动情况、地方的防空火力分布、武器的性能等多方面的信息，设计了一种基于多目标进化算法的多弹协同航路规划方法。本发明中提供的方法区别于现有方法的显著特征在于：其一，将多目标进化算法应用于解决多弹协同航路规划问题，很好地利用了多目标进化算法的全局搜索与并行计算能力；其二，在环境建模时，提出了一种采用垂直于发射点与目标点连线的平行线将规划环境等份分割的环境建模方法，简称平行等分法。将部分目标函数的约束引入其中，从而简化了多目标进化算法在进化计算中的约束，有利于缩短进化计算时间，提高进化效率；其三， 本发明针对多弹进行协同规划，异于传统的针对单一一枚弹进行航路规划。在规划中充分考虑多弹之间的空间冲突关系和攻击到达时间关系，有利于实现同时对多个敌方目标进行设定时间攻击、对某个敌方目标进行饱和攻击等，提高攻击效率。 

本发明公开了一种基于多目标进化算法的多弹协同航路计算方法，主要包括以下几个步骤： 

步骤一：对导弹航路进行编码并定义导弹的机动特性； 

步骤二：根据敌我双方舰船所在地理位置，确定一个能包含敌我双方舰船的正四边形规划区域，结合规划区域的环境和敌我双方舰船的运动和火力分布情况，对环境进行建模，采用垂直于导弹发射点与目标点连线的多条平行线将导弹发射点与目标点之间的连线从发射点开始等距离分割，相邻两平行线之间的距离为Length_Min，规划区域环境的障碍物分为岛屿与敌我双方舰船；岛屿简化成用一系列经纬度点表示的多边形禁飞区；以舰船所在位置为圆心，以威胁半径为半径的圆形禁飞区表示其位置，舰船的航行速度用圆形禁飞区的圆心的移动速度来表征，再将圆形禁飞区扩展成与圆相切的正四边形禁飞区； 

步骤三：生成航路初始种群P₁，P₂，...P_n。 

对规划环境采用垂直于发射点和目标点的多条平行线等距分割法建模，穿过发射点的平行线为第一条平行线，而第一条平行线与第二条平行线之间的航路为第1段航路，若i表示第i段航路，相邻两平行线之间的距离为Length_Min，第i段航路方位角与第i-1条平行线方位角的差角为α_i，在发射点至目标点之间的各条平行线上各取一个点作为航路点，将发射点、各条平行线上的各个航路点以及目标点相连接，确定一条航路；若某个航路上的第i个航路点坐标为(x_i，y_i)，第i个航路点至第i+1个航路点的方位角和距离分别为angle_i和length_i，则有： 

angle_i＝S_G_Angle-90°+α_i

length_i＝Length_Min/sinα_i

根据文森特公式，由目标点依次求出一条航线上各个航路点的经纬度坐标，改变第i个航路点至第i+1个航路点的方位角值angle_i，改变α_i，确定下一个航路点的经纬度坐标，对应生成一条不同的航路，选取m个不同的α_i值生成m条不同的航路，组成一个初始种群，共生成n个航路初始种群P₁，P₂，...P_n； 

步骤四：对航路初始种群P₁，P₂，...P_n分别进行进化操作，产生新一代航路种群，进化操作方法有交叉、变异和平滑； 

步骤五：计算新一代航路种群中每个种群中每个航路的适应度值，去掉适应度差的航路，保留每个种群中适应度最优的航路，得到适应度最优的航路种群P′₁，P′₂，...P′_n，采用针对航路个体适应度的评价函数对每个种群中的航路进行评价； 

航路个体的适应度评价函数f(m)为： 

f(m)＝δ_dD(m)+δ_sS(m)+δ_cC(m)；                            (5) 

其中，D(m)表示一条航路的总航程，S(m)表示航路的平滑度，C(m)表示航路的安全程度；δ_d、δ_s、δ_c分别表示航程、平滑度、安全程度在适应度函数中的权重；f(m)越小，航路个体越优；其中各个参数定义与计算公式分别为： 

$\left\{\begin{array}{c}D\left(m\right)=\underset{i=1}{\overset{t-1}{\mathrm{\Σ}}}{\mathrm{length}}_i\\ {\mathrm{length}}_i\≥\mathrm{Length}\_\mathrm{Min},(i=\mathrm{1,2},...t-1)\\ D\left(m\right)\≤\mathrm{Route}\_\mathrm{Length}\_\mathrm{Max}\\ t\≤\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\end{array}\right.$

$\left\{\begin{array}{c}S\left(m\right)=\underset{i=1}{\overset{t-2}{\mathrm{\Σ}}}({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)/(t-2)\\ ({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)\≤\mathrm{Angle}\_\mathrm{Max},(i=\mathrm{1,2},...t-2)\\ t\≤\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\\ \end{array}\right.$

$\left\{\begin{array}{c}C\left(m\right)=1/\underset{i=1}{\overset{t-1}{\mathrm{\Σ}}}{l}_i\\ l_i>0,(i=\mathrm{1,2},...,t-1)\\ t\≤\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\\ \end{array}\right.$

length_i、angle_i分别表示第i个导航点至第(i+1)个导航点的距离和方位角，t表示航路导航点总个数，包括发射点和目标点，，l_i表示length_i段航路距离规划区域的禁飞区的最小距离，l_i＞0时，航路不与禁飞区相交，当l_i＝0时，说明航路段与禁飞区相交，航路所有导航点的拐弯角不能超过允许的最大拐弯角Angle_Max，不包括发射点和目标点；航路的所有航路段长度不能小于允许的最小航路段距离Length_Min；航路的总航程不能超出允许的最大航程Route_Length_Max，航路的总导航点个数包括发射点和目标点不能超出允许的最大拐弯点个数Route_Node_Num_Max； 

计算每一代航路种群中每个种群所包含的航路个体适应度值的均方差D，若每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群中选取适应度值f(m)最小的航路作为最优航路，组成不同种群的航路集合Q，若每一代航路种群中任一种群的航路个体适应度值的均方差D不小于预先设定的航路个体的适应度值的均方差数值，则返回步骤四，进行优化操作，直至每一代航路种群中每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群选取一条适应度最优的航路组成了航路集合Q，此时航路集合为种群间的航路集合； 

步骤六：对种群间的航路集合Q进行进化操作，得到新一代航路集合Q′，设计的进化操作方法包括：种群间航路距离扰动变异、航路航程扰动变异和平滑变异； 

步骤七：对航路集合Q进化后得到新一代航路集合Q′，评价其是否满足种群间适应度评价函数的约束，同时对新一代航路集合Q′中的每个航路个体采用个体适应度评价函数是否满足条件； 

其中种群间的适应度评价函数D(n)为： 

$\left\{\begin{array}{c}D\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{dis}\tan \mathrm{ce}(p_i,p_{i+1})\right\},(i=\mathrm{1,2},...t-1)\\ D\left(n\right)\≥D_{\min }\end{array}\right.---\left(9\right)$

$\left\{\begin{array}{c}T\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{time}(S_i,S_{i+1})\right\},(i=\mathrm{1,2},...t-1)\\ T\left(n\right)\≥\mathrm{\Δt}\end{array}\right.---\left(10\right)$

其中dis tan ce(p_i，p_i+1)表示航路集合Q′空间相邻的两航路的最小距离，time(S_i，S_i+1)表示发射时间相邻的两条航路的发射时间差，D_min表示空间相邻的两条航路的最小间隔距离，Δt表示发射要求的最小间隔时间，T(n)表示所有发射时间相邻的航路的最小发射时间差； 

本步骤中航路个体所采用个体适应度评价函数与步骤五中的适应度评价函数相同；

步骤八：步骤八：根据步骤七中种群间的适应度评价函数得到进化后的新一代航路集合Q′种群间的适应度值的均方差E，同时用个体的适应度评价函数得到进化后的新一代航路集合Q′中每条航路的适应度值的均方差D’，若E小于预先设定的种群间的适应度值的均方差数值，D’也小于预先设定的航路个体的适应度值的均方差数值，则满足各航路之间的协同条件，输出结果；否则任意一个不满足，则返回步骤六，继续对航路集合Q进行进化操作，直至满足上述的协同条件。 

本发明的优点在于： 

第一，本发明提出的一种基于多目标进化算法的多弹航路协同计算方法，将航路规划这个多目标非线性问题与多目标进化算法结合。利用多目标进化计算的目标函数评价机制与并行计算的特点，很好的处理了多弹航路规划中涉及的规划区域的地理信息、敌我双方的位置坐标和运动情况、敌方的防空火力分布、武器的性能等多方面的约束，搜索出全局最优的航路。很好地应用了多目标算法的特点，恰当地解决了多弹航路规划问题。 

第二，本发明提出的一种基于多目标进化算法的多弹航路协同计算方法，在环境建模时，提出了一种采用垂直于发射点与目标点连线的平行线将规划环境等份分割的环境建模方法。将导弹自身的部分约束条件与环境约束条件引入到模型之中，垂线之间的距离即为导弹航路两点之间要求的最短距离；通过平行等分法建模，引出了本发明建立初始种群的方法：依靠改变当前航路点至下个航路点的方位角与当前点所在平行线方位角的差角，来确定初始种群。从而简化进化算法的目标函数，加速算法规划进程，有效地避免了进化计算时计算量过大，耗时过长，从而提高了进化效率。 

第三，本发明提出的一种基于多目标进化算法的多弹航路协同计算方法，摒弃了传统针对单一的一枚导弹进行航路规划模式，而是对多弹进行协同规划。在规划中充分考虑多弹之间的空间冲突关系和攻击到达时间关系，有利于实现同时对多个敌方目标进行设定时间攻击、对某个敌方目标进行饱和攻击等，提高攻击效率。 

附图说明

图1：本发明提出的基于多目标进化算法进行多弹航路计算方法的流程图； 

图2：本发明中对规划区域环境的建模图。 

具体实施方式

下面将结合附图对本发明进行详细说明。 

以电子海图为平台，以反舰导弹航路规划为应用背景。由于反舰导弹巡航段距离海平面较低，可仅考虑二维平面下的航路规划。 

本发明提出的一种基于多目标进化算法的多弹航路规划方法，如图1，具体包括以下几个步骤： 

步骤一：对导弹航路进行编码并定义导弹的机动特性。导弹的航路由一组有序的导航点组成，每个导航点包含该点的经纬度值信息。由此，导航点编码route_node为： 

route_node＝{x，y，angle}                        (1) 

其中，x，y分别表示该导航点的经纬度坐标(二维空间规划)，采用实数编码；angle表示该导航点与下一导航点的方位角。 

航路编码missile_route为： 

missile_route＝{list<route_node>route_list，fitness_value，route_length，feasible_flag，sum_turn_angle，...} 

                                                                                                       (2) 

其中，list<route_node>route_list为该航路的导航点链表集信息，fitness_valu为航路适应度值，route_length为航路的总长度，feasible_flag为航路是否可行的标志量，sum_turn_angle为航路的总拐弯角。 

所述的导弹的机动特性的包括： 

①方位角：以正北方向为0度方位角，顺时针方向方位角为正，取值范围为[0，360]； 

②航路允许的最大拐弯角：Angle_Max； 

③航路允许的最小航路段距离：Length_Min； 

④航路允许的最大航程：Route_Length_Max； 

⑤航路允许的最大拐弯点个数：Route_NodeNum_Max； 

⑥相邻两条航路的最小间隔距离：D_min； 

⑦发射要求的最小间隔时间：Δt。 

步骤二：根据敌我双方舰船所在地理位置，确定一个能包含敌我双方舰船的正四边形规划区域，如图，2所示。结合规划区域的环境和敌我双方舰船的运动和火力分布情况，对环境进行建模。采用垂直于导弹发射点与目标点连线的多条平行线将导弹发射点与目标点之间的连线从发射点开始等距离分割，其中穿过发射点的平行线为第一条平行线，相邻两平行线之间的距离为Length_Min，如果某一条平行线与目标点之间的距离大于Length_Min且小于2×Length_Min，则该平行线与目标点之间不再插入平行线，该平行线作为最后一条平行线。规划区域环境的障碍物基本可分为两类：岛屿与敌我双方舰船。其中岛屿可以简化成用一系列经纬度点表示的多边形禁飞区；舰船在进行建模时以舰船所在位置为圆心，以威胁半径为半径的圆形禁飞区表示其位置，舰船的航行速度用圆形禁飞区的圆心的移动速度来表征，再将圆形禁飞区扩展成与圆相切的正四边形禁飞区。如附图1所示：S点为发射点，G为目标点；F1与F4表示敌我双方舰船，F2、F3和F5表示岛屿经简化后的多边形禁飞区。L1至L5为垂直于发射点与目标点连线的等份分割规划区域的平行线。 

步骤三：生成航路初始种群P₁，P₂，...P_n。 

如图2，以生成一个初始种群中的一条航路为例，初始种群可以随机地产生，采用随机方法产生的航路种群一般能够覆盖整个规划区域，具有一定的广泛性，但是采用随机方法产生的航路可行性不高，增加搜索时间。本发明中通过对规划环境采用垂直于发射点和目标点的多条平行线等距分割法建模，提出了一种能够加速规划进程的新的初始种群生成方法。如图1所示，S点为发射点，G点为目标点，穿过发射点的平行线为第一条平行线，而第一条平行线与第二条平行线之间的航路为第1段航路，若i表示第i段航路，相邻两平行线之间的距离为Length_Min，第i段航路方位角与第i-1条平行线方位角的差角为α_i，例如，从发射点开始，第1段航路方位角与第0条平行分割线L0的方位角的差角为α₁。由于S点与G点已知，由文森特公式可求出S点至G点的距离和方位角S_G_Angle。在S点至G点之间的各条平行线上(L1、L2、L3和L4)各取一个点作为航路点，将S点和各条平行线上(L1、L2、L3、L4)取的各个航路点以及G点相连接，就可以确定一条航路。若某个航路上的第i个航路点坐标为(x_i，y_i)，第i个航路点至第i+1个航路点的方位角和距离分别为angle_i和length_i，则有： 

angle_i＝S_G_Angle-90°+α_i                        (3) 

length_i＝Length_Min/sinα_i                        (4) 

根据文森特公式，在已知一点的经纬度坐标和这点到所求点的方位和距离的情况下，可以求出目标点的经纬度坐标，则可由S点依次求出一条航线上各个航路点的经纬度坐标。因此只需要改变第i个航路点至第i+1个航路点的方位角值angle_i，即改变α_i，就可确定下一个航路点的经纬度坐标。而α_i为一旋转角度，该角度取值在[0，180]内任意选取，因此，任意选取一个不同的α_i值，对应生成一条不同的航路，选取m个不同的α_i值即可生成m条不同的航路，此m条航路组成一个初始种群P。m一般取值在30到50之间，数值越大，能越好的覆盖整个规划区间，但是进化过程耗时也越长。从而使航路种群能够覆盖整个规划空间。需特别注意的是，本发明要求在选择α_i时不能使导弹航路段与岛屿或敌我双方舰船的禁飞区相交。依此方法，共生成n个航路初始种群P₁，P₂，...P_n，每个种群中均含有m条航路。 

步骤四：对航路初始种群P₁，P₂，...P_n分别进行进化操作，产生新一代航路种群，种群数保持一致，还是n个种群，每个种群中还分别包含m条航路。设计以下进化操作方法，可以分别对同一个种群内的航路分别采取以下任意一种或几种进化操作，生成新一代航路种群。 

(1)交叉：采用双点交叉。在初始种群中任意选取两条航路作为母体，在两个母体上分别随机选取两个航路点作为交叉点(发射点与目标点除外)，将两条航路分别从交叉点断开成两个部分，然后第一个母体的第一部分与第二个母体的第二部分组合，第一个母体的第二部分与第一个母体的第一部分组合，从而生成两条新的航路。 

(2)变异：变异操作是保持物种多样性的一个重要途径，不仅被视为得到因交叉操作而遗失优良基因的手段，还是探索相邻空间、优化性能的有力工具。本发明针对航路初始种群内部进化设计了三种变异方法，可以同时使用或任选其一使用： 

删除变异——从航路个体即任意一条航路中随机删除一个导航点(发射点与目标点除 外)，生成一条新的航路； 

扰动变异——改变航路个体即任意一条航路中某个导航点的坐标，针对导航点是否在障碍物内或者连接该点的前后两段航路是否和障碍物相交，设置不同的扰动范围，具体做法是以选中的某导航点为圆心，以r为半径画圆，扰动区域选远离障碍物的半圆区域。如果该导航点在障碍物内，r取该导航点到此障碍物最远顶点的距离，如果该点不在障碍物内，r取航路允许的最小航路段距离的1/5(该数值需结合实际应用情况进行调整，通常情况下为1/5)，即1/5Length_Min； 

二点变异——选择航路个体即任意一条航路中相邻两个导航点(发射点与目标点除外)，重新生成两个导航点，替换选中的两个导航点。具体操作方法可参照生成初始种群中航路的方法，分别改变选中点对应的第i段航路方位角与第i-1条平行线方位角的差角αi的值，生成两个新的航路点，替换选中的导航点。 

(3)平滑：平滑算子针对导弹的最大拐弯角设计，通过该平滑操作实现航路转弯角小于航路允许的最大拐弯角Angle_Max，通常情况下，航路转弯角的取值为(Angle_Max-30°)。由生成初始种群航路的方法可知，改变第i段航路方位角与第i-1条平行线方位角的差角α_i，既可得到不同的航路点，而α_i取值在[0，180]之间，当α_i取值越趋于0度或者180度时候，该点的拐弯角越大，而越趋于[0，180]中间时(一般为[110，145])，该点拐弯角越小。改变α_i的值来使对应该点拐弯角变小，即可实现航路的平滑，同时也减短了路径的总长度。 

步骤五：计算新一代航路种群中每个种群中每个航路的适应度值，去掉适应度差的航路，保留每个种群中适应度最优的航路，得到适应度最优的航路种群P′₁，P′₂，...P′_n。采用针对航路个体适应度的评价函数对每个种群中的航路进行评价。 

对于航路个体的适应度评价函数考虑两个因素：航路的可行性和航路的优劣性。航路的可行性评价包括两个方面：航路不和障碍物相交、航路满足导弹自身性能的约束；航路的优劣评价性包括三个方面：航路的总航程、航路的平滑度、航路的安全程度。航路个体的适应度评价函数f(m)为： 

f(m)＝δ_dD(m)+δ_sS(m)+δ_cC(m)；                                   (5) 

其中，D(m)表示一条航路的总航程，总航程越小，导弹飞行时间越短，导弹飞行过程中带来误差越小。S(m)表示航路的平滑度，S(m)越小，说明航路越平滑，导弹转弯带来的误差越小。C(m)表示航路的安全程度，离禁飞区越远越安全，即C(m)越小，越安全。δ_d、δ_s、δ_c分别表示航程、平滑度、安全程度在适应度函数中的权重。由上可知，f(m)越小，航路个体越优。其中各个参数定义与计算公式分别为： 

$\left\{\begin{array}{c}D\left(m\right)=\underset{i=1}{\overset{t-1}{\mathrm{\&Sigma;}}}{\mathrm{length}}_i\\ {\mathrm{length}}_i\&GreaterEqual;\mathrm{Length}\_\mathrm{Min},(i=\mathrm{1,2},...t-1)\\ D\left(m\right)\&le;\mathrm{Route}\_\mathrm{Length}\_\mathrm{Max}\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\end{array}\right.---\left(6\right)$

$\left\{\begin{array}{c}S\left(m\right)=\underset{i=1}{\overset{t-2}{\mathrm{\&Sigma;}}}({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)/(t-2)\\ ({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)\&le;\mathrm{Angle}\_\mathrm{Max},(i=\mathrm{1,2},...t-2)\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\\ \end{array}\right.---\left(7\right)$

$\left\{\begin{array}{c}C\left(m\right)=1/\underset{i=1}{\overset{t-1}{\mathrm{\&Sigma;}}}{l}_i\\ l_i>0,(i=\mathrm{1,2},...,t-1)\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\\ \end{array}\right.---\left(8\right)$

length_i、angle_i分别表示第i个导航点至第(i+1)个导航点的距离和方位角，t表示航路导航点总个数(包括发射点和目标点)，l_i表示length_i段航路距离规划区域的禁飞区的最小距离，l_i＞0时，航路不与禁飞区相交，当l_i＝0时，说明航路段与禁飞区相交。航路所有导航点(不包括发射点和目标点)的拐弯角不能超过允许的最大拐弯角Angle_Max。航路的所有航路段长度不能小于允许的最小航路段距离Length_Min。航路的总航程不能超出允许的最大航程Route_Length_Max。航路的总导航点个数(包括发射点和目标点)不能超出允许的最大拐弯点个数Route_Node_Num_Max。 

计算每一代航路种群中每个种群所包含的航路个体适应度值的均方差D，若每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群中选取适应度值f(m)最小的航路作为最优航路，组成不同种群的航路集合Q，若每一代航路种群中任一种群的航路个体适应度值的均方差D不小于预先设定的航路个体的适应度值的均方差数值，则返回步骤四，进行优化操作，直至每一代航路种群中每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群选取一条适应度最优的航路组成了航路集合Q，此时航路集合为种群间的航路集合。 

步骤六：步骤五中从每个种群选取一条适应度最优的航路组成了航路集合Q，此时航路集合为种群间的航路集合。对种群间的航路集合Q进行进化操作，航路集合Q进化后得到新一代航路集合Q′。针对同一时间内航路的航迹线存在空间冲突现象，及需要实现的攻击要求(如设定时间攻击、饱和攻击等)，从空间和时间两方面考虑设计进化算子，对航路个体进行局部的微调，以满足多枚导弹之间航路的协调性。设计的进化操作方法如下： 

(1)种群间航路距离扰动变异：针对航路集合Q中任意两条航路的距离必须大于最小值D_min，对航路集合Q中航路距离小于此值两条航路的最接进处进行微调。若第一条航路与第二条航路最接近处的航路点分别为A与B，航路点A、B都可沿这点的前后两航路段移动，航路点A在第一条航路上移动时，必定有一个方向是远离第二条航路的方向，同理，航路点B在第二条航路上移动时，必定有一个方向是远离第一条航路的方向。将航路点A、B按照远离彼此所在航路的方向移动，使其距离分开，至两条航路之间的最小距离大于最小值D_min，则完成变异操作，形成新的航路。在进行变异操作时，需满足航路个体本身的约束(即满足 航路个体适应度评价函数)。 

(2)航路航程扰动变异：针对导弹前后两条航路的发射时间间隔必须大于最小值Δt，对导弹先后发射的两条航路，确定其发射时间后，要求其发射时间间隔需不小于Δt，若不满足，需调整其中一条航路的航程。由生成初始种群航路的方法可知，改变第i段航路方位角与第i-1条平行线方位角的差角α_i，既可得到不同的航路点，而α_i取值在[0，180]之间，当α_i取值越趋于0度或者180度时候，该点的拐弯角越大，航路航程越大，而越趋于[0，180]中间[110，145]时，该点拐弯角越小，航路航程越小。则可改变任意航路点对应的α_i的值，使航路航程变大，使其满足条件。在进行变异操作时，同时需满足航路个体本身的约束(即满足航路个体适应度评价函数)。 

(3)平滑变异：在导航点相邻的两个航路段上分别插入新导航点，新插入的导航点连线平行于变异点先前两相邻相导航点的连线，同时删除原导航点，实现航路的平滑，同时也减短了路径的总长度。 

以上各种进化操作可以同时进行，也可以任选其中几种进行，只需达到进化操作的目的即可。 

步骤七：航路集合Q进化后得到新一代航路集合Q′，评价其是否满足种群间适应度函数的约束，同时对新一代航路集合Q′中的每个航路个体采用个体适应度评价函数评价是否满足条件。种群间的适应度评价函数D(n)为： 

$\left\{\begin{array}{c}D\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{dis}\tan \mathrm{ce}(p_i,p_{i+1})\right\},(i=\mathrm{1,2},...t-1)\\ D\left(n\right)\&GreaterEqual;D_{\min }\end{array}\right.---\left(9\right)$

$\left\{\begin{array}{c}T\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{time}(S_i,S_{i+1})\right\},(i=\mathrm{1,2},...t-1)\\ T\left(n\right)\&GreaterEqual;\mathrm{\&Delta;t}\end{array}\right.---\left(10\right)$

其中dis tan ce(p_i，p_i+1)表示航路集合Q′空间相邻的两航路的最小距离，time(S_i，S_i+1)表示发射时间相邻的两条航路的发射时间差，D_min表示空间相邻的两条航路的最小间隔距离，Δt表示发射要求的最小间隔时间，T(n)表示所有发射时间相邻的航路的最小发射时间差。 

本步骤中航路个体所采用个体适应度评价函数与步骤五中的适应度评价函数相同。

步骤八：根据步骤七中种群间的适应度评价函数得到进化后的新一代航路集合Q′种群间的适应度值的均方差E，同时用个体的适应度评价函数得到进化后的新一代航路集合Q′中每条航路的适应度值的均方差D’。若E小于预先设定的种群间的适应度值的均方差数值，D’也小于预先设定的航路个体的适应度值的均方差数值，即满足各航路之间的协同条件，输出结果；否则任意一个不满足(如E小于预先设定的种群间的适应度值的均方差数值，但D’不小于预先设定的航路个体的适应度值的均方差数值，则不满足各航路之间的协同条件)，则不满足各航路之间的协同条件，返回步骤六，继续对航路集合Q进行进化操作，直至满足协同条件。 

Claims (5)

1.一种基于多目标进化算法的多弹航路规划方法，其特征在于：包括以下几个步骤：

步骤一：对导弹航路进行编码并定义导弹的机动特性；

步骤二：根据敌我双方舰船所在地理位置，确定一个能包含敌我双方舰船的正四边形规划区域，结合规划区域的环境和敌我双方舰船的运动和火力分布情况，对环境进行建模，采用垂直于导弹发射点与目标点连线的多条平行线将导弹发射点与目标点之间的连线从发射点开始等距离分割，相邻两平行线之间的距离为Length_Min，规划区域环境的障碍物分为岛屿与敌我双方舰船；岛屿简化成用一系列经纬度点表示的多边形禁飞区；以舰船所在位置为圆心，以威胁半径为半径的圆形禁飞区表示其位置，舰船的航行速度用圆形禁飞区的圆心的移动速度来表征，再将圆形禁飞区扩展成与圆相切的正四边形禁飞区；

步骤三：生成航路初始种群P₁，P₂，…P_n：

对规划环境采用垂直于发射点和目标点的多条平行线等距分割法建模，穿过发射点的平行线为第一条平行线，而第一条平行线与第二条平行线之间的航路为第1段航路，若i表示第i段航路，相邻两平行线之间的距离为Length_Min，第i段航路方位角与第i-1条平行线方位角的差角为α_i，在发射点至目标点之间的各条平行线上各取一个点作为航路点，将发射点、各条平行线上的各个航路点以及目标点相连接，确定一条航路；若某个航路上的第i个航路点坐标为(x_i,y_i)，第i个航路点至第i+1个航路点的方位角和距离分别为angle_i和length_i，则有：

angle_i＝S_G_Angle-90°+α_i

length_i＝Length_Min/sinα_i

S点为发射点，G为目标点，S_G_Angle是S点至G点方位角；

根据文森特公式，由目标点依次求出一条航线上各个航路点的经纬度坐标，改变第i个航路点至第i+1个航路点的方位角值angle_i，改变α_i，确定下一个航路点的经纬度坐标，对应生成一条不同的航路，选取m个不同的α_i值生成m条不同的航路，组成一个初始种群，共生成n个航路初始种群P₁，P₂，…P_n；

步骤四：对航路初始种群P₁，P₂，…P_n分别进行进化操作，产生新一代航路种群，进化操作方法有交叉、变异和平滑；

步骤五：计算新一代航路种群中每个种群中每个航路的适应度值，去掉适应度差的航路，保留每个种群中适应度最优的航路，得到适应度最优的航路种群P₁'，P₂'，…P_n'，采用针对航路个体适应度的评价函数对每个种群中的航路进行评价；

航路个体的适应度评价函数f(m)为：

f(m)＝δ_dD(m)+δ_sS(m)+δ_cC(m)；                 (5)

其中，D(m)表示一条航路的总航程，S(m)表示航路的平滑度，C(m)表示航路的安全程度；δ_d、δ_s、δ_c分别表示航程、平滑度、安全程度在适应度函数中的权重；f(m)越小，航路个体越优；其中各个参数定义与计算公式分别为：

$\left\{\begin{array}{c}D\left(m\right)=\underset{i=1}{\overset{t-1}{\mathrm{\&Sigma;}}}{\mathrm{length}}_i\\ {\mathrm{length}}_i\&GreaterEqual;\mathrm{Length}\_\mathrm{Min},i=\mathrm{1,2},...,t-1\\ D\left(m\right)\&le;\mathrm{Route}\_\mathrm{Length}\_\mathrm{Max}\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\end{array}\right.$

$\left\{\begin{array}{c}S\left(m\right)=\underset{i=1}{\overset{t-2}{\mathrm{\&Sigma;}}}({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)/(t-2)\\ ({\mathrm{angle}}_{i+1}-{\mathrm{angle}}_i)\&le;\mathrm{Angle}\_\mathrm{Max},i=\mathrm{1,2},...,t-2\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\end{array}\right.$

$\left\{\begin{array}{c}C\left(m\right)\text{=1/}\underset{i=1}{\overset{t-1}{\mathrm{\&Sigma;}}}{l}_i\\ l_i>0,i=\mathrm{1,2},...,t-1\\ t\&le;\mathrm{Route}\_\mathrm{Node}\_\mathrm{Num}\_\mathrm{Max}\end{array}\right.$

length_i、angle_i分别表示第i个航路点至第i+1个航路点的距离和方位角，t表示航路航路点总个数，包括发射点和目标点，l_i表示length_i段航路距离规划区域的禁飞区的最小距离，l_i＞0时，航路不与禁飞区相交，当l_i＝0时，说明航路段与禁飞区相交，航路所有航路点的拐弯角不能超过允许的最大拐弯角Angle_Max，不包括发射点和目标点；航路的所有航路段长度不能小于允许的最小航路段距离Length_Min；

航路的总航程不能超出允许的最大航程Route_Length_Max，航路的总航路点个数包括发射点和目标点不能超出允许的最大拐弯点个数Route_Node_Num_Max；

计算每一代航路种群中每个种群所包含的航路个体适应度值的均方差D，若每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群中选取适应度值f(m)最小的航路作为最优航路，组成不同种群的航路集合Q，若每一代航路种群中任一种群的航路个体适应度值的均方差D不小于预先设定的航路个体的适应度值的均方差数值，则返回步骤四，进行进化操作，直至每一代航路种群中每个种群的航路个体适应度值的均方差D均小于预先设定的航路个体的适应度值的均方差数值，则从每个种群选取一条适应度最优的航路组成了航路集合Q，此时航路集合为种群间的航路集合；

步骤六：对种群间的航路集合Q进行进化操作，得到新一代航路集合Q′，设计的进化操作方法包括：种群间航路距离扰动变异、航路航程扰动变异和平滑变异；

步骤七：对航路集合Q进化后得到新一代航路集合Q′，评价其是否满足种群间适应度评价函数的约束，同时对新一代航路集合Q′中的每个航路个体，评价其是否满足个体适应度评价函数的约束；

其中种群间的适应度评价函数D(n)为：

$\left\{\begin{array}{c}D\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{dis}\tan \mathrm{ce}(p_i,p_{i+1})\right\},i=\mathrm{1,2},...,t-1\\ D\left(n\right)\&GreaterEqual;D_{\min }\end{array}\right.---\left(9\right)$

$\left\{\begin{array}{c}T\left(n\right)=\underset{i=1}{\overset{t}{\mathrm{MIN}}}\left\{\mathrm{time}(S_i,S_{i+1})\right\},i=\mathrm{1,2},...,t-1\\ T\left(n\right)\&GreaterEqual;\mathrm{\&Delta;t}\end{array}\right.---\left(10\right)$

其中dis tan ce(p_i,p_i+1)表示航路集合Q′空间相邻的两航路的最小距离，time(S_i,S_i+1)表示发射时间相邻的两条航路的发射时间差，D_min表示空间相邻的两条航路的最小间隔距离，Δt表示发射要求的最小间隔时间，T(n)表示所有发射时间相邻的航路的最小发射时间差；

本步骤中航路个体所采用个体适应度评价函数与步骤五中的适应度评价函数相同；

步骤八：根据步骤七中种群间的适应度评价函数得到进化后的新一代航路集合Q′种群间的适应度值的均方差E，同时用个体的适应度评价函数得到进化后的新一代航路集合Q′中每条航路的适应度值的均方差D’，若E小于预先设定的种群间的适应度值的均方差数值，D’也小于预先设定的航路个体的适应度值的均方差数值，则满足各航路之间的协同条件，输出结果；否则任意一个不满足，则返回步骤六，继续对航路集合Q进行进化操作，直至满足上述的协同条件。

2.根据权利要求1所述的一种基于多目标进化算法的多弹航路规划方法，其特征在于：所述的步骤一中对导弹航路进行编码具体为：导弹的航路由一组有序的航路点组成，每个航路点包含该点的经纬度值信息，航路点编码route_node为：route_node＝{x,y,angle}；其中，x，y分别表示该航路点的经纬度坐标，采用实数编码；angle表示该航路点与下一航路点的方位角；

航路编码missile_route为：

missile_route＝{list＜route_node＞route_list,fitness_value,route_length,feasible_flag,sum_turn_angle}

其中，list＜route_node＞route_list为该航路的航路点链表集信息，fitness_value为航路适应度值，route_length为航路的总长度，feasible_flag为航路是否可行的标志量，sum_turn_angle为航路的总拐弯角。

3.根据权利要求1所述的一种基于多目标进化算法的多弹航路规划方法，其特征在于：所述的步骤一中导弹的机动特性包括：

①方位角：以正北方向为0度方位角，顺时针方向方位角为正，取值范围为[0,360]；

②航路允许的最大拐弯角：Angle_Max；

③航路允许的最小航路段距离：Length_Min；

④航路允许的最大航程：Route_Length_Max；

⑤航路允许的最大拐弯点个数：Route_Node_Num_Max；

⑥相邻两条航路的最小间隔距离：D_min；

发射要求的最小间隔时间：Δt。

4.根据权利要求1所述的一种基于多目标进化算法的多弹航路规划方法，其特征在于：所述的步骤四中交叉、变异和平滑具体为：

(1)交叉：采用双点交叉，在初始种群中任意选取两条航路作为母体，在两个母体上分别随机选取两个航路点作为交叉点，发射点与目标点除外，将两条航路分别从交叉点断开成两个部分，然后第一个母体的第一部分与第二个母体的第二部分组合，第一个母体的第二部分与第一个母体的第一部分组合，从而生成两条新的航路；

(2)变异：针对航路初始种群内部进化设计三种变异方法：

删除变异：从航路个体即任意一条航路中随机删除一个航路点，发射点与目标点除外，生成一条新的航路；

扰动变异：改变航路个体中某个航路点的坐标，针对航路点是否在障碍物内或者连接该点的前后两段航路是否和障碍物相交，设置不同的扰动范围，具体为以选中的某航路点为圆心，以r为半径画圆，扰动区域选远离障碍物的半圆区域，如果该航路点在障碍物内，r取该航路点到此障碍物最远顶点的距离，如果该点不在障碍物内，r取航路允许的最小航路段距离的1/5，1/5Length_Min；

二点变异：选择航路个体即任意一条航路中相邻两个航路点，发射点与目标点除外，重新生成两个航路点，替换选中的两个航路点，参照生成初始种群中航路的方法，分别改变选中点对应的第i段航路方位角与第i-1条平行线方位角的差角α_i的值，生成两个新的航路点，替换选中的航路点；

(3)平滑：平滑算子针对导弹的最大拐弯角设计，通过平滑操作实现航路转弯角小于航路允许的最大拐弯角Angle_Max，航路转弯角的取值为(Angle_Max-30°)，第i段航路方位角与第i-1条平行线方位角的差角α_i取值在[0,180]之间，当α_i取值越趋于0度或者180度时候，该航路点的拐弯角越大，而越趋于[110,145]，该航路点拐弯角越小，改变α_i的值来使对应该航路点拐弯角变小，实现航路的平滑。

5.根据权利要求1所述的一种基于多目标进化算法的多弹航路规划方法，其特征在于：所述的步骤六中种群间航路距离扰动变异、航路航程扰动变异和平滑变异具体为：

(1)种群间航路距离扰动变异：针对航路集合Q中任意两条航路的距离必须大于最小值D_min，对航路集合Q中航路距离小于此值两条航路的最接近处进行微调，若第一条航路与第二条航路最接近处的航路点分别为A与B，航路点A、B都可沿这点的前后两航路段移动，航路点A在第一条航路上移动时，必定有一个方向是远离第二条航路的方向，同理，航路点B在第二条航路上移动时，必定有一个方向是远离第一条航路的方向，将航路点A、B按照远离彼此所在航路的方向移动，使其距离分开，至两条航路之间的最小距离大于最小值D_min，则完成变异操作，形成新的航路；

(2)航路航程扰动变异：针对导弹前后两条航路的发射时间间隔必须大于最小值Δt，对导弹先后发射的两条航路，确定其发射时间后，要求其发射时间间隔需不小于Δt，若不满足，需调整其中一条航路的航程，由生成初始种群航路的方法可知，改变第i段航路方位角与第i-1条平行线方位角的差角α_i，即可得到不同的航路点，而α_i取值在[0,180]之间，当α_i取值越趋于0度或者180度时候，该航路点的拐弯角越大，航路航程越大，而越趋于[110,145]时，该航路点拐弯角越小，航路航程越小，则改变任意航路点对应的α_i的值，使航路航程变大，使其满足条件；

(3)平滑变异：在航路点相邻的两个航路段上分别插入新航路点，新插入的航路点连线平行于变异点先前两相邻的航路点的连线，同时删除原航路点，实现航路的平滑，同时也减短了路径的总长度。