王 銳，莫志超，彭向陽(yáng)，龐小峰，饒章權(quán)

(1.廣東電網(wǎng)有限責(zé)任公司 電力科學(xué)研究院，廣州 510080;2.中航工業(yè)洛陽(yáng)電光設(shè)備研究所，河南 洛陽(yáng) 471009)

基于遺傳算法的變電站巡檢機(jī)器人任務(wù)路徑規(guī)劃方法研究

王 銳1，莫志超2，彭向陽(yáng)1，龐小峰1，饒章權(quán)1

(1.廣東電網(wǎng)有限責(zé)任公司 電力科學(xué)研究院，廣州 510080;2.中航工業(yè)洛陽(yáng)電光設(shè)備研究所，河南 洛陽(yáng) 471009)

近年來(lái)，隨著變電站巡檢機(jī)器人在變電站中的廣泛使用，巡檢機(jī)器人路徑規(guī)劃問(wèn)題越來(lái)越成為亟待解決的問(wèn)題;巡檢機(jī)器人在已知的拓?fù)涞貓D中標(biāo)記了待執(zhí)行巡檢任務(wù)的?？奎c(diǎn)，不同任務(wù)需要從初始點(diǎn)出發(fā)經(jīng)過(guò)不同的一系列?？奎c(diǎn)再返回初始點(diǎn)，如何規(guī)劃路徑是機(jī)器人面臨的問(wèn)題;首先分析了路徑規(guī)劃面臨的問(wèn)題，然后通過(guò)分析拓?fù)涞貓D的特征，對(duì)地圖進(jìn)行等價(jià)簡(jiǎn)化，再對(duì)問(wèn)題進(jìn)行建模使用遺傳算法求解巡檢任務(wù)路徑規(guī)劃的近似最優(yōu)解;通過(guò)仿真實(shí)驗(yàn)證明，提出的基于遺傳算法的路徑規(guī)劃方法是可行有效的，為變電站巡檢機(jī)器人任務(wù)路徑規(guī)劃提供了一種有效方法。

變電站機(jī)器人；路徑規(guī)劃；遺傳算法；進(jìn)化算法；中國(guó)郵差問(wèn)題

0 引言

近年來(lái)，變電站巡檢機(jī)器人在變電站巡檢中占有了越來(lái)越重要的地位。尤其在少人或無(wú)人值守的變電站，巡檢機(jī)器人更是擔(dān)當(dāng)了主要角色。巡檢機(jī)器人巡航時(shí)間受到電池影響，如何提高巡檢效率成為亟待解決的問(wèn)題。如何在最短時(shí)間內(nèi)完成所下定的巡檢任務(wù)成為研究的方向。

巡檢機(jī)器人在掃描完變電站環(huán)境之后會(huì)生成一個(gè)無(wú)向連通拓?fù)鋱D，在拓?fù)鋱D的邊上會(huì)標(biāo)記有若干的停靠點(diǎn)。不同任務(wù)需要從初始點(diǎn)出發(fā)經(jīng)過(guò)不同的若干個(gè)?？奎c(diǎn)再返回初始點(diǎn)。這是一個(gè)近似的中國(guó)郵遞員問(wèn)題[1]。求解此類(lèi)問(wèn)題目前研究有以下幾大類(lèi)算法：1)動(dòng)態(tài)規(guī)劃算法[2]，通過(guò)尋求優(yōu)化的搜索算法求得較優(yōu)的解；2)模擬進(jìn)化算法，如蟻群算法，遺傳算法，粒子群算法等[3]；3)DNA算法[4]。本文通過(guò)對(duì)問(wèn)題分析，提出基于遺傳算法的解決方法，有效解決了巡檢機(jī)器人路徑規(guī)劃問(wèn)題。

1 巡檢路徑規(guī)劃面臨的問(wèn)題

1.1 路徑規(guī)劃原理

