基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃

陳亮 陳君若

摘 要：經(jīng)典遺傳算法的缺陷在于搜索耗時(shí)較長，容易出現(xiàn)局部最優(yōu)解。為解決該問題，引進(jìn)適應(yīng)度函數(shù)，并在設(shè)計(jì)遺傳算子時(shí)，重新定義適應(yīng)度函數(shù)。為盡量規(guī)避出現(xiàn)局部最優(yōu)解，在不改變種群參數(shù)的條件下，通過新算法得到最短路徑為31，搜索耗時(shí)均值為20.667m/s;與之對比，經(jīng)典遺傳算法兩項(xiàng)數(shù)據(jù)分別是37和24.667m/s。因此，新算法可在更短時(shí)間內(nèi)給出更佳解。

關(guān)鍵詞：遺傳算法;移動(dòng)機(jī)器人;路徑規(guī)劃;交叉算子;變異算子

DOI：10. 11907/rjdk. 191190

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）004-0024-04

0 引言

目前機(jī)器人智能化發(fā)展迅速，在工業(yè)、科學(xué)探索、國防軍事等重要領(lǐng)域應(yīng)用廣泛。移動(dòng)機(jī)器人是深度智能和人類智慧融合的產(chǎn)物，也是機(jī)械控制、傳感器、仿生學(xué)、信號(hào)處理等若干學(xué)科交叉發(fā)展的結(jié)果[1-4]。當(dāng)前，移動(dòng)機(jī)器人主要應(yīng)用難題之一是路徑規(guī)劃，即如何使機(jī)器人在避開各種障礙的前提下，以最優(yōu)路徑從出發(fā)點(diǎn)移動(dòng)到目標(biāo)點(diǎn)。通常情況下，移動(dòng)機(jī)器人工作環(huán)境較為復(fù)雜，首先需確定任務(wù)，然后機(jī)器人按照各方面環(huán)境信息（由操作者提供或通過傳感器采集）作出決策，最終執(zhí)行任務(wù)。大部分路徑規(guī)劃研究均應(yīng)用了多種優(yōu)化算法，如人工勢場法、蟻群優(yōu)化算法、神經(jīng)網(wǎng)絡(luò)和遺傳算法等[5-10]，本文綜合應(yīng)用優(yōu)化柵格法及回歸預(yù)測法探討在靜態(tài)、動(dòng)態(tài)障礙環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃。

為彌補(bǔ)傳統(tǒng)柵格法的缺陷，本文以障礙物為單位采集信息，有效縮小信息存儲(chǔ)空間。通過新勢場函數(shù)與沿墻跟蹤算法，解決障礙物目標(biāo)不可達(dá)和陷阱區(qū)等多個(gè)問題;再采取量子粒子群算法確定人工勢場參數(shù)以彌補(bǔ)傳統(tǒng)柵格法的缺陷，從而實(shí)現(xiàn)更優(yōu)的路徑規(guī)劃;最后探討機(jī)器人振蕩問題，對算法進(jìn)行針對性優(yōu)化[11-16]。

針對遺傳算法在路徑規(guī)劃方面的缺陷，如容易出現(xiàn)局部最優(yōu)解、收斂耗時(shí)長、優(yōu)化結(jié)果不夠穩(wěn)定等，學(xué)者們不斷對其優(yōu)化，但大部分學(xué)者通過隨機(jī)方法得到初始種群，該方法無法有效提高路徑質(zhì)量，導(dǎo)致收斂耗時(shí)延長，甚至出現(xiàn)過早收斂。因此，本文從優(yōu)化適應(yīng)度函數(shù)著手，提高進(jìn)化效率，降低出現(xiàn)早熟收斂的可能性。實(shí)驗(yàn)結(jié)果顯示，利用優(yōu)化自適應(yīng)遺傳算法可顯著提升路徑規(guī)劃質(zhì)量。

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

2.1 路徑編碼

按照由左到右、由上到下的順序，將柵格從1-400進(jìn)行編號(hào)，1號(hào)、400號(hào)柵格分別是機(jī)器人移動(dòng)起點(diǎn)和終點(diǎn)。利用MATLAB完成柵格模型序號(hào)編碼（見圖1）。

2.2 種群初始化

2.2.1 柵格路徑選擇

