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

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

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

3、序號(hào)法對(duì)柵格地圖中的柵格進(jìn)行編號(hào)，兩種方法可以依據(jù)實(shí)際比例相互換算得到。如圖4.15所示為10x10規(guī)模的區(qū)域柵格模型，柵格旁的行列標(biāo)號(hào)為柵格橫縱坐標(biāo)，柵格坐標(biāo)可用于快速獲得該柵格在地圖中的位置。柵格中間標(biāo)號(hào)為柵格序號(hào)，柵格序號(hào)適用于柵格的訪問和路徑的記錄。本文中所說柵格N即指柵格序號(hào)為N的柵格，這個(gè)序號(hào)可以由柵格中心點(diǎn)對(duì)應(yīng)的坐標(biāo)值(x,y)計(jì)算得到，計(jì)算公式為：N=x-10y+99(4.34)同樣的，當(dāng)由遺傳算法優(yōu)化路徑完成后，需要對(duì)路徑進(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)行了介紹。利用遺傳算法實(shí)現(xiàn)無人機(jī)避障路徑規(guī)劃的算法流程如圖所示。圖4.16基于遺傳算法的避障路徑規(guī)劃流程具體的算法內(nèi)容如下：（1）初始化種群。無人機(jī)的運(yùn)動(dòng)路徑表現(xiàn)為一系

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

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

7、當(dāng)遺傳代數(shù)過高時(shí)，模型計(jì)算過程過度冗余，浪費(fèi)計(jì)算資源，同時(shí)使得規(guī)劃過程耗時(shí)過長。因此需要對(duì)遺傳代數(shù)參數(shù)的選擇問題進(jìn)行研究。以圖為例，無人機(jī)以0號(hào)柵格為起點(diǎn)開始運(yùn)動(dòng)，目標(biāo)位置為99號(hào)柵格。顯然在全局無障礙的情況下，路徑一為最佳路徑規(guī)劃。但當(dāng)遺傳代數(shù)不足時(shí)，模型會(huì)給出路徑二、路徑三作為最優(yōu)解，這顯然不能滿足實(shí)際需要。圖4.17無障礙下的路徑選擇在路徑規(guī)劃問題中通常將遺傳代數(shù)G選擇在2001000的范圍內(nèi)。以上述問題為例，在這一范圍內(nèi)對(duì)基于遺傳算法的無人機(jī)避障模型性能進(jìn)行研究與評(píng)估。圖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計(jì)時(shí)器獲取的不同代數(shù)對(duì)應(yīng)的程序運(yùn)行時(shí)間情況?？梢钥闯瞿Ｐ偷挠?jì)算時(shí)間隨著遺傳代數(shù)的增加而增加。在200700代范圍內(nèi)，計(jì)算時(shí)間與代數(shù)基本呈線性關(guān)系，當(dāng)算法達(dá)到700代以上時(shí)，計(jì)算時(shí)間將顯著增大。綜合考慮模型穩(wěn)定性與時(shí)間性能兩個(gè)方面的因素，模型選擇遺傳代數(shù)為600。.64.2.0.833332計(jì)算吋訶津2.e11112004006008001000世代數(shù)G圖4.19避障路徑規(guī)劃模型中世代數(shù)與計(jì)算時(shí)間相關(guān)關(guān)系在傳統(tǒng)的遺傳算法中，交叉概率pc

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

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)性能個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)值；fvg是某代種群中所有個(gè)體的適應(yīng)度平均值；是進(jìn)行交叉操作的兩個(gè)個(gè)體中適應(yīng)度較高的個(gè)體；f是進(jìn)行變異操作的個(gè)體適應(yīng)度值。且有0<k1,k2,k3,k4<1。進(jìn)一步考慮到模型計(jì)算過程中，不同世代數(shù)下的

11、具體要求有所區(qū)別。在模型計(jì)算初期，某代種群中的最優(yōu)個(gè)體未必是全局最優(yōu)解，而依據(jù)上式，模型未考慮算法初期對(duì)種群豐富度的要求，導(dǎo)致較優(yōu)個(gè)體基本不發(fā)生變化，因而導(dǎo)致了模型收斂于局部最優(yōu)解的可能。針對(duì)這一缺陷，根據(jù)代數(shù)增加過程中個(gè)體適應(yīng)度值的具體情況，對(duì)自適應(yīng)算子計(jì)算公式進(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ù)上式計(jì)算得到的交叉概率pc與變異概率pm可以滿足模型在不同階段對(duì)于算子的區(qū)別要求，符合遺傳算法中的計(jì)算規(guī)律。當(dāng)種群中的某一個(gè)體的適應(yīng)

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

13、人機(jī)目標(biāo)是由0號(hào)柵格移動(dòng)到99號(hào)柵格。為了驗(yàn)證基于改進(jìn)后的自適應(yīng)遺傳算法的無人機(jī)避障路徑規(guī)劃模型的性能，利用基于傳統(tǒng)遺傳算法模型實(shí)現(xiàn)的避障模型作為對(duì)比。為了增加對(duì)比性，對(duì)模型參數(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個(gè)體長度（L）18y圖4.20為布置20個(gè)障礙區(qū)域時(shí)仿真得到的路徑規(guī)劃結(jié)果。路徑一是基于傳統(tǒng)遺傳算法計(jì)算得到的路線規(guī)劃方案，對(duì)應(yīng)適應(yīng)度函數(shù)值為15。路徑二是基于改進(jìn)后的自適應(yīng)遺傳算法模型獲得的避障線路規(guī)劃方案，對(duì)應(yīng)適應(yīng)度函數(shù)為14。路徑一對(duì)應(yīng)的計(jì)

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

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

16、q36373839402434445464748495041451匚J6575859605253545561626364卞6869707172737475278798081828384858687濤蜜909192939495969798991000x(a)Obs=10yA103456789101112補(bǔ)乞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)計(jì)每組適應(yīng)度函數(shù)與計(jì)算時(shí)間的平均值可以得到圖4.22。圖中Model1為基于傳統(tǒng)遺傳算法避障路徑規(guī)劃模型，Model2為改進(jìn)后自適應(yīng)遺傳算法避障路徑規(guī)劃模型?？梢钥闯鲭S著障礙區(qū)域數(shù)量的增加，兩個(gè)模型給出的最優(yōu)避障路徑的長度與計(jì)算時(shí)間均逐漸增加。總體而言，改進(jìn)后的自適應(yīng)遺傳算法模型的優(yōu)化路徑與計(jì)算時(shí)間均顯著優(yōu)于改進(jìn)前的傳統(tǒng)模型。隨著區(qū)域內(nèi)障礙物分布復(fù)雜程度的增加，傳統(tǒng)遺傳算法的路徑規(guī)劃