陳亮 陳君若

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

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

DOI：10. 11907/rjdk. 191190

中圖分類號：TP301文獻標識碼：A文章編號：1672-7800（2019）004-0024-04

0 引言

目前機器人智能化發(fā)展迅速，在工業(yè)、科學探索、國防軍事等重要領(lǐng)域應(yīng)用廣泛。移動機器人是深度智能和人類智慧融合的產(chǎn)物，也是機械控制、傳感器、仿生學、信號處理等若干學科交叉發(fā)展的結(jié)果[1-4]。當前，移動機器人主要應(yīng)用難題之一是路徑規(guī)劃，即如何使機器人在避開各種障礙的前提下，以最優(yōu)路徑從出發(fā)點移動到目標點。通常情況下，移動機器人工作環(huán)境較為復(fù)雜，首先需確定任務(wù)，然后機器人按照各方面環(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)、動態(tài)障礙環(huán)境下移動機器人路徑規(guī)劃。

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

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

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

2.1 路徑編碼

按照由左到右、由上到下的順序，將柵格從1-400進行編號，1號、400號柵格分別是機器人移動起點和終點。利用MATLAB完成柵格模型序號編碼（見圖1）。

2.2 種群初始化

2.2.1 柵格路徑選擇

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

2.2.2 算子插入

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

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

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

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

2.4 遺傳操作

2.4.1 算子選擇

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

2.4.2 交叉操作

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

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

隨機位置選擇5，通過單點交叉得到新個體 Y1、Y2。

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

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

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

2.4.3 變異操作

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

（1）基本變異。基于變異概率，個體染色體編碼串內(nèi)隨機挑選一個或更多基因展開變異，其詳細操作如下：

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

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

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

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

2.5 遺傳算法流程

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

3 實驗結(jié)果與分析

3.1 實驗結(jié)果

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

3.2 算法對比分析

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

4 結(jié)語

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

參考文獻：

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

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

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

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

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

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

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

[8] 薛陽，張曉宇，江天博，等. 基于視覺導航的巡檢機器人雙模控制研究[J]. 控制工程，2018，25（11）：1982-1987.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（責任編輯：江 艷）