變電站機(jī)器人巡檢是按照預(yù)先設(shè)定好的路徑進(jìn)行行走，在路徑上有?？奎c(diǎn)，機(jī)器人到達(dá)?？奎c(diǎn)停車(chē)進(jìn)行動(dòng)作。不同任務(wù)會(huì)選擇不同的停靠點(diǎn)，如何從初始點(diǎn)出發(fā)以最短的時(shí)間完成任務(wù)并返回初始點(diǎn)是本文要研究的目標(biāo)。由于機(jī)器人在?？奎c(diǎn)執(zhí)行動(dòng)作時(shí)間相同，如何以最短的路徑代價(jià)通過(guò)所有?？奎c(diǎn)并返回是問(wèn)題的核心。

機(jī)器人巡檢路徑構(gòu)成了一個(gè)連通無(wú)向圖[5]，如圖1所示，表示為G=(V,E)，V表示所有路徑頂點(diǎn)集合，E表示所有路徑集合。使用S表示所有停靠點(diǎn)集合，每個(gè)路徑包含若干個(gè)?？奎c(diǎn)。

圖1 機(jī)器人巡檢拓?fù)鋱D

機(jī)器人巡檢過(guò)程中會(huì)優(yōu)先巡檢同一條路徑上所有?？奎c(diǎn)。例如任務(wù)中含有2和3?？奎c(diǎn)，機(jī)器人在從初始點(diǎn)出發(fā)，巡視2號(hào)?？奎c(diǎn)之后一定會(huì)先巡視3號(hào)停靠點(diǎn)。這與中國(guó)郵差問(wèn)題中經(jīng)過(guò)街道一樣。所以可以將機(jī)器人巡視要經(jīng)過(guò)的?？奎c(diǎn)轉(zhuǎn)換為需要經(jīng)過(guò)的路徑。本文將路徑上停靠點(diǎn)最小編號(hào)作為路徑編號(hào)。

1.2 路徑規(guī)劃難點(diǎn)

巡檢機(jī)器人路徑規(guī)劃問(wèn)題可以總結(jié)為求從初始點(diǎn)出發(fā)經(jīng)過(guò)圖上選定的若干條路徑并返回初始點(diǎn)的最短代價(jià)。即給定一組待巡檢的路徑集合{e1…en}，求出一個(gè)集合排列的順序使得從初始點(diǎn)出發(fā)按順序經(jīng)過(guò)排列中的路徑然后返回初始點(diǎn)的路徑最短。2個(gè)點(diǎn)之間行走路徑按照Floyd算法[6]求解。此問(wèn)題類(lèi)似于中國(guó)郵差問(wèn)題[7]，路徑集合{e1…en}的所有排列有n!個(gè)，從n!個(gè)排列中找到代價(jià)最小的排列在n較大時(shí)這幾乎不可能。求解最優(yōu)排列問(wèn)題可以使用動(dòng)態(tài)規(guī)劃算法[8]，窮舉所有可能的解。

1.3 動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法是求取最優(yōu)解的一種算法。根據(jù)機(jī)器人當(dāng)前位置，在圖中進(jìn)行廣度優(yōu)先搜索，只保留第一層的搜索結(jié)果作為下一巡檢目標(biāo)的備選集。將機(jī)器人移動(dòng)到備選集中的一個(gè)位置，在此位置再進(jìn)行廣度優(yōu)先搜索[9]，繼續(xù)移動(dòng)。如圖2所示，當(dāng)巡檢全部?？奎c(diǎn)時(shí)，從初始點(diǎn)出發(fā)，首先搜索到1和2號(hào)停靠點(diǎn)，機(jī)器人選擇1號(hào)?？奎c(diǎn)，在1號(hào)?？奎c(diǎn)搜索下一個(gè)備選集為2、6、10、12號(hào)?？奎c(diǎn)，重復(fù)此過(guò)程，可以將所有可行路線遍歷，求出代價(jià)最小的路徑。

圖2 機(jī)器人巡檢動(dòng)態(tài)規(guī)劃算法示意圖

