多子群社會群體優化算法的無人機航跡規劃

項峻松

（浙江交通職業技術學院，浙江 杭州 311112）

1 引言

無人機可以在極端環境下進行高效作業，在軍用和民用等領域得到廣泛應用。無人機飛行航跡不僅影響其工作效率，而且對無人機飛行安全也有至關重要的影響［1］。因此研究無人機航跡規劃具有重要的安全意義和經濟意義。

無人機航跡規劃是指在滿足自身動力學約束、航程約束等約束條件下，規劃出一條某種意義下最優的航跡［2］。無人機航跡規劃可分為節點生長類方法和智能算法類規劃方法，節點生長類方法是以航跡起始點為始節點，不斷向目標點生長從而規劃出航跡，包括A*算法、Dijkstra算法等，文獻［3］將航跡規劃分為靜態規劃和動態規避兩個步驟，動態規避航跡使用A*算法的節點生長方法；文獻［4］在元細胞環境模型下，使用改進D*算法進行路徑規劃，與D*算法相比減少了轉彎次數和規劃時間。智能算法類規劃方法，通過建立模型將航跡規劃問題轉化為尋優問題，包括人工魚群算法［5］、人工蜂群算法［6］、粒子群算法［7］等。智能算法類航跡規劃質量主要受兩方面影響，一是模型精度，二是智能算法的性能。

這里以二維環境下無人機航跡規劃為研究對象，建立了威脅模型和航跡規劃模型，提出了多子群社會群體算法的規劃方法。在社會群體算法基礎上，將個體分為多個子群，通過對提高階段和獲得階段改進、子群間信息交流，實現了提高算法種群多樣性和尋優能力的目的，最終規劃出航程短且安全性高的航跡。

2 威脅分析及規劃模型

2.1 航跡生成方法

這里研究內容是無人機在二維環境下的航跡規劃問題，此時無人機在定高度飛行，或飛行高度起伏不大。為了簡化軌跡表達方法，這里直接將坐標系的OX軸建立在起點與終點連線上，然后將起始點與目標點間的線段等分成N段，只需規劃出各等分點處的縱坐標值（y值）就實現了航跡規劃，如圖1所示。

圖1 航跡生成方法Fig.1 Route Generating Method

2.2 威脅分析

無人機在特定高度飛行時，可能遭受的威脅包括山體等障礙物的碰撞威脅、雷達的探測威脅、導彈火炮等的打擊威脅等，下面具體分析。

（1）雷達的探測威脅。在理想情況下，雷達的探測范圍是一個半球形，但是考慮到雷達的探測角限制，雷達的實際探測范圍是一個近似圓錐形。在特定高度上，雷達探測范圍可視為圓形［8］，即：

式中：R—圓形探測區域半徑，半徑大小根據探測能力確定。

雷達通過接收探測無反射的回波捕捉目標，捕獲概率與回波質量有關，雷達接收的回波功率為：

式中：Pr—雷達接收功率；Pt—雷達發出功率；Gt—發射天線增益；λr—雷達波長；σr—被探測目標反射面積；Ft—傳播因子；dr—目標與雷達間距離，且為無人機飛行高度；drt—飛行面內無人機與雷達距離。

（2）導彈的打擊威脅。導彈的對空打擊具有最小攻擊角和最大攻擊角限制，從三維看，類似于中空的圓錐形，在特定高度的二維平面上，導彈打擊范圍為一個圓環，如圖2中陰影部分所示。圓環的內半徑r與外半徑R由最大最小攻擊角及飛行高度確定。

圖2 導彈打擊區域Fig.2 Missile Striking Area

導彈對無人機的命中概率與兩者間的距離無直接關系，只要無人機在導彈攻擊范圍內，命中概率與導彈的性能具有直接關系，因此為了保證無人機的絕對安全，這里將導彈打擊區域設置為禁飛區，即第i條航跡li受導彈打擊威脅為：

式中：Jsi—第i條航跡受的打擊威脅；

Rs—導彈打擊區域的外半徑；

di—第i條航跡li與導彈的最短距離。

（3）障礙物威脅。無人機飛行過程中的障礙物包括山體、高樓等，高樓的二維投影圖一般為方形，因此根據投影圖尺寸使用方形表示高樓障礙物。對于單山峰地形，山體在特定高度的截面類似于圓形，因此使用圓形代表山體障礙物。將障礙物對無人機威脅設置為無窮大，即無人機航跡必須完全避開障礙物區域，在實際操作時，將障礙物威脅取為較大值，則第i條航跡li受障礙物威脅為：

式中：Sobs—障礙物區域；

M—較大常值，可取為100。

綜合以上分析，無人機在整個飛行過程中受到的雷達探測、導彈打擊、障礙物等的綜合威脅J為：

式中：N—航跡段數量。

2.3 航跡規劃目標函數

