陳明杰，黃佰川，張旻

(哈爾濱工程大學(xué)自動化學(xué)院，黑龍江哈爾濱150001)

自2000年國際頂級學(xué)術(shù)刊物《Nature》發(fā)表了M.Dorigo的蟻群算法綜述以來，模擬自然界螞蟻進(jìn)行最優(yōu)路徑搜索的蟻群算法 (ant colony optimization，ACO)［1-13］作為求解組合優(yōu)化問題的有效手段，逐漸成為智能優(yōu)化算法領(lǐng)域的熱點［1］.由于其算法上具有正反饋機制、分布式計算、貪婪式搜索特征以及魯棒性強、并行處理等特點［2］，目前已被廣泛應(yīng)用于組合優(yōu)化問題中，在車輛調(diào)度問題、機器人路徑規(guī)劃問題等領(lǐng)域均取得了良好的效果.對一般函數(shù)的優(yōu)化問題也表現(xiàn)出優(yōu)異的性能，它可以克服傳統(tǒng)優(yōu)化方法的許多不足和缺陷，實現(xiàn)簡單，在函數(shù)不連續(xù)、不可微、局部極值點密集等苛刻的情況，仍然具有很好的尋優(yōu)能力［3］.W.J.Gutjahr發(fā)表的證明蟻群算法收斂性的文章在蟻群算法的發(fā)展過程中具有重要的意義［10］.但是，到目前為止，蟻群算法仍然存在很多不足，如易出現(xiàn)停滯現(xiàn)象、搜索時間長和解空間搜索不夠等缺點［4］.針對蟻群算法存在的上述問題，本文在文獻(xiàn)［5］的基礎(chǔ)上加以改進(jìn)，提出了一種混合改進(jìn)蟻群算法，并將其應(yīng)用于函數(shù)優(yōu)化問題中.

1 基于蟻群算法的函數(shù)優(yōu)化原理

文獻(xiàn)［5］所提出的基于蟻群算法的函數(shù)優(yōu)化原理如下.

不失一般性，在函數(shù)的優(yōu)化問題中，所有的優(yōu)化問題都可以表示為一個函數(shù)的最小化問題，即:

式中:c為常數(shù).如果在函數(shù)優(yōu)化中存在端點值，那么可以先將端點值剔除，最后計算比較.在下面的算法中將不再考慮端點值.

在多元函數(shù)優(yōu)化問題中，設(shè)決策變量由n個分量組成，并要求決策變量的每一個分量都精確到小數(shù)點后d位，則可構(gòu)造一副由n×d+n+1層數(shù)字組成，且第1、d+2、2d+3，…層由一個標(biāo)號為0的數(shù)字組成，其余層都由標(biāo)號為0～9的10個數(shù)字組成，第(b－1)×(d+1)+2到 b×(d+1)層(b=1，2，…，n)表示決策變量的第b個分量，其余層都是輔助層.解碼時，對各分量對應(yīng)的層分別解碼.采用這種方法，每個決策變量分量的最后一位與下一個分量的第一位之間都有輔助層隔開，因此前一個分量的末位不會影響后面一個分量的首位.

將待優(yōu)化函數(shù)的決策變量表示為一串十進(jìn)制的數(shù)字串{d(0)，d(1)，…，d(l－1)}，而決策變量可以通過解碼公式(2)解碼得到［6］:

式中:l為決策變量字符串的長度，n為決策變量的維數(shù).式(2)所代表的解碼過程可以用圖1來描述.

圖1 螞蟻路徑選擇Fig.1 Chosen path of ants

假設(shè)l=8，n=2，那么圖1所示的路徑由式(2)解碼后得到的決策變量為X=(X1，X2)=(0.206 4，0.971 3).

在圖1所示的螞蟻路徑選擇中，可知在螞蟻路徑的終點和起點之間有很多層數(shù)字.螞蟻要想從起點走到終點就必須經(jīng)過每層數(shù)字，這樣螞蟻在每經(jīng)過一層數(shù)字時，將會從10個數(shù)字中做出選擇，螞蟻在經(jīng)過下層數(shù)字時從哪個節(jié)點經(jīng)過根據(jù)式(3)選擇:

