虞馥澤，潘大志,2

(1.西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院，四川 南充 637009；2.西華師范大學(xué) 計(jì)算方法與應(yīng)用研究所，四川 南充 637009)

0 引 言

路徑規(guī)劃是指在有障礙物的環(huán)境中，依據(jù)一些標(biāo)準(zhǔn)搜索一條由起點(diǎn)到目標(biāo)點(diǎn)的安全無碰撞路徑。常用路徑規(guī)劃算法大致可分為：傳統(tǒng)算法、圖形學(xué)法、智能仿生學(xué)法及其他算法。傳統(tǒng)算法有人工勢(shì)場(chǎng)法[1]、模糊控制算法[2]等。圖形學(xué)法有C空間法[3]、柵格法[4]等。智能仿生學(xué)算法有模擬退火算法[5]、蟻群算法[6]、粒子群算法[7]、遺傳算法[8]等。

蟻群算法是Marco Dorigo受螞蟻覓食啟發(fā)，于1992年提出的一種仿生算法[9]。為解決蟻群算法在路徑規(guī)劃上的不足，研究人員提出了對(duì)它的各種改進(jìn)。牛龍輝等[10]提出的一種自適應(yīng)蟻群算法，引入自適應(yīng)信息素?fù)]發(fā)系數(shù)，能較好地提高算法收斂速度，但是對(duì)于路徑平滑性的改進(jìn)不夠；胡春陽等[11]利用頭尾搜索機(jī)制以及遺傳算法對(duì)改進(jìn)后的蟻群算法進(jìn)行參數(shù)優(yōu)化、引入獎(jiǎng)懲因子以及多指標(biāo)適應(yīng)度函數(shù)，對(duì)避免局部最優(yōu)和收斂速度方面有很大改進(jìn)；甄然等[12]提出的自適應(yīng)多態(tài)融合蟻群策略，在多態(tài)蟻群算法的基礎(chǔ)上，引入自適應(yīng)并行規(guī)則和偽隨機(jī)規(guī)則，以提高算法全局尋優(yōu)能力；趙靜等[13]通過改進(jìn)啟發(fā)函數(shù)和信息素?fù)]發(fā)因子以提升其全局搜尋能力；韓顏等[14]是根據(jù)粒子群算法最優(yōu)解調(diào)整路徑上初始信息素分布，解決蟻群算法中初始信息素缺乏的問題，并且利用簡(jiǎn)化操作優(yōu)化路徑，優(yōu)化后的路徑距離短且相對(duì)平滑，但是對(duì)于局部路徑平滑性的改進(jìn)依舊不足。趙開新等[15]提出將遺傳算法與蟻群算法相結(jié)合，利用遺傳算法得到的較優(yōu)個(gè)體設(shè)置蟻群的初始信息素，在蟻群算法更新全局最優(yōu)中，將當(dāng)前最優(yōu)與全局最優(yōu)路徑通過交叉操作，更新當(dāng)前最優(yōu)，進(jìn)而更新全局最優(yōu)。

對(duì)靜態(tài)全局環(huán)境下求解路徑的規(guī)劃方法做出改進(jìn)，提高算法的路徑規(guī)劃能力，是該文的研究目的。通過對(duì)兩種智能仿生算法進(jìn)行分析，將遺傳算法及蟻群算法融合求解路徑規(guī)劃，利用遺傳算法得到的較優(yōu)路徑，來設(shè)置蟻群算法所需的初始信息素，引導(dǎo)蟻群算法進(jìn)一步尋優(yōu)，最終得到全局最優(yōu)。

1 環(huán)境建模

進(jìn)行路徑規(guī)劃之前先建立環(huán)境地圖，該文采用柵格法建立移動(dòng)機(jī)器人的行走環(huán)境模型。將機(jī)器人處理為質(zhì)點(diǎn)，行走空間為二維空間，障礙物的大小、位置已知。

