基于模擬退火和改進遺傳算法的無人機風電檢測動態路徑最優規劃模型

林陽芷，董佳琦，秦李朝政

（長沙理工大學，湖南 長沙 410114）

0 引 言

風電產業作為清潔能源的先行者，已經成為推動能源轉型發展的中堅力量。由于風電運作需要大風場，因此風電葉片在運轉過程中要承受很大的拉應力、風的沖擊力及葉片震動帶來的剪切應力，在沙漠地區還會不斷受到風沙侵襲，-30℃至50 ℃的循環溫差，以及強紫外光的老化等。在這些因素影響下，風電葉片很容易受到損壞，如不能及時檢測出受損位置并加以維護，將會降低發電機性能、影響機組壽命、造成經濟損失，嚴重甚至將引發安全事故從而會影響整個風電系統的運作。而現行風葉運維仍多以人巡為主，需要大量人工且效率低；無人機風電巡檢控制存在諸多不穩定因素，極易發生“撞塔”事故；風電葉片檢測系統亟待優化，因此，以無人機為主的高效、安全、智能一體化風電運維方案具有極大現實意義。

但是現行關于風電場無人機系統研究善處于初級階段，關于風電場系統中無人機動態路徑規劃相關研究內容少之又少。近年來，在關于無人機路徑規劃研究中，周永濤、劉唐等以最大吞吐量為目標，計算每個時隙無人機飛行動作，實現單路徑規劃，但是忽視了多無人機場景下無人機總體最優布局。孫雪瑩、易軍凱針對傳統路徑規劃算法不足，采用了粒子群混合算法，進一步提高計算速度與求解最短路徑質量，但仍適用于單臺無人機三維路徑規劃?，F行研究多集中于單無人機場景下路徑最優，多無人機場景下路徑規劃模型少之又少。

本文針對單無人機模型運行場景，首先引入模擬退火算法（Simulated Annealing, SA），定義節點的實對稱矩陣D，以檢測無人機經過節點的路徑長度為目標函數，通過2變換法和代價函數差求解得出最短距離。后通過遺傳算法校正分析，優化模型。為了使得模型適配多臺無人機場景下檢測情況路徑最優規劃。本文以同時派出四個檢測無人機為例進行模型建立，我們引入優化遺傳算法（Genetic Algorithm,GA）提出了一種起點可尋優的多旅行商問題模型，設計一種編碼方式，在算法過程中對配送中心位置進行尋優，確定目標函數，從而求解得出四個檢測無人機的最優充電路徑。經仿真測試，本文所用模型方法可以較簡單快速適配多無人機檢測風電情況。

1 問題描述與假設

風電葉片智能運維對提升風電機組性能、減少風電機組安全事故具有重要意義。風電場系統中包括若干風電機組群（Wind turbine generator system）、一個數據中心（Data Center）、一個或多個具有缺陷檢測功能無人機（Unmanned aerial vehicle （UAV）），是一種分布式網絡。數據中心和若干風力發電機分布在一個隨意設置的二維空間，無人機從數據中心出發，以固定速度依次經過風電機，在每臺風電機處停留一段時間并以固定速率進行葉片檢測，直到所有風電機葉片完成內外缺陷檢測完成之后返回數據中心，所探討具體問題假設如下：

（1）由于無人機飛行距離遠大于無人機的長度、寬度以及風電機和數據中心的體積所造成距離偏差，所以無人機、風電機、數據中心類物理中的質點處理。

（2）假定無人機飛行距離為最小直線距離，忽略由于地形、道路影響所造成的飛行距離偏差。

（3）假定無人機在數據中心已充滿足夠電量，其電量可供所經過的風電機檢測所需。

2 單個無人機最小能量損耗的充電路線

2.1 每臺風電機之間的位置

將所給每臺風電機的經緯度數據導入到MATLAB中，通過數據分析處理得到每臺風電機與數據中心的位置關系圖，如圖1所示（其中，十字點為數據中心，星號點為風電機位置）。

圖1 風電機與數據中心的位置關系圖

2.2 每臺風電機與數據中心的距離求解

2.2.1 地理坐標的換算

