[發明專利]一種基于改進NSGA-II的無人機路徑規劃方法

有效

• 申請號: 202011362427.8
• 申請日: 2020-11-27
• 公開（公告）號: CN112462803B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 譚勵;王浩宇;連曉峰
• 申請（專利權）人: 北京工商大學
• 主分類號: G05D1/10
• 分類號: G05D1/10
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

1.一種基于改進NSGA-II的無人機路徑規劃方法，所述NSGA-II為基于非支配排序遺傳算法NSGA的改進算法，通過指數分布自適應動態調整交叉概率和突變概率，利用定向突變策略改進NSGA-II的隨機突變機制，由此減少計算過程中陷入局部最小值陷阱的風險，從而快速生成三維環境下長度較短且安全無碰撞的無人機飛行路徑；包括以下步驟：

1)無人機路徑初始化；包括：

路徑以坐標系中X、Y、Z三個整數組成的點坐標表示；對每一條待優化路徑通過網格坐標進行編碼，生成編碼數組；編碼數組的形式為長度為L的單鏈表；以編碼數組作為路徑規劃遺傳算法中的染色體進行初始化；隨機產生多條待優化的間斷無障礙可行路徑，即該路徑上的每兩個坐標點不一定直接相鄰，且不屬于預先設置的作為障礙空間的坐標點集合中，多條可行路徑組成的集合即路徑規劃遺傳算法中的種群；

初始化過程如下：

1a)生成待優化間斷無障礙可行路徑，作為初始化路徑；生成的初始化路徑具備可行性和種群多樣性；

預先設置某些點位包圍的空間作為障礙空間，選擇兩個不相鄰的非障礙空間坐標點作為路徑的起點和終點，在起點和終點之間的三維區域中，選擇點位連接形成路徑，具體從每一行列的非障礙空間坐標點里隨機選擇一個空節點，將這些空節點與起點和終點組合在一起，形成一條可能不連續的間斷無障礙路徑，記為I；

1b)對步驟1a)生成的間斷無障礙路徑，連接間斷無障礙路徑的間斷點，生成連續路徑；若無法生成連續路徑，則刪除該路徑；

2)構建無人機適應度函數，用于衡量生成路徑的優化程度；包括航路軌跡長度、航路威脅度和航路隱蔽度；

2a)構建航路軌跡長度，用于盡可能縮短路徑；

通過網格坐標進行編碼的路徑的長度為有序坐標點計算出的路徑長度的總和，表示為公式(3)：

其中，d(P_i,P_i+1)為第i和i+1個點之間的距離,X_i、Y_i、Z_i代表i點的三維坐標，X_i+1、Y_i+1、

Z_i+1代表i+1點的三維坐標，f₁為航跡軌跡長度適應度函數值；

2b)構建航路威脅度，用于優化計算并決策路徑上的軌跡平滑情況；當平滑情況超出預定值時，威脅度上升；

航路威脅度通過兩個相鄰坐標點計算得出，如式(4)：

式(4)中，α_i為兩個相鄰坐標點的航路威脅度，atan為正切函數，X_i、Y_i、Z_i代表i點的三維坐標，X_i+1、Y_i+1、Z_i+1代表i+1點的三維坐標，d(P_i-1,P_i)為第i-1和i個點之間的距離，d(P_i,P_i+1)為第i和i+1個點之間的距離，f₂為威脅度適應度函數值；

2c)構建航路隱蔽度，用于計算并決策路徑的安全程度；

航路隱蔽性與航路飛行高度，航路與障礙物距離相關，計算公式如式(5)：

其中，h_max代表環境中最高點的高度，d_safe為預設常量，代表安全距離，X_i、Y_i、Z_i代表i點的三維坐標，X_i+1、Y_i+1、Z_i+1代表i+1點的三維坐標，d(P_i-1,P_i)為第i-1和i個點之間的距離，d(P_i,P_i+1)為第i和i+1個點之間的距離，S_i、S_j和f₃均為相應條件下的隱蔽度適應度函數值；

3)進行非支配排序，得到多個等級的非支配層，每個非支配層都包含多個路徑個體；

多個等級的非支配層中的路徑個體組成的集合，記為種群I_fa，使得初始化生成的隨機路徑組成的父路徑集合即種群I_fa中，較優的路徑個體有更大的機會遺傳給下一代；

非支配排序用于對初始化種群進行分層以優化產生第一代子種群，包括如下步驟：

3a)假設初始化N條路徑的集合，令路徑種群I規模為N，j、g均為整數，j＝1，g＝1,2,3…，g≠j；

3b)對于I中的所有路徑個體，基于適應度函數比較路徑個體X_j和路徑個體X_g之間的支配與非支配關系，當X_j的適應度函數值小于X_g的適應度函數值，則X_j優于X_g，即X_j支配X_g；

