肖 橋，馮 琦，趙鴻森

(1西北工業(yè)大學(xué)電子信息學(xué)院，西安 710072;2中國飛行試驗研究院航電所，西安 710089)

0 引言

飛行器航跡規(guī)劃問題本質(zhì)是一個多維、非連續(xù)、非線性大空間內(nèi)的多約束、多目標(biāo)的NP優(yōu)化問題，進化算法已被證明是一種解決NP問題的有效全局搜索技術(shù)，在搜索空間和并行運算效率兩方面體現(xiàn)出其獨特的優(yōu)勢，在航跡規(guī)劃領(lǐng)域得到了廣泛的研究[1－2]。但傳統(tǒng)的進化算法存在初始種群大，影響進化效率，在搜索過程中存在早熟和收斂過慢問題;而且傳統(tǒng)的適應(yīng)度函數(shù)的選取方法并不能很全面的評價航跡個體的優(yōu)劣。

為改進進化算法進行航跡規(guī)劃時存在的問題，把細(xì)菌進化引入航跡規(guī)劃，設(shè)計了獨特的二進制編碼方式和更加合理的種群初始化方法，應(yīng)用細(xì)菌進化獨特的變異和基因傳遞[3]改良種群，并采用多屬性決策理論對種群航跡個體進行評價。

1 細(xì)菌變異的航跡規(guī)劃方法

航跡規(guī)劃目的是尋找從起始點通往目標(biāo)點間的幾個關(guān)鍵航路點，相鄰兩個航路點連線構(gòu)成一段航路。所以首先根據(jù)需要定出可能的航路點數(shù)量，然后據(jù)此編碼，在實際應(yīng)用中一般選取3～5個航路點。

1.1 角度和航段長度編碼方法

以起始點為坐標(biāo)原點，目標(biāo)點處于第一象限中，第一段航路的角度θ1限制在0°～90°;由于飛行器過載的限制，兩段航路之間最大角度改變量限制為θmax，假設(shè)第k段航路的角度為θk，第k+1段航路的角度為θk+1，則相鄰兩段航路的轉(zhuǎn)彎角度限制為|θk+1－θk|＜θmax，將此范圍等分為16份，則角度可采用4位二進制編碼：

式中ε為二進制編碼解碼出的整數(shù)，ε∈[0，15]。

假設(shè)航路點k的坐標(biāo)(xk，yk)和第k+1段nm航路點的角度θk+1、長度lk+1，則第k+1個航路點的坐標(biāo)計算如下：

每一段航路的編碼分為角度和段長，角度采用4位二進制編碼，航路長度采用8位二進制編碼，則兩個航路點之間的航路對應(yīng)12位二進制位。細(xì)菌個體的編碼為 θ1l1θ2l2…θnln，θi和 li(i=1，2，…，n)分別代表角度編碼和段長編碼，每個個體表示一條完整的航跡。編碼示意如圖1。

圖1 航跡編碼示意圖

1.2 初始種群產(chǎn)生

在進化算法中一般選取很大的種群以保證搜索范圍和防止早熟，種群數(shù)越大搜索范圍越廣，但進化效率越低，而細(xì)菌進化算法的優(yōu)勢之一就是較少的種群數(shù)即可達到目的[4]，假設(shè)細(xì)菌種群數(shù)為Nind，每一個細(xì)菌代表一條完整航跡，初始產(chǎn)生的個體編碼每一位都在0和1中隨機產(chǎn)生，為了使初始種群具有多樣性以克服早熟現(xiàn)象，航跡第一段航路初始角度編碼設(shè)置在0°～90°范圍內(nèi)均勻分布。

1.3 細(xì)菌變異

細(xì)菌變異是對單個個體執(zhí)行的操作，目的是為了提高種群的多樣性。首先對每一個細(xì)菌產(chǎn)生Nclone個克隆體，然后隨機選擇克隆體的某一段或某幾段，隨機改變這些段的參數(shù)。采用二進制編碼，變異操作通過使參數(shù)在0和1中重新隨機選取實現(xiàn)。然后對所有的克隆體和其原航跡個體進行評價，即采用多屬性決策方法，選出最優(yōu)個體，然后這個最優(yōu)細(xì)菌把變異部位復(fù)制給其余克隆體。繼續(xù)上述循環(huán)，直到所有片段被變異，然后保留最優(yōu)細(xì)菌，去掉它的克隆體。

上述操作同時對種群的所有細(xì)菌個體執(zhí)行。但在進化的同一代中，每個位置最多變異一次。采用變異操作，細(xì)菌種群會更加優(yōu)秀，由于每一次變異都為航跡規(guī)劃帶來了一種解決途徑，因此這種方法可以使航跡的搜索范圍更廣，同時克隆操作和并行變異使得運算更加高效?？寺?shù)Nclone越大，輸出結(jié)果越精確。細(xì)菌變異操作如圖2所示。

圖2 細(xì)菌變異示意圖

1.4 基因傳遞

