李 斌,陳愛斌,周國雄*,周 濤
(1.中南林業(yè)科技大學計算機與信息工程學院,長沙410004; 2.湖南省林業(yè)廳森林消防航空護林站,長沙410007)(*通信作者電子郵箱51840157@qq.com)
當發(fā)生森林火災時,制定合理的滅火應急調(diào)度方案是管理森林火災、減少經(jīng)濟損失的重要內(nèi)容。由于林火行為很難進行定量分析和描述,在一些不均勻的離散時刻點上其狀態(tài)時常發(fā)生變換,具有不可預見性,且狀態(tài)變換的內(nèi)部機制比較復雜,無法用常規(guī)的數(shù)學方程進行描述,使得調(diào)度力量在全局控制與局部優(yōu)化平衡方面難以把控,是一種具有NP難特性的組合優(yōu)化問題。
文獻[1]為提高全局搜索能力,采用一種集成遺傳算法(Genetic Algorithm,GA)和粒子群優(yōu)化(Particle Swarm Optimization,PSO)的混合智能算法,建立了一種應急調(diào)度模型,提高了群體搜索性能,但針對大計算量問題,局部尋優(yōu)能力不足;文獻[2]針對資源調(diào)度過程中的局部尋優(yōu)問題進行改進,提出了一種多目標混合差分進化粒子群調(diào)度(Multiobjective Hybrid Differential-Evolution Particle-Swarm-Optimization,MHDP)算法,但是在多峰搜索調(diào)度中,容易陷入局部最小,從而丟失了種群的多樣性。此外,無論是PSO還是MHDP算法都忽視了資源之間的信息共享,對資源有效利用率的提升沒有顯著效果。文獻[3]將網(wǎng)格模型與調(diào)度算法結(jié)合,引入預測機制推斷網(wǎng)格任務大小情況,提出了基于標準差與二次分配網(wǎng)格的調(diào)度算法,從全局搜索調(diào)度角度,提高了計算能力。文獻[4]與文獻[5]是針對森林消防調(diào)度問題較為成熟的研究成果,但都僅限于從全局搜索調(diào)度考慮,忽視了局部細節(jié):文獻[4]提出了一種集成模擬與優(yōu)化控制火災的DEVS(Discrete Event System Specification)-FIRE方法,采用DEVS-FIRE計算火勢蔓延參數(shù)并結(jié)合火災消防管理行為,生成消防資源調(diào)度計劃;文獻[5]在文獻[4]研究基礎上,研究了直接攻擊、間接攻擊、平行攻擊三種森林滅火資源調(diào)度策略,結(jié)果表明:采用火前鋒直接攻擊調(diào)度戰(zhàn)術效果最佳,用時最短,其次為平行攻擊調(diào)度戰(zhàn)術,但無論哪種戰(zhàn)術,均沒有沒有將資源進行差異化動態(tài)按需配置,降低了資源利用效率。
狼群算法作為一種基于群智能的元啟發(fā)式優(yōu)化算法,可以抽象描述為3種智能行為(游走行為、召喚行為、圍攻行為)以及“勝者為王”的頭狼產(chǎn)生規(guī)則和“強者生存”的狼群更新機制(Wolves Strong Survival Update Mechanism,WSSUM),已被成功運用于各類調(diào)度優(yōu)化問題的求解。文獻[6]針對裝配車間作業(yè)調(diào)度組織順序問題,采用一種灰狼優(yōu)化(Grey Wolf Optimizer,GWO)新型算法,優(yōu)點是以最短時間找到最優(yōu)作業(yè)序列,拓展了狼群算法的應用,但此種方法并不能保證系統(tǒng)的穩(wěn)定性,可能導致無解;文獻[7]為解決焊接動態(tài)調(diào)度過程中產(chǎn)生的機器負載過大和不穩(wěn)定性等問題,提出一種混合多目標灰狼優(yōu)化器(Hybrid Multi-Objective Grey Wolf Optimizer,HMOGWO)調(diào)度模型,雖對系統(tǒng)調(diào)度加強了深度探索,但容易陷入局部最優(yōu);文獻[8]針對狼群算法存在的收斂速度慢、人工交互不理想的缺點,提出一種改進搜索策略的狼群算法,對圍攻行為進行了自適應改進,使算法具有自我調(diào)節(jié)作用,達到了理想效果。
本文在綜合考慮了火場的滅火過程及森林消防所要遵從一般原則后,采取一種基于Cell-DEVS模型[9]的WSSUM算法進行森林滅火資源調(diào)度研究,并在全局搜索與局部尋優(yōu)方面進行了優(yōu)化平衡處理,提出一種改進局部搜索策略狼群優(yōu)化算法(Wolf Optimization Algorithm,WOA),提高了滅火效率,增強了調(diào)度系統(tǒng)穩(wěn)定性。
Cell-DEVS 模型[9]是基于 DEVS 仿真系統(tǒng)[10-11]事件流程處理原理,為元胞建模提供了動態(tài)系統(tǒng)層次化與模塊化描述機制。DEVS利用抽象數(shù)學集合形式來表達離散事件仿真框架,其特點主要包括:1)發(fā)生事件的時間通常是不連續(xù)的;2)事件變化域與狀態(tài)空間均具有離散性;3)事件的發(fā)生具有突發(fā)性。按照系統(tǒng)的層次分為原子模型與耦合模型:原子模型是不可再拆分的最基本模型,它定義了被建模實體的自治行為,包括系統(tǒng)狀態(tài)轉(zhuǎn)變、外部輸入事件響應和系統(tǒng)輸出等;原子模型通過連接可以組成耦合模型,一個 DEVS耦合模型應包含外部事件輸入、輸出,組件集合,外部輸入、輸出與內(nèi)部耦合,以及對并發(fā)事件的處理方法。
DEVS原子模型表示如下:
其中:X表示輸入事件的集合;Y表示輸出事件的集合;S表示系統(tǒng)狀態(tài)集合。δint是內(nèi)部轉(zhuǎn)換函數(shù),δint:S→S';δext是外部轉(zhuǎn)換函數(shù),δext:Q × Xb→ S;Q={(s,e)|s∈ S,0 ≤ e≤ ta(s)}表示所有狀態(tài)集,Xb表示接收到的X集,e表示系統(tǒng)在狀態(tài)S停留的時間。ta:S→R+0→∞是時間推進函數(shù),如果ta(S)=+∞,表示S為靜止狀態(tài),無外部事件到達時,系統(tǒng)將一直停留在該狀態(tài);如果ta(S)=0,表示S為瞬時狀態(tài),仿真時鐘不推進;如果ta(S)=t,表示外部事件在系統(tǒng)保持的時間為t。λ是輸出函數(shù),λ:S→Yb是輸出函數(shù)。
DEVS耦合模型表示如下:
其中:X表示耦合模型外部輸入集合;Y表示耦合模型輸出集合;D表示所有耦合模型的組件引用集合;Mi表示一個耦合DEVS模型中的原子DEVS模型或者耦合模型,i∈D;EIC表示耦合模型的外部輸入與其內(nèi)部包含模型輸入的連接;EOC表示內(nèi)部包含模型的輸出與耦合模型的輸出的連接;IC表示耦合模型內(nèi)部的連接關系;Select表示選擇函數(shù)。
在Cell-DEVS模型中,每個元胞均有事件輸入和輸出端口,能夠及時地跟相鄰的元胞進行信息交換;同時,每個元胞又作為子系統(tǒng),可以被看作為具有內(nèi)部獨立結(jié)構和輸入輸出接口的模塊,若干個模塊通過連接組成耦合模型(如圖1)。在用Cell-DEVS模型進行事件調(diào)度時,設有一個時間控制成分,該成分從事件表中選擇活動確定性較強的事件,并將仿真鐘修改到該事件發(fā)生的時間,再調(diào)用與該事件相應的事件處理模塊,該事件處理完后返回時間控制成分,這樣,事件不斷地被選擇與處理,直到事件終止。
圖1 Cell-DEVS耦合模型Fig.1 Cell-DEVS coupling model
基于WSSUM的森林滅火資源調(diào)度作業(yè)是關于分布式“任務-平臺”關系設計問題與平臺資源調(diào)度多目標優(yōu)化問題,根據(jù)食物源“由強到弱”的原則進行分配,在算法中去除目標函數(shù)值最差的R匹人工狼(R>1且為整數(shù)),同時隨機產(chǎn)生R匹人工狼[12]。在確定資源調(diào)度分配機制過程中,根據(jù)任務的資源需求動態(tài)分配任務優(yōu)先級,并利用Cell-DEVS動態(tài)系統(tǒng)層次化和模塊化建模方式,將離散事件與時間以元胞為統(tǒng)一體進行分析研究,任務優(yōu)先級隨著時間發(fā)生變化,并結(jié)合元胞的局部作用規(guī)則進行狀態(tài)分析。假設火場蔓延狀態(tài)為均勻燃燒,WOA全局搜索調(diào)度的過程如下:
1)初始化。初始化狼群數(shù)目ω,人工狼位置Xi,步長因子δ,更新比例因子ρ,探狼比例為參數(shù),元胞長度為a。
2)根據(jù)獵物氣味濃度Y分為m個等級,選取不同位置若干峰值為最優(yōu)解并派出探狼i,除頭狼外,按照獵物分配規(guī)則,根據(jù)獵物氣味濃度所處等級層次分批派出人工狼j,直到Xj(a,b)=Xi(a,b),(a,b) 為元胞坐標值。
3)人工狼根據(jù)式(3)向獵物奔襲,若途中頭狼感知的獵物氣味濃度逐漸加大,則對其后的人工狼進行召喚,加大對獵物的追捕,并按照“強者恒強,強者生存”的更新機制,對頭狼及其人工狼進行位置及群體更新。
4)判斷頭狼是否完成對獵物的合圍。依據(jù)是頭狼所處元胞中心點之間的距離不大于:若達到該條件,即輸出頭狼的位置及迭代次數(shù)k;否則轉(zhuǎn)2)。
人工狼j在第k+1次迭代中,在d維變量空間中所處的位置為:
式中,gkd為第k代群體頭狼在第d維空間中的位置。式(3)由兩部分組成,前者為人工狼當前位置,體現(xiàn)狼的圍獵基礎;后者表示人工狼逐漸向頭狼位置聚集的趨勢,體現(xiàn)頭狼對狼群的指揮。
在WOA作業(yè)中,離散事件主要包括林火蔓延速度、蔓延方向等。林火蔓延速度決定了火情威脅程度,直接決定了狼群分配的權重,由于火線元胞蔓延速度不一,決定了狼群向食物源發(fā)起攻擊的方向不唯一。在系統(tǒng)中,離散時間則采用時間步長法,每推進一個時間步長,就遍歷一遍系統(tǒng)中的事件。為簡化所研究問題的復雜性,食物源由火險等級確定,火險等級根據(jù)林火蔓延速度確定,分為五個等級,火險等級與蔓延速度關系如表1所示。
表1 火險等級和蔓延速度關系Tab.1 Relationship between level of fire danger and spread rate
林火蔓延速度可根據(jù)Rothermel林火蔓延模型[13]計算得到。Rothermel林火蔓延模型是基于能量守恒定律的物理機理模型,從宏觀角度研究火焰前鋒的蔓延過程,不考慮過火火場的持續(xù)燃燒,類似“似穩(wěn)態(tài)”機理。由于風在每一個方向?qū)β铀俣鹊挠绊懚疾煌?,這使得火災蔓延的形狀近似于橢圓。利用Rothermel林火蔓延模型求出林火在一維方向上的傳播速度后,根據(jù)橢圓模型,將林火蔓延從一維轉(zhuǎn)換到二維空間求得各個方向的蔓延速度。假設火源點為橢圓的焦點,火速最大的火前鋒的蔓延方向為橢圓的長軸,則長短軸之比為:
式中:LB為橢圓長軸和短軸比,U為風速。
火焰前后鋒之比(HB):
根據(jù)式(4)、(5)可以求出橢圓的短半軸長a,長半軸長b和橢圓焦點到中心點的距離c,a、b、c可以理解為著火點在火翼、火頭、火尾3個方向的蔓延速度(如圖2所示)。通過以上步驟,可以實現(xiàn)將一維方向的林火蔓延速度分解成8個方向的蔓延速度,從而實現(xiàn)林火蔓延在Cell模型中從一維到二維的轉(zhuǎn)換。
圖2 火勢蔓延示意圖Fig.2 Schematic diagram of fire spread
根據(jù)式(4)和(5)計算可得:
Rothermel林火蔓延模型公式經(jīng)過幾次變換,其最終形式如下:
其中:VRothermel為蔓延速度(m·min-1);φs為坡度修正系數(shù);φw為風速修正系數(shù);IR為火焰反應強度(kJ·min-1·m-2); ρb為可燃物床層密度(kg·m-3);ξ為林火的蔓延率;ε為有效熱系數(shù);Qig為預燃熱,即點燃單位質(zhì)量可燃物所需的熱量(kJ·kg-1)。
在用Cell-DEVS描述調(diào)度作業(yè)時,須關注事件驅(qū)動模型各模塊的狀態(tài)轉(zhuǎn)移過程,為此采用面向?qū)ο竽P头治鲈O計中的UML(Unified Modeling Language)時序圖,通過狀態(tài)轉(zhuǎn)移進行過程描述。圖3顯示了Cell-DEVS調(diào)度作業(yè)UML時序圖。
圖3 Cell-DEVS調(diào)度作業(yè)UML圖Fig.3 UML diagram of Cell-DEVS resource scheduling
基于CELL-DEVS的WSSUM調(diào)度算法在完成全局搜索同時,保證了較好的魯棒性與全局收斂性能,有效避免了其他群體智能算法易早熟的缺陷;尤其是針對復雜函數(shù),諸如Cell-DEVS多維函數(shù)計算,尋優(yōu)效果較好。然而,Cell-DEVS基于離散時間與事件機制,每一個時間步長推進一次,由于每個元胞完成作業(yè)效率不同,在這個時間間隙,就可能存在某些資源閑置問題,為保證資源高效與充分利用,就必須對調(diào)度資源進行魯棒優(yōu)化配置,使得在Cell-DEVS系統(tǒng)中鄰近元胞之間資源交互更加合理。
在森林滅火資源WSSUM調(diào)度算法中,頭狼通過指揮讓更多人工狼隨著探狼向獵物運動,同時火線各方向調(diào)度并發(fā)執(zhí)行,并沒有產(chǎn)生鄰域之間的交互規(guī)則。為增強探狼間局部搜索能力,從而實現(xiàn)交互,首先需要進行鄰域搜索,采用一種類似人工蜂群[14-15]的搜索開采方式。在搜索過程中,隨著元胞狀態(tài)變化,探狼可放棄已知的食物源,向著獵物濃度較高的地方移動,并以距離最近為次要原則尋找最新食物源,并根據(jù)式(7)進行狼群的位置更新:
式中: φi,d為[0,1]內(nèi)的隨機數(shù),ηi,d為[- 1,1]內(nèi)的隨機數(shù),k≠i≠d。前半段增強了狼群的局部尋優(yōu)能力,后半段增強了狼群的全局搜索能力,保持了狼群之間信息的密切交流,從而實現(xiàn)人工狼之間交互。
當狼群在奔襲途中選擇鄰域食物源的時候,若鄰域元胞獵物濃度相同、距離相等時,就以隨機的形式選擇食物源使系統(tǒng)進行下去,其概率計算如式(8);其后,再根據(jù)式(7)進行狼群位置的更新。
其中,n是食物源個數(shù),只有2個鄰域可選擇,故n=2,fiti是第i個食物源的適應度;fiti按照式(9)計算:
式中vi是火勢蔓延速度。
本文提出的WOA融合于森林滅火資源調(diào)度Cell-DEVS耦合模型中,通過對調(diào)度系統(tǒng)原子模型進行改進,引入調(diào)節(jié)機制,實現(xiàn)了鄰域交互搜索優(yōu)化。森林滅火資源調(diào)度耦合模型由3個子模型耦合而成,除了考慮調(diào)度指揮模型外,還要考慮Rothermel林火蔓延模型與調(diào)度評估模型,調(diào)度指揮模型主要針對參與滅火的人力資源進行調(diào)度分析,包括3個Cell-DEVS原子模型:分析系統(tǒng)、調(diào)度系統(tǒng)與通信系統(tǒng),其主要職能包括制定人力部署方案、滅火進攻方案、各級力量任務分配等;Rothermel林火蔓延模型為調(diào)度指揮模型提供初步火情預想,包括林火蔓延方向、蔓延速度與火勢等級評估等;調(diào)度評估模型主要為滅火調(diào)度提供力量調(diào)集預估及事后的滅火效果評估。
綜上,森林滅火資源調(diào)度Cell-DEVS耦合模型可以表示為:
其中,X={(p,v)|p∈InPorts,v∈Xin},InPorts={“in”},Xin={“火情警報”,“人力調(diào)集”},Y={(p,v)|p ∈OutPorts,v∈Yout},OutPorts={“out”},Yout={“人力部署”,“任務分配”,“滅火進攻”};D={“調(diào)度指揮”,“Rothermel林 火 蔓 延”, “調(diào) 度 評 估 ”},M調(diào)度指揮= 調(diào) 度 指 揮;MRothermel林火蔓延=Rothermel林火蔓延;M調(diào)度評估= 調(diào)度評估;EIC={(“接收 /分析火情信息”,“in”),(“DEVS-Agent”,“in”)};EOC={(“DEVS-Agent”,“out”),(“接收 /分析火情信息”,“out”)};IC={(“調(diào)度指揮”,“in”),(“Rothermel林火蔓延”,“out”),(“Rothermel林火蔓延”,“in”),(“調(diào)度指揮”,“out”),(" 調(diào)度指揮",“in”),(“調(diào)度評估”,“out”),(“調(diào)度評估”,“in”),(“調(diào)度指揮”,“out”)}。
調(diào)度指揮模型中調(diào)度系統(tǒng)Cell-DEVS狀態(tài)轉(zhuǎn)移圖表示如圖4。
圖4 調(diào)度指揮模型中調(diào)度系統(tǒng)原子模型狀態(tài)轉(zhuǎn)移圖Fig.4 State transfer diagram of scheduling command model scheduling system atom model
調(diào)度系統(tǒng)原子模型表示如下:
其中: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。
以湖南省水口山林場某區(qū)域為研究對象,應用GIS(Geographic Information System)[16]處理軟件 ArcGIS 10.0,針對該區(qū)域等高線地形圖進行數(shù)據(jù)分析處理。該林場系武功山系的一條支脈,低山地貌,最高海拔867 m,最低海拔205 m,坡度在30°~40°,最大坡地達45°,中亞熱帶季風濕潤氣候,年平均氣溫17.8℃,年平均降水量1 500 mm,林地面積為3.6597萬畝(1 畝≈666.667 m2),非林業(yè)用地 0.012 9 萬畝,森林覆蓋率98.6%。在選擇的研究區(qū)域中,主要分布以下植被類型:杉木林、銀杏、樟樹、三尖杉、金錢松、枯枝落葉、茅草雜草、莎草矮樺、牧場草原等林地。
圖5與圖6分別展示了研究區(qū)等高線圖(原始數(shù)據(jù))和用arcgis制作的200×200元胞地形圖,利用等高線原始數(shù)據(jù),可以轉(zhuǎn)換生成坡度數(shù)據(jù)。由于Rothermel林火蔓延模型參數(shù)復雜,其中部分參數(shù)必須經(jīng)過長期的實驗才能取得,所以本研究對某些參數(shù)賦經(jīng)驗值,總體考慮情況如下:天氣濕潤,植物含水率較高,試驗林地連續(xù)一周無雨;地面風干程度為50%;其次,Rothermel林火蔓延模型中的其他因子 IR,ξ,ρb,ε,Qig,φw,φs等均可以通過實驗與計算大致確定,這些參數(shù)的精確程度??梢栽谀P偷臋z驗和評價中,加以適當?shù)恼{(diào)整和變更,此處不再贅述,具體參與計算的參數(shù)類型與取值如表2所示。
圖5 研究區(qū)域等高線圖Fig.5 Contour map of study region
圖6 研究區(qū)域地形圖 Fig.6 Topographic map of study region
表2 Rothermel林火蔓延模型輸入?yún)?shù)Tab.2 Rothermel model input parameter
利用計算機對森林滅火資源調(diào)度進行仿真模擬是實驗中最關鍵的一步,其主要過程為:第一、從背景數(shù)據(jù)庫中輸入可燃物載量、含水率、可燃物類型等靜態(tài)數(shù)據(jù)及風速等動態(tài)數(shù)據(jù);第二、根據(jù)輸入的靜態(tài)數(shù)據(jù)與動態(tài)數(shù)據(jù),利用Rothermel林火蔓延模型計算出林火的蔓延速度;第三、根據(jù)林火的蔓延速度,分別對WOA及平行攻擊兩種調(diào)度算法進行仿真計算;第四、將計算結(jié)果與仿真效果圖在仿真平臺上輸出。
在森林滅火資源調(diào)度仿真實驗中,須充分考慮計算機數(shù)據(jù)處理的速度,因此將該研究區(qū)的數(shù)據(jù)信息“儲存”在200×200個元胞中,每個元胞代表實際大小為10 m×10 m,仿真界面大小為600像素×600像素。仿真實驗具體假設如下:單兵滅火效率為常量λ;派出消防人數(shù)為常量ε;失火時刻為t0;開始滅火時刻為t1;火被撲滅時刻為t2;在時刻t森林燒毀面積為B(t0),且B(0)=0;開始滅火后火勢蔓延速度為R-λε(R→0),當R=0時,火開始被逐漸撲滅。由于消防人數(shù)為常量,在進行火場滅火過程中,火場鄰域元胞人員不斷實現(xiàn)交互。
為測試本文提出的森林滅火資源調(diào)度策略的性能,采用兩種實驗方案,方案一為WOA;方案二為平行攻擊調(diào)度算法。圖7是兩個實驗方案的效果。
圖7 兩個方案滅火分時效果Fig.7 Fire-fighting effects of different moments for two schemes
為定量描述與比較兩個實驗方案的效率,分別計算得到兩個實驗方案的實時火線周長與滅火面積,為方便統(tǒng)計分析,每20 min記錄一次,直到作業(yè)完成。
表3 實時滅火面積與火線周長數(shù)據(jù)Tab.3 Real-time fire-fighting area and firewire perimeter data
對表1數(shù)據(jù)進行分析對比:該實驗仿真以20 min為一個時間步長,對森林滅火資源的調(diào)度進行了定量分析。從圖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
本文建立了一個基于Cell-DEVS的森林滅火資源調(diào)度模型,并充分利用Cell-DEVS良好的分層遞階特性和離散事件驅(qū)動的動態(tài)仿真功能,針對各個階段的林火蔓延態(tài)勢,實現(xiàn)了森林滅火資源的動態(tài)優(yōu)化調(diào)度。實驗證明了Cell-DEVS模型實現(xiàn)了從事件驅(qū)動層到行為表示層的模型重用;其次,將改進后的WOA應用于該模型中,滅火性能得到顯著提升,從實驗數(shù)據(jù)曲線圖看出,由于整體滅火效率的提高,滅火時間得到了有效縮短,得到了理想效果。另外,本文提出Cell-DEVS森林滅火資源調(diào)度模型采用了規(guī)則元胞形式,在實驗、計算、評估應用中簡潔高效,但在某些林場中,無線傳感器部署位置可能并不規(guī)則,導致數(shù)據(jù)采集,林火模擬等不能完全采用格則元胞形式,因此,可以引入泰森多邊形(Voronoi Polygon)模型[17]或多元復合元胞模型[18],進行數(shù)據(jù)插值處理與實驗模擬。