尹元元， 游曉明， 許明樂(lè)， 劉 升

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201600； 2.上海工程技術(shù)大學(xué) 機(jī)械工程學(xué)院，上海 201600)

0 引 言

許多智能算法用于解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，并取得了很好的效果，其中蟻群優(yōu)化(ant colony optimization,ACO)算法首先成功解決了旅行商問(wèn)題[1]，其后在組合優(yōu)化領(lǐng)域得到了廣泛應(yīng)用[2～4]。然而，蟻群算法在解決路徑規(guī)劃問(wèn)題時(shí)存在收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題。為了提高算法的收斂速度，唐良等人[5]引入了方向啟發(fā)，加強(qiáng)搜索限定搜索范圍為從起點(diǎn)到終點(diǎn)的橢圓區(qū)域。柳長(zhǎng)安等人[6]提出了根據(jù)目標(biāo)點(diǎn)自適應(yīng)函數(shù)作為啟發(fā)因子，加快了算法收斂速度。文獻(xiàn)[7]通過(guò)建立雙蟻群完全交叉算法，解決復(fù)雜凹形障礙環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題，仿真實(shí)驗(yàn)結(jié)果證明了該算法的有效性。文獻(xiàn)[8]引入雙種群獨(dú)立搜索，保證解的多樣性的同時(shí)，提高算法收斂速度。文獻(xiàn)[9]采用兩個(gè)蟻群分別進(jìn)行進(jìn)化求解，并定期交換優(yōu)良解，增加了解的多樣性。

本文算法采用雙種群A與B，首先由蟻群A構(gòu)造一條完整路徑，在該路徑上隨機(jī)選取兩點(diǎn)作為種群B的起點(diǎn)和終點(diǎn)，重新規(guī)劃兩點(diǎn)之間的路徑，并比較兩段路徑優(yōu)劣，判斷是否進(jìn)行該段解的替換，并全局更新種群B規(guī)劃所得路徑的信息素。此外，兩種群也采用不同的局部信息素?fù)]發(fā)系數(shù)[10],進(jìn)行了柵格環(huán)境下的機(jī)器人路徑規(guī)劃仿真實(shí)驗(yàn)[11]，結(jié)果證明本文算法在收斂速度、避免算法陷入局部最優(yōu)等方面都具有很好的表現(xiàn)。

1 蟻群系統(tǒng)

蟻群系統(tǒng)(ant conlony system,ACS)2個(gè)重要步驟如下：

1)路徑建立

在ACS中，螞蟻從當(dāng)前節(jié)點(diǎn)i選擇下一個(gè)城市節(jié)點(diǎn)j，其狀態(tài)轉(zhuǎn)移規(guī)則為

(1)

式中q為0～1之間的隨機(jī)數(shù)，q0∈(0,1)為可調(diào)參數(shù)，S為基本蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則

(2)

式中τij為路徑上的信息素濃度；ηij為啟發(fā)因子；β為能見(jiàn)度啟發(fā)因子，反映能見(jiàn)度信息的相對(duì)重要性；allowedk為螞蟻下一步可選擇的城市節(jié)點(diǎn)組合。

2)信息素更新

每只螞蟻建立一條從起點(diǎn)到終點(diǎn)的路徑后，需要對(duì)路徑上的信息素進(jìn)行局部更新，當(dāng)所有螞蟻完成一次循環(huán)后，將對(duì)當(dāng)前所有路徑中的最短路徑進(jìn)行全局信息素更新

τij=(1-α)τij+αΔτij

(3)

2 改進(jìn)的ACS

2.1 動(dòng)態(tài)隨機(jī)啟發(fā)算子

本文將兩種群分為種群A與種群B，其中，種群B中應(yīng)用動(dòng)態(tài)隨機(jī)啟發(fā)算子，其起始點(diǎn)SB和目標(biāo)點(diǎn)OB在種群A規(guī)劃所得的路徑上隨機(jī)選取。當(dāng)種群A完成一次迭代，種群B根據(jù)當(dāng)代最優(yōu)路徑隨機(jī)選取終點(diǎn)，新的啟發(fā)函數(shù)為

(4)

式中dig為螞蟻可選擇的下個(gè)柵格與種群B隨機(jī)選擇的新的終點(diǎn)之間的距離。

2.2 新型雙種群

在種群A所得當(dāng)代最優(yōu)路徑上隨機(jī)選取兩點(diǎn)作為種群B的起點(diǎn)SB和終點(diǎn)GB，且種群B重新規(guī)劃兩點(diǎn)之間的路徑：若種群B找到的兩點(diǎn)間的最短路徑比該段由種群A規(guī)劃所得路徑質(zhì)量更優(yōu)，則用種群B規(guī)劃的最優(yōu)路徑替換種群A的該段路徑，并全局更新種群B規(guī)劃所得路徑的信息素；否則，種群B不進(jìn)行全局信息素更新。

2.3 算法步驟

1)參數(shù)初始化，包括：兩蟻群規(guī)模m1，m2，最大迭代次數(shù)K，表征啟發(fā)式信息重要程度的參數(shù)β，信息素蒸發(fā)因子ρ，新增信息素強(qiáng)度因子q等。

2)將種群A中m1只螞蟻置于起始點(diǎn)S。

3)選取種群A的當(dāng)代最短路徑，并在該路徑上隨機(jī)選擇兩柵格SB，OB。

4)計(jì)算兩柵格SB與OB之間的路徑長(zhǎng)度d1。

5)將柵格SB，OB作為種群B的起點(diǎn)和終點(diǎn)，計(jì)算所得路徑長(zhǎng)度d2。

6)若d2

7)若循環(huán)次數(shù)NC≥NCmax，則算法結(jié)束；否則；轉(zhuǎn)到步驟(3)。

3 仿真分析

為了驗(yàn)證改進(jìn)算法的有效性，本文分別采用ACS和改進(jìn)的蟻群系統(tǒng)(improved ACS,IACS)在MATLAB軟件平臺(tái)下進(jìn)行機(jī)器人路徑規(guī)劃仿真實(shí)驗(yàn)。圖1為2種算法在4種地圖下的路徑規(guī)化對(duì)比。

圖1 ACS與IACS在4種地圖下的仿真實(shí)驗(yàn)

由表1、表2的實(shí)驗(yàn)結(jié)果證明，改進(jìn)的算法在最短路徑和平均路徑長(zhǎng)度以及路徑長(zhǎng)度的極差和標(biāo)準(zhǔn)差等方面表現(xiàn)得更好,且與傳統(tǒng)ACS相比，IACS算法找到最優(yōu)路徑的次數(shù)高很多，平均迭代時(shí)間較少，顯然，改進(jìn)后的算法具有更好的規(guī)劃效率。

表1 ACS與IACS的路徑規(guī)劃仿真實(shí)驗(yàn)結(jié)果 cm

表2 ACS與IACS的路徑規(guī)劃結(jié)果比較

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

本文介紹了一種改進(jìn)的雙種群蟻群算法，仿真結(jié)果表明：該算法能夠克服傳統(tǒng)ACS算法的缺點(diǎn)，具有較好的路徑規(guī)劃性能。