基于遗传算法的森林防火航空巡护路径规划

谢阳生,黄水生,李惺颖,唐小明

(中国林业科学研究院 资源信息研究所,北京 100091)

基于遗传算法的森林防火航空巡护路径规划

谢阳生,黄水生,李惺颖,唐小明

(中国林业科学研究院 资源信息研究所,北京 100091)

针对防火监测区地形地貌、 森林资源分布、 火灾发生规律以及执行巡护任务的飞机性能等影响因素,提出一种规划森林防火航空巡护路径的方法及流程,利用遗传算法实现路径规划最优解的求解. 对实验区的计算结果表明,该方法得到的最优路径与原路径相比,长度缩短了46.06%,且能实现对监测区域的全覆盖,从而减少巡护费用,提高巡护效率.

森林防火; 飞机巡护; 遗传算法; 航路规划

随着空、 天、 地一体化林火监测网络的逐步形成,遥感卫星、 航空飞机、 瞭望塔及地面巡护已经对森林火灾形成了立体监测[1]. 航空林火监测作为与卫星监测、 瞭望塔监测及地面巡护互相印证、 互为补充的一种林火监测方法,能较好地弥补卫星由于所处的高度和对热点性质分辨能力的限制,及地面监测范围小、 可达范围有限的缺点,主要用于地形复杂、 地面瞭望设施较差的地区开展巡护报警、 火场侦察及扑救工作.

航空巡护主要包括巡护飞行、 火场侦察、 扑救灭火和空投灭火物资等. 巡护飞行可使用有人机进行载人巡护飞行或使用无人机搭载传感器进行侦察飞行. 发生火灾时,飞机可空降灭火人员或空投灭火物资,同时也可进行吊桶洒水灭火、 机腹水箱洒水灭火等. 目前对飞机航路规划设计多见于军事领域[2-4],航路设计中多考虑地形、 威胁点和攻击目标等因素,而在森林火灾巡护上只有初步的探讨[5-6]. 本文根据林区地形、 地貌、 森林资源分布和火灾发生规律等林区情况制定高效的森林防火巡护飞行路线,以提高飞机巡护任务效率,并结合林区巡护的特点,将飞机巡护路径规划用于林火监测中.

1 影响飞机林火巡护路径规划的因素

飞机林火监测中巡护路线的规划与监测目标区域的地形地貌、 森林资源分布、 火灾发生规律和飞机性能等都紧密相关.

林区多为山区,地形复杂,地形的起伏会产生高度差的变化,同时形成对目标的遮蔽,使飞机上的机载巡护人员和设备出现探测盲区,导致林火目标被发现的概率减小； 同时机载传感器的摄像头或探头有机械转动的限制,地形的起伏也可能会使飞机和目标的高度差减小,从而减小了飞机侦察监视设备的作用距离； 同时为了确保飞行安全,山区中高山等障碍物,要求飞机尽量绕行,飞行高度一般高于地面绝对高度600 m以上. 森林资源分布是影响飞机林火监测巡护路线规划的另一个重要因素. 对于有林地、 灌木林地和未成林造林地集中的区域需要纳入日常巡护的路线； 对于重点林区,例如自然保护区、 稀有珍贵树种分布地及有特殊用途的森林植物群落等具有较高经济和社会价值的区域要列为重点巡护对象.

根据历年火灾发生的规律,包括野外用火和人员活动情况,对监测目标区域划分出重点火灾区； 或根据森林火险区划对区划等级较高的区域进行重点监测. 森林火险区划共分为3个等级,1级属于森林火险危险性大的区域,3级属于森林火险危险性小的区域.

对于人工巡护可达性较差的偏远林区及地面防火设施薄弱地区也应纳入飞机巡护的路线中进行重点监测. 此外,飞机性能也是确定航线的一个重要因素. 根据飞机的平均时速和续航时间,航线长度的确定要保证飞机到达终点后还有一定的油量储备.

2 飞机林火巡护路径规划流程和方法

