徐國生，徐祖永，周俊杰，張皖軍，邵珠鵬

(1.國家電投江西電力有限公司，江西 南昌 330096)

(2.國家電投集團信息技術(shù)有限公司，北京 100080)

為了解決人工巡檢工作效率低、存在安全隱患等問題，無人值守的機器人開始走入大眾視野。對于電力行業(yè)而言，智能電網(wǎng)的迅速發(fā)展促使機器人巡檢逐步取代人工巡檢，以減少危險工況環(huán)境對人員的安全威脅以及提高工作效率等。巡檢機器人工作在復雜環(huán)境中執(zhí)行巡檢任務，其路徑規(guī)劃成為了國內(nèi)外研究的熱點[1]。Qureshi[2]將粒子群優(yōu)化算法應用于最佳路徑尋優(yōu)問題中，并通過兩組實驗獲得了超出預期的結(jié)果；Osvald等[3]在傳統(tǒng)的啟發(fā)式算法求解最佳路徑的基礎上，引入花授粉算法來提升全局尋優(yōu)的性能，經(jīng)實驗論證，該算法在有限的算子范圍內(nèi)，能夠獲得較高質(zhì)量的最優(yōu)解，但是隨著算子數(shù)量的增加，性能出現(xiàn)了明顯的下降；周風余等[4]采用Lagrange建模進行機器人避障算法的研究，運用動力學模型獲得最佳的避障路徑；王建元等[5]提出了使用圖結(jié)構(gòu)的路徑建模法，并結(jié)合GIS(geographic information system)建立三維地圖，使其具有較好的尋址能力，但選擇最佳路徑的能力稍差。本文在前人研究的基礎上，提出了基于改進遺傳算法的巡檢機器人路徑規(guī)劃算法，在種群初始化階段使用混沌算法降低算法陷入局部最優(yōu)的概率，使用自適應策略優(yōu)化交叉算子與變異算子，進一步提升算法的收斂速度、執(zhí)行性能和求解質(zhì)量，另外，針對遺傳算法局部尋優(yōu)能力差的問題，采用模擬退火算法強化其整體尋優(yōu)能力。研究結(jié)果表明，與經(jīng)典的路徑選擇算法相比，結(jié)合了模擬退火及混沌算法的遺傳算法效率更高，搜索的路徑質(zhì)量更好，算法具有良好的表現(xiàn)力。

1 遺傳算法

遺傳算法的核心思想是在有限資源內(nèi)通過遺傳方式保持后代先進性的同時尋求最優(yōu)。其以群體中的全部個體為對象，采用隨機化技術(shù)在已編碼的種群的參數(shù)空間內(nèi)完成高效搜索。首先進行染色體種群初始化，然后選擇適應度函數(shù)、應用交叉以及變異完成最優(yōu)個體的選擇、遺傳，獲得最優(yōu)解。算法流程如圖1所示。

圖1 遺傳算法流程

算法的主要步驟如下：

1)參數(shù)初始化。初始化種群的規(guī)模、數(shù)量、交叉以及變異的概率值，同時對遺傳代數(shù)和結(jié)束條件以及整體種群進行初始化，明確種群編碼方式。

2)設置種群內(nèi)個體的適應度，選擇恰當?shù)倪m應度函數(shù)。

3)計算種群內(nèi)每個個體的染色體適應度值，使用選擇策略優(yōu)勝劣汰，獲得能進入到下一代的優(yōu)秀個體。

4)對于被選中的個體，使用交叉概率完成優(yōu)秀個體的橫向交叉。

5)對于被選中的優(yōu)良個體，使用變異概率完成優(yōu)秀個體的變異更新。

6)判斷是否滿足遺傳結(jié)束條件或者達到遺傳代數(shù)，滿足則終止運算，否則返回步驟4)重復迭代。

遺傳算法的核心是參數(shù)的編碼、群體初始化以及個體適應度函數(shù)和遺傳控制參數(shù)的選擇。

