林用无人机航迹非概率不确定性优化

徐玉洁 郑哲文

(中南林业科技大学材料与工程学院，湖南 长沙 410004)

引言

我国森林资源分布不均匀，森林的占有面积仅为世界的1/6，存在问题有很多。森林火灾是森林灾害中破坏性最强的，也是林业中最为可怕的灾害。森林防火是森林保护的重要内容。如何做到有效防火是人们日益关心的问题[1]。无人机具有成本较低、机动速度快、维修简单等特点，用途广泛；但无人机在环境未知的空间中飞行，会面临大量动态、未知的限制因素，如噪声、气流影响、传感器限制等[2]，这些因素的变化会导致在建模过程中的结构参数不确定。传统的优化模型均解决确定性问题，环境较为理想化，然而实际环境会受诸多因素影响。林用无人机受动态环境因素影响不确定性因素较多，如天气、风速以及无人机性能本身等，需要考虑实际工程结构中的不确定性以及对应的优化方法。不确定性的度量通常有概率与非概率模型，概率型所需样本较多，虽然计算较为精确，但成本较高，在实际情况下适用度不高；非概率模型所需样本相对较少，只需确定边界即可，虽然不确定性因素的详细信息很难获取或者根本无法知道，但是其不确定性的边界往往是很容易确定的[3]。人们对区间模型的理论和应用进行了广泛研究[4-8]。在求解区间模型的方法中，J Wu等[9]提出在不确定区间结构下基于区间算法和切比雪夫区间扩张函数的鲁棒拓扑优化方法；Jiang C等[10]基于区间序关系将不确定的目标函数和约束转化为确定性的模型，然后采用改进的带惩罚函数的遗传算法进行求解；姜潮[11]提出非线性区间数优化的数学转换模型即确定和不确定性之间的相互转换模型；符纯明[12]提出基于IDE模型不需转换直接求解不确定优化问题；邱志平和祁武超[13]提出结构非概率可靠性优化模型等。本文采用了符纯明[12]基于区间差分进化算法来解决非线性区间优化问题，该算法可直接求解无需转换，在方法上更为简便，计算效率较高，保真度较好。

1 区间不确定性优化

过去由于研究条件和手段的限制，通常把实际问题简化为理想化模型予以考虑，然而实际中存在大量的不确定因素。随着社会进步和科技发展，不确定性所带来的后果越来越受到人们的重视。无人机所处工作环境中的不确定因素非常显著，如果继续予以确定性问题来研究，难免会产生意想不到的后果，所以对无人机进行不确定分析很有必要。不确定性的度量通常有概率和非概率2种模型，概率模型所需样本多，虽在算法上有较强的数学依据，但是其抽样成本较高，适用度不适合少样本及成本高的场合。而非概率模型中的区间模型[14]只需要确定上下界，不需要具体的概率分布，具有成本低、适用度广等优点，越来越受到人们的青睐。

1.1 区间

根据区间数学[15]，区间数的定义是一组有序的实数：

