基于遺傳算法的無人機避障路徑規(guī)劃

1、基于遺傳算法的無人機避障路徑規(guī)劃1基于遺傳算法無人機避障模型設(shè)計隨著無人機在諸多領(lǐng)域的廣泛應(yīng)用，與之配套的具有避障功能的路徑規(guī)劃算法成為了需要重點討論的關(guān)鍵問題。伴隨著計算機技術(shù)的發(fā)展，基于智能算法的無人機避障路徑規(guī)劃研究也取得了長足的進(jìn)展。其中，遺傳算法以其優(yōu)越的計算性能與極強的問題普適性受到了最為廣泛的關(guān)注。在無人機避障路徑規(guī)劃問題上，遺傳算法相較于其他類型算法有較為突出的優(yōu)勢。首先，不同于各個類型的神經(jīng)網(wǎng)絡(luò)算法，遺傳算法不要求適應(yīng)度函數(shù)具有可導(dǎo)或連續(xù)的屬性，僅要求適應(yīng)度函數(shù)值為正即可。另外，大多數(shù)其他類型的優(yōu)化算法的本質(zhì)為單點搜索算法，面對較大規(guī)模的搜索區(qū)域時極易陷入局部最優(yōu)解全局搜索性

2、能較差，而遺傳算法作為一種多點搜索算法在面對大規(guī)模復(fù)雜區(qū)域時可以表現(xiàn)出極強的搜索性能，更易于獲得全局最優(yōu)解。基于這些優(yōu)點，遺傳算法近年來被大量的應(yīng)用于路徑規(guī)劃問題的解決。但針對于無人機避障問題而言，相關(guān)的研究仍然較為缺乏，為了確保無人機穩(wěn)定運行以及工作任務(wù)的實現(xiàn)，本文提出了基于遺傳算法的無人機避障路徑規(guī)劃模型來實現(xiàn)復(fù)雜環(huán)境下無人機避障問題的解決。為了能夠有效描述待規(guī)劃區(qū)域地圖，本文采用柵格法對路徑規(guī)劃場地進(jìn)行劃分。假設(shè)路徑規(guī)劃場地為矩形，根據(jù)場地具體尺寸可以確定柵格邊長，由此即可以將場地劃分為多個小正方形柵格，得到一個mn的柵格狀地圖。為了便于對模型進(jìn)行描述以及與實際場地結(jié)合，同時采用坐標(biāo)法與

