基于多目標算法合理配置火災中的無人機組合

邱 雪，王永忠，趙 志，楊傳軍，李佳駿

(中國民用航空飛行學院，四川 廣漢 618307)

0 引言

隨著全球環境遭到嚴重破壞，火災頻發。現在火災已成為威脅我們生存的一個重要災害。低效率、高危險的滅火活動使得眾多消防員受到傷害，且造成大量的財產損失。為了提高效率和安全，使用無人機進行監視和態勢感知(SSA)已經好幾年了；SSA 無人機攜帶有高清和熱成像攝像機以及遙測傳感器，可用于監測和報告前線人員的個人定位信標或更復雜的情況。同時搭載中繼器的懸停無人機被用來大幅擴大前線低功率無線電的射程[3]。但是SSA無人機和中繼無人機的造價高昂，因此合理配置SSA無人機和中繼無人機的數量和組合至關重要。借助算法求解無人機配置模型是一項跨學科交叉研究，它對無人機規劃配置方面課題研究具有重要推動意義。因而，本文將引入多目標遺傳智能算法，探討多目標遺傳算法在無人機配置模型中求解精度與適應性，并分析配置結果，為火災無人機配置規劃提供參考。

首先提出了一種快速的非支配排序算法，以無人排序的方式降低了數據處理的復雜度，并將優化算法的復雜度從mN3降到mN2，加快了數據處理的過程。

采用精英策略擴展樣本空間[4]。通過連接親本和后代群體，可以通過競爭創造下一代群體，這使得在老年群體中保存的優秀基因增大，從而提高優化結果的準確性。并且保證最新種群中不會失去最好的個體，確保群體的基因水平正在迅速提高。這對于種群的發展是至關重要的。

NSGA算法中需要人為確定公共參數，存在一定的主觀性，為了增加參數的可靠性，同時加入種群個體間的比較基準，因此引入了擁擠度比較算法[5]。它可以克服以上缺點，在整個Pareto域中可以得到個體的均勻分布，體現種群的分布的多樣性與隨機性。

1 基于無人機組合規劃的多目標優化研究

多目標優化廣泛應用于現實生活中。每個目標都不可能同時達到最優，每個目標都必須有自己的權重。權重分配問題是本文的研究重點，采用全局可能性搜索遺傳算法，解決了傳統多目標優化算法中陷入局部最優解的缺陷，同時還能夠體現個體的多樣性[6]。使用基于遺傳算法的多目標優化策略探究 無人機組合分布問題，兼顧整體分布的同時，充分發揮無人機單元的個體優點。

目前求解Pareto邊界的算法主要有兩種，一種是基于數學的規劃算法，這種方法過于簡單，在解決實際問題過程中易出錯[7]。另一種是基于遺傳算法，它存在以上優點，被廣泛應用于各個領域。因此本文也重點研究了目前廣泛應用的NSGA-II算法。

NSGA-Ⅱ算法流程如圖1所示。

分析多目標，求解并優化算法是多目標遺傳算法的研究核心。重點分析相關目標函數之間的內在函數關系，結合權重分布，研究目標函數的最優趨勢，探究其解的最優集[8]。NSGA-II(非支配排序遺傳算法的精華)在遺傳算法中具有獨特的優勢。一般來說，它的出現使得多目標求解更加簡單、高效和明顯的優點，這就是為什么它是多目標優化問題的基本算法之一。這個算法的優點主要有以下幾點：

1)首先提出了一種快速的非支配排序算法，以無人排序的方式降低了數據處理的復雜度，并將優化算法的復雜度從mN3降到mN2，加快了數據處理的過程。

2)采用精英策略擴展樣本空間。通過連接親本和后代群體，可以通過競爭創造下一代群體，這使得在老年群體中保存的優秀基因增大，從而提高優化結果的準確性。并且保證最新種群中不會失去最好的個體，確保群體的基因水平正在迅速提高。這對于種群的發展是至關重要的。

3)為了克服NSGA算法里面必須人為確定公共參數的不足。另外種群個體間也需要一定的比較基準，使用擁擠度比較算法。它可以克服以上缺點，在整個Pareto域內可以得到個體的均勻分布，能夠體現種群個體的優勢，增加整體的多樣性[9]。