3c)若不存在任何一個路徑個體X_g優于X_j，則X_j被標記為非支配路徑個體；

3d)令j＝j+1，轉到步驟3b),直到找到所有的非支配個體并進行標記；

通過上述步驟得到的非支配路徑個體集是路徑種群的第一級非支配層，也是最高層，作為較優個體，在后續遺傳優化迭代過程中保留；

然后,循環執行步驟3a)-3d),從剩余的個體中計算并劃分得到非支配個體集合作為第二級非支配層；直到整個種群被分類排序，得到多個等級的非支配層，每個非支配層都包含數個路徑個體，非支配層等級越低，其中路徑個體在后續過程中的優化優先度越高，此時的種群為I_fa；

4)利用遺傳算法，輸入種群I_fa，得到優化后的路徑集合子代種群I_son；

經過一次優化產生的路徑組成第一代子種群，子種群與父種群合并，產生多條新的路徑組成的合并種群作為快速非支配排序的輸入；

5)進行快速非支配排序，得到包含多個等級非支配層的路徑集合：對合并后的路徑種群P進行快速非支配排序，使得較優路徑個體有更大概率遺傳給下一代，同時降低了非支配排序計算復雜度；

通過快速非支配排序，將路徑集合I_fa和路徑集合I_son合并成為新的路徑種群P，并對其進行非支配性分層；包括如下步驟：

5a)對合并后的路徑集合P中每個路徑個體p計算n_p和S_p兩個參數，n_p為種群中可以支配個體p的所有個體的數量，即兩相比較之后適應度函數值小于p的路徑個體的數量；S_p為被p所支配的所有個體集合，即兩相比較之后適應度大于p的路徑個體的集合；

5b)對于集合F₁中的每個個體i，其所支配的個體集合為S_i，S_i中的個體均為至少處于第二非支配層的個體，即適應度函數值可以被優化的路徑個體； 遍歷S_i中的每個個體h，執行n_h＝n_h-1，當n_h＝0時，將個體h保存在集合H中，此時H中的全部個體均為只被第一非支配層的個體支配的個體；

5c)將F₁中得到的個體作為第一非支配層的個體，H作為當前集合；

5d)重復5b)操作，直到種群分層完成，得到包含多個等級非支配層的路徑集合；

6)通過擁擠度計算和比較，生成新一代父種群：

擁擠度指的是給定個體的周圍個體的密度，用于提高種群多樣性，避免超級個體的過度繁衍；在路徑規劃中，通過擁擠度避免兩條相似路徑的產生，提高生成路徑的多樣化；包括：

6a)每個路徑個體的擁擠度定義為n_d，基于適應度函數值f對種群中的路徑個體進行排序；

6b)設處于排序邊界，即函數值最高和最低的兩路徑個體擁擠度為無窮大；

6c)計算擁擠度：n_d＝n_d+(f(i+1)-f(i-1))；

根據非支配排序n_rank和擁擠度n_d進行任意兩路徑個體的支配順序比較，比較算子定義為符號“≥n”；當i≥n j，則個體i優于個體j，即路徑j比路徑i在待優化優先度上更高，當且僅當i_rank＜j_rank或i_rank＝j_rank且i_d＞j_d；

根據快速非支配排序和擁擠度排序得到排序結果，對種群中的所有路徑的優化優先度進行區分，根據路徑個體的優化優先度進入遺傳操作流程，迭代產生新的子代種群，得到優化路徑；

7)對交叉概率和突變概率進行自適應調整，以尋找最優解；

通過迭代次數和種群信息動態調整交叉概率和突變概率；在迭代的早期，交叉概率和突變概率采用較大的值；在迭代的后期，將交叉概率和突變概率調整為較小的值；改進的交叉概率和突變概率計算方式表示為式(6)：

其中，G代表最大迭代次數，g代表當前迭代次數，P_c為交叉概率，P_cmax為交叉概率最大值，P_cmin為交叉概率最小值，P_m為突變概率，P_mmax為突變概率最大值，P_mmin為突變概率最小值；

8)利用改進的突變概率計算方式進行遺傳操作，包括：

8a)采用的隨機突變策略表示為式(7)：

其中，F是比例因子，為(0,1)之間的常量；為突變策略中的一個向量，代表帶有較優適應度函數值的路徑個體；代表具有隨機信息的隨機基礎向量，即不含有較優適應度函數值的路徑個體；為差向量；

8b)采用定向突變策略，將最優個體引入突變算子，向最優方向迭代，表示為式(8)：

其中，為當前路徑種群內的最優路徑個體，該最優路徑個體具有當前種群內最優路徑對應的適應度函數值；

9)得到子代種群，返回步驟5)繼續執行，直至滿足迭代次數；

改進NSGA-II方法迭代結束后，輸出滿足優化條件的路徑，即實現基于改進NSGA-II的無人機路徑規劃。