航跡規劃的目標是在滿足無人機轉彎、航程等約束條件下，規劃出一條飛行安全、航程最短的航跡。按照圖1的航跡生成方法，得到航跡長度為：

式中：li—第i條航跡的長度。

由式（6）和式（7）得到航跡規劃的目標函數為：

式中：w1、w2—安全系數和航程系數，其作用是：（1）調節兩優化指標處于同一數量級；（2）調節優化重心，通過取值不同得到不同側重點的優化結果。

2.4 約束條件分析

對于二維環境下的無人機航跡規劃，其約束條件包括航程約束和轉彎角約束。

2.4.1 航程約束

由于無人機攜帶的燃料有限，在進行航跡規劃時，從起點至終點的航跡長度不能超過無人機最大航程，記無人機最大航程為lmax，則：

2.4.2 轉彎角約束

這里指出，規劃出航跡縱坐標{y1，y2，…，yN-1} 后使用B 樣條均值曲線對航跡進行平滑處理，若使用等分點處的轉彎角給出約束條件則有些不符合實際情況，這里使用等分點處的轉彎半徑進行約束，記無人機的最小轉彎半徑為rmin，則：

式中：ri—各等分點處的轉彎半徑。

3 多子群社會群體優化算法

通過第2節的建模過程，將航跡規劃問題轉化為帶約束條件的優化問題，本節提出了多子群社會群體優化算法用于求解此優化模型。

3.1 社會群體優化算法

當個體能力不足以解決復雜問題時，個體需要向周圍其他個體或擁有此能力的個體學習，社會群體優化算法就是基于這一思想提出的，包括種群初始化、提高階段、獲得階段三個步驟完成［9］。

3.1.1 種群初始化

記種群規模為D，使用隨機方式初始化種群，為：

式中：xij—第i個個體在第j維上的取值，i=1，2，…，D，j=1，2，…，N-1；xjmax、xjmin—j維上最大值和最小值；rand(0，1)—（0，1）上的隨機數。

3.1.2 提高階段

在提高階段，個體向群體最優學習，從而獲得解決問題的能力，方法為［10］：

式中：c∈(0，1)—自我反省參數，其經驗值為c=0.2；gbestj—最優個體在第j維上的取值。

3.1.3 獲得階段

在獲得階段，從種群中隨機選取一個個體作為學習對象，并結合全局最優信息對自身位置更新，方法為［10］：

若個體i優于個體k，則位置更新方法為：

若個體i劣于個體k，則位置更新方法為：

式中：rand1、rand2—（0，1）間的隨機數。

3.2 多子群社會群體優化算法

由3.1節可以看出，在算法的提高階段和獲得階段，個體均向當前最優個體學習，這種單目標或單向學習方式雖然能夠加速算法收斂，但是嚴重破壞了種群多樣性，極易導致算法早熟，尤其當前最優為局部極值時，會引導算法陷入局部最優。為了改善算法搜索過程中的種群多樣性，提出了多子群社會群體優化算法。首先按照等分原則，將D個個體等分為E個子群，不能等分時，將多余粒子隨機分配到若干子群中。

3.2.1 改進提高階段

在多子群算法中，提高階段按照就近向“好同學”學習的原則，向子群最優個體學習，使其在局部區域內獲得能力增長，為：

式中：abestj—子群a最優個體在j維上的取值。

3.2.2 改進獲得階段

為了兼顧學習范圍的局限性和學習方法的多樣性，在知識獲得階段，提出三種知識來源：一是子群內其他個體，二是任意子群的最優個體，三是整個種群的最優個體。這種多渠道知識獲取方法和學習方法，對提高種群多樣性具有重要意義。基于以上思想，個體i的學習和更新機制為：

若個體i優于個體k，則：

若個體i劣于個體k，則：

式中：xkj—與個體i處于同一子群內的個體k在j維上的取值；abestj—任意子群a的最優個體在j維上的取值；gbestj—種群最優個體在j維上的取值。

3.2.3 子群重組與信息交流。

算法搜索過程中只關注最優個體，而不關注種群均值，因此算法改進應傾向于增加種群多樣性使種群在搜索區域較為平均地分布。隨著算法的迭代進行，個體必然向較優區域靠攏，就導致個體聚集度越來越高而多樣性越來越差，為了維持種群多樣性，每當算法迭代一定次數后，將子群重新隨機分配，分配方法依然使用等數量隨機分配。記子群重新分配的迭代周期為T，T越大有利于種群收斂，T越小有利于種群多樣性。

3.3 多子群社會群體優化算法流程

根據3.2節對多子群社會群體優化算法的描述，制定算法流程，如圖3 所示。圖中：iter—當前迭代次數；mod—取余函數；itermax—最大迭代次數。

圖3 多子群社會群體優化算法流程Fig.3 Multiple Subgroups Social GroupOptimizing Algorithm Flow