1.1 多目標優化問題基本定義

1)Pareto最優：在比較解的優劣時，單目標優化直接根據適應度值大小比較不同解的優劣，但是多目標優化中目標值不只一個，根據某一個目標值決定優劣關系是不合理的，常用的比較方法是非支配排序法[10]。

2)Pareto支配：圖2中給出一個雙目標最小化的例子，B和A比較時，B的兩個目標值都比A好，因此B肯定比A好，則稱B支配A；B和C比較時，B的第一個目標比C好，但是第二個目標比C差，此時無法判斷B和C哪個更好，則稱B和C是互不支配的關系。另外，支配解可能不只一個，打個比方(1 000，30)和(2 000，10)這兩個向量各有千秋，誰都無法全方面等于或者壓制對面，但是它們可以支配其他所有的向量，那么它倆就形成了一個支配解集。這個判斷方法知道就好，實際上不會采用這個方法來判斷兩個解的優劣，因為在目標大于2后，這個方法的效果是相當地差[11]。

圖2 Pareto支配

3)Pareto前沿： 在任意一個種群里面，肯定存在著一種不受其他個體支配的解決方案。帕累托前沿(PF)是指0在目標區域中所有解的映射，如圖2所示，直觀理解帕累托最優解的分布[12]。其中實心的點線性分布帕累托最優解。所有的最優解的映射通過目標函數投射在Pareto最優解集之內，最優解分布于解集的邊界，總體上趨于最優解的范圍。如圖3所示，當存在兩個目標問題時，Pareto最優邊界一般情況下是一條直線形狀，當存在多個目標的問題，Pareto最優邊界一般情況下是一個超曲面形狀[11]。

圖3 Pareto前沿

4)Pareto解集：帕累托解集就是帕累托前沿所有的Pareto前沿的解不受Pareto前沿以外的解(以及Pareto前沿曲線內的其他解)的支配[13]。因此，與給予決策者更好選擇的其他解決方案相比，這些非主導解決方案的目的沖突最小。同時這是必要的，至少削弱另一個目標函數，并在非優勢解的基礎上，削弱任何目標函數。例如，我們有兩個人A和B，他們都喜歡吃西瓜。現在有8個西瓜讓他們分，無論兩個人怎么分，帕累托都是最優的。因為要使得A利益更大的唯一方法就是讓B利益受損，即只能結合實際情況尋求較優的結果，沒有最佳方案。

1.2 多目標優化的數學描述

簡而言之，由多目標函數和一些相關的方程和不等式約束條件的組合就是多目標優化問題[14]。在多目標決策過程當中，通常由于要達到最好的效果有許多目標需要考慮，而有些目標之間又是相互矛盾的。這就導致多目標問題變得很復雜和困難。然而，多目標決策問題在生活中應用很廣泛，因此該方法得到大量研究。解決這一決策問題的方法很多，一般來說，最根本的方法就是將多目標問題的解轉化為單個目標問題的解[15]。由簡入繁，先解決單目標問題，對多個單目標模型進行求解最優，構成多目標問題的最優解，便可以得到唯一目標模型的最優解。從數學角度可以做如下描述，其中目標函數表達式為：

minF(x)=(z1,z2,…,zm)

(1)

s.t.x∈Ω

(2)

目標空間：m維向量F(x)所在的空間；

以下為支配的數學定義:

定義1：解決最小化問題，需要使得一個向量v=(v1,v2,…,vn)支配另一個向量u=(u1,u2,…,un),當且僅當ui≤vi,i=1,2,…,n時且?j∈{1,2…,n},uj

定義2：對于任意兩個自變量向量x1,x2,…,Ω，如果下列條件成立：

fi(x1)≤fi(x2),?i={1,2,…,n}

(3)

fj(x1)≤fj(x2),?j={1,2,…,n}

(4)

則稱x1支配x2。

定義3：帕累托最優解是指，一個集合中找不到一個可以支配x的解[16]。所以滿足此條件的x解的集合被定義為Pareto最優解集,在目標函數空間中，Pareto前言是指由帕累托最優解集所構成的像集。

minF(x)={f1(x),f2(x),…,fn(x)}T

(5)

s.t.gi(x)≤0,i=1,2,…,p

(6)