3、序號法對柵格地圖中的柵格進(jìn)行編號，兩種方法可以依據(jù)實際比例相互換算得到。如圖4.15所示為10x10規(guī)模的區(qū)域柵格模型，柵格旁的行列標(biāo)號為柵格橫縱坐標(biāo)，柵格坐標(biāo)可用于快速獲得該柵格在地圖中的位置。柵格中間標(biāo)號為柵格序號，柵格序號適用于柵格的訪問和路徑的記錄。本文中所說柵格N即指柵格序號為N的柵格，這個序號可以由柵格中心點對應(yīng)的坐標(biāo)值(x,y)計算得到，計算公式為：N=x-10y+99(4.34)同樣的，當(dāng)由遺傳算法優(yōu)化路徑完成后，需要對路徑進(jìn)行解碼方能畫出最優(yōu)路徑，這一過程的變換公式為：fx=N%10x(4.35)|y=-int(N/10丿+10y12345678910111213141516

4、17181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991000x圖4.15避障區(qū)域10x10柵格模型關(guān)于遺傳算法的基本理論已經(jīng)在本文的4.2.2.1部分進(jìn)行了介紹。利用遺傳算法實現(xiàn)無人機避障路徑規(guī)劃的算法流程如圖所示。圖4.16基于遺傳算法的避障路徑規(guī)劃流程具體的算法內(nèi)容如下：（1）初始化種群。無人機的運動路徑表現(xiàn)為一系

5、列的連續(xù)柵格序號，利用遺傳算法進(jìn)行最優(yōu)路徑搜索時，首先將種群S初始化為包含有P個染色體個體。定義無人機運動起點為0號柵格，則這些個體當(dāng)中必然會包含有柵格序號0，其余序號則隨機生成。（2）適應(yīng)度函數(shù)。個體適應(yīng)度函數(shù)需要能夠反應(yīng)每個個體對問題給出解答的性能情況，針對無人機的避障問題，本文將規(guī)劃后的路徑長度作為種群中的路徑優(yōu)化標(biāo)準(zhǔn)。針對某一路徑能否有效避開障礙物這一問題，模型引入懲罰因子進(jìn)行評估，當(dāng)路徑經(jīng)過障礙物區(qū)域時，該個體將受到“嚴(yán)厲”的適應(yīng)度懲罰，因此不再參與到下一代計算。（3）遺傳算法的計算算子。遺傳算法的算子包括選擇、取代、交叉和變異等操作。選擇算子采用輪盤賭選擇法，即依據(jù)個體適應(yīng)度值的高

6、低來決定其被遺傳到子代種群中的概率。取代算子采用進(jìn)化策略和最優(yōu)保存策略實現(xiàn)，即用新一代種群中適應(yīng)度值優(yōu)秀的個體替換掉當(dāng)前代種群中適應(yīng)度值最小的個體。交叉算子是指交換兩個父代個體間的位值，本文采用單點交叉且交叉位置可變。變異算子則采用遺傳算法中常規(guī)變異方法進(jìn)行操作。需要說明，每一代個體中適應(yīng)度函數(shù)值最優(yōu)的個體將不再參與交叉、變異等操作而直接進(jìn)入下一代個體種群中，以保留當(dāng)前代的最優(yōu)解，增強算法的收斂性。在利用遺傳算法進(jìn)行無人機避障路徑規(guī)劃時，遺傳代數(shù)將成為模型中重要的參數(shù)。其原因在于當(dāng)遺傳代數(shù)較低時，目標(biāo)函數(shù)尚未達(dá)到最優(yōu)，模型對應(yīng)的全局最優(yōu)解存在偏離，使得模型性能降低，進(jìn)而導(dǎo)致無人機路徑規(guī)劃不佳。

7、當(dāng)遺傳代數(shù)過高時，模型計算過程過度冗余，浪費計算資源，同時使得規(guī)劃過程耗時過長。因此需要對遺傳代數(shù)參數(shù)的選擇問題進(jìn)行研究。以圖為例，無人機以0號柵格為起點開始運動，目標(biāo)位置為99號柵格。顯然在全局無障礙的情況下，路徑一為最佳路徑規(guī)劃。但當(dāng)遺傳代數(shù)不足時，模型會給出路徑二、路徑三作為最優(yōu)解，這顯然不能滿足實際需要。圖4.17無障礙下的路徑選擇在路徑規(guī)劃問題中通常將遺傳代數(shù)G選擇在2001000的范圍內(nèi)。以上述問題為例，在這一范圍內(nèi)對基于遺傳算法的無人機避障模型性能進(jìn)行研究與評估。圖4.18為模型的適應(yīng)度函數(shù)值與進(jìn)化代數(shù)的關(guān)系圖像，可以看出，當(dāng)進(jìn)化代數(shù)達(dá)到500代之后模型達(dá)到穩(wěn)定。15適應(yīng)度函數(shù)值

8、14t131211-40Q600800100010-世代數(shù)G圖4.18避障路徑規(guī)劃模型中世代數(shù)與適應(yīng)度函數(shù)相關(guān)關(guān)系圖4.19為在MATLAB環(huán)境下利用TikTok計時器獲取的不同代數(shù)對應(yīng)的程序運行時間情況?？梢钥闯瞿Ｐ偷挠嬎銜r間隨著遺傳代數(shù)的增加而增加。在200700代范圍內(nèi)，計算時間與代數(shù)基本呈線性關(guān)系，當(dāng)算法達(dá)到700代以上時，計算時間將顯著增大。綜合考慮模型穩(wěn)定性與時間性能兩個方面的因素，模型選擇遺傳代數(shù)為600。.64.2.0.833332計算吋訶津2.e11112004006008001000世代數(shù)G圖4.19避障路徑規(guī)劃模型中世代數(shù)與計算時間相關(guān)關(guān)系在傳統(tǒng)的遺傳算法中，交叉概率pc

9、與變異概率pm均為常數(shù)，在模型計算時不會發(fā)生變化。然而在解決路徑規(guī)劃問題時，固定不變的參數(shù)值往往會導(dǎo)致模型性能的降低。當(dāng)選擇較大的交叉概率pc時，在模型初始階段可以較大程度的豐富個體類型，增加全局最優(yōu)解的可靠性，但在模型運行的中后段，較大的交叉概率pc則會增加優(yōu)秀個體被破壞的概率，導(dǎo)致模型收斂性降低。反之，如果選擇較小的交叉概率pc值，具有優(yōu)秀性能的潛在個體將很難被開發(fā)出了，影響模型中種群的多樣性，降低全局最優(yōu)解尋找的可能性。同樣的，對于變異操作，當(dāng)選擇較大的變異概率時，每代種群中的優(yōu)秀個體將難以保留，導(dǎo)致收斂性下降。當(dāng)變異參數(shù)較小時，則會拖延最優(yōu)解的開發(fā)過程，影響模型效率。針對這一問題，本文

10、提出了改進(jìn)的遺傳算法避障路徑規(guī)劃模型。改進(jìn)后的模型中交叉概率pc與變異概率pm將隨著模型中種群世代數(shù)與收斂情況作出自適應(yīng)調(diào)整。改進(jìn)后的交叉概率pc與變異概率pm表達(dá)式為：(4.36)k（f-廣）f，一maxfff-favgmaxavgkfr<f(4.37)k（f2-f）；、f3maxff-favgmaxavgkf<f4avg式中：Znax是種群中最優(yōu)性能個體對應(yīng)的適應(yīng)度函數(shù)值；fvg是某代種群中所有個體的適應(yīng)度平均值；是進(jìn)行交叉操作的兩個個體中適應(yīng)度較高的個體；f是進(jìn)行變異操作的個體適應(yīng)度值。且有0<k1,k2,k3,k4<1。進(jìn)一步考慮到模型計算過程中，不同世代數(shù)下的

11、具體要求有所區(qū)別。在模型計算初期，某代種群中的最優(yōu)個體未必是全局最優(yōu)解，而依據(jù)上式，模型未考慮算法初期對種群豐富度的要求，導(dǎo)致較優(yōu)個體基本不發(fā)生變化，因而導(dǎo)致了模型收斂于局部最優(yōu)解的可能。針對這一缺陷，根據(jù)代數(shù)增加過程中個體適應(yīng)度值的具體情況，對自適應(yīng)算子計算公式進(jìn)一步改進(jìn)如下k1fTavg1+efmax-favg0.9-0.2f'nfavg(4.38)f'Vavgk-7251+ef(4.39)”avg-ma-favg丿0.1f<favg依據(jù)上式計算得到的交叉概率pc與變異概率pm可以滿足模型在不同階段對于算子的區(qū)別要求，符合遺傳算法中的計算規(guī)律。當(dāng)種群中的某一個體的適應(yīng)

12、度高于種群平均適應(yīng)度之值時，取較低的交叉概率pc與變異概率pm，這時該優(yōu)解將以較大概率直接進(jìn)入下一代種群當(dāng)中而避免遭到破壞。改進(jìn)后的遺傳算法避障路徑規(guī)劃模型中的算子不僅可以隨適應(yīng)度變化而自主變化，而且可以避免模型沉溺”與當(dāng)前的優(yōu)解中產(chǎn)生停滯，幫助算法能夠跳出局部最優(yōu)解，并能夠以更高效率給出全局最優(yōu)解。2無人機避障模型效果對比分析為了能夠?qū)崿F(xiàn)無人機避障線路規(guī)劃的有效性，模型需要從兩個方面保證所給出路徑的性能：（1）路徑不經(jīng)過障礙區(qū)域；（2）所給出路徑長度為最短。按照本文4.3.1給出的基于遺傳算法的避障路徑規(guī)劃模型，在MATLAB環(huán)境下展開仿真試驗。如圖所示，在待規(guī)劃區(qū)域內(nèi)布置20個障礙柵格。無

