基于细菌进化及多属性决策的航迹规划方法研究*

肖 桥，冯 琦，赵鸿森

(1西北工业大学电子信息学院，西安 710072;2中国飞行试验研究院航电所，西安 710089)

0 引言

飞行器航迹规划问题本质是一个多维、非连续、非线性大空间内的多约束、多目标的NP优化问题，进化算法已被证明是一种解决NP问题的有效全局搜索技术，在搜索空间和并行运算效率两方面体现出其独特的优势，在航迹规划领域得到了广泛的研究[1－2]。但传统的进化算法存在初始种群大，影响进化效率，在搜索过程中存在早熟和收敛过慢问题;而且传统的适应度函数的选取方法并不能很全面的评价航迹个体的优劣。

为改进进化算法进行航迹规划时存在的问题，把细菌进化引入航迹规划，设计了独特的二进制编码方式和更加合理的种群初始化方法，应用细菌进化独特的变异和基因传递[3]改良种群，并采用多属性决策理论对种群航迹个体进行评价。

1 细菌变异的航迹规划方法

航迹规划目的是寻找从起始点通往目标点间的几个关键航路点，相邻两个航路点连线构成一段航路。所以首先根据需要定出可能的航路点数量，然后据此编码，在实际应用中一般选取3～5个航路点。

1.1 角度和航段长度编码方法

以起始点为坐标原点，目标点处于第一象限中，第一段航路的角度θ1限制在0°～90°;由于飞行器过载的限制，两段航路之间最大角度改变量限制为θmax，假设第k段航路的角度为θk，第k+1段航路的角度为θk+1，则相邻两段航路的转弯角度限制为|θk+1－θk|＜θmax，将此范围等分为16份，则角度可采用4位二进制编码：

式中ε为二进制编码解码出的整数，ε∈[0，15]。

假设航路点k的坐标(xk，yk)和第k+1段nm航路点的角度θk+1、长度lk+1，则第k+1个航路点的坐标计算如下：

每一段航路的编码分为角度和段长，角度采用4位二进制编码，航路长度采用8位二进制编码，则两个航路点之间的航路对应12位二进制位。细菌个体的编码为 θ1l1θ2l2…θnln，θi和 li(i=1，2，…，n)分别代表角度编码和段长编码，每个个体表示一条完整的航迹。编码示意如图1。

图1 航迹编码示意图

1.2 初始种群产生

在进化算法中一般选取很大的种群以保证搜索范围和防止早熟，种群数越大搜索范围越广，但进化效率越低，而细菌进化算法的优势之一就是较少的种群数即可达到目的[4]，假设细菌种群数为Nind，每一个细菌代表一条完整航迹，初始产生的个体编码每一位都在0和1中随机产生，为了使初始种群具有多样性以克服早熟现象，航迹第一段航路初始角度编码设置在0°～90°范围内均匀分布。

1.3 细菌变异

细菌变异是对单个个体执行的操作，目的是为了提高种群的多样性。首先对每一个细菌产生Nclone个克隆体，然后随机选择克隆体的某一段或某几段，随机改变这些段的参数。采用二进制编码，变异操作通过使参数在0和1中重新随机选取实现。然后对所有的克隆体和其原航迹个体进行评价，即采用多属性决策方法，选出最优个体，然后这个最优细菌把变异部位复制给其余克隆体。继续上述循环，直到所有片段被变异，然后保留最优细菌，去掉它的克隆体。

上述操作同时对种群的所有细菌个体执行。但在进化的同一代中，每个位置最多变异一次。采用变异操作，细菌种群会更加优秀，由于每一次变异都为航迹规划带来了一种解决途径，因此这种方法可以使航迹的搜索范围更广，同时克隆操作和并行变异使得运算更加高效。克隆数Nclone越大，输出结果越精确。细菌变异操作如图2所示。

图2 细菌变异示意图

1.4 基因传递