在問(wèn)題描述中已說(shuō)明巡檢時(shí)會(huì)將路徑上所有?？奎c(diǎn)一次巡檢，即巡檢2號(hào)?？奎c(diǎn)是機(jī)器人會(huì)將3號(hào)?？奎c(diǎn)巡檢。所以在搜索算法中需要搜索的次數(shù)為待巡檢的路徑個(gè)數(shù)n，每次搜索到的備選集個(gè)數(shù)約為2～4個(gè)?？傻盟惴〞r(shí)間復(fù)雜度在2n～4n。在待巡檢路徑n較多時(shí)此算法求得最優(yōu)解需要的時(shí)間是不能忍受的，本文提出了基于遺傳算法的求解方法。

2 基于遺傳算法的求解方法

首先通過(guò)分析拓?fù)鋱D的特征對(duì)拓?fù)鋱D簡(jiǎn)化，減少參與計(jì)算的路徑；再根據(jù)動(dòng)態(tài)規(guī)劃算法給出路徑排列的等價(jià)模型；最后給出遺傳算法的選擇、交叉、變異、適應(yīng)度模型使用遺傳算法進(jìn)行求解。

路徑規(guī)劃方法的具體步驟如圖3所示，首先初始化算法：簡(jiǎn)化拓?fù)鋱D以減少計(jì)算路徑，再使用Flord算法計(jì)算點(diǎn)到點(diǎn)最短路徑和代價(jià)并存儲(chǔ)到持續(xù)存儲(chǔ)；然后根據(jù)輸入任務(wù)點(diǎn)序列使用本文提出的遺傳算法進(jìn)行迭代求解；最后輸出最優(yōu)個(gè)體作為最優(yōu)任務(wù)序列。

圖3 路徑規(guī)劃方法步驟

2.1 拓?fù)鋱D簡(jiǎn)化

在機(jī)器人巡檢拓?fù)鋱D中存在一些“死胡同”，這些“死胡同”總是需要進(jìn)入再退出。無(wú)論何時(shí)巡檢“死胡同”內(nèi)的停靠點(diǎn)，進(jìn)入、退出的代價(jià)是固定的。如圖4所示，13號(hào)停靠點(diǎn)在一條“死胡同”中，巡檢13號(hào)?？奎c(diǎn)必須從圖中空心頂點(diǎn)出發(fā)再回到圖中空心頂點(diǎn)，這類(lèi)在“死胡同”內(nèi)的?？奎c(diǎn)在不同的路徑集合{e1…en}的排列中的代價(jià)是固定的，所以在計(jì)算最優(yōu)排列是可以忽略這些點(diǎn)所在的路徑。

圖4 巡檢路徑簡(jiǎn)化示意圖

具體算法流程：

1)尋找圖中度為1的頂點(diǎn)，不存在則結(jié)束；

2)尋找頂點(diǎn)所在邊的另一頂點(diǎn)(兄弟頂點(diǎn))；

3)將頂點(diǎn)標(biāo)記到兄弟頂點(diǎn)；

4)刪除頂點(diǎn)所在邊，返回1)。

如圖4所示，左邊圖經(jīng)過(guò)簡(jiǎn)化之后變?yōu)橛疫叺膱D。

2.2 路徑排列等價(jià)模型

路徑集合{e1…en}的所有排列組合有n!個(gè)，但是其中有很多是無(wú)效的巡檢序列，例如{e1,e2,e4,e5}集合的一個(gè)排列{e1,e4,e2,e5}是一個(gè)無(wú)效序列，因?yàn)閺膃1到e4的過(guò)程必然經(jīng)過(guò)e2,e5中一個(gè)。對(duì)于{e1,e2,e4,e5}，根據(jù)動(dòng)態(tài)規(guī)劃算法可知，在e1下一個(gè)巡檢路徑只能是e2,e5中一個(gè)。

在此本文給出一個(gè)轉(zhuǎn)換算法，將任意排列轉(zhuǎn)換為符合搜索邏輯的序列。算法過(guò)程如下：

