基于Cell-DEVS 的森林灭火资源调度狼群优化算法

李 斌，陈爱斌，周国雄*，周 涛

(1．中南林业科技大学计算机与信息工程学院，长沙410004; 2．湖南省林业厅森林消防航空护林站，长沙410007)(*通信作者电子邮箱51840157@qq．com)

0 引言

当发生森林火灾时，制定合理的灭火应急调度方案是管理森林火灾、减少经济损失的重要内容。由于林火行为很难进行定量分析和描述，在一些不均匀的离散时刻点上其状态时常发生变换，具有不可预见性，且状态变换的内部机制比较复杂，无法用常规的数学方程进行描述，使得调度力量在全局控制与局部优化平衡方面难以把控，是一种具有NP难特性的组合优化问题。

文献［1］为提高全局搜索能力，采用一种集成遗传算法(Genetic Algorithm，GA)和粒子群优化(Particle Swarm Optimization，PSO)的混合智能算法，建立了一种应急调度模型，提高了群体搜索性能，但针对大计算量问题，局部寻优能力不足;文献［2］针对资源调度过程中的局部寻优问题进行改进，提出了一种多目标混合差分进化粒子群调度(Multiobjective Hybrid Differential-Evolution Particle-Swarm-Optimization，MHDP)算法，但是在多峰搜索调度中，容易陷入局部最小，从而丢失了种群的多样性。此外，无论是PSO还是MHDP算法都忽视了资源之间的信息共享，对资源有效利用率的提升没有显著效果。文献［3］将网格模型与调度算法结合，引入预测机制推断网格任务大小情况，提出了基于标准差与二次分配网格的调度算法，从全局搜索调度角度，提高了计算能力。文献［4］与文献［5］是针对森林消防调度问题较为成熟的研究成果，但都仅限于从全局搜索调度考虑，忽视了局部细节:文献［4］提出了一种集成模拟与优化控制火灾的DEVS(Discrete Event System Specification)-FIRE方法，采用DEVS-FIRE计算火势蔓延参数并结合火灾消防管理行为，生成消防资源调度计划;文献［5］在文献［4］研究基础上，研究了直接攻击、间接攻击、平行攻击三种森林灭火资源调度策略，结果表明:采用火前锋直接攻击调度战术效果最佳，用时最短，其次为平行攻击调度战术，但无论哪种战术，均没有没有将资源进行差异化动态按需配置，降低了资源利用效率。

狼群算法作为一种基于群智能的元启发式优化算法，可以抽象描述为3种智能行为(游走行为、召唤行为、围攻行为)以及“胜者为王”的头狼产生规则和“强者生存”的狼群更新机制(Wolves Strong Survival Update Mechanism，WSSUM)，已被成功运用于各类调度优化问题的求解。文献［6］针对装配车间作业调度组织顺序问题，采用一种灰狼优化(Grey Wolf Optimizer，GWO)新型算法，优点是以最短时间找到最优作业序列，拓展了狼群算法的应用，但此种方法并不能保证系统的稳定性，可能导致无解;文献［7］为解决焊接动态调度过程中产生的机器负载过大和不稳定性等问题，提出一种混合多目标灰狼优化器(Hybrid Multi-Objective Grey Wolf Optimizer，HMOGWO)调度模型，虽对系统调度加强了深度探索，但容易陷入局部最优;文献［8］针对狼群算法存在的收敛速度慢、人工交互不理想的缺点，提出一种改进搜索策略的狼群算法，对围攻行为进行了自适应改进，使算法具有自我调节作用，达到了理想效果。

本文在综合考虑了火场的灭火过程及森林消防所要遵从一般原则后，采取一种基于Cell-DEVS模型［9］的WSSUM算法进行森林灭火资源调度研究，并在全局搜索与局部寻优方面进行了优化平衡处理，提出一种改进局部搜索策略狼群优化算法(Wolf Optimization Algorithm，WOA)，提高了灭火效率，增强了调度系统稳定性。

1 Cell-DEVS模型

