基于動態啟發算子的雙種群蟻群算法及其應用*

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

(1.上海工程技術大學 電子電氣工程學院，上海 201600； 2.上海工程技術大學 機械工程學院，上海 201600)

0 引 言

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

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

1 蟻群系統

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

1)路徑建立

在ACS中，螞蟻從當前節點i選擇下一個城市節點j，其狀態轉移規則為

(1)

式中q為0～1之間的隨機數，q0∈(0,1)為可調參數，S為基本蟻群算法的狀態轉移規則

(2)

式中τij為路徑上的信息素濃度；ηij為啟發因子；β為能見度啟發因子，反映能見度信息的相對重要性；allowedk為螞蟻下一步可選擇的城市節點組合。

2)信息素更新

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

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

(3)

2 改進的ACS

2.1 動態隨機啟發算子

本文將兩種群分為種群A與種群B，其中，種群B中應用動態隨機啟發算子，其起始點SB和目標點OB在種群A規劃所得的路徑上隨機選取。當種群A完成一次迭代，種群B根據當代最優路徑隨機選取終點，新的啟發函數為

(4)

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

2.2 新型雙種群

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

2.3 算法步驟

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

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

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

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

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

6)若d2

7)若循環次數NC≥NCmax，則算法結束；否則；轉到步驟(3)。

3 仿真分析

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

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

由表1、表2的實驗結果證明，改進的算法在最短路徑和平均路徑長度以及路徑長度的極差和標準差等方面表現得更好,且與傳統ACS相比，IACS算法找到最優路徑的次數高很多，平均迭代時間較少，顯然，改進后的算法具有更好的規劃效率。

表1 ACS與IACS的路徑規劃仿真實驗結果 cm

表2 ACS與IACS的路徑規劃結果比較

4 結束語

本文介紹了一種改進的雙種群蟻群算法，仿真結果表明：該算法能夠克服傳統ACS算法的缺點，具有較好的路徑規劃性能。