2 改進遺傳算法的路徑規(guī)劃

2.1 種群編碼

種群編碼及參數(shù)編碼就是把問題的可行性解轉(zhuǎn)換為遺傳算法的搜索空間。由于編碼方式對交叉算子、變異算子的執(zhí)行效率會產(chǎn)生較大影響[6]，而廣泛使用的二進制編碼方式存在無效解的情況，因此本文選擇整數(shù)編碼方式進行染色體編碼，具體過程如下：使用n標識巡檢點位并編碼，依次標識為1,2,…,n，使用m標識巡檢機器人的數(shù)量，巡檢完成的點位使用0標識，使用整數(shù)編碼方式完成的染色體編碼串為{1，…,S1，0，…,S2}，其中Si代表巡檢點位，由此可見種群編碼串的長度為(m+n+1)。由染色體編碼串可知，染色體中必然存在的從0點位到0點位之間的子路徑，該路徑即為機器人巡檢起始位置到各個巡檢點位的巡檢路徑。如染色體編碼串{0,1,3,4,0,2,5,7,0,9,6,8,0}中，有3個巡檢機器人完成了9個點位的巡檢，對應的巡檢路徑如圖2所示。

圖2 巡檢路徑示意圖

2.2 種群初始化

種群初始化主要是設置種群規(guī)模，規(guī)模設置得過小，尋找最優(yōu)解過程中容易陷入局部最優(yōu)，降低算法的整體性能和質(zhì)量；規(guī)模設置得過大，則運算量會明顯增加[7]。目前常用的初始化種群算法(隨機初始化、啟發(fā)式算法)存在典型染色體優(yōu)良度不均衡以及群體可行性無法保證的問題，本文引入了混沌算法，發(fā)揮其優(yōu)秀的全局迭代搜索能力，來擴大染色體的遍歷范圍，具體做法是使用混沌算法生成混沌序列編碼并成為種群染色體。

混沌序列為大量的非線性的多變結(jié)構(gòu)模式。使用Logistic映射函數(shù)生成混沌序列，如式(1)所示：

Yn+1=μYn(1-Yn)

(1)

式中：μ為控制序列變化的參數(shù)，為0～4的常量；Yn為對變量x的n次循環(huán)遍歷值，為0～1的隨機數(shù)。對應的混沌映射結(jié)構(gòu)圖如圖3所示。

圖3 混沌映射初始化

由圖3可以發(fā)現(xiàn)，經(jīng)過對x變量的600次循環(huán)遍歷，Logistic映射將混沌空間向量映射為對稱、整體穩(wěn)定但局部不穩(wěn)定的分布在0～1的相對均勻的解空間向量，從而在初始化種群階段降低遺傳算法陷入局部最優(yōu)解的概率。

2.3 自適應策略優(yōu)化遺傳參數(shù)

由于遺傳算法的收斂速度、執(zhí)行性能和求解質(zhì)量受交叉算子和變異算子的影響較大，本文采用自適應策略優(yōu)化交叉算子與變異算子，選擇合理的參數(shù)。

1)交叉算子選擇流程。

交叉算子受交叉概率的影響，如果交叉概率設置小了，在進化初期即開始出現(xiàn)相對近似的適應度值，產(chǎn)生局部最優(yōu)解；如果交叉概率設置過大，則會降低搜索能力。因此，本文采用自適應策略產(chǎn)生動態(tài)交叉概率來優(yōu)化交叉算子。由于種群采用優(yōu)勝劣汰的模式，因此適應度較高的個體需要降低交叉概率，減少其破壞度，相反地適應度低的個體需要提高其交叉概率。采用式(2)對種群中優(yōu)良個體間的適應度進行標定：

(2)

適應度函數(shù)Fi的計算公式為：

(3)

式中：Zi為成本；p為種群的規(guī)模。

在種群最初幾代遺傳過程中，由于種群的平均適應度值低，k值較小，進化接近尾聲時，k值會增大到接近1，因此本文提出自適應交叉概率算法，如式(4)所示：