13、人機目標(biāo)是由0號柵格移動到99號柵格。為了驗證基于改進(jìn)后的自適應(yīng)遺傳算法的無人機避障路徑規(guī)劃模型的性能，利用基于傳統(tǒng)遺傳算法模型實現(xiàn)的避障模型作為對比。為了增加對比性，對模型參數(shù)進(jìn)行統(tǒng)一設(shè)置如表4.3所示，其中自適應(yīng)遺傳算法中參數(shù)k1=2，k2=0.5。表4.3遺傳算法模型中的參數(shù)設(shè)置參數(shù)名稱參數(shù)值種群規(guī)模（G）30-最大進(jìn)化次數(shù)（MAXGEN）600個體長度（L）18y圖4.20為布置20個障礙區(qū)域時仿真得到的路徑規(guī)劃結(jié)果。路徑一是基于傳統(tǒng)遺傳算法計算得到的路線規(guī)劃方案，對應(yīng)適應(yīng)度函數(shù)值為15。路徑二是基于改進(jìn)后的自適應(yīng)遺傳算法模型獲得的避障線路規(guī)劃方案，對應(yīng)適應(yīng)度函數(shù)為14。路徑一對應(yīng)的計

14、算時間為2.7760s，而路徑二的計算時間僅為0.9841s。yA345678910111)12131415161718192021627282930礦232425231323334356373839404142434445464748495051525354565758.59606162636465066676869771727374：Z57677787980818283848卜86878889909192939495910069798990x圖4.20改進(jìn)前后的遺傳算法路徑規(guī)劃比較事實上，兩種避障路徑規(guī)劃算法模型均存在一定的隨機性，每次規(guī)劃得到的路線也會有所區(qū)別。導(dǎo)致這一現(xiàn)象發(fā)生的原因有兩

