基于量子遗传算法的无人机冲突解脱方法

甄 然，王 攀，武晓晶，吴学礼*

(1.河北科技大学电气工程学院，石家庄 050018；2.河北省生产过程自动化工程技术研究中心，石家庄 050018)

随着科技的日益发展，无人机的应用越来越广泛,致使空域变得越来越拥堵,导致无人机飞行冲突易发、空域资源紧张等，严重影响了无人机飞行安全和可行性。无人机飞行数量的增加和飞行路线的多向性也增加了飞行冲突的可能性，因此，无人机冲突解脱问题的研究变得异常重要。多年来各国学者对飞行冲突解脱进行了各种各样的研究，Alonso-Ayuso等[1]提出了一种混合整数线性优化模型，采用近似序列混合整数线性优化方法来解决飞行冲突解脱问题。Lehouillier等[2]利用一种最小权最大集团模型的新形式来解决飞行冲突，通过引入两个分解算法，可在较短时间内获得飞行机动集合最优解。Vela等[3]构建了一种优化模型来避免飞机冲突，并考虑了燃油成本因素，使其成本最小。Yang等[4]提出了一种无人机的双层冲突探测与解脱机制，并采用了航向变化和速度变化混合的冲突解脱方法，能够较好地处理复杂情况，降低额外成本。Emmanuel等[5]建立了一种三维冲突计数模型来分析非结构化空域和分层空域设计的安全性，其对两种空域设计的瞬时冲突计数都有较高的估计精度。梁曼等[6]提出一种改进的案例检索方法，提高推理速度，从而更好地实现飞行冲突智能解脱。黄洋等[7]利用复杂网络快速同步修改无人机轨迹，从而达到冲突解脱避险的目的。杨新湦等[8]通过划分兴趣区，分析管制员在冲突解脱时的眼动行为，提高进行管制飞行冲突的效率，但是其没有对解脱航迹优化方面进行分析研究。文献[9]将A*算法应用到飞行冲突解脱中，文献[10]和文献[11]分别基于合作博弈和改进蚁群算法来解决冲突解脱问题，均取得不错的效果，但他们都没有考虑和优化整体解脱过程中的航向转弯次数，这关系到整体的飞行成本。文献[12]使用蒙特卡洛法，仿真了无人机飞行冲突过程，较明显地减小了事故率，但其没有在算法的求解时间方面进行比较分析。

在综合以上研究的基础上，充分考虑研究了解脱航迹优化、求解时间、航向转弯次数、总延误距离等方面，提出了一种基于量子遗传算法的无人机冲突解脱方法。首先建立冲突解脱模型，然后确定适应度函数，设计并加入延误指数函数强制优化策略和变航向优化策略，利用量子遗传算法求解得出最优的解脱航迹，通过MATLAB仿真，验证其有效性，以期达到比遗传算法更好的解脱航迹、更小延误距离等效果。

1 无人机冲突解脱问题的描述与建模

根据国家空中交通管制的安全规定和无人机实际飞行情况，对无人机的冲突解脱问题进行了合理简化。

(1)考虑到无人机在实际飞行时，除了起飞和降落期间外，其他阶段都是在固定的高度飞行，且考虑到无人机的油耗等要求，把无人机的冲突解脱问题简化为二维平面进行研究。

(2)无人机在实际巡航飞行过程中，其速度没有较大变化，所以假设无人机的速度大小不变。

(3)根据国家的空中交通管制规定，两架飞行器之间的安全间隔至少为20 km，所以设定两架飞机间的距离需大于20 km作为约束条件，无人机的飞行步长定为10 km[13]。

(4)假设无人机在进行航向调整时，只能进行3种航向调整：保持原飞行航向、左转30°、右转30°。

图1 原计划航迹Fig.1 Original planning tracks

假设两架无人机以相同速度且保持不变同时进入一个200 km×200 km的正方形区域里，无人机如果按图1所示的无航迹调整的原计划航迹飞行时，两机将在正方形的几何中心点发生碰撞，过程中每架无人机每飞行一个步长取一个航迹节点，即每架无人机在整个区域飞行了20个步长，其在正方形区域的总飞行时间也分为了20步。其中无人机的飞行步长可理解为检测频率，无人机每飞行一个步长就被检测一回，判断是否发生冲突。无人机在每一个步长飞行时，保持飞行的航向和速度。在进入每一个步长时，无人机进行航向调整，从而防止冲突发生。

约束条件设定为两架无人机之间的距离D大于飞行安全距离20 km[14]，即

(1)

对于每架无人机根据其进入正方形空域入口点、开始航向、每一个航迹节点的位置坐标和航向变化等方面，计算分析整个航迹，并分析是否有冲突情况。一旦在任何一节点发现冲突情况，那么包含这条航迹的个体适应度值将被设置为0。