對于已知且確定的決策變量x={x1,x2,…,xn}T，能夠與n維歐氏變量空間Rn中的各個點形成對應的映射關系，經過決策優化后的目標函數f(x)能夠映射m維的歐式目標函數Rm空間中的各個點[17]。換句話說，由n維歐氏設計變量空間到m維的歐式目標函數空間的映射關系便是目標函數：

f:Rn→Rm

(7)

解決多目標優化問題的三個必要步驟是：確定決策變量，尋找目標函數，補充約束條件。決策變量x1,x2,…,xn在解決實際問題過程當中可以人為設定，而且還可以根據實際問題的需要設置多個變量，不同變量具有不同的意義。他們可以任意組合得出不同的結果。但一般情況下都是直接用向量x={x1,x2,…,xn}T表示，我們把它叫做多目標優化問題的一個解。

目標函數指的是一個問題我們需要達到效果的評價指標用一個數學表達式來表達，在實際問題里面,每個性能指標都能夠達到最優是決策的最佳狀態。但是由帕累托解集可以知道。不可能同時達到最好，只能盡量尋求最優。因此所有的目標函數f1(x),f2(x),…,fn(x)就一起構成了多目標優化問題的目標函數向量F(X)。

約束條件是目標函數存在的屬性要求，它要求決策變量需要滿足這些條件，通常使用等式或是不等式來表示[18]。我們的目標是尋求可行解的集合，整體優化的可行域便是包含了滿足約束條件的要求的最優可行解，由此我們需要全面考慮問題，尋求所有滿足條件的約束條件。

1.3 多目標優化問題的解

單目標問題里面只需要用很簡單并且常用的數學方法就可以得到最優解。但是，多目標優化問題中，單個目標之間的相互限制往往會使得一個目標得到改善但是其他目標損失較大，而犧牲其他目標的損失并且沒有解決方案來實現所有目標的最佳性能。組合所有多目標優化問題的解為一個集合，我們稱之為成Pareto解集，其中集合中所有的解為非劣解[19]。

如果有許多個帕累托最優解，并且沒有關于問題的進一步詳細信息，就很難選擇哪個解是最理想的。因此，所有的帕累托最優解都是同等重要的這就是為什么多目標優化最重要的任務是優化盡可能多的Pareto解。由于這個原因多目標優化就應該解決以下兩個任務：

1)找到一組盡可能接近Pareto最優域的解。

2)找到一組盡可能不同的解。

2 基于無人機組合規劃的多目標模型構建及求解

2.1 仿真模擬

仿真空間：假定森林區域為一個100 km×100 km的正方形區域。

仿真無人機：一個10 W的中繼器，重1.3 kg，由一架懸停在遠高于地面的無人機攜帶，可以達到 20 km的射程。其無人機高度大約可達到17 km，則令其仿真面積為一個半徑是10 km的圓；SSA無人機攜帶高清和熱成像攝像機以及遙測傳感器，可用于監測和報告前線人員的個人定位信標或更復雜的情況。一臺Akme公司的原型機 WileE-15.2X 混合動力無人機裝備一個5 W的無線電設備，射程可以達到4 km，高度大約2 km，仿真面積為一個以3.5 km為半徑的圓。具體輻射情況如圖1所示。無人機組合覆蓋區域的幾何模型如圖1所示，搭載天線的無人機可以向下進行360°的信號覆蓋，其覆蓋半徑記為R， SSA無人機的輻射半徑記為r[21]。SSA無人機的高度記為h，中繼無人機的高度記為H,中繼無人機和SSA無人機之間的距離為的d，則其有效覆蓋區域面積分別為：

S1=2πRH

(8)

S2=2πRh

(9)

此時天線輻射的最小波束寬度為:

(10)

(11)

(12)

(13)

根據以上公式分別畫出中繼無人機和SSA無人機的輻射范圍,如圖4所示。

圖4 無人機輻射范圍

在一個仿真空間范圍之內，根據火災發生的頻率和地形來布局無線電中繼無人機，SSA無人機在仿真空間內進行規定路徑游走，在覆蓋全局的條件下，根據中繼無人機的無線電發射射程20 km，在仿真空間內確定中繼無人機的數量；