1)輸入任意排列E={e1…en}，元素個(gè)數(shù)為num。初始化n=1，輸出排列R={E(1)}，即將輸入排列第一個(gè)加入輸出排列。

2)廣度優(yōu)先搜索尋找E(n)下一步備選集合B={ei…ej}。

3)C=B-R,即從備選集合移除已存在R中的元素。

4)將C中元素按在E排列中順序排序，將C(1)加入R尾部。n=n+1。

5)若n

6)將E(n)加入R尾部，結(jié)束。

例如{e1,e4,e2,e5}，e1之后備選集合為{e2,e5}，e2在{e1,e4,e2,e5}中順序靠前選擇e2。e2之后備選集合為{e5,e4}，e4在{e1,e4,e2,e5}中順序靠前選擇e4。最后得到等價(jià)排列為{e1,e2,e4,e5}。

2.3 遺傳算法

首先需要給出一個(gè)排列序列的代價(jià)。本文路徑長(zhǎng)度計(jì)算使用Floyd[10]算法求得每對(duì)頂點(diǎn)之間的最短路徑，機(jī)器人到巡檢序列中一個(gè)路徑代價(jià)為機(jī)器人從當(dāng)前位置巡檢路徑近處的頂點(diǎn)，再將路徑上?？奎c(diǎn)依次巡檢所走的路線總長(zhǎng)度。機(jī)器人從初始點(diǎn)開(kāi)始將排列序列所有路徑巡視完并按最短路徑返回初始點(diǎn)，總路線長(zhǎng)度為此排列序列的代價(jià)。計(jì)算一個(gè)排列序列的代價(jià)總是計(jì)算其有效的等價(jià)序列的代價(jià)。

遺傳算法[11]需要計(jì)算每個(gè)個(gè)體的適應(yīng)度，此問(wèn)題中適應(yīng)度與排列序列代價(jià)成反比。本文使用基準(zhǔn)對(duì)比的方法求得適應(yīng)度。首先隨機(jī)一個(gè)基準(zhǔn)排列序列，求得其代價(jià)作為基準(zhǔn)代價(jià)；任何一個(gè)排列序列的適應(yīng)度為基準(zhǔn)代價(jià)除以待求序列的代價(jià)。將此方法記為f(R)，R為排列序列。

選擇運(yùn)算[12]：遺傳算法使用選擇運(yùn)算來(lái)實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。本文采用輪盤(pán)賭選擇方法，基本思想：各個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度通過(guò)f(R)求得，記為Fi，則個(gè)體i被選中遺傳到下一代群體的概率為：

交叉算子[13]作為遺傳算法重要的部分，2個(gè)父?jìng)€(gè)體通過(guò)交叉算子產(chǎn)生帶著2個(gè)父?jìng)€(gè)體共同信息的子個(gè)體。本文采用順序交叉法作為交叉算子。順序交叉法為從父代A隨機(jī)選一個(gè)編碼子串，放到子代A的對(duì)應(yīng)位置；子代A空余的位置從父代B中按B的順序選取(與己有編碼不重復(fù))。同理可得子代B。如：

父代A: 872 | 139 | 0546

父代B: 983 | 567 | 1420

交叉后：

子代A: 856 | 139 | 7420

子代B: 821 | 567 | 3904

變異算子[14]增加了遺傳算法全局搜索能力，避免遺傳算法陷入局部最優(yōu)解。本文采用逆轉(zhuǎn)變異算法，在個(gè)體中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，再將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因交換。如14527，隨機(jī)選擇2,4位置交換變異為12547。

本文增加了精英保留策略[15]，將最優(yōu)的個(gè)體復(fù)制到下一代中。遺傳算法具體流程如圖5所示。

圖5 遺傳算法流程圖