无人机飞行冲突的出现会迫使无人机进行航迹调整，从而不可避免地造成脱离原计划航迹的情况，产生飞行延误，使无人机从出发地到目的地的飞行距离增加，实际飞行时间相比无冲突时的原计划航行时间增加，无人机的能耗也因此增加，从飞行时间、经济成本等方面考虑，在保证无人机间无冲突的前提下，优化目标为使无人机实际飞行解脱航迹相比原计划航迹的总延误距离最小(此处的总延误距离指两架飞机的延误距离之和，每架无人机延误距离定义为从第一个航迹节点到第20个航迹节点冲突解脱结束时，实际解脱航迹节点与原计划航迹节点的直线距离之和。)则冲突解脱问题的目标函数为

(2)

根据要优化的目标设定了适应度函数，适应度值越大，最终的解质量越好。适应度函数为

(3)

式(3)中：k1为常数。

在染色体的编码环节涉及了二进制编码，用N表示空域中的无人机数量，I为各无人机在区域内的总飞行步长。构建了一个N×I×2的解空间，将每个染色体对应的解空间分解成N个I维向量：Xn=(xn1,xn2,…，xnI)(i=1,2,…,I)，其指第n架无人机在区域内的航向调整。其中：xni=10表示第n架无人机在第i步时左偏30°；xni=01表示第n架无人机在第i步时右偏30°；xni=00或11时表示第n架无人机在第i步时保持直行[15]。

根据所设计的两架无人机的冲突解脱模型，设定无人机数目N=2，每架无人机总飞行步长I=20。

2 算法原理

2.1 量子遗传算法

量子遗传算法是在标准遗传算法的基础上，结合量子计算而生成的一种改进的遗传算法，其编码方式独特，在传统的遗传编码中加入了量子态，使染色体中的基因既可以为0态，也可以为1态，或是两者的随机叠加态。因此，每条染色体可以呈现多种态的叠加。然后利用量子旋转门来实现种群中个体的更新和演化。与标准遗传算法相比，量子遗传算法能够获得更好的种群多样性，从而最终能求得更优的解。

2.2 量子比特表示

在量子计算机当中，作为信息存储单元的物理介质是一个双态量子系统，其称作量子比特。其独特之处是其可以处在“0”态和“1”态的叠加态中，即

|φ〉=α|0〉+β|1〉

(4)

式(4)中：α、β均为复数，表示相应状态的概率幅[16]，|α|2、|β|2分别指处在“0”态和“1”态的概率，其满足|α|2+|β|2=1；|0〉表示自旋向下态；|1〉表示自旋向上态[17]。

在量子遗传算法中，染色体中的每个基因可含有一个或多个量子比特，每条染色体可由多个量子比特表达的基因组成。如一条由s个量子比特组成的染色体C可以表示为

(5)

式(5)中：|αi|2+|βi|2=1(i=1,2,…,s)，染色体C可以表示2s个状态[18]。

2.3 量子旋转门

量子遗传算法的演化方式不同于标准遗传算法的选择、交叉、变异等操作，主要通过利用量子旋转门进行演化操作，通过对叠加态加以作用，使叠加态之间进行相互干涉，发生相位形变，因此改变了各基态的概率幅，完成染色体的更新演化。采用如下的量子旋转门调整操作：

(6)

量子旋转门更新过程为

(7)

式(7)中：[α′i,β′i]T为更新后的第i个量子比特；θi为旋转角，θi由表1的旋转角调整策略决定。

3 基于量子遗传算法的无人机冲突解脱

3.1 染色体编码

(8)

式(8)中：m为一条染色体的基因数目；s为单个基因中的量子比特数目。

(9)

图2 航迹二进制编码示意图Fig.2 A diagram of tracks binary coding

3.2 旋转角选择策略

根据本文冲突解脱的设计需求，采用了表1的旋转角调整策略。

3.3 延误指数函数强制优化策略

图3 总延误距离骤增示意图Fig.3 A diagram of the sharp increase in total delay distance

(10)

3.4 变航向优化策略

在无人机飞行冲突解脱的过程中，航向转弯次数也会影响整体解脱的效果。设计提出了一种变航向优化策略，约束规范航向转弯次数，减少飞行能耗，且避免过多偏离原航线的情况，如式(11)所示。

T>k2⟹适应度值置0

(11)

式(11)中：T为两架无人机的总转弯次数；k2为允许的最大转弯次数。k2的取值关系到解脱的效果，如果取值过小，对算法解的约束过大，会造成算法搜索不到合适的解，得不到理想的航迹，此外也有大幅度偏离原航线的可能；如果取值过大，则对转弯约束过小，也有可能造成转弯过多的现象。根据多次仿真验证得出，k2在区间[12,17]内取值的效果较为理想，既防止了过度偏离原航线，又能节约飞行成本。

3.5 求解流程

(3)对这组确定解进行适应度值评价，加入延误指数函数强制优化策略和变航向优化策略进行适应度值的筛选优化，并记录最优个体和其适应度值, 并作为当前的目标值。