式中:Si為螞蟻在第i層數(shù)字會選擇的節(jié)點號碼;argmax為第i數(shù)字層上使得τi(j)最大的節(jié)點j的值;τi(j)是第i層數(shù)字上第j個節(jié)點上的信息素殘留量，q是一個隨機數(shù)，且 q∈［0，1］，q0是信息素閾值，q0∈［0，1］，根據(jù)經(jīng)驗一般設(shè)為0.8;Si(rand)為第 i層數(shù)字中j號節(jié)點被螞蟻選中的概率，由式(4)計算得出:

式中:pi(j)為第i層數(shù)字中節(jié)點j被螞蟻選擇的概率.

螞蟻每經(jīng)過一層數(shù)字中的某個節(jié)點時，都會根據(jù)局部信息素殘留更新式(5)，修改該節(jié)點上的信息素殘留量.

式中:τ0是常數(shù)，表示初始時刻信息素的含量;ρ是數(shù)字節(jié)點上的信息素?fù)]發(fā)速度，ρ∈［0，1］.

當(dāng)螞蟻如圖1所示在每層數(shù)字中選擇好一個節(jié)點后，這時螞蟻就找到了一條路徑.將這條路徑按式(2)解碼可以獲得決策變量的值，這樣就可以求得函數(shù)值.當(dāng)蟻群中每只螞蟻都按照圖1找到一條路徑后，就可以在蟻群中找到一只螞蟻，它走過的路徑解碼后得到的決策變量使函數(shù)值最小，稱這只螞蟻為迭代最優(yōu)螞蟻.讓迭代最優(yōu)螞蟻的函數(shù)值和全局螞蟻的函數(shù)值相比較，如果迭代最優(yōu)螞蟻路徑解碼后求出的函數(shù)值要小于全局最優(yōu)螞蟻解碼后求出的函數(shù)值，那么迭代最優(yōu)螞蟻成為全局最優(yōu)螞蟻.當(dāng)蟻群中每只螞蟻都選擇好路徑后，這時全局最優(yōu)螞蟻要根據(jù)信息素殘留量的全局更新式(6)對所經(jīng)過的第i層數(shù)字的第j個節(jié)點上的信息素殘留量τi(j)進(jìn)行更新:

式中:τi(j)為最優(yōu)螞蟻在第i層數(shù)字中所選擇的節(jié)點j上的信息素殘留量;μ是一個常數(shù)，且μ∈［0，1］;fbest表示全局最優(yōu)螞蟻解碼后求出的函數(shù)值.

該蟻群算法就是一直重復(fù)進(jìn)行上述螞蟻選擇的路徑和信息素更新的過程，至滿足結(jié)束條件.

文獻(xiàn)［5］所提到的蟻群優(yōu)化算法采用十進(jìn)制編碼，縮短了螞蟻需要搜索的路徑長度;信息素直接存儲在數(shù)字層的數(shù)字上面，減少了信息素的存儲量;采用了信息素局部更新和全局更新相結(jié)合的信息素更新規(guī)則.但上文所提到的蟻群優(yōu)化算法仍然有不足:1)容易陷入局部最優(yōu)，算法的全局搜索能力有待提高;2)在處理維數(shù)較多的函數(shù)問題時，搜索速度有待提高.

2 混合改進(jìn)蟻群算法的原理

本文在文獻(xiàn)［5］的基礎(chǔ)上研究了一種基于自適應(yīng)信息素?fù)]發(fā)因子、決策變量高斯變異和決策變量邊界自調(diào)整3種改進(jìn)策略的混合改進(jìn)蟻群算法，提高基本蟻群算法的收斂速度和全局搜索能力.

2.1 基于自適應(yīng)信息素?fù)]發(fā)因子的蟻群算法改進(jìn)

研究發(fā)現(xiàn)，蟻群算法是啟發(fā)式算法和信息素正反饋機制相結(jié)合產(chǎn)生的算法.在蟻群算法搜索最優(yōu)解過程中，應(yīng)用的是隨機選擇策略，而隨機策略會使蟻群算法的進(jìn)化速度較慢;蟻群算法中的信息素正反饋機制的目的在于強化螞蟻搜索到的較優(yōu)的解，但很容易出現(xiàn)停滯現(xiàn)象［7］.這正是蟻群算法的不足之處.