15、個，一是算法自身限于局部最優(yōu)解而無法求得全局最優(yōu)解，其二在于問題本身具有多個相同適應(yīng)度函數(shù)值相同的最優(yōu)解。為了能夠更加全面的分析與評估改進(jìn)前后的遺傳算法避障路徑規(guī)劃模型的性能，本文通過在相同的障礙條件下，分別利用兩個避障模型模型進(jìn)行路徑規(guī)劃計算，以此來比較兩個模型的具體效果。具體操作在10X10規(guī)模的區(qū)域內(nèi)分別設(shè)置了5組障礙物個數(shù)Obs為1030的測試區(qū)域，利用兩個模型在每組區(qū)域內(nèi)分別計算30次。圖4.21為不同障礙布置下，兩種模型在某次計算后給出不同路徑規(guī)劃結(jié)果的圖像。103456789101112補乞1161718192021222324¥r6272829303132333435

16、q36373839402434445464748495041451匚J6575859605253545561626364卞6869707172737475278798081828384858687濤蜜909192939495969798991000x(a)Obs=10yA103456789101112補乞1161718192021222324¥26272829303132333435q36373839402434445464748495041451匚6575859605253545561626364656869707172737475278798081828384858687濤蜜90

17、919293949596979899100(b)Obs=15345678910111)12131415161718192021627282930疔23242523132333435q36373839404142434445464748495051525354片J5J65758.59606162636465666768697071727374I57677787980818283848>弋687888990919293949591)069798990x1r»2345678910111213141516171819202162730122232425228293132333435q3

18、63738394014142434445464748495051匚2535455J657585960616263646566676869707172737427677787980818283848586878889909192939495969798991000x(c)Obs=20(d)Obs=25111)345678910121314151617181920262728293012223242523132333435Q3637383940414243444516474849502535455匚65758596051A6162636465666768697071677787980727374"2818283848590878889919293949596|979891000x(e)Obs=30圖4.21改進(jìn)前后的遺傳算法在不同障礙物數(shù)量下的路徑規(guī)劃結(jié)果比較統(tǒng)計每組適應(yīng)度函數(shù)與計算時間的平均值可以得到圖4.22。圖中Model1為基于傳統(tǒng)遺傳算法避障路徑規(guī)劃模型，Model2為改進(jìn)后自適應(yīng)遺傳算法避障路徑規(guī)劃模型?？梢钥闯鲭S著障礙區(qū)域數(shù)量的增加，兩個模型給出的最優(yōu)避障路徑的長度與計算時間均逐漸增加。總體而言，改進(jìn)后的自適應(yīng)遺傳算法模型的優(yōu)化路徑與計算時間均顯著優(yōu)于改進(jìn)前的傳統(tǒng)模型。隨著區(qū)域內(nèi)障礙物分布復(fù)雜程度的增加，傳統(tǒng)遺傳算法的路徑規(guī)劃