基于改進(jìn)操作算子的遺傳算法無人機(jī)航路規(guī)劃

錢海力

（中國電子科技集團(tuán)公司第二十八研究所 江蘇省南京市 210007）

無人機(jī)在執(zhí)行任務(wù)之前需要進(jìn)行任務(wù)規(guī)劃，其中，最為主要的一部分就是無人機(jī)的航路規(guī)劃。合理有效航路規(guī)劃能幫助無人機(jī)平臺(tái)規(guī)避威脅，提高偵察和生存能力。運(yùn)用改進(jìn)操作算子的遺傳算法對(duì)無人機(jī)的航路進(jìn)行精細(xì)規(guī)劃，能有效提高算法收斂速度，規(guī)劃出更科學(xué)的任務(wù)航路。

1 遺傳算法

遺傳算法是以生物進(jìn)化機(jī)制為基礎(chǔ)的一種算法，屬于搜索算法中的一種。美國密歇根大學(xué)霍蘭德教授于1967年根據(jù)自然選擇理論提出了關(guān)于遺傳算法的相關(guān)概念，此后其學(xué)生在自己的研究著作中，總結(jié)了遺傳算法的研究成果，即一種全局優(yōu)化的搜索算法，其核心為：

（1）合理編碼方式與有效終止條件；

（2）建立適合評(píng)價(jià)個(gè)體性能與適應(yīng)度的函數(shù)；

（3）合理復(fù)制、交叉與變異操作[1]。

1.1 編碼評(píng)測(cè)

遺傳算法在應(yīng)用中，先建立問題染色體，之后形成問題種群，最后，對(duì)染色體適應(yīng)能力進(jìn)行測(cè)量并對(duì)其進(jìn)行迭代繁殖分析。遺傳算法利用染色體表達(dá)優(yōu)化搜索問題的解，通常運(yùn)用字符或數(shù)值兩種編碼形式去描述染色體。編碼評(píng)測(cè)方法是遺傳算法問題建立之后的一種主要優(yōu)化機(jī)制，評(píng)測(cè)能根據(jù)適應(yīng)度對(duì)染色體適應(yīng)性進(jìn)行評(píng)價(jià)，通過對(duì)比分析方式不斷對(duì)染色體個(gè)體進(jìn)行優(yōu)化迭代，最終找到最優(yōu)解。在遺傳算法優(yōu)化中，染色體繁衍迭代，通過編碼評(píng)測(cè)實(shí)現(xiàn)對(duì)染色體適應(yīng)能力的計(jì)算，模擬生物的進(jìn)化過程[2]。

1.2 終止條件

在繁衍過程中，使用突變操作或者交叉操作方法進(jìn)行染色體迭代。其中，突變操作主要是使染色體某部位基因參數(shù)產(chǎn)生突然性變化；交叉操作采用染色體某個(gè)部位基因交換，適應(yīng)性強(qiáng)的染色體會(huì)逐漸完成統(tǒng)治，適應(yīng)性弱的部分會(huì)消失，提高整個(gè)種群適應(yīng)能力。通過對(duì)整個(gè)群體的繁衍優(yōu)化，其群體的適應(yīng)能力會(huì)不斷上升。因此，通過對(duì)染色體群體的適應(yīng)性分析方法，能夠掌握整體適應(yīng)性上升或者下降的發(fā)展趨勢(shì)，并最終作為算法的終止條件。此外，還可以通過規(guī)定染色體群繁殖時(shí)間，檢驗(yàn)最優(yōu)染色體是否達(dá)到相關(guān)要求，如果沒有達(dá)到要求，則要進(jìn)行重新運(yùn)算，如果達(dá)到，則停止計(jì)算。

2 航路規(guī)劃

2.1 空間建模

考慮地形因素、威脅因素、無人機(jī)平臺(tái)運(yùn)動(dòng)因素等對(duì)其任務(wù)過程所產(chǎn)生的影響，分析無人機(jī)飛行的環(huán)境條件并進(jìn)行數(shù)學(xué)抽象和描述，建立無人機(jī)飛行過程中的空間約束模型?；跓o人機(jī)飛行過程空間約束模型，以最優(yōu)化目標(biāo)函數(shù)的方式對(duì)無人機(jī)的航路進(jìn)行規(guī)劃，從而生成無人機(jī)最優(yōu)航路[3]。由于無人機(jī)任務(wù)剖面在巡航段時(shí)高度保持不變，因此采用二維空間模型，能比較直觀地反映出其飛行過程中在同一高度平面的航路規(guī)劃問題。針對(duì)任務(wù)空間中的威脅區(qū)域，本文采用圓形近似表示，將圓形半徑作為威脅區(qū)域的有效覆蓋距離，圓形范圍內(nèi)作為禁止飛行區(qū)域。