由于本研究中機(jī)器人周圍環(huán)境已知，所以障礙物信息（數(shù)量、位置）均可確定，在環(huán)境模型柵格化時(shí)，自由柵格、障礙物柵格的區(qū)分十分簡單。為提高初始化準(zhǔn)確性、節(jié)省初始化時(shí)間，筆者利用先驗(yàn)知識(shí)，確保路徑以目標(biāo)點(diǎn)為方向進(jìn)行初始化，并在自由柵格中選定路徑。如此路徑不會(huì)經(jīng)過障礙物，但無法確保路徑可不間斷地抵達(dá)目標(biāo)點(diǎn)，因此本文采用不連續(xù)自由柵格路徑，即在起點(diǎn)和終點(diǎn)之間，隨機(jī)選擇自由柵格為路徑節(jié)點(diǎn)，盡管選出的柵格難以完全連續(xù)地連接起點(diǎn)和終點(diǎn)，但可使算法更加靈活。

2.2.2 算子插入

在路徑非連續(xù)位置，通過附近的自由柵格予以填補(bǔ)，從而得到不經(jīng)過障礙物的連續(xù)路徑，此即為插入算子。通過式（2）分析相鄰兩個(gè)柵格是否連續(xù)。

若計(jì)算得出[pi]序號(hào)柵格屬于自由式柵格，則僅需填補(bǔ)插入。非自由柵格以最近自由柵格插入，若該操作無法實(shí)現(xiàn)，則證明該個(gè)體是不可行路徑，算子被淘汰。反復(fù)執(zhí)行上述步驟，直至某個(gè)體變?yōu)檫B續(xù)可行路徑或被淘汰。如果是種群初始化形成的非連續(xù)自由柵格路徑，通過插入算子予以修補(bǔ)使之連續(xù)，此時(shí)種群初始化成功。先驗(yàn)知識(shí)的應(yīng)用使初始化的個(gè)體均屬于可行路徑，無需應(yīng)用懲罰函數(shù)，可大幅減少運(yùn)算工作量和算法耗時(shí)。

2.3 適應(yīng)度函數(shù)

該函數(shù)為最小化目標(biāo)函數(shù)，定義適應(yīng)度函數(shù)為：

2.4 遺傳操作

2.4.1 算子選擇

算子選擇的作用是為了實(shí)現(xiàn)在群體規(guī)模恒定下，刪除較弱適應(yīng)度的個(gè)體，以免群體內(nèi)較強(qiáng)適應(yīng)度個(gè)體遭到淘汰，然后對未被刪除的個(gè)體予以交叉、變異處理，由此得到下一代個(gè)體。在選擇環(huán)節(jié)，筆者綜合應(yīng)用輪盤賭法及精英保留策略，以確保機(jī)器人適應(yīng)度目標(biāo)的實(shí)現(xiàn)。

2.4.2 交叉操作

交叉環(huán)節(jié)內(nèi)，彼此配對的兩個(gè)個(gè)體交換部分基因，進(jìn)而獲得兩個(gè)新個(gè)體。生物進(jìn)化過程十分繁瑣，其中最重要的是染色體重組、變異。所以，遺傳算法最重要的步驟為交叉環(huán)節(jié)，其賦予了算法極強(qiáng)的搜索能力。以二進(jìn)制編碼為例，目前應(yīng)用最廣泛的交叉方法有如下3種[17-20]：

（1）單點(diǎn)交叉。交叉的兩個(gè)個(gè)體編碼串內(nèi)，隨機(jī)選擇某交叉點(diǎn)進(jìn)行交叉，則它們的點(diǎn)前或點(diǎn)后部分會(huì)產(chǎn)生兩個(gè)新個(gè)體。用X1、X2代表待交叉的兩個(gè)個(gè)體，則有：

隨機(jī)位置選擇5，通過單點(diǎn)交叉得到新個(gè)體 Y1、Y2。

（2）兩點(diǎn)交叉。上一種交叉方式僅需采用一個(gè)交叉點(diǎn)，其需用到兩個(gè)交叉點(diǎn)，然后交換兩者結(jié)構(gòu)，用X1、X2代表待交叉的兩個(gè)個(gè)體，則有：

隨機(jī)位置選擇3、7，完成交叉操作后得到個(gè)體 Y1、Y2。

（3）一致交叉。采用該交叉方式時(shí)，需要設(shè)定屏蔽字，從而確定兩個(gè)父代個(gè)體含有的特定基因可延續(xù)至下一代。當(dāng)屏蔽字為0時(shí)，父代X1基因?qū)⑦z傳予子代個(gè)體Y1;在屏蔽字為1時(shí)，父代個(gè)體X2基因?qū)⑦z傳予子代個(gè)體Y1，由此得到子代個(gè)體Y1，否則得到子代個(gè)體Y2，例如：

2.4.3 變異操作