飞机林火巡护路径的规划方法,对于常规飞机巡护路线是根据监测目标区域的相关资料及实地调查,确定飞机巡航的一些重要目标点,根据目标点制定出多条路径规划,从路径规划方案中选出与瞭望塔互相补充监测面积范围最大的较优方案,即得到飞机林火巡护路径. 流程如下：

1) 确定巡护目标区域,对监测目标林区的相关资料进行收集,包括地形地貌、 河流、 道路和居民点等基础地理资料,监测区域的森林资源分布资料,重点防火区域、 森林火险区划、 历年火灾发生地点和规律等森林防火相关资料及航飞相关设施资料,并对资料进行整理分析,确定地面调查的重点区域；

2) 组织专业人员对重点区域进行实地调查,进一步核实及获取巡护区域森林资源分布情况、 地理情况、 社会情况和防火设施情况等防火区域相关情况及资料,将实地踏查中获取的防火设施及可用于机降的位置等标识于地形图上；

3) 整理实地踏查结果,对相关资料进行补充；

4) 根据掌握的资料和实地踏查情况,确定航飞路线中的重要目标点；

5) 以飞机起降点为航飞路径的起点和终点,以重要目标点为途经点,制定航线；

6) 将航线绘制于地形图上.

酸奶营养丰富，具有维持肠道菌群生态平衡、降低血中胆固醇的含量、预防便秘、促进消化、缓解乳糖不耐症、提高人体对钙磷铁的吸收的功效[37]。淮山有健脾胃、补肺益肾、止泻利湿之功效，将淮山加入奶粉或牛奶，生产功能性酸奶，可以丰富酸奶品种，提高产品的营养保健功效。

对于火灾发生后的火情跟踪和扑救路线,则会根据火灾具体情况、 火灾发生周边的取水点、 防火扑救队伍分布和机降点等的分布进行临时调配,本文只讨论常规路线的算法.

3 飞机林火巡护路径规划算法

飞机侦察路径规划算法主要包括动态规划法[7]、 启发式搜索算法[8]、 遗传算法[2,9-11]和蚁群算法[3,12-13],在防火扑救中目前研究结果较少[14-15].

图1 遗传算法基本流程Fig.1 Basic flow of genetic algorithm

遗传算法(genetic algorithm,GA)是一种模拟生物环境中遗传和进化过程的随机化搜索优化方法. 该算法的基本流程如图1所示,先确定实际问题的参数集； 对参数集进行编码； 然后以随机生成的M个个体作为初始群体； 再对群体中的个体进行适应度评价； 对群体进行选择、 交叉、 变异运算得到下一代群体； 当迭代次数到达初始设置的最大进化代数时,将进化过程中所得到的最大适应度个体作为最优解输出. 遗传算法用生物进化的思想,采用编码技术和繁殖机制解决了复杂的搜索问题. 它的特点是从问题解的集合开始搜索,同时处理群体中的多个个体,不用搜索空间的知识或其他辅助信息,其适应度函数不受连续可微的约束,且适应度函数的定义域可任意设定,这些特点都是传统优化方法所不具有的,因此遗传算法适用于路径规划领域.

本文在目前航空任务路径规划研究成果的基础上,采用改进的遗传算法进行飞机林火巡护路径的规划,流程如下:

1) 路径规划问题提出. 假设已从飞机巡护区域的资料中获得n个目标点集合:

A中各点均为监测区域内的监测目标,且已去除瞭望塔覆盖面积内的目标. 另设aS为飞机出发地,aE为飞机的巡护终点,aS和aE有可能为同一点,也可以不同. 假设飞机一次的飞行航程为mmin,飞行速度为v,要求飞机在小于m的最短时间内从aS点出发经A或A中的一个子集到aE点降落,目标是经过的路径对监测目标区域的覆盖面积最大.

2) 解空间. 飞机林火巡护路径规划问题的解空间就是从aS点出发经A或A中的一个子集到aE点降落的所有组合路径,解空间S可表示为

S={ξ1,ξ2,…,ξS}.