為了克服上述不足，在蟻群算法的尋優(yōu)過程中，當(dāng)?shù)欢ù螖?shù)、進(jìn)化方向基本確定時，利用自適應(yīng)改變信息素?fù)]發(fā)因子大小的方法，對尋優(yōu)路徑上的信息素作動態(tài)調(diào)節(jié)，逐漸縮小最優(yōu)路徑和最差路徑上的信息量，以實現(xiàn)對決策變量空間的充分尋優(yōu).

本文引入一種自適應(yīng)信息素?fù)]發(fā)因子，探討了一種基于自適應(yīng)信息素?fù)]發(fā)因子的蟻群算法的改進(jìn).該方法旨在使產(chǎn)生的新的蟻群算法通過信息素?fù)]發(fā)因子μ的自適應(yīng)來提高算法的全局性.即將式(6)中的全局信息素?fù)]發(fā)因子μ用隨迭代自適應(yīng)的μ(t)代替，此時式(6)變?yōu)?/p>

式中:μ(t)是隨迭代變化的信息素?fù)]發(fā)因子，μ(t)按式(8)進(jìn)行自適應(yīng)變化:

式中:μmin表示 μ的最小值，其目的是可以防止由于μ過小使算法的收斂速度變慢.為了提高算法的全局搜索能力，提高算法的搜索速度，在每次循環(huán)搜索結(jié)束時，都求出最優(yōu)解，并將最優(yōu)解保留，作為判斷μ自適應(yīng)的條件.

2.2 基于決策變量高斯變異的蟻群算法改進(jìn)

在蟻群算法的搜索尋優(yōu)過程中，當(dāng)優(yōu)化函數(shù)的非全局極值點比較集中時，會影響算法的收斂速度，并可能陷入局部最優(yōu)，得不到高精度的解.為了使搜索到的解有更好的遍歷性，收斂速度更快，擺脫局部最優(yōu)，本文加入決策變量高斯變異策略，將待優(yōu)化函數(shù)的決策變量進(jìn)行高斯變異，提出了一種基于決策變量高斯變異的蟻群改進(jìn)算法.以加強解的多樣性，擴大搜索范圍，使算法在搜索過程中加快搜索速度，擺脫局部最優(yōu).

基于決策變量高斯變異的蟻群算法改進(jìn)原理如下［8］.

高斯分布式概率論是數(shù)理統(tǒng)計中一類重要的分布.將高斯變異應(yīng)用到蟻群算法，其思想主要來自于遺傳算法中的變異因子.在蟻群算法中應(yīng)用高斯變異來改善蟻群算法的全局搜索能力，避免早熟，并加快收斂速度.式(9)是以原點為中心的高斯函數(shù)(Gaussian)，其概率分布如圖2所示.

圖2 高斯分布概率分布Fig.2 Gaussian distribution

在式(1)所示的函數(shù)優(yōu)化問題中，函數(shù)的決策變量用X表示，決策變量的維數(shù)為n;lb表示決策變量的下界，每一維決策變量的下界用lb(i)表示;ub表示決策變量的上界，每一維決策變量的上界用ub(i)表示;設(shè)MX表示經(jīng)高斯變異后的決策變量，MX(i)表示變換后的第i維決策變量;為了使高斯分布覆蓋整個決策變量空間，設(shè)Gaussian分布函數(shù)中的參數(shù)σ =0.16.

決策變量高斯變異基本步驟如下:

1)給經(jīng)高斯變異后的決策變量賦初值;

2)求出決策變量上下界的均值和均方差;

3)根據(jù)Gaussian分布函數(shù)產(chǎn)生一個均值為2)求出的決策變量上下界的均值，均方差為2)求出的決策變量上下界的均方差的隨機數(shù);

4)將3)產(chǎn)生的隨機數(shù)限定在決策變量的上下界之間;

5)將4)產(chǎn)生的隨機數(shù)作為高斯變異后的決策變量.

2.3 基于決策變量邊界自調(diào)整的蟻群算法改進(jìn)