基因传递是对整个种群执行的操作，是为了实现细菌个体之间的信息交互，类似于遗传算法中的交叉操作，与交叉操作不一样的是，整个过程中没有基因交换，只有优势个体把基因复制给劣势个体，基因传递实现了信息从优等个体向种群的传播。

首先对于整个种群，依据多属性决策方法排序，把种群分为两部分：优等种群和劣等种群;然后分别从优等集中随机选一个个体(源细菌)，从劣等集中随机选一个个体(目标细菌)，随机从源细菌上选取一个片段，复制到目标细菌上。在每一代中，细菌的基因传递会发生Ninf次，其中Ninf为每一代的基因传递次数。Ninf过大会出现早熟现象而导致局部最优化，故Ninf小一点会取得不错的效果，同时也会减少运算量。基因传递操作如图3所示。

图3 基因传递示意图

1.5 进化流程

Stept1产生初始种群;

Stept2对每一个细菌执行变异操作;

Stept3在种群中执行基因传递操作;

Stept4若达到终止条件，则终止循环;否则，用最优个体取代最差个体，然后回到Stept2继续循环。终止条件为设定的最大进化代数Ngen。

2 多属性决策理论的航迹个体评价方法

在计算航迹个体的适应度函数时，已有的进化算法大多将各个优化属性统一量纲进行加权处理，例如在无人机航迹规划中，有采用航迹总长度、飞行高度和威胁指数加权计算的方法[5];在反舰导弹航迹规划中，有采用被探测的威胁度、被拦截威胁度和航程加权计算的方法[6]，但实际中各属性的量纲很难统一，并且各个属性的数量级相差甚大，这样处理往往导致矛盾的结果，并因此而丢失优良个体。航迹个体的评价从根本上看都是一个多属性决策问题，因此在个体评价时应用决策理论更切合问题的本质，在进行航迹个体评价时主要参考三个主要属性：航迹总长度、转弯角度和生存概率;航迹总长度是一项基本属性，总长度越短，受威胁时间越短，耗油也越少;很多规划方法容易忽略转弯角，但转弯角也是一个很重要的属性，转弯越多耗油越大;对于作战飞行器，最重要的属性还是生存概率。

2.1 航迹总长度

设起始点为(x0，y0)，目标点为(xD，yD)，第 i段航路长为li，通过式(1)解码出的最后一个航路点的坐标为(xn，yn)，则整段航迹长度L可用下式计算：

2.2 转弯角

设第i段航路的角度为θi，则整条航迹的总转弯角度θ为：

2.3 生存概率

首先把总航迹等距离散化为一系列的点{x1，…，xj，…，xK}，假设有H个威胁源，在某一点x处的生存概率为P(x)为：

Ri(x)是在点x处被威胁源i杀伤的概率。

则总航迹{x1，…，xj，…，xK}生存概率 P 为[7]：

2.4 多属性航迹评价

种群中各个航迹个体的优劣主要是由上述三个不同属性综合决定的，而且在航迹评价中不同的任务对于这三个不同属性的要求不一样，同时各属性的数量级也有较大差异，需要采用多属性决策方法对航迹个体进行优劣评价。

决策矩阵(Decision Matrix)是求解多属性决策问题的依据，是属性值和决策准则的基础。设Ai(i=1，2，…，m)表示第 i个体，Xj(j=1，2，…，n)表示第 j属性，则多属性决策问题可用下面的矩阵M表示：

决策矩阵M中的元素xij表示第i个体Ai在第j属性Xj下的属性值。各方案的属性值可构成决策矩阵，或称为属性矩阵、属性值表，该决策矩阵提供了分析决策问题所需的基本信息[8]。

对于各属性优属度μ的确定，航迹长度和转弯角度都是越小航迹越好，故采用成本型相对优属度确定方法，生存概率越大航迹越优，故采用效益型相对优属度确定方法。

成本型的相对优属度计算公式为：

效益型属性的相对优属度计算公式：

通过选择合适的目标相对优属度计算公式，可将决策矩阵M变换成为目标相对优属度矩阵μ，即：