（2）

图2 遗传算法染色体编码示意图Fig.2 Chromosome coding of genetic algorithm

3) 编码设计. 给A中每个监测目标以1～n的自然数编码,起点aS为0,终点aE为n+1,则一条染色体即是一条以0为起点,以n+1为终点,中间经过m(1≤m≤n)个监测目标点的飞行路径,即一个监测目标编码序列. 如有5个监测点分别是1,2,3,4,5, 则从0出发,到6降落的一条染色体编码为02456,如图2所示.

4) 种群初始化. 初始种群为从0～(n+1)中随机产生的u个随机序列. 根据飞机转弯半径r和总里程的限制,先将u中转弯半径小于r的路线去除,得到一个较合理的初始种群.

5) 适应度函数. 适应度函数是遗传算法进化的评价指标,飞机林火巡护路径规划为一个多目标问题,目标函数为路径总长度与飞行速度v和飞行时间m的乘积比值最小,且路径对监测目标区域的覆盖率最大. 覆盖率根据飞机的高度h、 航线计算可视域范围和监测目标点集合的交集和所有监测目标点集合的比值确定. 目标函数为

其中d为一条路径中从目标点n到n+1的路径长度. 采用权重方法将两个目标函数数值转化为单目标函数值作为适应度函数,公式为

其中w1和w2分别为两个目标函数的权重值,0≤w1,w2≤1,w1+w2=1,适应度函数值f最大的路径即为最优路径.

6) 选择算子. 根据适应度函数所计算的每条路径适应度值从大到小排序,将适应度函数值最大的染色体直接复制到下一代,然后用轮盘赌的方法产生下一代种群中剩余的染色体, 适应度函数值大的路径被选为下一代种群的几率更大.

7) 交叉算子. 将经过选择后的路径进行交叉操作,先在父代的基因位中确定几个基因位,然后随机选出两个父代个体进行基因交换,从而产生新的个体,如图3所示.

8) 变异算子. 变异算子是根据一定的变异概率对染色体中的基因进行突变,从而产生新的子染色体,如图4所示.

图3 染色体交叉算子示意图Fig.3 Crossover operator of chromosome

图4 染色体变异算子示意图Fig.4 Mutation operator of chromosome

9) 终止设计. 根据实现设定的迭代次数进行判断,若达到迭代次数,则计算停止,选出当前最优适应度函数值对应的染色体为最优解,即最优路径； 若未达到迭代次数,则进入下一个循环计算.

4 飞机林火巡护路径规划

本文根据以往飞行数据,采用本文飞机巡护路径算法的设计,对北京市重点防火区域的飞机林火巡护路径进行规划. 如图5所示,北京市域范围内的19块桔黄色区域为重点防火区域. 由图5可见,重点防火区域集中在西部和北部山区,路径规划的目标是覆盖19个目标区域,行程小于原来的飞行距离600 km.

图5 北京市重点防火区域Fig.5 Key fire prevention areas in Beijing

对每个监测区域多边形取内点,得到19个监测目标点. 由于北京地面瞭望塔资源非常丰富,同时飞机巡护的可视范围较大,所以在本文实例中飞机巡护作为与地面瞭望塔相互补充和印证的方法,不排除瞭望塔所能观察范围内的监测目标点. 监测目标确定后,还需确定飞机的起降点,如图6所示,森林防火飞机起降点共10个,也集中在北部和西部,选取平谷大溶洞机场为起点,房山燕山消防队为终点进行飞机林火巡护路径的规划. 图7给出了起点、 终点及重点防火区域点间的位置关系. 实例中飞机以匀速185 km/h飞行,总时长为4 h,即飞机的最大飞行里程为740 km,飞机飞行高度为3 km,可视半径为35 km,目标函数中的权重值w1=w2=0.5,参数列于表1.

图6 北京市森林防火飞机起降点Fig.6 Aircraft landing points of forest fire prevention in Beijing

图7 飞机起降点及监测目标的位置关系Fig.7 Spatial relationships between aircraft landing point and monitoring target

