基于遺傳算法的巡檢機(jī)器人路徑規(guī)劃算法的研究

徐國(guó)生，徐祖永，周俊杰，張皖軍，邵珠鵬

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

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

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

1 遺傳算法

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

圖1 遺傳算法流程

算法的主要步驟如下：

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

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

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

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

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

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

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

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

2.1 種群編碼

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

圖2 巡檢路徑示意圖

2.2 種群初始化

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

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

Yn+1=μYn(1-Yn)

(1)

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

圖3 混沌映射初始化

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

2.3 自適應(yīng)策略?xún)?yōu)化遺傳參數(shù)

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

1)交叉算子選擇流程。

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

(2)

適應(yīng)度函數(shù)Fi的計(jì)算公式為：

(3)

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

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

(4)

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

自適應(yīng)交叉概率算法流程如圖4所示。

圖4 自適應(yīng)交叉概率算法流程

2)變異概率進(jìn)化流程。

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

(5)

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

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

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

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

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

(6)

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

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

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

算法的具體步驟為：

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

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

3)計(jì)算每個(gè)個(gè)體的適應(yīng)度值。

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

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

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

3 仿真與分析

3.1 路徑規(guī)劃仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

3.2 機(jī)器人巡檢應(yīng)用

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

圖8 巡檢地圖

路徑規(guī)劃后，模擬機(jī)器人按照路徑進(jìn)行巡檢，由于是單向巡檢模式，因此在一側(cè)巡檢完畢后掉頭巡檢另一側(cè)，按點(diǎn)位順序的巡檢路徑為0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 12 → 11 → 10 → 9 → 13 → 14→ 15 → 16 → 17 → 18。巡檢2號(hào)點(diǎn)位、15號(hào)點(diǎn)位和18號(hào)點(diǎn)位置的巡檢路徑分別為：路徑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)多次運(yùn)行驗(yàn)證，機(jī)器人的巡檢結(jié)果與預(yù)計(jì)結(jié)果完全吻合。

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

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