蚁群优化算法是模拟蚂蚁觅食的原理,设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路程上留下一种称之为信息素的物质(叶志伟,郑肇葆,2004),并在觅食过程中感知这种物质的强度,指导自己行动方向,它们总是朝着该物质强度高的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象(袁培燕等,2010)。同理,某一航拍区域被选中,区域上经过的蚂蚁越多,其信息素遗留也就越多,信息素的浓度也就越高,蚂蚁选择这一区域的几率也就越高,由此构成正反馈过程,从而逐渐逼近最优航拍区域。

在初始时刻,m只蚂蚁随机放置于地震极灾区中,各个极灾区中的航拍区域上的信息素初始值相等,设τ_ij(0)=τ₀为信息素初始值,其中:τ₀=m/L_m,L_m是由最近邻启发式方法构造的航拍价值量。蚂蚁k(k=1,2…m)按照随机比例规则选择下一步要访问的航拍区域,其选择概率公式为:

p^k_ij(t)={([τ_ij(t)]^α[η_ij(t)]^β)/(∑_S∈allowed[τ_is(t)]^α[η_ij(t)]^β), j∈allowed_k

0, 其它(1)

式中:τ_ij为区域(i,j)上的信息素; η_ij=1/d_ij为从区域i转移到区域j的启发式因子; allowed_k为蚂蚁k下一步被允许访问的航拍区域集合。

为了不让蚂蚁选择已经访问过的航拍区域,采用禁忌表tabu_k来记录蚂蚁k当前所选择的航拍区域。经过t时刻,所有蚂蚁都完成一次周游,计算每只蚂蚁所走过的航拍区域的总价值,保存最大航拍区域的总价值,同时,更新各边上的信息素。首先是信息素挥发,其次是蚂蚁在它们所经过的边上释放信息素(陈亮,张启义,2012),计算公式如下:

τ_ij=(1-ρ)τ_ij(2)

式中:ρ为τ信息素挥发系数,且0≤ρ≤1。

τ_ij=τ_ij+∑^m_k=1Δτ^k_ij(3)

式中:Δτ^k_ij是第k只蚂蚁向它经过的区域释放的信息素,可表示为:

Δτ^k_ij={1/d_ij, if(i, f)∈T^bs

0, 其它(4)

由式(4)可知,蚂蚁经过航拍区域的总价值量d_ij越大,则路径上各条边就会获得更多的信息素,在以后的迭代中就更有可能被其他蚂蚁选择。

蚂蚁完成一次循环后,清空禁忌表,重新对极灾区的所有航拍区域进行选择,准备下一次周游; 信息素的更新公式为(黄永青等,2006):

τ_ij(t+1)=(1-ρ)τ_ij(t)+∑^m_k=1Δτ^k_ij(t)+eΔτ^bs_ij(t)(5)

式中:Δτ^bs_ij(t)是第k只蚂蚁向它经过的区域释放的信息素,其的定义如下:

Δτ^bs_ij(t)={1/L^bs, if(i, f)∈T^bs

0, otherwise(6)

式中:L^bs为每次循环中被蚂蚁选中航拍区域的总价值量。允许更新的路径可以是全局最优解,或本次迭代的最优解。实践证明逐渐增加全局最优解的使用频率,会使该算法获得较好的性能。

我们设计了蚁群优化算法最优航拍区域选择流程图(图1),即:提取极灾区航拍信息并进行数据化表示,再对数据进行初始化,以蚂蚁的觅食原理对航拍数据求取最优方案。当蚂蚁选择最优航拍区域时,若总航拍时间T(j)大于无人机飞行限制时间T,蚂蚁则不再选取该区域,而对于限制时间T内的航拍区域,蚂蚁每次走过都会留下信息素。在船拍总时间小于T的情况下,其所选航拍

图1 蚁群优化算法最优航拍区域选择流程图
Fig.1 Flow chart of the region selection based on the ant colony optimization algorithm

无人机最优航拍区域选择需提取每个自然村的震中距(自然村距震中的直线距离)、房屋户数、人口数量与地形条件等影响因子。经过专家调查问卷,得出每个航拍因素的权重如表1所示; 其中地形条件采用层次分析法,根据海拔、断裂带、地质条件等因素综合考虑,分为6个等级,如表2所示。

表1 航拍区域参数权重比
Tab.1 The weight ratio of in aerial photography area

表2 地形条件评价参数
Tab.2 The evaluation parameters of terrain conditions

蚂蚁的数量越多,可使被选择的最有价值航拍区域的信息量越来越大,其不被选择的航拍区域的信息量越来越小,从而直到其信息量消失。所以理论上,蚂蚁数量越多越好,但会增加运算的时间,降低效率。蚂蚁最优航拍区域选择:对于很多的蚂蚁,都有n个选择方式,其可选区域增多,可以克服蚂蚁搜寻的局限性,使其可搜寻的航拍区域更多。蚂蚁c++编译中随机寻找路径(陈昊,2006)的方式为随机选择为:

double choose=[(double)rand()]/(TAND_MAX)(7)

为了使电脑硬件能够快速运行,蚂蚁数量(胡小兵,2004)应限制在3 000只范围内,蚂蚁的区域数量应限制在1 000个范围内; 程序所预设的值为随机数,所以采用循环10次求平均值的方法,以保证结果的准确性。

2016年5月21日云南省大理州云龙县发生5.0级地震,宏观震中位于云龙县多依树村一带,大理州洱源县部分乡镇遭受不同程度破坏。此次地震余震频繁,加之受震后降雨的影响,出现了滑坡、崩塌等次生地质灾害。214国道云龙县至震中多依树村一带落石,路基、路面严重损毁。通往大麦地村、长新乡(镇)、白石乡(镇)等40多条通村公路多处塌方,因受余震影响,通往震中多依树村公路多次交通中断,长新、白石等乡镇的乡村公路和桥梁也受到不同程度的破坏。云龙县境内山高坡陡,高山河谷落差较大,通往地震灾区的唯一生命线告急,此时,若能有无人机在灾情获取和道路侦察方面提供技术支持,将对应急救援提供很好的帮助。

此次航拍所采用的无人机为大疆悟 inspire 2。由于村镇人口密集,因此以云龙5.0级地震极灾区多依树村、长新乡、白石镇等30个自然村为单位开展无人机航拍。根据2016年云龙县5.0级地震灾害信息调查,得到每个航拍区房屋户数、人口数量、地形条件,如表4所示; 再计算出各自然村的震中距及无人机到达指定地点的飞行时间; 最后采用最优航拍区域选择方法得到被选中的航拍区域(表4中1表示选中,0表示未被选中)。

表4 云龙5.0级地震灾害信息
Tab.4 The seismic hazard information of the Yunlong M5.0 Earthquake

图3为震后极灾区无人机最优航拍区域选择结果,其中被选中航拍总价值量为760。由图3可以看出,航拍区域的优选很大程度上由震中距决定,因为震中距在影响航拍区域选取的因素达到总影响因素的40%; 而对于中和上村,震中距较远,但该区域的房屋户数和人口数量相对较多,轻微的震感也会导致很大的经济损失。所以中和上村也被选中为最优航拍区域。由于此次航拍备有5块无人机电池,总航拍时间为80 min,因此在有限的飞行时间内,能最快、最有效、第一时间获取地震灾情。

图3 云龙5.0级地震无人机最优航拍区域选择结果
Fig.3 The optimal result of aerial photography area in the Yunlong M5.0 Earthquake