根據所給每臺風電機節點的經緯度地理坐標，依據問題假設，將風電機看作質點，因為無人機飛行過程中，多在兩點之間直接移動，求解檢測路線最優規劃時，首先需計算各點之間的最小實際距離。假設兩質點為A與B，兩者的地理坐標分別為（x，y），（x，y），則A，B兩質點之間實際距離即為大圓的劣弧長長度。以地心為坐標O，以赤道平面為XOY平面，以0度經線圈所在的平面為XOZ平面建立三維直角坐標系。則A，B兩點的直角坐標分別為

式中：R=6 370 km為地球半徑。

A，B兩點的實際距離：

化簡可得任意兩點距離計算公式為：

2.2.2 建立距離矩陣

假設風電場系統中數據中心為編號1，目標風電機依次編號為2，3，…，30，最后數據中心再重復編號31。距離矩陣D=（d），其中d表示i，j兩點的距離，i，j=1，2，…，31，這里D為是對稱矩陣。

2.3 模擬退火算法模型建立

根據模擬退火算法原理的闡述，得以模擬退火算法具體求解流程如下：

2.3.1 解空間

設定解空間S可表示為{1，2，…，31}，所有固定起點和終點正如上文建立距離矩陣，依次編號并進行排列集合，初始點循環，即：

其中：每一個循環排列表示檢測無人機對29臺風電機檢測的一個回路，π=j為在第i-1次檢測目標風電機j，初始解可選擇為（1，2，…，31）。

2.3.2 目標函數

以距離矩陣為自變量，無人機檢測所有風電機檢測的最小路徑規劃長度為因變量建立對應目標函數。要求依次迭代，具體由下列三步構成。

2.3.3 新解的產生

設第一步迭代的解為：

進行2變換，任選序號u，v，交換u與v之間的順序，變成逆序，此時的新路徑為：

2.3.4 代價函數差

對于2變換法，路徑差可表示為：

2.3.5 接受準則

如式（9）所示，若Δf＜0，則說明所求得新解小于原解，新解為更優路徑，則接受新的路徑；若Δf＞0，則以概率e極低概率接受新的路徑?？衫斫鉃橥ㄟ^加入rand函數，系統自動產生一個[0，1]區間上均勻分布的隨機數，若所產生rand函數值滿足rand≤e不等式，則接受新路徑。

2.3.6 降溫

利用選定的降溫系數α進行降溫，取新的溫度T為αT，這里的T為上一步迭代的溫度，這里選定α=0.999。

2.3.7 結束條件

判斷退火過程是否結束，通過選定指定終止溫度e進行判斷，本文假設e=3。若T＜e，滿足所給降溫條件，則直接輸出當前狀態。

2.4 模型求解結果

首先將1個數據中心和29個風電機位置的經緯度坐標數據導入到MATLAB中，利用經緯度距離公式，導出距離矩陣，后代入原先所編寫好的模擬退火算法程序。無人機運動路徑（path）、運動路徑長度（long）、選定終止溫度（e）、循環次數（?）、降溫系數（α）等參數默認與坐標距離求解程序參數相同，程序循環10 000次，取相對最優解。

MATLAB的運行結果為：

path：

0 -＞ 1 -＞ 2 -＞ 20-＞9-＞ 8 -＞ 12 -＞ 10 -＞ 13-＞ 16-＞ 27-＞15-＞ 14 -＞ 11-＞ 6-＞ 7-＞ 18 -＞ 25 -＞ 26 -＞ 29 -＞ 19 -＞ 17 -＞ 21 -＞23 -＞24-＞ 28 -＞ 22 -＞ 4 -＞ 3-＞5 -＞0 （0表示數據中心，其他數字表示風電機數字）

long：12.2552km

具體如圖2所示（其中，十字為數據中心，星號為風電機）。

圖2 檢測無人機實際距離最優化路程規劃圖

檢測無人機移動的實際最小距離為12.255 2 km，由于正時針走向與逆時針走向總路程不變，因此無人機最小化能量消耗的具體行程有順逆時針兩種走法：

逆時針走法：數據中心→風電機1→風電機2→風電機20→風電機9→風電機8→風電機12→風電機10→風電機13→風電機16→風電機27→風電機15→風電機14→風電機11→風電機6→風電機7→風電機18→風電機25→風電機26→風電機29→風電機19→風電機17→風電機21→風電機23→風電機24→風電機28→風電機22→風電機4→風電機3→風電機5→數據中心（順時針即為反向）。

2.5 模擬退火模型的改進結果