SSA無人機在仿真空間內進行全覆蓋性的游走，保證能夠與中繼無人機保持實時的雙向通信，把收集到的地面監測、前線人員可穿戴設備的數據通過中繼無人機傳輸到應急行動中心，同時ECO能夠對SSA無人機進行遠距離監控。如圖5所示。

圖5 無人機空間布局圖

中繼無人機和SSA無人機的空間位置布局大致如圖，接下來利用多目標智能算法來確定一下無人機的數量配置。

2.2 智能算法確定無人機的數量組合

基于以上多目標規劃的原則，對于該森林火災中無人機配置問題，本文以經濟和效率2個子目標綜合優化配置無人機數量組合。我們假設某消防部門有一億美元用于購買無人機，某公司的混合動力無人機預計在配備無線電中繼器或視頻和遙測功能時成本約為 10 000美元，假設一臺SSA無人機的價格是300美元，一臺中繼無人機的價格是2 000美元。假設購買SSA無人機臺，購買中繼無人機臺。約束函數設計如表1所示。

表1 無人機數量組合約束函數

效率最大化用下式表達：

(14)

為了更加準確地檢測火災的發生，希望無人機能盡最大可能覆蓋全局。使得火情能被SSA無人機迅速檢測到并傳遞給應急行動中心，讓應急行動中心(EOC)以最佳方式指揮現役人員，以獲得最佳效果和最大安全。

經濟最大化用下式表達：

minz2=10000(x1+x2)+300x1+2000x2

(15)

為了能迅速檢測到火情，當然是無人機越多越好。但是無人機價格高昂，因此我們需要在有效的范圍內使用盡可能少的無人機，因此實現經濟效益也是目標函數之一。

根據上述模型建模得出如下結論，無人機覆蓋范圍越大，需要的無人機越多，花費的費用就越多。具體無人機覆蓋范圍與無人機花費的關系如圖6所示。

圖6 無人機覆蓋范圍和無人機費用之間的關系

圖6只是討論了無人機覆蓋范圍與無人機花費的關系，下面要具體討論一下SSA無人機和中繼無人機不同的數量組合對無人機花費的影響。如圖7可以看出，在100*100平方公里的正方形區域最多只需要32架中繼無人機，257架SSA無人機，花費大約320萬美元。根據該圖可以看到不同的組合所花費的金額。如配備32架中繼無人機，166架SSA無人機時大約花費230萬美元。

圖7 不同無人機組合所需的無人機費用

圖7討論了無人機數量組合對無人機花費的影響，下面要具體討論一下SSA無人機和中繼無人機不同的數量組合所形成的覆蓋面積。如圖8可以看出無人機的覆蓋范圍的趨勢和無人機花費金額的趨勢是類似的。即無人機越多，覆蓋面積越大，同時花費也越大。由圖可以看出在100*100平方公里的正方形區域內最多只需要32架中繼無人機，257架SSA無人機。并且根據該圖也可以看到不同的無人機組合所覆蓋的具體范圍。

圖8 不同無人機組合的覆蓋范圍

3 結束語

根據以上數據進行分析得出在仿真空間之內，依靠32架無線電中繼無人機和257架SSA無人機就可以實現對100*100平方公里的區域進行全局監控，但是這種組合花費巨大，需要花費大約350萬美元。因此，綜合考慮決定選取32架無線電中繼無人機和186架SSA無人機通過圖5的布局形式進行覆蓋，這種方案是最經濟有效的。

本文的創新性在于使用多目標規劃來創建的無人機配置模型，即考慮了效率又兼顧了經濟效益。利用遺傳算法對目標函數進行優化求解，其中把無人機的數量組合編碼作為決策變量，應用到算法中，可以直接對集合、序列、矩陣、樹、圖等結構對象進行操作。這樣的方式有助于模擬生物的基因、染色體和遺傳進化的過程，方便遺傳操作算子的運用。合理且準確地給出了無人機配置方案，為有關消防部門規劃提供了參考。并且針對不同的火災范圍，只需改變該模型中的一些參數即可得出不同的配置方案。同時該模型也適用于其他相關的多目標配置問題，如公司購置電腦，工廠配備產品等。但本文還存在進一步優化的可能性，可以結合不同的情況，多增加一些約束條件。比如火災的地形，無人機在不同地形的監視情況等。