2.2 評(píng)價(jià)建模

航路規(guī)劃的目標(biāo)是綜合考慮無人機(jī)飛行性能所產(chǎn)生的限制，規(guī)避飛行中面臨的各類威脅到達(dá)指定目標(biāo)點(diǎn)，在保證任務(wù)過中的生存能力的同時(shí)提高任務(wù)完成度。為實(shí)現(xiàn)上述目的，在評(píng)價(jià)建模中，需要選擇最優(yōu)目標(biāo)函數(shù)，對(duì)無人機(jī)航路進(jìn)行評(píng)價(jià)，判斷各類約束條件的滿足情況，并引導(dǎo)搜索算法逐步迭代逼近最優(yōu)解。在航路規(guī)劃評(píng)價(jià)中，航路規(guī)劃結(jié)果為航路點(diǎn)間構(gòu)成航路段，此時(shí)航路約束條件可以表示為航路段的約束。在具體規(guī)劃過程中，考慮到無人機(jī)平臺(tái)運(yùn)動(dòng)約束，定義最小路段為無人機(jī)在執(zhí)行下一動(dòng)作之前需要做出的最短飛行距離。

3 改進(jìn)操作算子遺傳算法無人機(jī)航路規(guī)劃

3.1 規(guī)劃要點(diǎn)

3.1.1 編碼問題

染色體編碼是無人機(jī)航路遺傳算法規(guī)劃中的重要前提，編碼方法決定個(gè)體染色體排列形式，還決定個(gè)體從搜索空間基因變換到解空間的解碼方法。編碼方法影響到交叉、變異與選擇算子，常用的編碼方式可以為二進(jìn)制、字母、整數(shù)或浮點(diǎn)數(shù)等。研究證明，編碼方式與問題原始形式接近程度越高，則表現(xiàn)形式越有效，最終結(jié)論更優(yōu)。但同時(shí)，編碼方式越復(fù)雜，則搜索復(fù)雜度越高，搜索時(shí)間越長(zhǎng)。

如前所述，在進(jìn)行無人機(jī)的航路規(guī)劃中，由于無人機(jī)任務(wù)剖面在巡航段時(shí)高度保持不變，主要考慮無人機(jī)在巡航高度平面內(nèi)的運(yùn)動(dòng)，因此本文將三維航路規(guī)劃問題轉(zhuǎn)化為同一高度下的二維平面航路規(guī)劃問題[4]，采用平面內(nèi)優(yōu)化搜索解決無人機(jī)航路規(guī)劃問題。建立直角坐標(biāo)系X-O-Y，將無人機(jī)航路劃分為N 等分，得到L1（x1，y1），L2（x2，y2）...LN（xN，yN）共N 個(gè)航路節(jié)點(diǎn)。綜合考慮無人機(jī)在飛行中受到的轉(zhuǎn)彎約束或者方向性問題，將起始點(diǎn)到目標(biāo)點(diǎn)的航路P 用節(jié)點(diǎn)集合描述表示，即：

其中，S 為航路起始點(diǎn)，G 為航路目標(biāo)點(diǎn)。

為了方便運(yùn)算，在進(jìn)行無人機(jī)的飛行航路節(jié)點(diǎn)編碼時(shí)僅將縱坐標(biāo)作為基因進(jìn)行編碼，而橫坐標(biāo)的變化保持不變。本文采用浮點(diǎn)數(shù)形式進(jìn)行編碼，此時(shí)航路P 的編碼形式為：y1y2...yN。

3.1.2 航路代價(jià)

航路代價(jià)主要考慮無人機(jī)任務(wù)過程中的油耗代價(jià)和威脅代價(jià)。一方面，無人機(jī)飛行過程中受自身油耗因素影響，其飛行航程受到受限；另一方面，任務(wù)過程中會(huì)遭遇雷達(dá)、導(dǎo)彈等各類威脅因素，其飛行空間受到限制。因此，為使無人機(jī)任務(wù)航路耗油最低且受威脅最小，要從航路長(zhǎng)度、航路油耗量、航路點(diǎn)是否受威脅、航路段是否跨越威脅區(qū)等方面進(jìn)行分析，并根據(jù)無人機(jī)的任務(wù)要求，調(diào)整各類型代價(jià)函數(shù)的權(quán)重大小，綜合代價(jià)指標(biāo)得到相對(duì)較優(yōu)的無人機(jī)任務(wù)航路。