模擬退火算法雖然具有局部搜索能力強、運行時間短的優點，但具有全局搜索能力差，容易受到參數的影響的缺點。為了使模型更加準確，采用遺傳算法改進現有的模擬退火算法，以此得出檢測無人機行駛最小距離最優值，改進結果如圖3所示。

圖3 檢測無人機實際距離最優化路程規劃圖（遺傳算法）

求解得，檢測無人機移動的實際最小距離為11.481 5 km，同樣由于順時針走向與逆時針走向總路程不變，因此移動無人機最小化能量消耗的具體行程有順逆時針兩種走法：

順時針走法：數據中心→風電機2→風電機1→風電機9→風電機7→風電機6→風電機14→風電機11→風電機8→風電機12→風電機15→風電機27→風電機16→風電機13→風電機10→風電機5→風電機3→風電機4→風電機22→風電機28→風電機24→風電機23→風電機21→風電機29→風電機26→風電機25→風電機18→風電機19→風電機20→風電機17→數據中心（逆時針即為反向）。

3 多個移動檢測無人機情況下最優路程規劃與風電機電池容量最優解（以四個為例）

3.1 遺傳算法多旅行商模型建立

用遺傳算法研究關于多個移動檢測無人機情況下最優路程規劃，可看作多旅行商問題模型建立。

本程序需具備的條件有：（1）每臺檢測無人機均從數據中心出發，最后需返回數據中心，且每臺移動檢測無人機行駛過程中不重復經過同臺風電機節點。（2）除了第一個條件外，每臺風電機節點有且只能被一臺檢測無人機檢測一次。

所建立具體模型的參數設定如下：

檢測無人機數=4；種群大小M=80；最大代數G=5 000；理想迭代次數（NUMITER）=10 000；交叉率p=1，交叉概率為1能保證種群的充分進化；變異率p=0.1，一般而言，變異發生的可能性較小，

根據所設經緯度數據，計算兩個風電機節點距離需經緯度轉化坐標可得。因此，根據單位經緯度長度公式得：緯度1°=111.194 km，緯度36°左右時經度1°= 89.469 km。導入所給各風電機節點經緯度數據成為坐標數據，后利用數據中心和29個風電機節點坐標數據，得到各個節點的距離。

3.1.1 編碼策略

由于遺傳算法主要原理為染色體交匯變異，在一般解空間表示中，大多采用二進制編碼形式，但是由于本問題為多旅行商問題，該模型使用二進制編碼方式不宜表示相應解，因此本模型所采用的遺傳算法需要用特殊的修補算子來修復變化算子所產生的非法路徑（即不可行路徑）。根據上文所得數據中心與29個風電機編號，相應解用十進制數編碼表示更加直觀判斷無人機最優路徑，如上文數據中心編號為1，風電機1編號為2，風電機2編號為3……以此類推，風電機29編號為30。

遺傳算法采用十進制編碼，隨機數列w，…，w作為染色體，其中0≤w≤10（i=2，3，…，30）；每個隨機序列都和種群中的個體相對應。例如，目標3的一個染色體為：

[0.82，0.29，0.73，0.38，0.78，0.56，0.87，0.62，0.11]

式中：編碼位置i為數據中心或風電機節點，位置i所對應染色體所產生隨機數表示目標i在巡回中的順序，將這些隨機數按升序排列得到如下巡回：9-2-4-6-8-3-5-1-7

3.1.2 初始種群

采用經典改良圈算法可求得一個較優質初始種群，對于隨機產生的四個初始圈：

交換u與v、w與x、y與z、a與b之間的順序，此時四個無人機新路徑為：

3.1.3 目標函數

函數因變量為4臺無人機僅經過一臺風電機情況最短路徑長度，算法中適應度函數即為目標函數：

3.1.4 交叉操作

為了算法簡便化，更快求出所需解，本算法采用單點交叉操作形式。設f和f為C的兩個父代個體，其值假設為f=ww…w，f=w′w′…w′，隨機地選取第t個基因處為交叉點，經過交叉運算后，所得到新式即為子代個體Z和Z，其中Z的基因由f的前t個基因和f的后31-t個基因構成，Z的基因由f的前t個基因和f的后31-t個基因構成，例如：

若交叉點為第4個基因處，則：

C，C，C的交叉操作同C，在交叉操作過程中，正是子代不斷進化的過程，交換選擇方式多樣，為了能保證子代繼承父代的優良特性，變異操作在交叉操作運行過程中也同樣有所體現。