在蟻群算法的尋優(yōu)過程中，特別是在高維的函數(shù)尋優(yōu)中，由于蟻群的尋優(yōu)范圍較大，搜索的隨機性也很大，為了加快蟻群的搜索速度，克服算法陷入局部最優(yōu)，本文引入決策變量的邊界自調(diào)整策略，研究了一種基于決策變量邊界自調(diào)整的蟻群算法改進(jìn)方法.

決策變量的邊界自調(diào)整策略的原理主要是在算法的迭代尋優(yōu)過程中，通過對決策變量邊界進(jìn)行自調(diào)整，使算法的尋優(yōu)范圍不斷向最小適應(yīng)值附近收斂，以加快收斂速度，克服局部最優(yōu).

加入決策變量邊界自調(diào)整的改進(jìn)蟻群算法步驟如下:

1)設(shè)定決策變量的上下界、決策變量維數(shù)、螞蟻個數(shù).

2)初始化決策變量矩陣，即在決策變量的上下界之間隨機產(chǎn)生一個初始化矩陣.

3)開始進(jìn)行循環(huán)，當(dāng)未達(dá)到要求的迭代步數(shù)時，決策變量的邊界按式(10)、(11)進(jìn)行自調(diào)整:

式中:R為一個在(0，1)上隨迭代變化的常數(shù)，用來控制決策變量的邊界.

在迭代尋優(yōu)過程中，決策變量的邊界不斷按上述原理進(jìn)行自調(diào)整，這樣在尋優(yōu)的初期，蟻群會在整個決策變量定義域內(nèi)尋優(yōu)，搜索范圍較大，全局性較好;隨著尋優(yōu)的進(jìn)行，決策變量的范圍逐漸變小，向最優(yōu)解附近收縮，這樣有助于提高算法的尋優(yōu)速度.

2.4 混合改進(jìn)蟻群算法

融合上述基于自適應(yīng)信息素?fù)]發(fā)因子、決策變量高斯變異以及決策變量邊界自調(diào)整3種策略，本文提出了一種混合改進(jìn)蟻群算法.其程序流程圖如圖3所示.

混合改進(jìn)蟻群算法的具體實現(xiàn)步驟如下:

1)初始化.設(shè)置螞蟻個數(shù) m，最大循環(huán)次數(shù)Ncmax，初始化循環(huán)次數(shù)Nc和信息素含量.

2)將初始化蟻群放置在路徑選擇圖的初始點.

3)設(shè)置循環(huán)次數(shù)Nc=Nc+1.

4)對所有螞蟻進(jìn)行4)～5).

5)選擇螞蟻在下一層到達(dá)的節(jié)點.此選擇按照式(3)、(4)進(jìn)行.

6)在每只螞蟻選擇好下一層到達(dá)的節(jié)點后，按照式(5)進(jìn)行局部信息素的更新.

7)當(dāng)所有的螞蟻完成一次循環(huán)后，按式(8)更新μ，然后按照式(7)進(jìn)行全局信息素更新.

8)根據(jù)式(10)和(11)進(jìn)行決策變量邊界自調(diào)整，調(diào)整蟻群搜索范圍.

9)根據(jù)式(9)對決策變量進(jìn)行高斯變異.

10)如果循環(huán)次數(shù)Nc≥Ncmax，即滿足結(jié)束條件，則循環(huán)結(jié)束并輸出程序計算結(jié)果;否則繼續(xù).

圖3 混合改進(jìn)蟻群算法程序流程Fig.3 Flow chart of hybrid improved ACO

3 混合改進(jìn)蟻群算法的仿真與分析