3.2 規(guī)劃方案

3.2.1 適應(yīng)度函數(shù)

在明確無人機(jī)航路編碼問題及其在任務(wù)過程中面臨的威脅、油耗等航路代價(jià)后，如何選擇最優(yōu)的算法對(duì)無人機(jī)飛行航路進(jìn)行規(guī)劃是解決問題的核心。可見，建立合適的適應(yīng)度函數(shù)，是采用遺傳算法解決無人機(jī)航路規(guī)劃問題的關(guān)鍵。

在對(duì)無人機(jī)的航線規(guī)劃中，基于提出的航路編碼方式及航路代價(jià)條件，本文提出包含航路總長(zhǎng)度f1、航路點(diǎn)是否在威脅區(qū)域內(nèi)罰函數(shù)f2、航路段是否穿越威脅區(qū)罰函數(shù)f3 的適應(yīng)度函數(shù)。即適應(yīng)度函數(shù)F 可描述為：

其中，罰函數(shù)f2、f3 取1 時(shí)，航路點(diǎn)在威脅區(qū)域內(nèi)或航路段穿越威脅區(qū)域，反之取0；w1、w2、w3 為權(quán)重系數(shù)，有w1+w2+w3=1。

3.2.2 遺傳操作

對(duì)無人機(jī)航路進(jìn)行規(guī)劃時(shí)，根據(jù)適應(yīng)度大小，選擇適應(yīng)度較強(qiáng)的個(gè)體，完成對(duì)個(gè)體的遺傳操作，產(chǎn)生適應(yīng)性更優(yōu)的下一代個(gè)體。通常情況下，適應(yīng)度高的個(gè)體被選擇概率較大，適應(yīng)度較低的個(gè)體被選擇的概率較小。遺傳算法的遺傳操作即體現(xiàn)了生物界“優(yōu)勝劣汰”的原則，其操作分為：選擇、交叉、變異三個(gè)部分。

根據(jù)無人機(jī)航路規(guī)劃問題復(fù)雜性，本文對(duì)選擇算子進(jìn)行改進(jìn)。按照適應(yīng)度從高到低的順序?qū)€(gè)體適應(yīng)性進(jìn)行排序，給定適應(yīng)度閾值S，適應(yīng)度高于S 的個(gè)體復(fù)制成n 份，適應(yīng)度低于S 的個(gè)體不單獨(dú)進(jìn)行復(fù)制。通過這種方式，可以在確保群體內(nèi)多樣性的基礎(chǔ)上，逐步淘汰適應(yīng)度低的個(gè)體，并收斂得到最優(yōu)解。

交叉是以交叉概率Pc 從群體中選擇兩個(gè)個(gè)體，并對(duì)個(gè)體內(nèi)的某個(gè)、某些基因位進(jìn)行交換?；趯?duì)遺傳算法的交叉操作分析可知，當(dāng)前主要的交叉方式包括了單點(diǎn)交叉、雙點(diǎn)交叉和均勻交叉等。其中，雙點(diǎn)交叉模式是個(gè)體中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，之后進(jìn)行基因交換的一種方式，具有適應(yīng)性強(qiáng)和操作復(fù)雜度低的特點(diǎn)。因此，本文即采用兩點(diǎn)交叉方式進(jìn)行交叉操作。

變異方法是以較小的變異概率Pm 對(duì)個(gè)體編碼串上某個(gè)單獨(dú)、某些基因位進(jìn)行隨機(jī)改變。本文對(duì)變異算子進(jìn)行改進(jìn)，以變異概率Pm 選取個(gè)體的兩個(gè)基因位，通過航路點(diǎn)坐標(biāo)距離改變5000 米實(shí)現(xiàn)變異?；跓o人機(jī)路徑規(guī)劃仿真驗(yàn)證和工程實(shí)踐，當(dāng)兩個(gè)航路點(diǎn)之間坐標(biāo)不超過5000 米時(shí)，能保證相鄰航路點(diǎn)距離相差不大，而且航路點(diǎn)也不會(huì)產(chǎn)生跳躍現(xiàn)象，使無人機(jī)在飛行的過程中，能始終保持相對(duì)穩(wěn)定的狀態(tài)，同時(shí)也可以加快算法收斂速度，便于得到最優(yōu)解。

3.3 改進(jìn)策略