如圖1以4×4的柵格矩陣為例，map表示柵格環(huán)境矩陣，可行區(qū)域?yàn)榘咨?，即map(i,j)=0；禁行區(qū)域?yàn)楹谏?，即map(i,j)=1。從左上角到右下角、從左到右、從上往下對(duì)柵格編號(hào)，依次為{1,2,…,16}。

圖1 柵格矩陣及柵格地圖

在環(huán)境模型中，每個(gè)柵格均與二維空間中的一個(gè)坐標(biāo)(x,y)相對(duì)應(yīng)。如圖1所示，柵格1對(duì)應(yīng)坐標(biāo)(0.5,3.5)、柵格2對(duì)應(yīng)坐標(biāo)(1.5,3.5)，以此類推，利用式(1)、(2)可將柵格序號(hào)轉(zhuǎn)化為對(duì)應(yīng)坐標(biāo)。

(1)

(2)

其中，N、M分別是柵格環(huán)境矩陣的行數(shù)、列數(shù)，index為柵格序號(hào)。

2 遺傳算法

2.1 染色體編碼

柵格序號(hào)形式簡(jiǎn)單，易于遺傳操作，故采用柵格序號(hào)對(duì)染色體進(jìn)行編碼。P={p1,p2,…,pn}表示一條路徑，其中pi(i=1,2,…,n)為路徑上第i個(gè)節(jié)點(diǎn)的柵格序號(hào)，p1、pn分別為起止柵格序號(hào)。

2.2 適應(yīng)度函數(shù)及選擇策略

由于在生物遺傳進(jìn)化過程中，適應(yīng)度較高的個(gè)體遺傳到下一代的概率較大，反之則較小。故該文將適應(yīng)度函數(shù)設(shè)定為機(jī)器人從起點(diǎn)到終點(diǎn)所經(jīng)歷的路徑長(zhǎng)度的倒數(shù)。

采用輪盤賭的方式選擇出下一代個(gè)體，確保部分非最優(yōu)的個(gè)體進(jìn)入下一代，有效地避免算法陷入局部最優(yōu)。

2.3 交叉策略

采用單點(diǎn)交叉，具體過程為：先找出兩父代個(gè)體中除去起止點(diǎn)外所有相同的點(diǎn)構(gòu)成集合I，若I非空，則隨機(jī)選擇其中的一個(gè)基因，在父代中將其之后的路徑進(jìn)行交叉；反之則不交叉。

例如，父代個(gè)體分別為{1,8,11,14,17,19,21,22,26,30}、{1,6,8,9,13,14,18,19,28,30}，I={8,14,19}，產(chǎn)生一個(gè)隨機(jī)正整數(shù)R=2，則交換路徑節(jié)點(diǎn)I(R)后面的路徑，得到子代{1,8,11,14,18,19,28,30}和{1,6,8,9,13,14,17,19,21,22,26,30}。

2.4 變異策略

隨機(jī)選取父代個(gè)體中除起點(diǎn)和終點(diǎn)以外的兩個(gè)不相鄰柵格，刪去這兩個(gè)柵格之間的路徑，再分別以這兩個(gè)柵格為起止點(diǎn)，使用路徑初始化方法對(duì)這兩個(gè)柵格進(jìn)行連續(xù)化操作。若無法產(chǎn)生新的連續(xù)路徑，則重新選擇兩個(gè)不相鄰柵格執(zhí)行連續(xù)化操作。

例如，對(duì)于父代{1,8,11,14,17,19,21,22,26,30}，隨機(jī)選兩個(gè)柵格11和22，若連續(xù)化操作得到{11,13,16,17,18,21,22}，則得到新個(gè)體{1,8,11,13,16,17,18,21,22,26,30}。

3 蟻群算法

蟻群算法是一種仿生算法，在路徑規(guī)劃中的應(yīng)用主要分為覓食規(guī)則、行走規(guī)則及信息素規(guī)則。覓食規(guī)則要求建立禁忌表，規(guī)定螞蟻可行位置；行走規(guī)則要求螞蟻k在當(dāng)前節(jié)點(diǎn)i轉(zhuǎn)移到下一節(jié)點(diǎn)j的轉(zhuǎn)移概率由信息素濃度和啟發(fā)式函數(shù)決定，即式(3)決定。