變異的本質(zhì)是用基因取代染色體中的某些基因，從而得到全新的染色體。該環(huán)節(jié)旨在確保種群具有充分的多樣性，同時(shí)降低出現(xiàn)早熟收斂問題的可能性。以二進(jìn)制編碼串為例，目前應(yīng)用最廣泛的變異操作包含[21-22]：

（1）基本變異?；谧儺惛怕?，個(gè)體染色體編碼串內(nèi)隨機(jī)挑選一個(gè)或更多基因展開變異，其詳細(xì)操作如下：

在3和6這兩個(gè)位置發(fā)生變異，此時(shí)可得新個(gè)體Y1。

（2）逆轉(zhuǎn)變異。逆轉(zhuǎn)變異也屬于基本變異范疇。通過隨機(jī)方法，在染色體編碼串內(nèi)挑選兩個(gè)點(diǎn)進(jìn)行逆轉(zhuǎn)，基于逆轉(zhuǎn)概率對兩點(diǎn)基因值展開反向排序。以二進(jìn)制編碼串為例，其逆轉(zhuǎn)變異過程如下：

于3、7兩個(gè)位置產(chǎn)生逆轉(zhuǎn)變異，此時(shí)可得到個(gè)體Y1。

（3）自適應(yīng)變異。該方式的變異概率可基于種群多樣性靈活改變。通常情況下，其與交叉環(huán)節(jié)得到的子代個(gè)體海明距離呈線性負(fù)相關(guān)關(guān)系。

2.5 遺傳算法流程

遺傳算法流程如圖2所示。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)結(jié)果

為了解算法改良后的效果，在[20×20]的柵格環(huán)境模型中對算法展開仿真分析，然后與經(jīng)典遺傳算法進(jìn)行對比。在應(yīng)用經(jīng)典遺傳算法時(shí)，隨機(jī)產(chǎn)生初始種群，通過輪盤賭法確定算子，算法參數(shù)包括：種群規(guī)模[M=50]，交叉概率[pc=0.8]，變異概率[pm=0.1]，最大進(jìn)化代數(shù)[T=100]。實(shí)驗(yàn)結(jié)果見圖3-圖5，對該圖進(jìn)行分析可以確定該算法提供的路徑比經(jīng)典算法更短。

3.2 算法對比分析

在實(shí)驗(yàn)中保持控制參數(shù)不變，如種群規(guī)模、交叉或變異概率、遺傳代數(shù)上限值等。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的算法能夠在更短的時(shí)間內(nèi)得到全局最優(yōu)解，在收斂時(shí)不會(huì)出現(xiàn)局部最優(yōu)解。兩種算法在路徑規(guī)劃時(shí)間、最短路徑長度方面的對比詳見表1。對表中數(shù)據(jù)進(jìn)行分析可知，優(yōu)化后的算法能夠在更短的時(shí)間內(nèi)給出規(guī)劃路徑，且路徑長度比經(jīng)典算法更短。

4 結(jié)語

經(jīng)典遺傳算法收斂耗時(shí)長、容易出現(xiàn)局部最優(yōu)解等缺陷極大限制了其在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域的應(yīng)用。為此，本文對適應(yīng)度函數(shù)進(jìn)行重新定義，從而有效優(yōu)化了遺傳算法，使算法能夠在更短時(shí)間內(nèi)完成進(jìn)化。在柵格環(huán)境中展開實(shí)驗(yàn)以了解優(yōu)化后的算法表現(xiàn)。結(jié)果發(fā)現(xiàn)，經(jīng)過優(yōu)化后的遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃方面具有更大的實(shí)用性。但是本文遺傳算法時(shí)效性與準(zhǔn)確性有待提高，下一步研究可采用鯨魚優(yōu)化算法提高遺傳算法算子的優(yōu)良性，降低搜索范圍，大幅降低傳統(tǒng)遺傳算法工作量，盡量規(guī)避局部最優(yōu)解出現(xiàn)的可能性。

參考文獻(xiàn)：

[1] 孫紹華，王魁生，張?zhí)裉? 基于Mirosot平臺(tái)改進(jìn)遺傳算法避障策略[J]. 中北大學(xué)學(xué)報(bào)：自然科學(xué)版，2019（1）：70-73+78.

[2] 牟玲龍，柴永生，殷守民，等. 一種多關(guān)節(jié)機(jī)器人幾何標(biāo)定方法研究[J]. 機(jī)電工程技術(shù)，2019（1）：16-20+142.