(4)

式中：Pc,f′,favg,Pmax分別為第i代種群交叉概率及其下限值、均值、上限值；Pc1(i)和Pc2(i)分別為第(i-1)代和第(i-2)代交叉概率。

自適應交叉概率算法流程如圖4所示。

圖4 自適應交叉概率算法流程

2)變異概率進化流程。

遺傳算法通過變異算子參數(shù)增加種群的多樣性，有效避免算法陷入局部最優(yōu)解，若其值選擇過大將會破壞優(yōu)良個體，出現(xiàn)無最優(yōu)解的情況，若其值過小，則會導致早熟[8-9]，因此本文提出自適應策略優(yōu)化變異概率，既保持了種群的多樣性，又避免了算法出現(xiàn)局部最優(yōu)解的情況。具體計算公式如下：

(5)

式中：Pm，Pm1(i)，Pm2(i)分別為第i代種群變異概率及其上、下限值。

引入自適應策略的變異算子和交叉算子，可以適應性地調(diào)整種群遺傳過程中的變化規(guī)律，保證優(yōu)秀個體的傳承，同時避免算法收斂過快以及局部最優(yōu)等問題的出現(xiàn)。

2.4 改進遺傳算法執(zhí)行流程

為解決遺傳算法局部尋優(yōu)表現(xiàn)不足的問題，引入模擬退火算法，在遺傳算法完成選擇、交叉和變異操作的優(yōu)選個體中，進行局部尋優(yōu)，從空間深度獲取最優(yōu)解。

使用C代表當前的優(yōu)選個體，Ti代表當前問題，P代表調(diào)整后的最新解，對應的目標函數(shù)為O，目標函數(shù)的增量使用Δf標識，模擬退火算法優(yōu)化過程的metropolis準則[9-10]如公式(6)所示：

(6)

當Δf為負數(shù)時，則接受新解P，否則放棄新解。后續(xù)通過衰減率進行持續(xù)降溫操作，直至獲得最優(yōu)解。

將模擬退火算法引入遺傳算法獲得巡檢最佳路徑的流程如圖5所示。

圖5 改進遺傳算法的路徑規(guī)劃流程圖

算法的具體步驟為：

1)初始化種群及模擬退火參數(shù)，包括種群規(guī)模p、模擬退火初始溫度T、溫降參數(shù)以及終止溫度和迭代循環(huán)次數(shù)。

2)使用種群編碼方式完成種群整體的初始化工作。

3)計算每個個體的適應度值。

4)執(zhí)行優(yōu)良個體選擇操作，選擇遺傳到下一代的個體。

5)根據(jù)適應度標定動態(tài)調(diào)整概率進行變異和交叉操作，獲得變異算子和交叉算子。

6)將優(yōu)良個體引入模擬退火算法，計算個體新的適應度值，使用式(4)確認新的個體是否可以接受，如可接受則完成模擬退火算法的迭代，獲得最優(yōu)個體，輸出最佳路徑，否則重新執(zhí)行步驟2)。

3 仿真與分析

3.1 路徑規(guī)劃仿真實驗

為了驗證本文提出的基于模擬退火和自適應策略改進的遺傳算法規(guī)劃機器人巡檢最佳路徑的性能，進行了仿真對比實驗。仿真參數(shù)設置：種群規(guī)模為90，交叉概率的上、下限分別為0.51和0.84，變異概率的上、下限分別為0.04和0.20，最大迭代次數(shù)為500，模擬退火的初始溫度為1 000 ℃，結(jié)束溫度為100 ℃，溫降系數(shù)為0.99。

本文進行了2組對比實驗。首先與經(jīng)典遺傳算法進行對比，遺傳算法的變異概率和交叉概率分別設為0.05和0.50，其他條件與本文算法一致。經(jīng)典遺傳算法的路徑規(guī)劃結(jié)果如圖6所示，本文算法的路徑規(guī)劃結(jié)果如圖7所示。