Cell-DEVS 模型［9］是基于 DEVS 仿真系统［10－11］事件流程处理原理，为元胞建模提供了动态系统层次化与模块化描述机制。DEVS利用抽象数学集合形式来表达离散事件仿真框架，其特点主要包括:1)发生事件的时间通常是不连续的;2)事件变化域与状态空间均具有离散性;3)事件的发生具有突发性。按照系统的层次分为原子模型与耦合模型:原子模型是不可再拆分的最基本模型，它定义了被建模实体的自治行为，包括系统状态转变、外部输入事件响应和系统输出等;原子模型通过连接可以组成耦合模型，一个 DEVS耦合模型应包含外部事件输入、输出，组件集合，外部输入、输出与内部耦合，以及对并发事件的处理方法。

DEVS原子模型表示如下:

其中:X表示输入事件的集合;Y表示输出事件的集合;S表示系统状态集合。δint是内部转换函数，δint:S→S';δext是外部转换函数，δext:Q × Xb→ S;Q={(s，e)|s∈ S，0 ≤ e≤ ta(s)}表示所有状态集，Xb表示接收到的X集，e表示系统在状态S停留的时间。ta:S→R+0→∞是时间推进函数，如果ta(S)=+∞，表示S为静止状态，无外部事件到达时，系统将一直停留在该状态;如果ta(S)=0，表示S为瞬时状态，仿真时钟不推进;如果ta(S)=t，表示外部事件在系统保持的时间为t。λ是输出函数，λ:S→Yb是输出函数。

DEVS耦合模型表示如下:

其中:X表示耦合模型外部输入集合;Y表示耦合模型输出集合;D表示所有耦合模型的组件引用集合;Mi表示一个耦合DEVS模型中的原子DEVS模型或者耦合模型，i∈D;EIC表示耦合模型的外部输入与其内部包含模型输入的连接;EOC表示内部包含模型的输出与耦合模型的输出的连接;IC表示耦合模型内部的连接关系;Select表示选择函数。

在Cell-DEVS模型中，每个元胞均有事件输入和输出端口，能够及时地跟相邻的元胞进行信息交换;同时，每个元胞又作为子系统，可以被看作为具有内部独立结构和输入输出接口的模块，若干个模块通过连接组成耦合模型(如图1)。在用Cell-DEVS模型进行事件调度时，设有一个时间控制成分，该成分从事件表中选择活动确定性较强的事件，并将仿真钟修改到该事件发生的时间，再调用与该事件相应的事件处理模块，该事件处理完后返回时间控制成分，这样，事件不断地被选择与处理，直到事件终止。

图1 Cell-DEVS耦合模型Fig．1 Cell-DEVS coupling model

2 基于Cell-DEVS的WSSUM调度算法

基于WSSUM的森林灭火资源调度作业是关于分布式“任务－平台”关系设计问题与平台资源调度多目标优化问题，根据食物源“由强到弱”的原则进行分配，在算法中去除目标函数值最差的R匹人工狼(R＞1且为整数)，同时随机产生R匹人工狼［12］。在确定资源调度分配机制过程中，根据任务的资源需求动态分配任务优先级，并利用Cell-DEVS动态系统层次化和模块化建模方式，将离散事件与时间以元胞为统一体进行分析研究，任务优先级随着时间发生变化，并结合元胞的局部作用规则进行状态分析。假设火场蔓延状态为均匀燃烧，WOA全局搜索调度的过程如下:

1)初始化。初始化狼群数目ω，人工狼位置Xi，步长因子δ，更新比例因子ρ，探狼比例为参数，元胞长度为a。

2)根据猎物气味浓度Y分为m个等级，选取不同位置若干峰值为最优解并派出探狼i，除头狼外，按照猎物分配规则，根据猎物气味浓度所处等级层次分批派出人工狼j，直到Xj(a，b)=Xi(a，b)，(a，b) 为元胞坐标值。

3)人工狼根据式(3)向猎物奔袭，若途中头狼感知的猎物气味浓度逐渐加大，则对其后的人工狼进行召唤，加大对猎物的追捕，并按照“强者恒强，强者生存”的更新机制，对头狼及其人工狼进行位置及群体更新。

4)判断头狼是否完成对猎物的合围。依据是头狼所处元胞中心点之间的距离不大于:若达到该条件，即输出头狼的位置及迭代次数k;否则转2)。

人工狼j在第k+1次迭代中，在d维变量空间中所处的位置为:

式中，gkd为第k代群体头狼在第d维空间中的位置。式(3)由两部分组成，前者为人工狼当前位置，体现狼的围猎基础;后者表示人工狼逐渐向头狼位置聚集的趋势，体现头狼对狼群的指挥。

在WOA作业中，离散事件主要包括林火蔓延速度、蔓延方向等。林火蔓延速度决定了火情威胁程度，直接决定了狼群分配的权重，由于火线元胞蔓延速度不一，决定了狼群向食物源发起攻击的方向不唯一。在系统中，离散时间则采用时间步长法，每推进一个时间步长，就遍历一遍系统中的事件。为简化所研究问题的复杂性，食物源由火险等级确定，火险等级根据林火蔓延速度确定，分为五个等级，火险等级与蔓延速度关系如表1所示。

表1 火险等级和蔓延速度关系Tab．1 Relationship between level of fire danger and spread rate

林火蔓延速度可根据Rothermel林火蔓延模型［13］计算得到。Rothermel林火蔓延模型是基于能量守恒定律的物理机理模型，从宏观角度研究火焰前锋的蔓延过程，不考虑过火火场的持续燃烧，类似“似稳态”机理。由于风在每一个方向对蔓延速度的影响都不同，这使得火灾蔓延的形状近似于椭圆。利用Rothermel林火蔓延模型求出林火在一维方向上的传播速度后，根据椭圆模型，将林火蔓延从一维转换到二维空间求得各个方向的蔓延速度。假设火源点为椭圆的焦点，火速最大的火前锋的蔓延方向为椭圆的长轴，则长短轴之比为:

式中:LB为椭圆长轴和短轴比，U为风速。

火焰前后锋之比(HB):

根据式(4)、(5)可以求出椭圆的短半轴长a，长半轴长b和椭圆焦点到中心点的距离c，a、b、c可以理解为着火点在火翼、火头、火尾3个方向的蔓延速度(如图2所示)。通过以上步骤，可以实现将一维方向的林火蔓延速度分解成8个方向的蔓延速度，从而实现林火蔓延在Cell模型中从一维到二维的转换。

图2 火势蔓延示意图Fig．2 Schematic diagram of fire spread

根据式(4)和(5)计算可得:

Rothermel林火蔓延模型公式经过几次变换，其最终形式如下:

其中:VRothermel为蔓延速度(m·min－1);φs为坡度修正系数;φw为风速修正系数;IR为火焰反应强度(kJ·min－1·m－2); ρb为可燃物床层密度(kg·m－3);ξ为林火的蔓延率;ε为有效热系数;Qig为预燃热，即点燃单位质量可燃物所需的热量(kJ·kg－1)。

在用Cell-DEVS描述调度作业时，须关注事件驱动模型各模块的状态转移过程，为此采用面向对象模型分析设计中的UML(Unified Modeling Language)时序图，通过状态转移进行过程描述。图3显示了Cell-DEVS调度作业UML时序图。

图3 Cell-DEVS调度作业UML图Fig．3 UML diagram of Cell-DEVS resource scheduling

3 基于Cell-DEVS的WOA调度算法

基于CELL-DEVS的WSSUM调度算法在完成全局搜索同时，保证了较好的鲁棒性与全局收敛性能，有效避免了其他群体智能算法易早熟的缺陷;尤其是针对复杂函数，诸如Cell-DEVS多维函数计算，寻优效果较好。然而，Cell-DEVS基于离散时间与事件机制，每一个时间步长推进一次，由于每个元胞完成作业效率不同，在这个时间间隙，就可能存在某些资源闲置问题，为保证资源高效与充分利用，就必须对调度资源进行鲁棒优化配置，使得在Cell-DEVS系统中邻近元胞之间资源交互更加合理。

在森林灭火资源WSSUM调度算法中，头狼通过指挥让更多人工狼随着探狼向猎物运动，同时火线各方向调度并发执行，并没有产生邻域之间的交互规则。为增强探狼间局部搜索能力，从而实现交互，首先需要进行邻域搜索，采用一种类似人工蜂群［14－15］的搜索开采方式。在搜索过程中，随着元胞状态变化，探狼可放弃已知的食物源，向着猎物浓度较高的地方移动，并以距离最近为次要原则寻找最新食物源，并根据式(7)进行狼群的位置更新:

式中: φi，d为［0，1］内的随机数，ηi，d为［－ 1，1］内的随机数，k≠i≠d。前半段增强了狼群的局部寻优能力，后半段增强了狼群的全局搜索能力，保持了狼群之间信息的密切交流，从而实现人工狼之间交互。

当狼群在奔袭途中选择邻域食物源的时候，若邻域元胞猎物浓度相同、距离相等时，就以随机的形式选择食物源使系统进行下去，其概率计算如式(8);其后，再根据式(7)进行狼群位置的更新。

其中，n是食物源个数，只有2个邻域可选择，故n=2，fiti是第i个食物源的适应度;fiti按照式(9)计算:

式中vi是火势蔓延速度。

本文提出的WOA融合于森林灭火资源调度Cell-DEVS耦合模型中，通过对调度系统原子模型进行改进，引入调节机制，实现了邻域交互搜索优化。森林灭火资源调度耦合模型由3个子模型耦合而成，除了考虑调度指挥模型外，还要考虑Rothermel林火蔓延模型与调度评估模型，调度指挥模型主要针对参与灭火的人力资源进行调度分析，包括3个Cell-DEVS原子模型:分析系统、调度系统与通信系统，其主要职能包括制定人力部署方案、灭火进攻方案、各级力量任务分配等;Rothermel林火蔓延模型为调度指挥模型提供初步火情预想，包括林火蔓延方向、蔓延速度与火势等级评估等;调度评估模型主要为灭火调度提供力量调集预估及事后的灭火效果评估。

综上，森林灭火资源调度Cell-DEVS耦合模型可以表示为:

其中，X={(p，v)|p∈InPorts，v∈Xin}，InPorts={“in”}，Xin={“火情警报”，“人力调集”}，Y={(p，v)|p ∈OutPorts，v∈Yout}，OutPorts={“out”}，Yout={“人力部署”，“任务分配”，“灭火进攻”};D={“调度指挥”，“Rothermel林 火 蔓 延”， “调 度 评 估 ”}，M调度指挥= 调 度 指 挥;MRothermel林火蔓延=Rothermel林火蔓延;M调度评估= 调度评估;EIC={(“接收 /分析火情信息”，“in”)，(“DEVS-Agent”，“in”)};EOC={(“DEVS-Agent”，“out”)，(“接收 /分析火情信息”，“out”)};IC={(“调度指挥”，“in”)，(“Rothermel林火蔓延”，“out”)，(“Rothermel林火蔓延”，“in”)，(“调度指挥”，“out”)，(" 调度指挥"，“in”)，(“调度评估”，“out”)，(“调度评估”，“in”)，(“调度指挥”，“out”)}。

调度指挥模型中调度系统Cell-DEVS状态转移图表示如图4。

图4 调度指挥模型中调度系统原子模型状态转移图Fig．4 State transfer diagram of scheduling command model scheduling system atom model

调度系统原子模型表示如下:

其中:X={report，analyze，organize，fighting};Y={orders，feedback};S = {S_actuality，S_command，S_est-power，S_all-task，S_action};ta(S_actuality)=+ ∞，ta(S_command)=t，ta(S_est-power)=0，ta(S_all-task)=0，ta(S_action)=t;int:S_actuality → S_command，S_command → S_est-power，S_est-power→S_all-task，S_command → S_all-task;ext:S_all-task×fighting → S_action，S_action × feedback →S_command，λ:S_command→ orders;S_action→ feedback。

4 仿真实验

以湖南省水口山林场某区域为研究对象，应用GIS(Geographic Information System)［16］处理软件 ArcGIS 10．0，针对该区域等高线地形图进行数据分析处理。该林场系武功山系的一条支脉，低山地貌，最高海拔867 m，最低海拔205 m，坡度在30°～40°，最大坡地达45°，中亚热带季风湿润气候，年平均气温17．8℃，年平均降水量1 500 mm，林地面积为3．6597万亩(1 亩≈666．667 m2)，非林业用地 0．012 9 万亩，森林覆盖率98．6%。在选择的研究区域中，主要分布以下植被类型:杉木林、银杏、樟树、三尖杉、金钱松、枯枝落叶、茅草杂草、莎草矮桦、牧场草原等林地。