基因傳遞是對整個種群執(zhí)行的操作，是為了實現(xiàn)細(xì)菌個體之間的信息交互，類似于遺傳算法中的交叉操作，與交叉操作不一樣的是，整個過程中沒有基因交換，只有優(yōu)勢個體把基因復(fù)制給劣勢個體，基因傳遞實現(xiàn)了信息從優(yōu)等個體向種群的傳播。

首先對于整個種群，依據(jù)多屬性決策方法排序，把種群分為兩部分：優(yōu)等種群和劣等種群;然后分別從優(yōu)等集中隨機選一個個體(源細(xì)菌)，從劣等集中隨機選一個個體(目標(biāo)細(xì)菌)，隨機從源細(xì)菌上選取一個片段，復(fù)制到目標(biāo)細(xì)菌上。在每一代中，細(xì)菌的基因傳遞會發(fā)生Ninf次，其中Ninf為每一代的基因傳遞次數(shù)。Ninf過大會出現(xiàn)早熟現(xiàn)象而導(dǎo)致局部最優(yōu)化，故Ninf小一點會取得不錯的效果，同時也會減少運算量。基因傳遞操作如圖3所示。

圖3 基因傳遞示意圖

1.5 進化流程

Stept1產(chǎn)生初始種群;

Stept2對每一個細(xì)菌執(zhí)行變異操作;

Stept3在種群中執(zhí)行基因傳遞操作;

Stept4若達到終止條件，則終止循環(huán);否則，用最優(yōu)個體取代最差個體，然后回到Stept2繼續(xù)循環(huán)。終止條件為設(shè)定的最大進化代數(shù)Ngen。

2 多屬性決策理論的航跡個體評價方法

在計算航跡個體的適應(yīng)度函數(shù)時，已有的進化算法大多將各個優(yōu)化屬性統(tǒng)一量綱進行加權(quán)處理，例如在無人機航跡規(guī)劃中，有采用航跡總長度、飛行高度和威脅指數(shù)加權(quán)計算的方法[5];在反艦導(dǎo)彈航跡規(guī)劃中，有采用被探測的威脅度、被攔截威脅度和航程加權(quán)計算的方法[6]，但實際中各屬性的量綱很難統(tǒng)一，并且各個屬性的數(shù)量級相差甚大，這樣處理往往導(dǎo)致矛盾的結(jié)果，并因此而丟失優(yōu)良個體。航跡個體的評價從根本上看都是一個多屬性決策問題，因此在個體評價時應(yīng)用決策理論更切合問題的本質(zhì)，在進行航跡個體評價時主要參考三個主要屬性：航跡總長度、轉(zhuǎn)彎角度和生存概率;航跡總長度是一項基本屬性，總長度越短，受威脅時間越短，耗油也越少;很多規(guī)劃方法容易忽略轉(zhuǎn)彎角，但轉(zhuǎn)彎角也是一個很重要的屬性，轉(zhuǎn)彎越多耗油越大;對于作戰(zhàn)飛行器，最重要的屬性還是生存概率。

2.1 航跡總長度

設(shè)起始點為(x0，y0)，目標(biāo)點為(xD，yD)，第 i段航路長為li，通過式(1)解碼出的最后一個航路點的坐標(biāo)為(xn，yn)，則整段航跡長度L可用下式計算：

2.2 轉(zhuǎn)彎角

設(shè)第i段航路的角度為θi，則整條航跡的總轉(zhuǎn)彎角度θ為：

2.3 生存概率

首先把總航跡等距離散化為一系列的點{x1，…，xj，…，xK}，假設(shè)有H個威脅源，在某一點x處的生存概率為P(x)為：

Ri(x)是在點x處被威脅源i殺傷的概率。

則總航跡{x1，…，xj，…，xK}生存概率 P 為[7]：

2.4 多屬性航跡評價

種群中各個航跡個體的優(yōu)劣主要是由上述三個不同屬性綜合決定的，而且在航跡評價中不同的任務(wù)對于這三個不同屬性的要求不一樣，同時各屬性的數(shù)量級也有較大差異，需要采用多屬性決策方法對航跡個體進行優(yōu)劣評價。

決策矩陣(Decision Matrix)是求解多屬性決策問題的依據(jù)，是屬性值和決策準(zhǔn)則的基礎(chǔ)。設(shè)Ai(i=1，2，…，m)表示第 i個體，Xj(j=1，2，…，n)表示第 j屬性，則多屬性決策問題可用下面的矩陣M表示：

決策矩陣M中的元素xij表示第i個體Ai在第j屬性Xj下的屬性值。各方案的屬性值可構(gòu)成決策矩陣，或稱為屬性矩陣、屬性值表，該決策矩陣提供了分析決策問題所需的基本信息[8]。

對于各屬性優(yōu)屬度μ的確定，航跡長度和轉(zhuǎn)彎角度都是越小航跡越好，故采用成本型相對優(yōu)屬度確定方法，生存概率越大航跡越優(yōu)，故采用效益型相對優(yōu)屬度確定方法。

成本型的相對優(yōu)屬度計算公式為：

效益型屬性的相對優(yōu)屬度計算公式：