3.1.5 變異操作

3.1.6 選擇操作

最終確定結果，即選擇路徑數值最小的解。從遺傳算法層面來說，即在父代種群和子代種群變異過程中，通過不斷篩選目標函數值最小的M個體進化到下一代，以此不斷進行，變換與選擇過程中同樣需保證保存父代的優良特性。

具體流程圖如圖4所示。

圖4 遺傳算法多旅行商問題算法具體流程圖

3.2 優化遺傳算法求解結果

將每個風電機和數據中心節點的地理經緯度坐標代入MATLAB程序中，程序循環10 000次，取相對最優解。

MATLAB的運行結果為：

path：

C1：0 -＞ 1 -＞2-＞ 0

C2：0 -＞ 3 -＞ 28 -＞ 24 -＞23 -＞ 22 -＞ 21 -＞ 4 -＞ 0

C3：0 -＞5 -＞10-＞13-＞16-＞27 -＞ 15 -＞ 12 -＞8 -＞ 11 -＞ 14-＞6-＞7-＞9 -＞ 0

C4：0 -＞ 17 -＞ 19 -＞ 29 -＞ 26 -＞ 25 -＞ 18 -＞ 20 -＞ 0

（0表示數據中心，其他數字表示風電機數字）

Distance：

C1：0.9535 km

C2：3.4981 km

C3：4.7231 km

C4：4.0247 km

long：13.1994km

四臺檢測無人機移動的實際最小距離總和為13.199 4 km，充電具體路徑如圖5所示，由于正時針走向與逆時針走向總路程不變，因此檢測無人機最小化能量消耗的具體行程有順逆時針兩種走法：

圖5 四臺檢測無人機實際距離最優化路程規劃圖

逆時針走法：

C1：數據中心→風電機1→風電機2→數據中心；

C2：數據中心→風電機3→風電機28→風電機24→風電機23→風電機22→風電機21→風電機4→數據中心；

C3：數據中心→風電機5→風電機10→風電機13→風電機16→風電機27→風電機15→風電機12→風電機8→風電機11→風電機14→風電機6→風電機7→風電機9→數據中心；

C4：數據中心→風電機17→風電機19→風電機29→風電機26→風電機25→風電機18→風電機20→數據中心（順時針即為反向）。

3.3 遺傳算法模型結果的檢驗

為了測試得到相對優良的結果，并且考慮到增加局部搜索的能力，子代代數越大，變異的概率也相應有一定的增大。因此，我們對種群規模、迭代次數、交叉概率和突變概率做了相應的一些變化，測試了多組數據，如表1所示。

表1 多種參數條件下的充電路徑路程

注：由于每次產生后代都是在隨機概率情況下進行交叉和變異，在迭代次數固定情況下，以上最小總路程是經過多次試驗后取得的最優解；在迭代飽和的情況下，以上最小總路程是以人為觀察隨迭代次數增加其不變的取值，最小總距離有一定的誤差。

經過多次調整參數進行實驗，當種群規模為80，迭代次數為2 000，交叉概率為0.65，突變概率為0.05時，檢測路徑的總路程最優解為13.199 4 km。

4 結 論

本文構建了基于模擬退火和改進遺傳算法無人機風電檢測最優路徑模型，很好解決了檢測無人機最小化路線規劃問題，具有一定合理性，模型具體優缺點如下：

（1）建立的模型能與實際緊密聯系，結合實際情況對所提出的問題求解，通過修改程序參數，理論上其實可以使用任何正常數量的檢測無人機和正常數量的風電機之間的最優路線規劃，模型具有通用性，推廣性較強。

（2）本文采用了模擬退火算法與遺傳算法，選用了機器算法，算法新穎，考慮相對全面，仿真結果合理性較強，模型所得結果可信度高。

（3）該模型對于數據分布及樣本量限制小，既可以用于小規模樣本，亦可以用于大規模樣本，較為靈活、方便。

（4）但該模型運算過程較麻煩，運算時間耗費較長，程序運行時間耗時長。

（5）模型還存在一定的隨機性，需要不斷嘗試最后選取最優解。除此之外，程序在搜索過程中，多采取全局搜索和局部搜索方式，沒有進行完整搜索。

（6）現實生活中，需要考慮較為復雜的其他因素（例如：地形、無人機時速限制、運行路徑、路障等），該模型較簡單，未能對其進行全面考慮，造成與實際有不符之處。