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

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

0 引言

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

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

采用精英策略擴(kuò)展樣本空間[4]。通過連接親本和后代群體，可以通過競(jìng)爭(zhēng)創(chuàng)造下一代群體，這使得在老年群體中保存的優(yōu)秀基因增大，從而提高優(yōu)化結(jié)果的準(zhǔn)確性。并且保證最新種群中不會(huì)失去最好的個(gè)體，確保群體的基因水平正在迅速提高。這對(duì)于種群的發(fā)展是至關(guān)重要的。

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

1 基于無人機(jī)組合規(guī)劃的多目標(biāo)優(yōu)化研究

多目標(biāo)優(yōu)化廣泛應(yīng)用于現(xiàn)實(shí)生活中。每個(gè)目標(biāo)都不可能同時(shí)達(dá)到最優(yōu)，每個(gè)目標(biāo)都必須有自己的權(quán)重。權(quán)重分配問題是本文的研究重點(diǎn)，采用全局可能性搜索遺傳算法，解決了傳統(tǒng)多目標(biāo)優(yōu)化算法中陷入局部最優(yōu)解的缺陷，同時(shí)還能夠體現(xiàn)個(gè)體的多樣性[6]。使用基于遺傳算法的多目標(biāo)優(yōu)化策略探究 無人機(jī)組合分布問題，兼顧整體分布的同時(shí)，充分發(fā)揮無人機(jī)單元的個(gè)體優(yōu)點(diǎn)。

目前求解Pareto邊界的算法主要有兩種，一種是基于數(shù)學(xué)的規(guī)劃算法，這種方法過于簡(jiǎn)單，在解決實(shí)際問題過程中易出錯(cuò)[7]。另一種是基于遺傳算法，它存在以上優(yōu)點(diǎn)，被廣泛應(yīng)用于各個(gè)領(lǐng)域。因此本文也重點(diǎn)研究了目前廣泛應(yīng)用的NSGA-II算法。

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

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

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

2)采用精英策略擴(kuò)展樣本空間。通過連接親本和后代群體，可以通過競(jìng)爭(zhēng)創(chuàng)造下一代群體，這使得在老年群體中保存的優(yōu)秀基因增大，從而提高優(yōu)化結(jié)果的準(zhǔn)確性。并且保證最新種群中不會(huì)失去最好的個(gè)體，確保群體的基因水平正在迅速提高。這對(duì)于種群的發(fā)展是至關(guān)重要的。

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

1.1 多目標(biāo)優(yōu)化問題基本定義

1)Pareto最優(yōu)：在比較解的優(yōu)劣時(shí)，單目標(biāo)優(yōu)化直接根據(jù)適應(yīng)度值大小比較不同解的優(yōu)劣，但是多目標(biāo)優(yōu)化中目標(biāo)值不只一個(gè)，根據(jù)某一個(gè)目標(biāo)值決定優(yōu)劣關(guān)系是不合理的，常用的比較方法是非支配排序法[10]。

2)Pareto支配：圖2中給出一個(gè)雙目標(biāo)最小化的例子，B和A比較時(shí)，B的兩個(gè)目標(biāo)值都比A好，因此B肯定比A好，則稱B支配A；B和C比較時(shí)，B的第一個(gè)目標(biāo)比C好，但是第二個(gè)目標(biāo)比C差，此時(shí)無法判斷B和C哪個(gè)更好，則稱B和C是互不支配的關(guān)系。另外，支配解可能不只一個(gè)，打個(gè)比方(1 000，30)和(2 000，10)這兩個(gè)向量各有千秋，誰(shuí)都無法全方面等于或者壓制對(duì)面，但是它們可以支配其他所有的向量，那么它倆就形成了一個(gè)支配解集。這個(gè)判斷方法知道就好，實(shí)際上不會(huì)采用這個(gè)方法來判斷兩個(gè)解的優(yōu)劣，因?yàn)樵谀繕?biāo)大于2后，這個(gè)方法的效果是相當(dāng)?shù)夭頪11]。

圖2 Pareto支配

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

圖3 Pareto前沿

4)Pareto解集：帕累托解集就是帕累托前沿所有的Pareto前沿的解不受Pareto前沿以外的解(以及Pareto前沿曲線內(nèi)的其他解)的支配[13]。因此，與給予決策者更好選擇的其他解決方案相比，這些非主導(dǎo)解決方案的目的沖突最小。同時(shí)這是必要的，至少削弱另一個(gè)目標(biāo)函數(shù)，并在非優(yōu)勢(shì)解的基礎(chǔ)上，削弱任何目標(biāo)函數(shù)。例如，我們有兩個(gè)人A和B，他們都喜歡吃西瓜?，F(xiàn)在有8個(gè)西瓜讓他們分，無論兩個(gè)人怎么分，帕累托都是最優(yōu)的。因?yàn)橐沟肁利益更大的唯一方法就是讓B利益受損，即只能結(jié)合實(shí)際情況尋求較優(yōu)的結(jié)果，沒有最佳方案。

1.2 多目標(biāo)優(yōu)化的數(shù)學(xué)描述

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

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

(1)

s.t.x∈Ω

(2)

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

以下為支配的數(shù)學(xué)定義:

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

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

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

(3)

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

(4)

則稱x1支配x2。

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

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

(5)

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

(6)

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

f:Rn→Rm

(7)

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

