基于細(xì)菌進(jìn)化及多屬性決策的航跡規(guī)劃方法研究*

肖 橋，馮 琦，趙鴻森

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

0 引言

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

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

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

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

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

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

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

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

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

圖1 航跡編碼示意圖

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

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

1.3 細(xì)菌變異

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

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

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

1.4 基因傳遞

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

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

圖3 基因傳遞示意圖

1.5 進(jìn)化流程

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

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

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

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

2 多屬性決策理論的航跡個(gè)體評(píng)價(jià)方法

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

2.1 航跡總長度

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

2.2 轉(zhuǎn)彎角

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

2.3 生存概率

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

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

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

2.4 多屬性航跡評(píng)價(jià)

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

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

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

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

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

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

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

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

3 仿真結(jié)果

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

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

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

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

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

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

4 結(jié)論

設(shè)計(jì)了適用于航跡規(guī)劃的細(xì)菌進(jìn)化算法，采用切合實(shí)際任務(wù)需求的編碼方式和種群初始化方法及基因變異、基因傳遞操作增大了搜索空間，使得采用一般進(jìn)化算法存在的初始種群大、早熟及收斂過慢問題得到了很好的解決;首次采用多屬性決策方法進(jìn)行航跡個(gè)體評(píng)價(jià)，使得規(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]沈建鋒，劉興明，吳凌華，等.多平臺(tái)反艦導(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)彈攻防對(duì)抗的建模與仿真[M].北京：國防工業(yè)出版社，2009.