4 仿真驗證與分析

本節對兩個方面的內容進行驗證：（1）驗證多子群社會群體優化算法的多樣性和尋優性能；（2）驗證多子群社會群體優化算法在航跡規劃中的性能。

4.1 多子群算法的種群多樣性和性能測試

種群多樣性的計算方法有多種，包括所有個體的平均漢明距離、所有個體與群體中心距離之和、所有個體與群體中心距離熵等，這里使用平均漢明距離計算種群多樣性。

種群中個體pi與pl間的距離H(pi，pl)為：

兩者的歸一化距離為：

所有個體的平均漢明距離為：

多子群社會群體優化算法參數設置為：種群規模D= 50，子群規模為10，算法最大迭代次數為400，選擇標準測試函數中的Schwefel 函數和Rotated Schwefel 函數進行性能測試，兩函數維度均設置為50，自變量變化范圍為［-500，500］，在此范圍內的函數最小值均為0。兩種算法對兩種測試函數均獨立運行30次，隨機選擇某次算法迭代過程中，種群多樣性變化過程，如圖4所示。

圖4 迭代過程中種群多樣性測試Fig.4 Population Diversity Test in the Iteration Process

從圖4中可以看出，對Schwefel函數尋優時，在前30次迭代過程中，社會群體算法的種群多樣性急劇下降，而多子群社會群體算法的種群多樣性雖然經歷了下降過程，但是經過子群重組和信息交流，種群多樣性又恢復到較高水平。對Rotated Schwefel函數的尋優過程中，多子群社會群體算法的種群多樣性也保持較高水平，總體上遠遠大于社會群體算法，說明這里的改進措施對增加算法的種群多樣性具有明顯效果。

兩種算法對兩種基本測試函數的尋優結果，如表1所示。

表1 測試函數的尋優結果Tab.1 Optimizing Result of Different Testing Function

由表1可以看出，通過增加物種多樣性的方式提高了算法的最優解精度，相比于傳統的社會群體算法，多子群算法搜索的測試函數最優解均提高了一個數量級，但是尋優結果的平均值相差不大，這是因為通過增加種群多樣性，使個體在搜索空間較為均勻的分布，必然會留有較多劣質解拉低平均值。這里只關注種群中的最優解，因此多子群社會群體算法的尋優能力遠遠優于傳統算法。而且從方差上看，多子群算法的尋優穩定性優于傳統算法。

4.2 航跡規劃結果及分析

為了驗證多子群社會群體算法在航跡規劃中的性能，使用MATLAB R2014a軟件進行仿真實驗。算法種群規模D=50，子群規模為10，算法最大迭代次數為400。無人機飛行環境設置在（100×100）km2區域內，起點為（10km，10km），目標點為（90km，90km）。航跡等分點數設置為N=21，航跡點搜索范圍為［0，100km］。環境中的威脅設置，如表2所示。

表2 威脅分布情況Tab.2 Distribution of Every Threaten

分別使用社會群體優化算法和多子群算法規劃從起始點到目標點的航跡。兩種算法各獨立運行20次，挑選出兩種算法各自的最優航跡結果，如圖5所示。圖中陰影覆蓋的圓形威脅為山體，陰影覆蓋的方形威脅為建筑物，其余圓形威脅為雷達、導彈威脅等。實線為使用多子群社會群體算法規劃的航跡，虛線為使用傳統社會群體算法規劃的航跡。

圖5 不同算法規劃的航跡Fig.5 Route Planned by Different Algorithm

由圖5可以看出，多子群算法規劃的航跡明顯短于傳統算法規劃的航跡，從受威脅程度看，兩個航跡在威脅2邊沿處轉彎時受的威脅最大，航跡其余段均絕對安全。經統計，傳統算法在迭代至100代時適應度不再下降，搜索的目標函數值為103.25；多子群算法在算法迭代至40代時搜索到最優值，目標函數最優值為96.38，相比于傳統算法減少了6.65%。綜合圖5和統計數據可知，多子群社會群體算法規劃的航跡長度和安全性方面均優于社會群體算法規劃的航跡，且算法完成收斂的迭代次數大大減少，這是因為多子群算法將個體分為多個子群，通過對提高階段、獲得階段進行改進，使個體通過多渠道獲得知識，實現了學習方式多樣性；而且通過子群重組實現了子群間的信息交流，維持了算法在整個迭代過程中的種群多樣性，最終實現了提高算法搜索能力的目的。

5 結論

這里研究了無人機的二維航跡規劃問題，提出了多子群社會群體算法的規劃方法。經過仿真實驗得出了以下結論：（1）通過對提高階段、獲得階段的改進和子群間信息交流，提高了算法的種群多樣性和尋優能力；（2）多子群社會群體算法規劃的航跡在長度和安全性方面均優于社會群體算法。