遺傳算法首先要設(shè)定結(jié)束條件，本文設(shè)置結(jié)束條件為迭代次數(shù)100次和不出現(xiàn)更優(yōu)秀個(gè)體次數(shù)10次。當(dāng)超過(guò)設(shè)定迭代次數(shù)或者超過(guò)設(shè)定不出現(xiàn)更優(yōu)秀個(gè)體次數(shù)沒(méi)有出現(xiàn)更優(yōu)秀個(gè)體時(shí)結(jié)束算法。設(shè)置交叉概率為90%，即選擇的2個(gè)父?jìng)€(gè)體有90%就行交叉產(chǎn)生自個(gè)體。設(shè)置變異概率為1%，每個(gè)個(gè)體有1%的概率產(chǎn)生隨機(jī)變異。

3 仿真實(shí)驗(yàn)分析

為驗(yàn)證本文提出的基于遺傳算法求解路徑規(guī)劃的有效性，本文利用仿真手段進(jìn)行驗(yàn)證。實(shí)驗(yàn)數(shù)據(jù)在visualstudio2015上使用C#編程仿真得到。實(shí)驗(yàn)所用拓?fù)鋱D6所示，路徑權(quán)重按照最小權(quán)重路徑歸一化結(jié)果，如圖6中所示。

圖6 實(shí)驗(yàn)拓?fù)鋱D

仿真實(shí)驗(yàn)測(cè)試的機(jī)器人任務(wù)是巡檢?？奎c(diǎn)5,6,10,11,12,13,14,15。實(shí)驗(yàn)結(jié)果如圖7所示，隨著迭代次數(shù)的增加群體評(píng)價(jià)代價(jià)逐漸降低，在迭代20次之后趨于穩(wěn)定。在迭代30次的群體中取最優(yōu)個(gè)體作為算法的解。本文提出的方法得出的巡檢序列為1,12,13,11,15,14,5,6,10；然后返回初始點(diǎn)。巡檢代價(jià)為65。與使用動(dòng)態(tài)規(guī)劃求得最優(yōu)一致，表明本文提出的基于遺傳算法的求解方法是迅速且有效的。

圖7 仿真實(shí)驗(yàn)結(jié)果圖

本文通過(guò)與基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃與仿真[16]所提出的算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖,8所示，實(shí)驗(yàn)表明本文通過(guò)拓?fù)鋱D的簡(jiǎn)化和路徑等價(jià)模型減少了求解的迭代次數(shù)，可以更加迅速地收斂到最優(yōu)解。

圖8 對(duì)比實(shí)驗(yàn)圖

通過(guò)實(shí)際運(yùn)行本算法在路徑教較少情況下總是能找到最優(yōu)解，在路徑較多的情況下也可以找到比較良好的解，充分滿足了變電站巡檢機(jī)器人任務(wù)路徑規(guī)劃的需求。

4 結(jié)束語(yǔ)

本文首先分析研究了變電站巡檢機(jī)器人任務(wù)路徑規(guī)劃的問(wèn)題，將其抽象為路徑排序問(wèn)題。通過(guò)分析動(dòng)態(tài)規(guī)劃算法，得出其時(shí)間復(fù)雜度高不適用于解決此問(wèn)題；然后根據(jù)變電站巡檢路徑拓?fù)鋱D的特點(diǎn)，將圖進(jìn)行簡(jiǎn)化減少了參與計(jì)算的路徑個(gè)數(shù)，減少計(jì)算復(fù)雜度；再根據(jù)動(dòng)態(tài)規(guī)劃的方式給出路徑排列的等價(jià)模型；最后建立遺傳算法模型對(duì)問(wèn)題進(jìn)行求解。通過(guò)仿真實(shí)驗(yàn)分析得出：本文提出的基于遺傳算法的路徑規(guī)劃方法有效解決了變電站巡檢機(jī)器人任務(wù)路徑規(guī)劃問(wèn)題。

[1] 高敬振, 高 勃. 中國(guó)郵遞員問(wèn)題50年[J]. 運(yùn)籌學(xué)學(xué)報(bào), 2013, 17(1):17-28.

[2] 費(fèi) 蓉, 崔杜武. 中國(guó)郵遞員問(wèn)題的動(dòng)態(tài)規(guī)劃算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(2):294-299.