(4)判断是否达到最大迭代次数，满足则退出，输出最优解，否则继续计算。

(5)对种群再进行一次测量，得到其对应的确定解，求出其中个体的适应度值，并加入延误指数函数强制优化策略和变航向优化策略进行优化。

(6)使用量子旋转门调整策略进行更新演化，得到更新后的种群；记录更新后的最优个体和其适应度值，并与当前目标值进行比较，如果大于目标值，则进行替换并作为新的目标值，否则的话保留当前的目标值。

(7)代数t加1，并返回步骤(4)。

4 仿真及验证

分别使用本文中提出的基于量子遗传算法的冲突解脱方法和遗传算法在两架无人机的冲突解脱问题上进行了仿真验证，并在算法的适应度函数值、飞行解脱航迹与飞行总延误距离等方面进行了分析对比。假设两架无人机以相同的恒定速度同时进入一个200 km×200 km的一个正方形空域，各自直线飞行前往目的地，一架在(0,100)开始从正西向东飞行，一架在(100,0)开始从正南向北飞行，若不进行冲突解脱调整，则将在正方形空域几何中心位置发生碰撞，为保证仿真对比的客观性，仿真所用的两种算法的种群数目均为200，迭代次数均为200代，所用适应度函数也相同。其中所用遗传算法的交叉概率为0.7，变异概率为0.03。

4.1 适应度函数值对比

本文方法与遗传算法得出的适应度值曲线如图4所示，两种算法的适应度数据对比如表2所示。

图4 两种算法的适应度值曲线Fig.4 Fitness value curves of the two algorithms

表2 适应度值数据对比Table 2 Data comparison of fitness value

由图4和表2可以看出，迭代结束时，相比遗传算法，本文方法得出的适应度值更高，则求出的解质量更好，且在较小代得到的适应度值比遗传算法最终代的适应度值还要高。

4.2 冲突解脱航迹对比

遗传算法与本文方法得出的解脱航迹分别如图5和图6所示，两种算法冲突解脱航迹数据对比如表3所示。

图5 基于遗传算法的冲突解脱航迹Fig.5 Conflict resolution tracks based on GA

图6 基于本文方法的冲突解脱航迹Fig.6 Conflict resolution tracks based on the proposed method

表3 冲突解脱航迹数据对比Table 3 Data comparison of conflict resolution tracks

由图5、图6和表3可以得出，使用本文方法的解脱航迹相比遗传算法的航迹更加平滑，更加贴近于原计划航迹，转弯次数更少，节省飞行能耗；在解脱结束后两架飞机距目的地的总距离相比使用遗传算法的距离更近，从而无人机在解脱后能更快到达目的地。

4.3 总延误距离对比

本文方法与遗传算法得出的总延误距离曲线如图7所示，两种算法总延误距离数据的对比如表4所示。

图7 两种算法的总延误距离曲线Fig.7 Total delay distance curves of two algorithms

表4 总延误距离数据对比Table 4 Data comparison of total delay distance

由图7和表4可以得出，本文方法求得的总延误距离相比遗传算法更小，实现了更小的飞行延误，在第9代时就能达到408 km的延误距离，比遗传算法最终代的延误距离还要小，即能更早地实现比遗传算法更小的延误。

4.4 与多种性能算法的综合对比

不同的交叉概率pc和变异概率pm会使遗传算法具有不同的性能和求解能力，为了更全面地进行比较，用本文方法与3种具有不同pc、pm值的遗传算法进行对比，通过多次的仿真实验，求出了各项主要对比数据的平均值，如表5所示。

表5 综合数据对比Table 5 Comprehensive data comparison

从表5结果可以看出,本文方法相比不同性能的遗传算法仍有明显的优势，适应度值更高，解的质量更高，求解时间较短，总延误距离小，解脱后能更快到达目的地，转弯次数少，节省飞行成本，在解决无人机冲突解脱问题上更有优势。

5 结论

针对两架无人机在空域内的飞行冲突问题，提出了一种基于量子遗传算法的无人机冲突解脱方法。构建了冲突解脱相关的数学模型，设置了合理的适应度函数和约束条件，设计加入延误指数函数强制优化策略和变航向优化策略在总延误距离值、转弯次数、适应度值等方面进行了优化，利用量子遗传算法求出最优解，得到最优的冲突解脱航迹。通过仿真证明，本文方法有效地解决了两架无人机的冲突解脱问题，求解时间较短，求得解的质量高，无人机在解脱后能更快到达目的地，且在适应度值、解脱航迹质量、总延误距离等方面均优于遗传算法。

在以后的研究中将开展以下几方面工作：①尝试将本文方法用于解决多架无人机的冲突解脱问题，并验证其可行性；②考虑空域中的复杂情况，比如风力扰动的因素，提高无人机在扰动情况下的冲突解脱成功率；③增加优化目标，提高优化的全面性；④在已有二维空域飞行冲突研究的基础上，尝试进行无人机在三维空域的冲突解脱研究。