图5与图6分别展示了研究区等高线图(原始数据)和用arcgis制作的200×200元胞地形图，利用等高线原始数据，可以转换生成坡度数据。由于Rothermel林火蔓延模型参数复杂，其中部分参数必须经过长期的实验才能取得，所以本研究对某些参数赋经验值，总体考虑情况如下:天气湿润，植物含水率较高，试验林地连续一周无雨;地面风干程度为50%;其次，Rothermel林火蔓延模型中的其他因子 IR，ξ，ρb，ε，Qig，φw，φs等均可以通过实验与计算大致确定，这些参数的精确程度常可以在模型的检验和评价中，加以适当的调整和变更，此处不再赘述，具体参与计算的参数类型与取值如表2所示。

图5 研究区域等高线图Fig．5 Contour map of study region

图6 研究区域地形图 Fig．6 Topographic map of study region

表2 Rothermel林火蔓延模型输入参数Tab．2 Rothermel model input parameter

利用计算机对森林灭火资源调度进行仿真模拟是实验中最关键的一步，其主要过程为:第一、从背景数据库中输入可燃物载量、含水率、可燃物类型等静态数据及风速等动态数据;第二、根据输入的静态数据与动态数据，利用Rothermel林火蔓延模型计算出林火的蔓延速度;第三、根据林火的蔓延速度，分别对WOA及平行攻击两种调度算法进行仿真计算;第四、将计算结果与仿真效果图在仿真平台上输出。

在森林灭火资源调度仿真实验中，须充分考虑计算机数据处理的速度，因此将该研究区的数据信息“储存”在200×200个元胞中，每个元胞代表实际大小为10 m×10 m，仿真界面大小为600像素×600像素。仿真实验具体假设如下:单兵灭火效率为常量λ;派出消防人数为常量ε;失火时刻为t0;开始灭火时刻为t1;火被扑灭时刻为t2;在时刻t森林烧毁面积为B(t0)，且B(0)=0;开始灭火后火势蔓延速度为R－λε(R→0)，当R=0时，火开始被逐渐扑灭。由于消防人数为常量，在进行火场灭火过程中，火场邻域元胞人员不断实现交互。

为测试本文提出的森林灭火资源调度策略的性能，采用两种实验方案，方案一为WOA;方案二为平行攻击调度算法。图7是两个实验方案的效果。

图7 两个方案灭火分时效果Fig．7 Fire-fighting effects of different moments for two schemes

为定量描述与比较两个实验方案的效率，分别计算得到两个实验方案的实时火线周长与灭火面积，为方便统计分析，每20 min记录一次，直到作业完成。

表3 实时灭火面积与火线周长数据Tab．3 Real-time fire-fighting area and firewire perimeter data

对表1数据进行分析对比:该实验仿真以20 min为一个时间步长，对森林灭火资源的调度进行了定量分析。从图8与图9的曲线斜率上看，无论是从实时火线周长还是实时灭火面积的角度进行分析，从时间t1到时间t2，方案一比方案二灭火时间更短，缩短了10．1%。其次，从曲线收敛程度可以看出，本文提出的改进算法WOA较WSSUM算法收敛速度更快，在整个过程中的中间时段，收敛速度达到最快。

图9 两个方案火线实时周长对比Fig．9 Comparison of real-time firewire perimeter for two schemes

图10 两个方案灭火实时面积对比Fig．10 Comparison of real-time fire-fighting area for two schemes

5 结语

本文建立了一个基于Cell-DEVS的森林灭火资源调度模型，并充分利用Cell-DEVS良好的分层递阶特性和离散事件驱动的动态仿真功能，针对各个阶段的林火蔓延态势，实现了森林灭火资源的动态优化调度。实验证明了Cell-DEVS模型实现了从事件驱动层到行为表示层的模型重用;其次，将改进后的WOA应用于该模型中，灭火性能得到显著提升，从实验数据曲线图看出，由于整体灭火效率的提高，灭火时间得到了有效缩短，得到了理想效果。另外，本文提出Cell-DEVS森林灭火资源调度模型采用了规则元胞形式，在实验、计算、评估应用中简洁高效，但在某些林场中，无线传感器部署位置可能并不规则，导致数据采集，林火模拟等不能完全采用格则元胞形式，因此，可以引入泰森多边形(Voronoi Polygon)模型［17］或多元复合元胞模型［18］，进行数据插值处理与实验模拟。