通過選擇合適的目標(biāo)相對優(yōu)屬度計算公式，可將決策矩陣M變換成為目標(biāo)相對優(yōu)屬度矩陣μ，即：

則個體優(yōu)劣決策向量T1×m=ω·μT，對決策向量進行排序等價于對種群航跡個體進行評價，其中ω=(ωL，ωθ，ωp)，分別表示航跡總長度、轉(zhuǎn)彎角和生存概率的評價權(quán)重，ω的選取對于順利完成航路規(guī)劃任務(wù)至關(guān)重要，ωL、ωθ、ωp的選取是根據(jù)飛行器的性能、具體的飛行任務(wù)和飛行環(huán)境等因素綜合決定，有人駕駛飛行器可以根據(jù)經(jīng)驗知識來調(diào)整，但是一般來說應(yīng)該采取更加科學(xué)的方法，特別是對于在航跡規(guī)劃屬性更多、要求更精確的情況下。對于權(quán)重的選取主要有：基于目標(biāo)偏好的綜合集成賦權(quán)法;基于熵的綜合集成賦權(quán)法;基于模糊層次分析法的權(quán)重計算模型;模糊綜合評估法[9];基于知識的模糊推理方法等。

3 仿真結(jié)果

規(guī)劃區(qū)域內(nèi)有五個威脅源，在圖中用黑色灰度區(qū)域表示，黑色越深表示該區(qū)域的殺傷概率越大，右上角黑點代表目標(biāo)點，根據(jù)過載要求得出相鄰兩段航路最大角度改變量θmax=60°，種群數(shù)Nind=200，克隆數(shù)Nclnoe=50，基因傳遞數(shù)Ninf=50，進化代數(shù)Ngen=400。ω =(0.2，0.6，0.2)時規(guī)劃結(jié)果如圖 4 所示;ω=(0.6，0.2，0.2)時規(guī)劃結(jié)果如圖 5所示;ω =(0.2，0.2，0.6)時規(guī)劃結(jié)果如圖6所示;ω =(0.33，0.33，0.34)時規(guī)劃結(jié)果如圖7所示。

圖4 權(quán)重偏向于轉(zhuǎn)彎角度

圖5 權(quán)重偏向于航跡長度

圖6 權(quán)重偏向于生存概率

圖7 權(quán)重均勻選取

對比圖4～圖7可看出，轉(zhuǎn)彎角、航跡長度和生存概率都會影響航跡的生成效果。如果需要盡快到達目標(biāo)點可以設(shè)置較大的轉(zhuǎn)彎角度權(quán)重或者較大的航跡長度權(quán)重，如果需要保證飛行器的生存概率而繞過威脅區(qū)，則可以設(shè)置較大的生存概率權(quán)重。為了搜索到符合條件的最優(yōu)航跡，合理選取各屬性權(quán)重對于航跡規(guī)劃具有很重要的作用。

4 結(jié)論

設(shè)計了適用于航跡規(guī)劃的細(xì)菌進化算法，采用切合實際任務(wù)需求的編碼方式和種群初始化方法及基因變異、基因傳遞操作增大了搜索空間，使得采用一般進化算法存在的初始種群大、早熟及收斂過慢問題得到了很好的解決;首次采用多屬性決策方法進行航跡個體評價，使得規(guī)劃決策者可以根據(jù)任務(wù)需求而設(shè)定不同的約束條件和優(yōu)化屬性，具有很好的應(yīng)用前景。仿真結(jié)果表明所提方法具有很好的全局規(guī)劃能力及靈活性。

[1]C Hocaoglu，A C Sanderson.Planning multiple paths with evolutionary speciation[J].IEEE Transaction on Evolutionary Computation，2001，5(3)：169－192.

[2]K Sugiara，J Smith.Genetic algorithms for adaptive planning of path and trajectory of a mobile robot in 2D terrains[J].IEEE Transaction on Information System，1999，E82－D(1)：309－316.

[3]N E Nawa，T Furuhashi.Fuzzy system parameters discovery by bacterial evolutionary algorithm[J].IEEE Trans.Fuzzy Systems，1999，7(5)：608－616.

[4]Cabrita，C.Botzheim，J.Ruano，A.E.Kóczy，and L.T：Design of B-spline neural networks using a bacterial programming approach[C]//International Joint Conference on Neural Networks，2004：2313－2318.

[5]丁明躍，鄭昌文，周成平，等.無人飛行器航跡規(guī)劃[M].北京：電子工業(yè)出版社，2009.

[6]沈建鋒，劉興明，吳凌華，等.多平臺反艦導(dǎo)彈協(xié)同航跡規(guī)劃[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2009(2)：62－66.

[7]Adam McLendon Eames.Enabling path planning and threat avoidance with wireless sensor networks[D].America：Massachusetts Institute of Technology，2005.

[8]楊保安，張科靜.多目標(biāo)決策分析理論、方法與應(yīng)用研究[M].上海：東華大學(xué)出版社，2008.

[9]羅小明.彈道導(dǎo)彈攻防對抗的建模與仿真[M].北京：國防工業(yè)出版社，2009.