初始种群从解空间中随机选取200个个体,交叉概率取0.8,变异概率取0.06. 终止条件设为限制进化代数,进化代数设为300代. 进化到50代时,种群中的个体减少到121个,到100代时个体减少到73个,300代时剩下10个较优解,结果列于表2.

表1 飞机林火巡护路径规划参数Table 1 Parameters of airline planning of forest fire monitoring

表2 飞机林火巡护路径规划结果Table 2 Result of airline planning of forest fire monitoring

图8 飞机林火巡护路径规划结果Fig.8 Result of airline planning of forest fire monitoring

从10个较优解中选出适应值最大的一条为最优航线,如图8所示的路径. 该路径的编码为0→8→9→12→13→3→2→6→14→1→17→19→20,路径长度为323.608 km,对目标点的覆盖率为100%,其适应度函数值为0.824 3,与原路径相比,路径缩短了46.06%,且覆盖了9个区县的19个目标及周边区域,覆盖面积达12 564.67 km2.

综上所述,本文飞机林火巡护路径规划考虑了监测目标区域的地形地貌、 森林资源分布、 火灾发生规律和飞机性能等因素,利用遗传算法进行了路径最优解的求解. 求解的最佳路径与原路径相比,缩短了46.06%,且覆盖了9个区县的19个重点防火目标及周边区域.

[1]黄水生,唐小明,张煜星,等. 面向集成多监测平台的森林火灾监测信息系统设计 [J]. 林业资源管理,2009(5): 24-28. (HUANG Shuisheng,TANG Xiaoming,ZHANG Yuxing,et al. Multi-monitoring Platforms Integration Oriented Design on the Information System of Forest Fire Monitoring [J]. Forest Resources Management,2009(5): 24-28.)

[2]王英勋,陈宗基. 基于遗传算法(GA)的具有约束的飞行轨迹规划 [J]. 北京航空航天大学学报,1999,25(3): 355-358. (WANG Yingxun,CHEN Zongji. Genetic Algorithms (GA) Based Flight Path Planning with Constraints [J]. Journal of Beijing University of Aeronautics and Astronautics,1999,25(3): 355-358.)

[3]白俊强,柳长安. 基于蚁群算法的无人机航路规划 [J]. 飞行力学,2005,23(2): 35-38. (BAI Junqiang,LIU Changan. Path Planning Based on the Ant Algorithm for a Reconnaissance UAV [J]. Flight Dynamics,2005,23(2): 35-38.)

[4]鲁艺,周德云. 基于数学形态学的无人机航路规划方法研究 [J]. 弹箭与制导学报,2006,26(1): 677-680. (LU Yi,ZHOU Deyun. Study on Path Planning for UAV Based on Mathematical Morphology [J]. Journal of Projectiles,Rockets,Missiles and Guidance,2006,26(1): 677-680.)

[5]李开达. 对于航空护林航线的讨论 [J]. 科技促进发展,2011,4: 136. (LI Kaida. Discuss on Airline of Forest Protection [J]. Science & Technology for Development,2011,4: 136.)

[6]王留林,张滨. 浅谈对航空护林调度工作的几点认识 [J]. 森林防火,2010(1): 50-52. (WANG Liulin,ZHANG Bin. Opinions on Aviation Schedule of Forest Protection [J]. Forest Fire Prevention,2010(1): 50-52.)

[7]马向玲,叶文,范洪达. 低空突防航路规划算法仿真研究 [J]. 系统仿真学报,2004,16(3): 458-460. (MA Xiangling,YE Wen,FAN Hongda. Research of Computer Simulation on Route Planning of Low Altitude Penetration [J]. Journal of System Simulation,2004,16(3): 458-460.)

[8]史和生,张晓红,梁鹤,等. 基于战术数据链的多飞行器飞行航路协同规划 [J]. 中国电子科学研究院学报,2008,3(4): 415-420. (SHI Hesheng,ZHANG Xiaohong,LIANG He,et al. Coordinated Route Planning for Multiple Aircraft Based on Tactical Data Link [J]. Journal of CAEIT,2008,3(4): 415-420.)