[3] 嚴(yán) 露. 粒子群算法研究與應(yīng)用[D]. 成都:電子科技大學(xué), 2013.

[4] 李 瑋, 王 雷. 中國(guó)郵遞員問(wèn)題的DNA計(jì)算[J]. 計(jì)算機(jī)應(yīng)用, 2009, 29(7):1880-1883.

[5] Kay E. Graph Theory with Applications[M]. London: Macmillan, 1976.

[6] Floyd R W. Algorithm 97: Shortest path[J]. Communications of the Acm, 1962, 5(6):345-345.

[7] 管梅谷.關(guān)于中國(guó)郵遞員問(wèn)題研究和發(fā)展的歷史回顧[J]. 運(yùn)籌學(xué)學(xué)報(bào)，2015,19(3)：1-7.

[8] Coaker P B. Applied Dynamic Programming[M]. Princeton: Princeton University Press, 1962.

[9] Eckstein D M. Parallel processing using depth-first search and Breadth First search[J]. Algorithm Synthesis A Comparative Study, 1977:8-23.

[10] 石為人, 王 楷. 基于Floyd算法的移動(dòng)機(jī)器人最短路徑規(guī)劃研究[J]. 儀器儀表學(xué)報(bào), 2009, 30(10):2088-2092.

[11] 武廣號(hào), 文 毅. 遺傳算法及其應(yīng)用[M]. 北京:人民郵電出版社, 1996.

[12] 鐘求喜, 謝 濤, 陳火旺. 遺傳算法中解個(gè)體的生存策略[J]. 計(jì)算機(jī)工程與科學(xué), 2000, 22(1):14-17.

[13] 熊 軍, 高敦堂, 沈慶宏,等. 遺傳算法交叉算子性能對(duì)比研究[J]. 南京大學(xué)學(xué)報(bào):自然科學(xué)版, 2004, 40(4):432-437.

[14] 鄺航宇, 金 晶, 蘇 勇. 自適應(yīng)遺傳算法交叉變異算子的改進(jìn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 42(12):93-96.

[15] 朱 燦, 梁昔明. 一種多精英保存策略的遺傳算法[J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(4):939-941.

[16] 李 剛, 魚(yú)佳欣, 郭道通,等. 基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃與仿真[J]. 計(jì)算技術(shù)與自動(dòng)化, 2015(2):24-27.

ResearchofSubstationInspectionRobotpathPlanningMethodBasedonGeneticAlgorithm

WangRui1,MoZhichao2,PengXiangyang1,PangXiaofeng1,RaoZhangquan1

(1.Electric Power Research Institute of Guangdong Power Grid Co., Ltd., Guangzhou 510080, China;2.AVIC Luoyang Electro-optical Equipment Research Institute, Luoyang 471009, China)

In recent years, substation inspection robot is widely used in substations, but inspection robot path planning problem is a serious problem. Inspection robot has marked task stops in topology map, different tasks require starting from the initial point and through a series of stops and then returns to the initial point, how to planning the path is a problem. First, this paper analyzes the path planning problems, second proposed a map equivalent deformation method by analyzing the topological map features, finally used the genetic algorithm to calculate the approximate optimal solution. Simulation results show the method based on genetic algorithm this paper proposed is an effective method to solve substation inspection robot path planning problem.

substation inspection robot; path planning;genetic algorithm; evolutionary algorithm; Chinese postman problem

2016-10-22；

2016-11-21。

王 銳(1988-)，男，湖北潛江市人，工學(xué)碩士，工程師，主要從事變電站機(jī)器人智能巡檢及高電壓試驗(yàn)研究工作。

彭向陽(yáng)(1971-)，男，湖北黃岡市人，工學(xué)碩士，教授級(jí)高級(jí)工程師，長(zhǎng)期從事輸電線路及高電壓技術(shù)工作。

1671-4598(2017)04-0153-03DOI：10.16526/j.cnki.11-4762/tp

TP

A