[3] 劉寧寧，陳志軍，閆學(xué)勤. 基于IAFSA和AGA混合算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 現(xiàn)代電子技術(shù)，2019（3）：157-162.

[4] 裴以建，楊亮亮，楊超杰. 基于一種混合遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 現(xiàn)代電子技術(shù)，2019，42（2）：183-186.

[5] 溫貽芳，孫立寧，徐朋. 表面改性冗余機(jī)器人關(guān)節(jié)空間的軌跡優(yōu)化算法[J]. 機(jī)械科學(xué)與技術(shù)，2018，37（12）：1870-1874.

[6] 陳爾奎，吳梅花. 基于改進(jìn)遺傳算法和改進(jìn)人工勢場法的復(fù)雜環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃[J]. 科學(xué)技術(shù)與工程，2018，18（33）：79-85.

[7] 趙蕊，許建，王淼，等. 基于遺傳算法和分?jǐn)?shù)階技術(shù)的水下機(jī)器人航向控制[J]. 中國艦船研究，2018，13（6）：87-93.

[8] 薛陽，張曉宇，江天博，等. 基于視覺導(dǎo)航的巡檢機(jī)器人雙?？刂蒲芯縖J]. 控制工程，2018，25（11）：1982-1987.

[9] 侯慶隆，楊冬，郭士杰. 工業(yè)機(jī)器人能耗優(yōu)化方法研究綜述[J]. 計(jì)算機(jī)工程與應(yīng)用，2018，54（22）：1-9.

[10] 楊帥，鄒智慧. 積分滑模水下機(jī)器人導(dǎo)航定位控制方法仿真[J]. 計(jì)算機(jī)仿真，2018，35（11）：306-309+365.

[11] 于振中，李強(qiáng)，樊啟高. 智能仿生算法在移動(dòng)機(jī)器人路徑規(guī)劃優(yōu)化中的應(yīng)用綜述[J/OL]. 計(jì)算機(jī)應(yīng)用研究：1-13.2018-11-05. http：//www.arocmag.com/article/02-2019-11-086.html.

[12] 吳瑞芳，孫兆丹. 采用粒子群算法耦合遺傳算法優(yōu)化雙臂機(jī)器人模糊邏輯控制研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù)，2018（10）：40-43.

[13] 陳慶勝. 基于改進(jìn)遺傳算法的機(jī)器人軌跡跟蹤[J]. 智能機(jī)器人，2018（5）：58-61.

[14] 陳爾奎，吳梅花，張英杰. 復(fù)雜環(huán)境下煤礦救災(zāi)機(jī)器人路徑規(guī)劃[J]. 煤炭技術(shù)，2018，37（10）：301-304.

[15] 林曉青，楊繼之，樂毅，等. 一種可移動(dòng)檢測機(jī)器人站位規(guī)劃策略[J]. 宇航學(xué)報(bào)，2018，39（9）：1031-1038.

[16] 張毅，劉芳君，胡磊. 結(jié)合MPGA-RBFNN的一般機(jī)器人逆運(yùn)動(dòng)學(xué)求解[J]. 智能系統(tǒng)學(xué)報(bào)，2019（1）：165-170.

[17] 曹凱，高佳佳，高嵩，等. 移動(dòng)機(jī)器人在復(fù)雜環(huán)境中的在線路徑規(guī)劃[J]. 自動(dòng)化與儀表，2018，33（9）：27-31+62.

[18] 李房云，趙巍，鄧文鵬. 基于行為進(jìn)化的智能保潔機(jī)器人設(shè)計(jì)與仿真[J]. 計(jì)算機(jī)產(chǎn)品與流通，2018（9）：128.

[19] 梁凱，陳志軍，閆學(xué)勤. 移動(dòng)機(jī)器人路徑規(guī)劃仿真研究[J]. 現(xiàn)代電子技術(shù)，2018，41（17）：167-172.

[20] 翁祖昊. 遺傳算法在自動(dòng)機(jī)器人揀貨路徑選擇中的應(yīng)用研究[J]. 自動(dòng)化應(yīng)用，2018（8）：91-92.

[21] 侯仰強(qiáng)，王天琪，岳建鋒，等. 基于多目標(biāo)遺傳算法的雙機(jī)器人協(xié)調(diào)焊接路徑規(guī)劃[J]. 中國機(jī)械工程，2018，29（16）：1984-1989.

[22] 賈超廣，肖海霞，胡廣新. 基于改進(jìn)遺傳算法的包裝機(jī)器人軌跡規(guī)劃[J]. 包裝工程，2018，39（15）：183-187.

（責(zé)任編輯：江 艷）