[9]王校锋,司守奎,孙玺菁. 基于无人机航路规划的改进遗传算法研究 [C]//第25届中国控制会议论文集. [出版地不详]: IEEE Press,2006: 1431-1434. (WANG Xiaofeng,SI Shoukui,SUN Xijing. The Study of Improved Genetic Algorithm to Solve Flight Optimization Problem [C]//Proceedings of the 25th Chinese Control Conference. [S.l.]: IEEE Press,2006: 1431-1434.)

[10]左益宏,柳长安,罗昌行,等. 多无人机监控航路规划 [J]. 飞行力学,2004,22(3): 31-34. (ZUO Yihong,LIU Chang’an,LUO Changxing,et al. Path Planning for Surveillance of Multiple Unmanned Air Vehicles [J]. Flight Dynamics,2004,22(3): 31-34.)

[11]柳长安,王和平,李为吉. 无人机的侦察航路规划 [J]. 西北工业大学学报,2003,21(4): 490-494. (LIU Chang’an,WANG Heping,LI Weiji. On Path Planning for More Efficient Reconnaissance of UAV [J]. Journal of Northwestern Polytechnical University,2003,21(4): 490-494.)

[12]SU Fei,LI Yuan,PENG Hui,et al. Multi-UCAV Cooperative Path Planning Using Improved Coevolutionary Multi-ant-colony Algorithm [J]. Lecture Notes in Computer Science,2009,5754: 834-845.

[13]Lim K,Ong Y S,Lim M,et al. Hybrid Ant Colony Algorithms for Path Planning in Sparse Graphs [J]. Soft Computing: A Fusion of Foundations,Methodologies and Applications,2008,12(10): 981-994.

[14]刘丽峰,张树清,李新红. 人工免疫算法路径规划在林火救援中的应用 [J]. 吉林大学学报: 信息科学版,2012,30(4): 433-439. (LIU Lifeng,ZHANG Shuqing,LI Xinhong. Application of Artificial Immune Algorithm in Forest Fire Rescue Path Planning [J]. Journal of Jilin University: Information Science Edition,2012,30(4): 433-439.)

[15]刘元宁,王刚,朱晓冬,等. 基于自适应多种群遗传算法的特征选择 [J]. 吉林大学学报: 工学版,2011,41(6): 1690-1693. (LIU Yuanning,WANG Gang,ZHU Xiaodong,et al. Feature Selection Based on Adaptive Multi-population Genetic Algorithm [J]. Journal of Jilin University: Engineering and Technology Edition,2011,41(6): 1690-1693.)

(责任编辑： 韩 啸)

PlanningofAirbornePatrollingPathforForestFirePreventionBasedonGeneticAlgorithms

XIE Yangsheng,HUANG Shuisheng,LI Xingying,TANG Xiaoming
(ResearchInstituteofForestResourcesandInformationTechniques,
ChineseAcademyofForestry,Beijing100091,China)

A planning method based on genetic algorithms for forest fire airborne patrolling path was proposed after the factors,including landforms,distribution of forest resources,forest fire occurrence regulation,airborne platform’s performance,had been fully taken into account. The results of tested region show that the method can not only make the path shorter than the original path (46.06%) but also meet the requirements of covering the monitoring area.

forest fire prevention; airborne patrolling; genetic algorithm; path planning

2014-01-13.

谢阳生(1975—),女,汉族,博士,从事GIS开发与应用的研究,E-mail: xieys@caf.ac.cn. 通信作者： 黄水生(1974—),男,汉族,博士,从事GIS开发与应用的研究,E-mail: huangss@caf.ac.cn.

中央公益性科研院所基本科研业务费专项基金(批准号: IFRIT201102)和国家高技术研究发展计划863项目基金(批准号: 2012AA102001).

TP393

A

1671-5489(2014)05-1001-06