基于模擬退火蟻群算法的機(jī)器人路徑規(guī)劃

王正存 張曉玲 吳作君

摘 要：針對蟻群算法在機(jī)器人路徑規(guī)劃中易陷入局部最優(yōu)問題，提出首先利用蟻群算法尋找移動路徑，然后采用模擬退火算法進(jìn)行迭代，并加入回火機(jī)制消除局部最優(yōu)，有效提高蟻群算法的全局搜索能力。仿真研究表明，模擬退火蟻群算法在機(jī)器人路徑搜索上可得到較短路徑。

關(guān)鍵詞：蟻群算法；模擬退火；路徑規(guī)劃

機(jī)器人路徑規(guī)劃問題中，路徑規(guī)劃算法是核心，蟻群算法具有較強(qiáng)的優(yōu)化能力和魯棒性，成為近年來的研究熱點(diǎn)。[1] [2]但當(dāng)尋優(yōu)過程中問題規(guī)模變大時，存在收斂精度變低和易落入局部最優(yōu)問題。本文采用改進(jìn)的蟻群算法在搜索路徑過程中，使用模擬退火算法迭代，尋找柵格地圖中的可行性路徑。

1 環(huán)境建模

首先建立機(jī)器人路徑規(guī)劃的工作地圖，鑒于柵格法的方便實(shí)現(xiàn)、高精度優(yōu)點(diǎn)，選用柵格法建立機(jī)器人運(yùn)行的模擬環(huán)境。[3]環(huán)境建模后，需要對柵格地圖進(jìn)行路徑規(guī)劃尋找較短路徑，其中路徑的移動和計算過程如下描述。假設(shè)t時刻機(jī)器人在柵格地圖上移動一步長度d：

d=2，xt+1=xt±1且yt+1=yt±11，xt+1=xt±1或yt+1=yt±1（1）

機(jī)器人從起點(diǎn)到終點(diǎn)所走路徑總長度等于每次移動長度之和。

2 基于模擬退火蟻群算法的路徑規(guī)劃

本文將模擬退火與蟻群算法結(jié)合，旨在解決蟻

群算法在尋優(yōu)過程中不能得到全局最優(yōu)解的問題，其迭代步驟如下：

S1：建立柵格地圖，將機(jī)器人看做一只螞蟻。

S2：初始化參數(shù)，包括螞蟻數(shù)量num、迭代次數(shù)m、模擬退火算法的冷卻系數(shù)q，初始溫度T0，最大回火次數(shù)Hmax等。

S3：初始化信息素和設(shè)置啟發(fā)值，即預(yù)先初始化各邊信息素強(qiáng)度以及各螞蟻的禁忌表。

S4：利用螞蟻搜索路徑，每一步移動方向由不同路徑上的信息濃度決定，并計算轉(zhuǎn)移概率（公式參考文獻(xiàn)[4]）。重復(fù)該過程直到到達(dá)目的地或者找不到目的地退出。

S5：根據(jù)目標(biāo)函數(shù)，計算尋優(yōu)得到的路徑長度，將其與原有路徑比較，若短于原路徑，則接受該路徑，否則更新信息素（公式參考文獻(xiàn)[4]）。

S6：比較當(dāng)前溫度T與前一時刻溫度下的解（指用蟻群算法優(yōu)化得到的解），若較前一時刻溫度下的解好，便保留新解，否則計算溫度T下接受劣解的概率[5]：

P=edEkT（2）

同時產(chǎn)生一個隨機(jī)數(shù)X ，其取值范圍為[0，1]，若X

S7：更新模擬退火溫度，判斷回火次數(shù)是否未達(dá)到或當(dāng)前溫度是否低于最小回火溫度，成立則回火。

S8：檢驗(yàn)?zāi)M退火迭代次數(shù)是否滿足條件，不滿足則進(jìn)入下一次循環(huán)迭代，滿足則退出。

S9：輸出最短路徑。

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

首先在二維平面生成大小為20*20的隨機(jī)柵格地圖，采用序號對柵格編號，藍(lán)色方塊為環(huán)境中的障礙物；然后將傳統(tǒng)蟻群算法和模擬退火蟻群算法分別應(yīng)用到機(jī)器人路徑規(guī)劃中，仿真結(jié)果見圖1、圖2。

仿真結(jié)果對比可見，傳統(tǒng)蟻群算法得到的路徑長度196，模擬退火蟻群算法搜索到的最佳路徑長度179，明顯優(yōu)于傳統(tǒng)算法。

4 結(jié)語

本文在傳統(tǒng)蟻群算法基礎(chǔ)上加入帶回火的模擬退火算法，解決機(jī)器人路徑規(guī)劃時容易陷入局部最優(yōu)、不能得到真正的最短路徑問題。通過MATLAB仿真研究發(fā)現(xiàn)，該模擬退火蟻群算法在路徑搜索上具有更強(qiáng)的尋優(yōu)能力。

參考文獻(xiàn)：

[1]邱莉莉.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].東華大學(xué)，2015.

[2][JP2]屈鴻，黃利偉，柯星.動態(tài)環(huán)境下基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J].電子科技大學(xué)學(xué)報， 2015， 2： 260265.

[3]朱磊，樊繼壯，趙杰，吳曉光，劉罡.基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J].中南大學(xué)學(xué)報（自然科學(xué)版），2011，42（11）：34213428.

[4]何小虎.基于改進(jìn)蟻群算法在糧食物流配送路徑優(yōu)化的應(yīng)用研究[J].電子設(shè)計工程，2016，24（09）：3941.

[5]徐鵬.基于模擬退火算法的機(jī)器人路徑規(guī)劃與研究[J].科技廣場， 2011， 1： 4244.

基金項(xiàng)目：中國石油大學(xué)勝利學(xué)院大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項(xiàng)目資助（2017026）

作者簡介：王正存（1994），男，山東濟(jì)寧人，本科，中國石油大學(xué)勝利學(xué)院機(jī)械與控制工程學(xué)院自動化專業(yè)學(xué)生，主要從事機(jī)器人路徑規(guī)劃研究；張曉玲（1982），女，山東濰坊人，碩士，中國石油大學(xué)勝利學(xué)院講師，主要從事自動化專業(yè)教學(xué)、機(jī)器人路徑規(guī)劃研究、工業(yè)過程故障診斷方法研究等。