(3)

(4)

其中，dj, end為柵格j距目標(biāo)柵格的歐氏距離[16]。

3.1 信息素規(guī)則

初始信息素產(chǎn)生規(guī)則。針對(duì)初始信息素匱乏的問題，采用遺傳算法尋找初始較優(yōu)路徑集合，按照適應(yīng)度排序，選取前50%的較優(yōu)個(gè)體，不考慮信息素的揮發(fā)，只考慮對(duì)走過的路徑進(jìn)行信息素增加，根據(jù)式(5)、(6)得到蟻群算法所需的初始信息素。

(5)

(6)

其中，ganum為種群規(guī)模，Q為常數(shù)，Lm為個(gè)體m所走路徑長(zhǎng)。

信息素更新規(guī)則。隨著時(shí)間的推移，螞蟻在運(yùn)動(dòng)中留下信息素的同時(shí)，路徑上已存的信息素按照一定比例丟失。蟻群完成一次循環(huán)后，各路徑上的信息素按式(7)～式(9)更新。

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(7)

(8)

(9)

其中，ρ∈(0,1)為信息素?fù)]發(fā)因子，antnum為螞蟻數(shù)，Q為常數(shù)，Lk為螞蟻k所走路徑長(zhǎng)。

3.2 簡(jiǎn)化操作

為進(jìn)一步優(yōu)化路徑及其長(zhǎng)度，加入簡(jiǎn)化操作。圖2給出了簡(jiǎn)化操作示意圖。從起點(diǎn)開始遍歷，與當(dāng)前點(diǎn)不相鄰的點(diǎn)相連接，得到的路徑不經(jīng)過障礙物，則刪去冗余節(jié)點(diǎn)并重新計(jì)算適應(yīng)度。

圖2 簡(jiǎn)化路徑示意圖

4 遺傳-蟻群算法設(shè)計(jì)

利用遺傳算法對(duì)蟻群算法的信息素進(jìn)行優(yōu)化，解決蟻群算法初始信息素缺乏的問題，以此來提高算法精度。具體做法是利用遺傳算法得到的較優(yōu)解，計(jì)算得到蟻群算法所需的初始信息素，再用蟻群算法求解最優(yōu)路徑。遺傳-蟻群算法流程如圖3所示。

圖3 遺傳-蟻群算法流程

遺傳-蟻群算法步驟：

步驟1：初始化遺傳算法參數(shù)；初始化染色體；保留當(dāng)前全局最優(yōu)。

步驟2：選擇、交叉、變異操作；更新全局最優(yōu)。

步驟3：利用截?cái)噙x擇，根據(jù)式(5)、(6)更新信息素。

步驟4：若是達(dá)到最大迭代次數(shù)，或當(dāng)前全局最優(yōu)與前若干次全局最優(yōu)相同，則停止迭代，輸出次優(yōu)解；否則返回步驟2。

步驟5：蟻群參數(shù)初始化。

步驟6：利用式(2)移動(dòng)螞蟻；計(jì)算路徑長(zhǎng)度；利用式(7)～式(9)更新信息素。

步驟7：更新全局最優(yōu)，簡(jiǎn)化路徑。

步驟8：若達(dá)到最大迭代次數(shù)，則輸出最優(yōu)值。否則返回步驟6。

5 仿真結(jié)果分析

為驗(yàn)證遺傳-蟻群算法的性能，構(gòu)建地圖模型進(jìn)行仿真對(duì)比實(shí)驗(yàn)。遺傳算法參數(shù)：ganum=30、pc=0.8、pm=0.2、Q=1；蟻群算法參數(shù)：antnum=50、α=5、β=2.5、Q=1、ρ=0.01。為了增加對(duì)比性，分析文中算法的有效性，分別做了以下兩組對(duì)比實(shí)驗(yàn)。