则个体优劣决策向量T1×m=ω·μT，对决策向量进行排序等价于对种群航迹个体进行评价，其中ω=(ωL，ωθ，ωp)，分别表示航迹总长度、转弯角和生存概率的评价权重，ω的选取对于顺利完成航路规划任务至关重要，ωL、ωθ、ωp的选取是根据飞行器的性能、具体的飞行任务和飞行环境等因素综合决定，有人驾驶飞行器可以根据经验知识来调整，但是一般来说应该采取更加科学的方法，特别是对于在航迹规划属性更多、要求更精确的情况下。对于权重的选取主要有：基于目标偏好的综合集成赋权法;基于熵的综合集成赋权法;基于模糊层次分析法的权重计算模型;模糊综合评估法[9];基于知识的模糊推理方法等。

3 仿真结果

规划区域内有五个威胁源，在图中用黑色灰度区域表示，黑色越深表示该区域的杀伤概率越大，右上角黑点代表目标点，根据过载要求得出相邻两段航路最大角度改变量θmax=60°，种群数Nind=200，克隆数Nclnoe=50，基因传递数Ninf=50，进化代数Ngen=400。ω =(0.2，0.6，0.2)时规划结果如图 4 所示;ω=(0.6，0.2，0.2)时规划结果如图 5所示;ω =(0.2，0.2，0.6)时规划结果如图6所示;ω =(0.33，0.33，0.34)时规划结果如图7所示。

图4 权重偏向于转弯角度

图5 权重偏向于航迹长度

图6 权重偏向于生存概率

图7 权重均匀选取

对比图4～图7可看出，转弯角、航迹长度和生存概率都会影响航迹的生成效果。如果需要尽快到达目标点可以设置较大的转弯角度权重或者较大的航迹长度权重，如果需要保证飞行器的生存概率而绕过威胁区，则可以设置较大的生存概率权重。为了搜索到符合条件的最优航迹，合理选取各属性权重对于航迹规划具有很重要的作用。

4 结论

设计了适用于航迹规划的细菌进化算法，采用切合实际任务需求的编码方式和种群初始化方法及基因变异、基因传递操作增大了搜索空间，使得采用一般进化算法存在的初始种群大、早熟及收敛过慢问题得到了很好的解决;首次采用多属性决策方法进行航迹个体评价，使得规划决策者可以根据任务需求而设定不同的约束条件和优化属性，具有很好的应用前景。仿真结果表明所提方法具有很好的全局规划能力及灵活性。

[1]C Hocaoglu，A C Sanderson.Planning multiple paths with evolutionary speciation[J].IEEE Transaction on Evolutionary Computation，2001，5(3)：169－192.

[2]K Sugiara，J Smith.Genetic algorithms for adaptive planning of path and trajectory of a mobile robot in 2D terrains[J].IEEE Transaction on Information System，1999，E82－D(1)：309－316.

[3]N E Nawa，T Furuhashi.Fuzzy system parameters discovery by bacterial evolutionary algorithm[J].IEEE Trans.Fuzzy Systems，1999，7(5)：608－616.

[4]Cabrita，C.Botzheim，J.Ruano，A.E.Kóczy，and L.T：Design of B-spline neural networks using a bacterial programming approach[C]//International Joint Conference on Neural Networks，2004：2313－2318.

[5]丁明跃，郑昌文，周成平，等.无人飞行器航迹规划[M].北京：电子工业出版社，2009.

[6]沈建锋，刘兴明，吴凌华，等.多平台反舰导弹协同航迹规划[J].战术导弹技术，2009(2)：62－66.

[7]Adam McLendon Eames.Enabling path planning and threat avoidance with wireless sensor networks[D].America：Massachusetts Institute of Technology，2005.

[8]杨保安，张科静.多目标决策分析理论、方法与应用研究[M].上海：东华大学出版社，2008.

[9]罗小明.弹道导弹攻防对抗的建模与仿真[M].北京：国防工业出版社，2009.