基于細菌進化及多屬性決策的航跡規劃方法研究*

肖 橋，馮 琦，趙鴻森

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

0 引言

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

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

1 細菌變異的航跡規劃方法

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

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

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

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

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

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

圖1 航跡編碼示意圖

1.2 初始種群產生

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

1.3 細菌變異

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

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

圖2 細菌變異示意圖

1.4 基因傳遞

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

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

圖3 基因傳遞示意圖

1.5 進化流程

Stept1產生初始種群;

Stept2對每一個細菌執行變異操作;

Stept3在種群中執行基因傳遞操作;

Stept4若達到終止條件，則終止循環;否則，用最優個體取代最差個體，然后回到Stept2繼續循環。終止條件為設定的最大進化代數Ngen。

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

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

2.1 航跡總長度

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

2.2 轉彎角

設第i段航路的角度為θi，則整條航跡的總轉彎角度θ為：

2.3 生存概率

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

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

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

2.4 多屬性航跡評價

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

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

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

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

成本型的相對優屬度計算公式為：

效益型屬性的相對優屬度計算公式：

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

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

3 仿真結果

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

圖4 權重偏向于轉彎角度

圖5 權重偏向于航跡長度

圖6 權重偏向于生存概率

圖7 權重均勻選取

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

4 結論

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

[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]丁明躍，鄭昌文，周成平，等.無人飛行器航跡規劃[M].北京：電子工業出版社，2009.

[6]沈建鋒，劉興明，吳凌華，等.多平臺反艦導彈協同航跡規劃[J].戰術導彈技術，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]楊保安，張科靜.多目標決策分析理論、方法與應用研究[M].上海：東華大學出版社，2008.

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