實(shí)驗(yàn)一采用文獻(xiàn)[11]的30×30柵格地圖。由圖4知，各個(gè)算法均可找到一條由起點(diǎn)抵達(dá)終點(diǎn)的路徑，基本蟻群算法(如圖4(a))、文獻(xiàn)[11]算法(如圖4(b))、文獻(xiàn)[13]算法(如圖4(c))及文獻(xiàn)[15]算法(如圖4(d))的最優(yōu)路徑長(zhǎng)分別為56.769 6、44.526 9、42.183 8、45.526 9，文中算法(如圖4(e))的最優(yōu)路徑長(zhǎng)為41.471 2，效果最好。圖4(f)所示為算法每次迭代的最優(yōu)路徑，可知文中算法收斂速度更快且最優(yōu)路徑更短。為驗(yàn)證文中算法的優(yōu)越性，采用最優(yōu)路徑長(zhǎng)、運(yùn)行若干次的平均最優(yōu)路徑長(zhǎng)、最佳迭代次數(shù)作為對(duì)比算法相關(guān)指標(biāo)，其詳細(xì)數(shù)據(jù)如表1所示。綜合對(duì)比易知，文中算法在提高全局搜索能力以及收斂速度方面有很大改進(jìn)。

(a)傳統(tǒng)蟻群算法

(b)文獻(xiàn)[11]算法

(c)文獻(xiàn)[13]算法

(d)文獻(xiàn)[15]算法

(e)文中算法

(f)迭代圖

表1 實(shí)驗(yàn)一算法指標(biāo)

實(shí)驗(yàn)二采用40×40柵格地圖。各算法找到的最優(yōu)路徑如圖6，傳統(tǒng)蟻群算路徑長(zhǎng)為67.497 5，文獻(xiàn)[11]算法路徑長(zhǎng)為64.426 4，文獻(xiàn)[13]算法路徑長(zhǎng)為61.012 2，文獻(xiàn)[15]算法路徑長(zhǎng)為65.598 0，文中算法最優(yōu)路徑長(zhǎng)為58.110 5。將算法指標(biāo)記入表2，同時(shí)如圖5(f)最優(yōu)路徑迭代可知，在復(fù)雜環(huán)境下，文中算法相比于其他算法仍具有較好的全局搜索能力。

(a)傳統(tǒng)蟻群算法

(b)文獻(xiàn)[11]算法

(c)文獻(xiàn)[13]算法

(d)文獻(xiàn)[15]算法

(e)文中算法

(f)迭代圖

表2 實(shí)驗(yàn)二算法指標(biāo)

實(shí)驗(yàn)結(jié)果表明：提出的遺傳-蟻群算法相比于其他算法具有全局搜索能力強(qiáng)且收斂速度快的優(yōu)點(diǎn)，能快速、準(zhǔn)確、高效地實(shí)現(xiàn)機(jī)器人的路徑規(guī)劃。

6 結(jié)束語

針對(duì)蟻群算法在靜態(tài)環(huán)境下的機(jī)器人路徑規(guī)劃中存在的初始信息素缺乏、易陷入局部最優(yōu)、搜索效率低等缺陷，提出了將遺傳算法和蟻群算法融合的方案。相對(duì)于傳統(tǒng)蟻群算法按照經(jīng)驗(yàn)設(shè)定初始信息素的方式，該文采取對(duì)遺傳算法每次迭代得到的種群按照適應(yīng)度降序排列，選取種群前50%的較優(yōu)個(gè)體，根據(jù)初始信息素產(chǎn)生規(guī)則得到蟻群算法所需的初始信息素；由于混合算法涉及到算法之間的轉(zhuǎn)換時(shí)間問題，文中設(shè)計(jì)相應(yīng)的控制策略來控制遺傳算法向蟻群算法轉(zhuǎn)換的時(shí)機(jī)；為使規(guī)劃路徑更平滑且距離更短，對(duì)蟻群算法得到的全局最優(yōu)路徑采取簡(jiǎn)化操作。在柵格環(huán)境下對(duì)機(jī)器人路徑規(guī)劃進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，該算法具有全局搜索能力強(qiáng)、收斂速度快的優(yōu)點(diǎn)，在路徑規(guī)劃上是可行且有效的。