基于動態(tài)啟發(fā)算子的雙種群蟻群算法及其應(yīng)用*

尹元元， 游曉明， 許明樂， 劉 升

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

0 引 言

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

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

1 蟻群系統(tǒng)

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

1)路徑建立

在ACS中，螞蟻從當(dāng)前節(jié)點i選擇下一個城市節(jié)點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ā)因子；β為能見度啟發(fā)因子，反映能見度信息的相對重要性；allowedk為螞蟻下一步可選擇的城市節(jié)點組合。

2)信息素更新

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

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

(3)

2 改進(jìn)的ACS

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

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

(4)

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

2.2 新型雙種群

在種群A所得當(dāng)代最優(yōu)路徑上隨機(jī)選取兩點作為種群B的起點SB和終點GB，且種群B重新規(guī)劃兩點之間的路徑：若種群B找到的兩點間的最短路徑比該段由種群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只螞蟻置于起始點S。

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

4)計算兩柵格SB與OB之間的路徑長度d1。

5)將柵格SB，OB作為種群B的起點和終點，計算所得路徑長度d2。

6)若d2

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

3 仿真分析

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

圖1 ACS與IACS在4種地圖下的仿真實驗

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

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

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

4 結(jié)束語

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