本文分別采用 Sphere、DeJongF4、Rosenbrock、Griewank和Rastrigin 5個基準(zhǔn)測試函數(shù)作為適應(yīng)度函數(shù)，分別應(yīng)用文獻(xiàn)［5］中的基本蟻群算法以及基于信息素?fù)]發(fā)因子自適應(yīng)的蟻群算法、基于決策變量高斯變異和信息素?fù)]發(fā)因子自適應(yīng)的蟻群算法，和基于信息素?fù)]發(fā)因子自適應(yīng)、決策變量高斯變異、決策變量邊界自調(diào)整三者相融合的混合改進(jìn)蟻群算法進(jìn)行仿真實驗.其中，參數(shù)設(shè)置為:螞蟻個數(shù)為30，迭代次數(shù)為30，基準(zhǔn)函數(shù)決策變量為五維，以最大迭代次數(shù)作為算法的終止條件，對5個基準(zhǔn)函數(shù)各進(jìn)行50次試驗.選取字節(jié)點上的信息素?fù)]發(fā)速度ρ=0.3，Gaussian 分布函數(shù)中的參數(shù) σ =0.16.則其仿真結(jié)果具體數(shù)據(jù)見表1和圖4～8所示.

表 1中，f1～f5分別代表 Sphere、DeJongF4、Rosenbrock、Griewank和Rastrigin 5個基準(zhǔn)測試函數(shù);基本蟻群是指文獻(xiàn)［5］的蟻群算法;改進(jìn)蟻群算法1指基于自適應(yīng)信息素?fù)]發(fā)因子的改進(jìn)蟻群算法;改進(jìn)蟻群算法2指基于自適應(yīng)信息素?fù)]發(fā)因子和決策變量高斯變異策略的改進(jìn)蟻群算法;改進(jìn)蟻群算法3指基于自適應(yīng)信息素?fù)]發(fā)因子、決策變量高斯變異策略和決策變量邊界自調(diào)整策略的混合改進(jìn)蟻群算法.

表1 基于5種基準(zhǔn)測試函數(shù)的蟻群優(yōu)化仿真結(jié)果對比Table 1 Comparison of simulation results using different ACOs based on 5 basic test functions

圖4 基于Sphere函數(shù)的蟻群優(yōu)化仿真結(jié)果Fig.4 Simulation results of ACO based on Sphere function

圖5 基于DeJongF4函數(shù)的蟻群優(yōu)化仿真結(jié)果Fig.5 Simulation results of ACO based on DeJongF4 function

圖6 基于Rosenbrock函數(shù)的蟻群優(yōu)化仿真結(jié)果Fig.6 Simulation results of ACO based on Rosenbrock function

圖7 基于Griewank函數(shù)的蟻群優(yōu)化仿真結(jié)果Fig.7 Simulation results of ACO based on Griewank function

圖8 基于Rastrigin函數(shù)的蟻群優(yōu)化仿真結(jié)果Fig.8 Simulation results of ACO based on Rastrigin function

根據(jù)表1及圖4～8的仿真結(jié)果可以看出，對比于文獻(xiàn)［5］的基本蟻群算法以及本文涉及的單個改進(jìn)算法，可以得出如下結(jié)論:

1)在最優(yōu)適應(yīng)值和收斂時間方面，混合改進(jìn)蟻群算法尋優(yōu)的精度最高，并且能在最短的運行時間和最少的迭代次數(shù)內(nèi)達(dá)到收斂，這是因為加入信息素?fù)]發(fā)因子自適應(yīng)策略和決策變量邊界自調(diào)整策略，逐漸縮小最優(yōu)路徑和最差路徑上的信息量，實現(xiàn)了對決策變量空間的充分尋優(yōu).

2)在收斂率方面，在對比較難尋優(yōu)的DeJongF4函數(shù)進(jìn)行尋優(yōu)時，混合改進(jìn)蟻群算法仍然能達(dá)到100%的收斂率，對于Griewank和 Rastrigin 2個多峰函數(shù)，以及比較難尋優(yōu)的Rastrigin函數(shù)進(jìn)行尋優(yōu)時，考慮到函數(shù)本身性能的影響，混合改進(jìn)蟻群算法沒有達(dá)到100%的收斂率，但是在3種改進(jìn)蟻群算法中，收斂率也是最高的，這是因為加入決策變量高斯變異策略，改善了蟻群算法的全局搜索能力，避免了局部的早熟現(xiàn)象.

綜上所述，本文提出的基于信息素?fù)]發(fā)因子自適應(yīng)、決策變量高斯變異和自變量邊界自調(diào)整的混合改進(jìn)蟻群算法在收斂速度和收斂率方面都有很大改進(jìn)，具有更好的尋優(yōu)性能.