對比圖6和圖7可以發(fā)現(xiàn)，本文算法規(guī)劃的路徑最優(yōu)路徑的長度為6 581個單位長度，比經(jīng)典遺傳算法獲得的最佳路徑長度7 845個單位長度減少了264個單位長度，路徑優(yōu)化效果明顯。

圖6 遺傳算法的路徑規(guī)劃圖

圖7 本文算法的規(guī)劃路徑

然后就算法的收斂速度分別與經(jīng)典遺傳算法、蟻群算法、模糊控制算法進行對比，共進行了2 000次仿真實驗，平均搜索時間以及搜索成功率分別見表1和表2。由表可知，本文提出的算法在機器人路徑規(guī)劃中具有較快的收斂速度，準確率高，并且能以較大的概率收斂獲得全局最優(yōu)解，在復雜環(huán)境中體現(xiàn)得更加明顯。

表1 本文算法與其他算法規(guī)劃時間對比表 單位：s

表2 本文算法與其他算法規(guī)劃成功率對比表 %

3.2 機器人巡檢應用

將本文提出的算法應用于電子地圖進行仿真實驗，人為設置模擬機器人從指定位置出發(fā)到1號主變壓器所在的500 kV設備待檢驗區(qū)域(圖8中的右上角框選部位，即為從1號主變壓器到500 kV設備待檢驗區(qū)域)為最佳巡檢路徑。進行巡檢點位編號，分別從機器人巡檢開始的位置到巡檢點按照一定規(guī)律編號，如圖8所示。機器人初始位置設置為0號(圖中箭頭所示位置)，自左至右分別為1號、2號、3號，右邊從下而上分別為4～8號，上方為9～12號，左邊從下而上為13～18號。選擇圖8中的2號、15號和18號為巡檢點位，完成規(guī)劃后的路徑將顯示所有途徑的點位。圖8中標定的路徑是本文算法規(guī)劃的最佳路徑，經(jīng)過人工測量后符合最佳安全無障礙路徑要求。經(jīng)過多次試驗，路徑規(guī)劃成功率可達100%。

圖8 巡檢地圖

路徑規(guī)劃后，模擬機器人按照路徑進行巡檢，由于是單向巡檢模式，因此在一側(cè)巡檢完畢后掉頭巡檢另一側(cè)，按點位順序的巡檢路徑為0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 12 → 11 → 10 → 9 → 13 → 14→ 15 → 16 → 17 → 18。巡檢2號點位、15號點位和18號點位置的巡檢路徑分別為：路徑1，0 → 1 → 2；路徑2，2 → 3 → 4 → 5 → 6 → 7 → 8 → 12 → 11 → 10 → 9 → 13 → 14 → 15；路徑3，15 → 16 → 17 → 18。

經(jīng)多次運行驗證，機器人的巡檢結(jié)果與預計結(jié)果完全吻合。

4 結(jié)束語

為了提高機器人的巡檢能力，滿足智能電網(wǎng)無人化作業(yè)的要求，本文提出了基于模擬退火和自適應策略改進遺傳算法的巡檢機器人路徑規(guī)劃算法。以提升算法的尋優(yōu)能力以及收斂速度為目標，在各個階段分別使用混沌算法降低算法陷入局部最優(yōu)的概率、自適應策略優(yōu)化交叉算子與變異算子、使用模擬退火算法強化遺傳算法整體尋優(yōu)能力等，進一步提升算法的收斂速度、執(zhí)行性能和求解質(zhì)量。通過實驗對比發(fā)現(xiàn)，本文提出的算法路徑規(guī)劃成功率比傳統(tǒng)的遺傳算法及蟻群算法平均提高了6%左右，巡檢點數(shù)量在100以內(nèi)時算法的執(zhí)行時間平均在1 s左右，與其他算法相比性能有較大的提升，本文提出的算法具有較高的推廣應用價值。