遺傳算法中使用交叉算子作用于個(gè)體，會(huì)促使新個(gè)體的產(chǎn)生，這實(shí)質(zhì)上是基因重組的過程，使算法在解空間中進(jìn)行有效搜索。若交叉概率Pc 過大，種群中個(gè)體更新會(huì)變快，那么適應(yīng)度高的個(gè)體將很快遭到破壞，即優(yōu)良模式很快被破壞；若交叉概率太小，交叉操作將進(jìn)行得很少，基因重組就會(huì)減少，最終使得搜索停滯，遺傳算法不收斂。

遺傳算法中變異操作實(shí)質(zhì)上是對(duì)種群模式進(jìn)行擾動(dòng)，以增加基因種類的豐富性，有利于種群多樣性的增加。但是，若變異概率Pm 太小，那么新模式就會(huì)很難產(chǎn)生，若有過大的變異概率，那么遺傳算法的搜索將變得比較隨機(jī)。

可見，交叉概率Pc 和變異概率Pm 的選取對(duì)遺傳算法的收斂效率和解的最優(yōu)性至關(guān)重要。分析可知，當(dāng)個(gè)體的適應(yīng)度越接近種群最大適應(yīng)度時(shí)，其交叉和變異的概率應(yīng)越低，此時(shí)其優(yōu)良基因越可能在下一代個(gè)體中保留下來。因此，本文基于Logistic 方程提出一種對(duì)Pc 和Pm 的改進(jìn)策略，實(shí)現(xiàn)在遺傳算法迭代過程中對(duì)Pc 與Pm 的自適應(yīng)調(diào)整，其數(shù)學(xué)描述如下：

其中，f'為要交叉的個(gè)體中適應(yīng)度值較大的個(gè)體的適應(yīng)度，f為要變異的個(gè)體的適應(yīng)度，favg為種群中所有個(gè)體的平均適應(yīng)度，fmax為種群中最大個(gè)體適應(yīng)度，k1、k2為大于0 的常數(shù)。

通過仿真分析，對(duì)本文提出的航路規(guī)劃方法的合理性和有效性進(jìn)行判斷。針對(duì)典型無人機(jī)航路規(guī)劃任務(wù)，受限采用傳統(tǒng)遺傳算法仿真，初始種群設(shè)定為200 個(gè)，最大迭代次數(shù)設(shè)定為300，在使用輪盤選擇方法和兩點(diǎn)交叉模式，變異過程為實(shí)體變異。之后，在經(jīng)過操作算子改進(jìn)之后的遺傳算法進(jìn)行仿真分析，采用相同的參數(shù)指標(biāo)操作，能夠發(fā)現(xiàn)本文提出的基于改進(jìn)操作算子的遺傳算法相較傳統(tǒng)方法在收斂迭代次數(shù)和收斂概率上有一定提升。結(jié)果證明，經(jīng)過操作算子改進(jìn)之后的遺傳算法最優(yōu)航線算法比傳統(tǒng)算法的迭代速度更快，而且航路比較平滑，這些均有利于無人機(jī)任務(wù)的實(shí)施。經(jīng)過改進(jìn)之后遺傳算法在多個(gè)評(píng)價(jià)標(biāo)準(zhǔn)上的指標(biāo)均比傳統(tǒng)算法更優(yōu)，而且規(guī)劃出的路徑適合無人機(jī)平臺(tái)正常飛行。同時(shí)規(guī)劃得到的最優(yōu)航路，合理規(guī)避了各類障礙物和威脅要素，縮短了飛行距離，可有效節(jié)約燃料，降低了能耗與成本。

4 總結(jié)

綜上所述，在現(xiàn)代社會(huì)，特別是在軍事領(lǐng)域，無人機(jī)應(yīng)用越來越廣泛，智能化需求不斷提高，這些均對(duì)無人機(jī)航路規(guī)劃方面提出了新的挑戰(zhàn)。為此，本文基于對(duì)遺傳算法以及無人機(jī)航路規(guī)劃相關(guān)領(lǐng)域研究成果的分析研究，提出一種基于改進(jìn)操作算子的遺傳算法無人機(jī)航路規(guī)劃方法，針對(duì)性地對(duì)遺傳算法中選擇算子、交叉算子、變異算子等遺傳操作算子進(jìn)行改進(jìn)，提高了算法搜索效率。針對(duì)傳統(tǒng)遺傳算法中交叉概率Pc 和變異概率Pm 不變?cè)斐伤惴ㄊ諗克俣嚷膯栴}，本文基于Logistic 方程提出一種對(duì)Pc 和Pm 的改進(jìn)策略，并通過仿真驗(yàn)證了本文提出算法的有效性。