4 結(jié)束語

本文在文獻(xiàn)［5］蟻群算法理論的基礎(chǔ)上，針對蟻群算法易出現(xiàn)停滯現(xiàn)象、搜索時間長、對尋優(yōu)解空間搜索不夠等不足，提出了一種基于自適應(yīng)信息素?fù)]發(fā)因子、決策變量高斯變異和決策變量邊界自調(diào)整3種改進(jìn)策略的混合改進(jìn)蟻群算法.將該算法應(yīng)用于函數(shù)優(yōu)化中，通過5個基準(zhǔn)測試函數(shù)的仿真結(jié)果表明，本文提出的混合改進(jìn)蟻群算法提高了尋優(yōu)精度，加快了尋優(yōu)速度，提高了收斂率，具有更好的尋優(yōu)性能.

［1］DERIGO M，CARO G D.Ant algorithms for discrete optimization［J］.Artificial Life，1999，5(3):137-172.

［2］張紀(jì)會，高齊圣，徐心和.自適應(yīng)蟻群算法［J］.控制理論與應(yīng)用，2000，17(1):1-8.

ZHANG Jihui，GAO Qisheng，XU Xinhe.Adaptive ant colony optimization［J］.Control Theory and Applications，2000，17(1):1-8.

［3］詹士昌，吳俊.基于蟻群算法的PID參數(shù)優(yōu)化設(shè)計［J］.測控技術(shù)，2004，23(2):69-71.

ZHAN Shichang，WU Jun.Design of PID optimization based on ACO［J］.Measurement＆ Control Technology，2004，23(2):69-71.

［4］李玉英.混沌螞蟻群優(yōu)化算法及其應(yīng)用研究［D］.北京:北京郵電大學(xué)，2009:15-21.

LI Yuying.On chaos ant colony optimization and its application［D］.Beijing:Beijing University of Posts and Tele-communications，2009:15-21.

［5］陳燁.用于連續(xù)函數(shù)優(yōu)化的蟻群算法［J］.四川大學(xué)學(xué)報:工程科學(xué)版，2004，36(6):117-120.

CHEN Ye.Ant colony optimization for continuous functions［J］.Journal of Sichuan University:Engineering Science E-dition，2004，36(6):117-120.

［6］陳燁.變尺度混沌蟻群算法［J］.計算機工程與應(yīng)用，2007，43(3):68-70.

CHEN Ye.On mutative scaled chaos ant colony optimization［J］.Computer Engineering and Applications，2007，43(3):68-70.

［7］王穎，謝劍英.一種自適應(yīng)蟻群算法及其仿真研究［J］.系統(tǒng)仿真學(xué)報，2002，14(1):31-33.

WANG Ying，XIE Jianying.An adaptive ant colony optimization and its simulations［J］.Journal of System Simulation，2002，14(1):31-33.

［8］STUTZLE T，HOOS H H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16(8):889-914.

［9］BILCHEV G A，PARMEE I C.The ant colony metaphor for searching continuous space［J］.Lecture Notes in Computer Science，1995，993(1):25-39.

［10］GUTJAHR W J.A graph-based ant system and its convergence［J］.Future Generation Computer System，2000，16(8):873-888.

［11］DREO J，SIARRY P.Continuous interacting ant colony algorithm based on dense heterarchy［J］.Future Generation Computer Systems，2004，20(5):841-856.

［12］周爽，張鈞萍，張楓，等.基于蟻群算法的遙感圖像聚類方法［J］.哈爾濱工程大學(xué)學(xué)報，2009，30(2):210-214.

ZHOU Shuang，ZHANG Junping，ZHANG Feng，et al.Clustering method for remote sensing images based on an ant colony algorithm［J］.Journal of Harbin Engineering U-niversity，2009，30(2):210-214.

［13］趙百軼，張利軍，賈鶴鳴.基于四叉樹和改進(jìn)蟻群算法的全局路徑規(guī)劃［J］.應(yīng)用科技，2011，38(10):23-28.

ZHAO Baiyi，ZHANG Lijun，JIA Heming.Global path planning based on quadtree and improved ant colony optimization algorithm［J］.Applied Science and Technology，2011，38(10):23-28.