AI=[AL,AR]=[x|AL

(1)

式中，I、L、R分别表示区间、区间下界和区间上界，当L=R时，区间为一实数。

区间也可以用中点和半径表示：

AI=〈AC,AW〉={x|AC-AW

(2)

式中，AC是中点；AW是半径。

(3)

(4)

普通的参数为固定值，参数用区间表示就不为某一实数，而是区间数，是一个服从更均匀分布的波动。

1.2 区间差分进化算法

大多数求解非线性区间优化的方法是将原始不确定性问题转换成确定性问题，求解过程复杂，计算量大，结果误差较大，求解问题仅限于最一般的不确定性问题，局限性较大。而直接法不需进行转换，在一般的计算资源中均可使用，为了避免将不确定性优化问题转化为确定性问题，本文采用符纯明的基于区间差分进化算法来解决非线性区间优化问题，其中区间概率模型用于确定不确定性优化问题的区间约束[12]，区间优先规则用于选择当前最优的解决方案以保留到下一个进化种群中。区间差分进化算法主要包括4个步骤，初始化、变异、交叉和选择策略。

1.2.1 初始化

(5)

式中，i=1,2,…,NP;j=1,2,…,N;randj(0,1)是一个在区间(0,1)上服从均匀分布的随机数。

1.2.2 变异策略

第g次迭代时，差分变异操作产生变异向量。常见的差分变异算子：

DE/rand/1/bin

Vi,k=Xr1,k+F(Xr2,k-Xr3,k)

(6)

DE/rand-to-best/1/bin

Vi,k=Xr1,k+F(Xbest,k-Xr1,k)+F(Xr2,k-Xr3,k)

(7)

DE/rand/2/bin

Vi,k=Xr1,k+F(Xr2,k-Xr3,k)+F(Xr4,k-Xr5,k)

(8)

DE/current-to-rand/1/bin

Vi,k=Xi,k+F(Xr1,k-Xi,k)+F(Xr2,k-Xr3,k)

(9)

式中，r1,r2,r3,r4,r5∈{1,2,…,NP}均为两两互不相同的整数，且与当前的目标向量索引i不同，因此要求种群规模NP≥4；F为缩放因子，是介于(0,1)的常数，用于控制差分向量的大小。F过小会降低收敛速度，但F也不能过大，否则种群将无法收敛。

1.2.3 交叉策略

在变异操作后，需要将目标向量Xi,k与变异向量Vi,k进行二项式交叉，生成最终的试验向量Ui,k=[ui,1,k,ui,2,k,…,ui,N,k]，按照以下公式执行交叉操作。

(10)

式中，jrand是从集合{1,2,…,N}内随机选取的一个整数，以保证变异向量Vi,k至少有一维信息被保留下来。交叉概率CR是(0,1)区间范围内的一个常数。

1.2.4 选择策略

传统选择策略对试验向量ui,k与目标向量Xi,k的目标函数值进行比较，若ui,k具有更优的目标函数，则将Xi,k替换为ui,k；否则，Xi,k保持不变。以目标最小化为例，选择操作可表示为：

(11)

而区间优先规则在原有选择策略的基础上引入区间概率模型，主要用于量化评估一个区间优于或劣于另一个区间。对于区间Al和Bl，区间概率：

(12)

则第j个不等式对应的区间概率：

(13)

2 无人机航迹规划建模

2.1 无人机航迹规划确定性模型

通常情况下，无人机航迹规划是指在任务区域D={(xi,yi,zi)|i∈(1,n)}内，在满足飞行约束和机动性能约束的前提下，计算获得一组最优路径规划点pi=(xi,yi,zi)，最终使整个规划代价最小，其优化问题可描述为：

(14)

飞行约束条件包括以下几点。

转向角约束：为了保证飞行轨迹平滑，在每一航路点的最大转向角[16]可表示：

(15)

式中，nmax为最大横向过载；g为重力加速度；V为飞行速度；则无人机转向角约束为：

φ1=max(μi-μmax)≤0

(16)

爬升/下降约束：路径点pi处的斜率si由最大爬升斜率βi和最小下降斜率γi约束[17]，可表示：

(17)

(18)

爬升和下降约束：

(19)

2.2 无人机航迹规划不确定性模型

在实际优化问题建模时，优化问题的目标函数和约束函数中往往含有不确定变量及参数，引入区间模型后，原问题的形式转化：

(20)

(21)

(22)

(23)

(24)

(25)

(26)

无人机航迹规划流程如图1所示。

图1 林用无人机航迹规划流程图

3 算例分析

无人机航迹规划的过程中，其环境信息往往是动态的、不确定的，在实际场景下已知的信息会发生一些变化，如产生运动障碍(飞鸟、空中散落的树枝)或者地图信息改变(植被生长更替)等，因此需要对动态环境进行算法验证。为了验证本文所述区间差分进化算法的有效性，对无人机森林航迹规划的3个地图的20组实验结果进行分析与讨论。设置任务区D=[0,1500]×[0,1500]×[0,2500]，m；算法初始参数配置为NP=200,kmax=500，F=0.8，CR=0.2，α=0.3；第2部分的具体飞行参数及不确定参数区间见表1。

表1 飞行参数及不确定区间

本文同时给出基于区间差分进化算法IDE的路径规划、传统的非区间优化算法(遗传算法[18]GA、差分进化算法DE)的路径规划以及IP-GA结果，如表2所示。相比传统的非区间优化算法(GA、DE)，区间差分进化算法生成的路径长度与代价值更小，对比GA，最优子路径缩短了约18.26%。与基于区间的非线性优化方法IP-GA相比，IDE在路径长度更长的地图中具备更大优势。通过对比GA、DE、IP-GA、IDE算法的收敛性，由图2可以看出，区间差分进化算法和IP-GA收敛性较强，但IDE算法运行时间至少比IP-GA算法快了10.39%。综合多次搜索路径结果来看，区间差分进化算法搜索结果更稳定，鲁棒性更强。综合比较表中数据，区间差分进化算法在不确定性空间下的全局路径规划能力表现出良好的性能。

表2 3个地图中不同算法的路径长度、代价值和运行时间的统计结果

图2 对比GA、DE、IP-GA、IDE算法的收敛曲线

4 结论

本文对考虑不确定性参数的非概率林用无人机航迹规划问题进行研究，通过描述不确定性参数对无人机航迹规划进行建模，采用一种基于区间差分进化算法的非线性不确定优化问题的分解分析方法，选择最优的解决方案来提高算法搜索效率。研究表明，采用区间差分进化算法的林用无人机航迹优化可直接处理存在于目标函数和约束中的区间不确定性，无需进行转化，适用度高，结果保真度较好；基于区间差分进化算法的林用无人机航迹规划能够有效考虑不确定参数对最优路径的影响，其优化效率较高；相比于GA、DE、IP-GA算法，基于区间差分进化算法拥有更好的鲁棒性，平均搜索路径更短，对比IP-GA求解效率提升约10.39%。