目標(biāo)函數(shù)指的是一個(gè)問題我們需要達(dá)到效果的評(píng)價(jià)指標(biāo)用一個(gè)數(shù)學(xué)表達(dá)式來表達(dá)，在實(shí)際問題里面,每個(gè)性能指標(biāo)都能夠達(dá)到最優(yōu)是決策的最佳狀態(tài)。但是由帕累托解集可以知道。不可能同時(shí)達(dá)到最好，只能盡量尋求最優(yōu)。因此所有的目標(biāo)函數(shù)f1(x),f2(x),…,fn(x)就一起構(gòu)成了多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù)向量F(X)。

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

1.3 多目標(biāo)優(yōu)化問題的解

單目標(biāo)問題里面只需要用很簡(jiǎn)單并且常用的數(shù)學(xué)方法就可以得到最優(yōu)解。但是，多目標(biāo)優(yōu)化問題中，單個(gè)目標(biāo)之間的相互限制往往會(huì)使得一個(gè)目標(biāo)得到改善但是其他目標(biāo)損失較大，而犧牲其他目標(biāo)的損失并且沒有解決方案來實(shí)現(xiàn)所有目標(biāo)的最佳性能。組合所有多目標(biāo)優(yōu)化問題的解為一個(gè)集合，我們稱之為成Pareto解集，其中集合中所有的解為非劣解[19]。

如果有許多個(gè)帕累托最優(yōu)解，并且沒有關(guān)于問題的進(jìn)一步詳細(xì)信息，就很難選擇哪個(gè)解是最理想的。因此，所有的帕累托最優(yōu)解都是同等重要的這就是為什么多目標(biāo)優(yōu)化最重要的任務(wù)是優(yōu)化盡可能多的Pareto解。由于這個(gè)原因多目標(biāo)優(yōu)化就應(yīng)該解決以下兩個(gè)任務(wù)：

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

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

2 基于無人機(jī)組合規(guī)劃的多目標(biāo)模型構(gòu)建及求解

2.1 仿真模擬

仿真空間：假定森林區(qū)域?yàn)橐粋€(gè)100 km×100 km的正方形區(qū)域。

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

S1=2πRH

(8)

S2=2πRh

(9)

此時(shí)天線輻射的最小波束寬度為:

(10)

(11)

(12)

(13)

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

圖4 無人機(jī)輻射范圍

在一個(gè)仿真空間范圍之內(nèi)，根據(jù)火災(zāi)發(fā)生的頻率和地形來布局無線電中繼無人機(jī)，SSA無人機(jī)在仿真空間內(nèi)進(jìn)行規(guī)定路徑游走，在覆蓋全局的條件下，根據(jù)中繼無人機(jī)的無線電發(fā)射射程20 km，在仿真空間內(nèi)確定中繼無人機(jī)的數(shù)量；

SSA無人機(jī)在仿真空間內(nèi)進(jìn)行全覆蓋性的游走，保證能夠與中繼無人機(jī)保持實(shí)時(shí)的雙向通信，把收集到的地面監(jiān)測(cè)、前線人員可穿戴設(shè)備的數(shù)據(jù)通過中繼無人機(jī)傳輸?shù)綉?yīng)急行動(dòng)中心，同時(shí)ECO能夠?qū)SA無人機(jī)進(jìn)行遠(yuǎn)距離監(jiān)控。如圖5所示。

圖5 無人機(jī)空間布局圖

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

2.2 智能算法確定無人機(jī)的數(shù)量組合

基于以上多目標(biāo)規(guī)劃的原則，對(duì)于該森林火災(zāi)中無人機(jī)配置問題，本文以經(jīng)濟(jì)和效率2個(gè)子目標(biāo)綜合優(yōu)化配置無人機(jī)數(shù)量組合。我們假設(shè)某消防部門有一億美元用于購(gòu)買無人機(jī)，某公司的混合動(dòng)力無人機(jī)預(yù)計(jì)在配備無線電中繼器或視頻和遙測(cè)功能時(shí)成本約為 10 000美元，假設(shè)一臺(tái)SSA無人機(jī)的價(jià)格是300美元，一臺(tái)中繼無人機(jī)的價(jià)格是2 000美元。假設(shè)購(gòu)買SSA無人機(jī)臺(tái)，購(gòu)買中繼無人機(jī)臺(tái)。約束函數(shù)設(shè)計(jì)如表1所示。

表1 無人機(jī)數(shù)量組合約束函數(shù)

效率最大化用下式表達(dá)：

(14)

為了更加準(zhǔn)確地檢測(cè)火災(zāi)的發(fā)生，希望無人機(jī)能盡最大可能覆蓋全局。使得火情能被SSA無人機(jī)迅速檢測(cè)到并傳遞給應(yīng)急行動(dòng)中心，讓應(yīng)急行動(dòng)中心(EOC)以最佳方式指揮現(xiàn)役人員，以獲得最佳效果和最大安全。

經(jīng)濟(jì)最大化用下式表達(dá)：

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

(15)

為了能迅速檢測(cè)到火情，當(dāng)然是無人機(jī)越多越好。但是無人機(jī)價(jià)格高昂，因此我們需要在有效的范圍內(nèi)使用盡可能少的無人機(jī)，因此實(shí)現(xiàn)經(jīng)濟(jì)效益也是目標(biāo)函數(shù)之一。

根據(jù)上述模型建模得出如下結(jié)論，無人機(jī)覆蓋范圍越大，需要的無人機(jī)越多，花費(fèi)的費(fèi)用就越多。具體無人機(jī)覆蓋范圍與無人機(jī)花費(fèi)的關(guān)系如圖6所示。

圖6 無人機(jī)覆蓋范圍和無人機(jī)費(fèi)用之間的關(guān)系

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

圖7 不同無人機(jī)組合所需的無人機(jī)費(fèi)用

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

圖8 不同無人機(jī)組合的覆蓋范圍

3 結(jié)束語(yǔ)

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

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