朱宏偉，游曉明，劉 升

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620；2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620)

蟻群算法(Ant Colony Optimization，ACO)是一種群智能優(yōu)化算法。它基于自然界蟻群集體覓食行為，模擬真實(shí)蟻群的協(xié)作過程。1991年，Dorigo提出螞蟻系統(tǒng)(Ant System，AS)［1］用于解決TSP等復(fù)雜難問題。1996年，Dorigo等人為了限制信息素的正反饋?zhàn)饔茫岢鱿伻合到y(tǒng)(Ant Colony System，ACS)［2］，通過兩種信息素更新方式，平衡每條邊之間的信息素差異，提高蟻群算法性能。同理，T.Stutzle等人提出了最大-最小螞蟻系統(tǒng)(MAX-MIN Ant System，MMAS)［3］，通過限制信息素最大值和最小值，保證算法的多樣性。后來專家學(xué)者在這兩者基礎(chǔ)不斷改進(jìn)［4-7］，使算法不斷向前方展。同時(shí)還將蟻群算法延展于機(jī)器人路徑規(guī)劃、調(diào)度等一系列優(yōu)化問題上，使算法向多方向發(fā)展［8-9］。

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)最早是由Kennedy和Eberhart提出的，最初是模擬鳥群的捕食行為，逐漸發(fā)展成為群體智能算法。在尋優(yōu)過程中，每個(gè)潛在的最優(yōu)解都與粒子運(yùn)動(dòng)速度相關(guān)，根據(jù)粒子的歷史經(jīng)驗(yàn)以及鄰居們的經(jīng)驗(yàn)來調(diào)整其速度大小和方向，朝著最優(yōu)解的方向逼近。粒子群優(yōu)化算法已經(jīng)廣泛應(yīng)用于連續(xù)優(yōu)化問題和離散優(yōu)化問題，特別是其天然的實(shí)數(shù)編碼特點(diǎn)適合于處理實(shí)優(yōu)化問題并可以有效地對(duì)系統(tǒng)參數(shù)進(jìn)行優(yōu)化。

雖然使用粒子群優(yōu)化的參數(shù)會(huì)提高解的質(zhì)量，但是找到全局最優(yōu)解還有一定的困難，故本文提出一種基于粒子群參數(shù)優(yōu)化的同構(gòu)雙種群蟻群算法(Homogeneous Dual Ant Colony Algorithm Based on Particle Swarm Optimization，HDAP)來提高找到全局最優(yōu)解的概率。以ACS作為框架基礎(chǔ)，算法開始時(shí)，將螞蟻均分為兩個(gè)子種群，分別命名Population1和Population2。Population1引入單位距離信息素路徑構(gòu)造算子，將距離因素和信息素因子相統(tǒng)一，提高算法遍歷整個(gè)地圖的能力。Population2引入粒子群優(yōu)化算法對(duì)蟻群算法中的多個(gè)參數(shù)進(jìn)行優(yōu)化，減小蟻群算法中參數(shù)的影響，實(shí)現(xiàn)對(duì)解空間高效、快速的全面尋優(yōu)。Population1中由于未使用α和β等參數(shù)，與Population2的參數(shù)優(yōu)化形成優(yōu)勢(shì)互補(bǔ)關(guān)系，兩個(gè)種群相隔一定迭代次數(shù)進(jìn)行協(xié)同交流，提高發(fā)現(xiàn)全局最優(yōu)解的概率。仿真實(shí)驗(yàn)表明，針對(duì)TSP問題，本文算法提高了解的質(zhì)量，增強(qiáng)了算法的種群多樣性。

1 相關(guān)工作

1.1 基本蟻群算法的TSP問題

以NP-難問題中最常用的TSP問題為例說明基本蟻群算法的模型。

設(shè)螞蟻的數(shù)量為m，城市的數(shù)量為n，dij(i，j=1，2，…)代表兩兩城市之間的距離，τij(t)代表t時(shí)刻i城市和j城市之間的信息素的濃度大小。在ACS算法中，每條邊上的起始濃度都是相同的，記為τ0。

1.1.1 路徑構(gòu)建

首先每個(gè)螞蟻被隨機(jī)分配到城市中，然后根據(jù)狀態(tài)轉(zhuǎn)移概率尋找下一個(gè)要到達(dá)的城市。ACS算法中，每只螞蟻從i城市到j(luò)城市的選擇方式為

式中，ηij為 i，j城市之間距離的倒數(shù)，即 1/dij；q0為一個(gè)人為設(shè)置的固定值；q為一個(gè)隨機(jī)生成的隨機(jī)數(shù)；S為將要被選擇的下一個(gè)城市；s為另一種輪盤賭的選擇方式。當(dāng)不符合上述條件，采用輪盤賭進(jìn)行路徑構(gòu)建。

式中，allowed為螞蟻當(dāng)前可行城市集。

1.1.2 信息素更新

ACS算法中分為全局信息素更新以及局部信息素更新部分。

①全局信息素更新：當(dāng)所有的螞蟻都完成一次周游以后，算法只允許每一代的最優(yōu)螞蟻釋放信息素。

式中，

其中，ρ為全局信息素?fù)]發(fā)率；Δτij為信息素增量；Lgb為當(dāng)前最優(yōu)路徑長(zhǎng)度。

②局部信息素更新：當(dāng)所有的螞蟻都完成一次周游后，算法允許每只螞蟻都對(duì)其走過的路徑進(jìn)行信息素的更新。

全局信息素和局部信息素之間相互配合是ACS算法最重要的特點(diǎn)。

1.2 粒子群算法

粒子群優(yōu)化算法的基本原理為：一個(gè)由m個(gè)粒子組成的群體在d維搜索空間中，以一定的速度飛行，每個(gè)粒子在搜索時(shí)，既考慮自己搜索到的歷史最好點(diǎn)，又考慮群體內(nèi)其他粒子的歷史最好點(diǎn)，在此基礎(chǔ)上進(jìn)行位置更新。

設(shè)第 i個(gè)粒子的位置表示為 xi=(xi1，xi2，…，xid)，其速度表示為vi=(vi1，vi2，…，vid)，其經(jīng)歷過的歷史最好點(diǎn)表示為pi=(pi1，pi2，…，pid)。群體內(nèi)所有粒子所經(jīng)歷的最好的點(diǎn)表示為Gg=(Gg1，Gg2，…，Gpd)。一般來說，粒子的位置和速度分別根據(jù)式(5)和式(6)進(jìn)行更新。

式中，w為慣性權(quán)重，其大小決定了粒子對(duì)當(dāng)前速度繼承的多少；c1和c2為學(xué)習(xí)因子，通常在0～2之間取值；rand()是在［0，1］區(qū)間內(nèi)均勻分布的偽隨機(jī)數(shù)，即rand()∈U［0，1］。

2 改進(jìn)的蟻群算法

本文提出一種基于粒子群參數(shù)優(yōu)化的雙種群蟻群算法，通過加強(qiáng)蟻群間的合作，使算法更加符合自然界中螞蟻種群間相互協(xié)同、相互競(jìng)爭(zhēng)的特點(diǎn)，進(jìn)一步減少種群陷入局部最優(yōu)的概率，增強(qiáng)解的質(zhì)量。將送螞蟻均分為兩種類型，命名為Population1和Populatin2，分別按照式(8)和使用粒子群優(yōu)化的參數(shù)ACS進(jìn)行路徑構(gòu)建，獨(dú)立地進(jìn)行最優(yōu)解的搜尋，每隔w次迭代后交流最優(yōu)解，加強(qiáng)種群之間相互學(xué)習(xí)，相互合作，從而使每個(gè)種群皆獲得更優(yōu)解。

2.1 單位距離信息素算子

本文提出一種改進(jìn)的路徑構(gòu)建策略，即單位距離路徑構(gòu)造算子(Unit Distance of Path Constructor，UD-PC)，將距離因素與信息素因子相結(jié)合，增加種群的多樣性。本文的路徑構(gòu)建公式如下：

式中，τirn為i城市到 rn城市之間的信息素；dirn為i城市到rn城市之間的距離值。

式(7)與式(1)對(duì)比可知，式(1)中由于ηij的β的次方使距離因素對(duì)路徑構(gòu)建影響較多，減少了信息素的引導(dǎo)的作用，而式(7)則很好地平衡了這兩個(gè)因素，其減少了距離因子在路徑構(gòu)建中的權(quán)重，增加其他城市被選擇的概率，跳出局部最優(yōu)。

Population1采用式(8)進(jìn)行路徑構(gòu)建，增強(qiáng)算法搜索整個(gè)地圖的能力，同時(shí)增加算法多樣性，使算法更易跳出局部最優(yōu)，找到最優(yōu)解。

式中，s為輪盤賭選擇方式；q0為一固定常數(shù)；q為一個(gè)隨機(jī)數(shù)。

2.2 粒子群對(duì)于蟻群算法參數(shù)的優(yōu)化

本文提出一種使用粒子群算法優(yōu)化蟻群算法參數(shù)的方法，將ACS中β、q0和ρ放在三維空間坐標(biāo)系中，進(jìn)一步優(yōu)化這3個(gè)參數(shù)，提升了算法的性能。

設(shè)一個(gè)三維坐標(biāo)xi=(xi0，xi1，xi2)來對(duì)應(yīng)一組β、q0和ρ參數(shù)，用于表現(xiàn)粒子的位置。同時(shí)，與位置相對(duì)應(yīng)的，每個(gè)粒子在解空間中的移動(dòng)有3個(gè)方向的速度，記為 vi=(vi0，vi1，vi2)。

算法開始，初始化粒子P0，P1，…，PN的位置參數(shù)xi=(xi0，xi1，xi2) ，一個(gè)粒子對(duì)應(yīng)一組三維坐標(biāo)，即參數(shù)β、q0和ρ，并將每個(gè)粒子所對(duì)應(yīng)的參數(shù)值反饋回蟻群算法。蟻群根據(jù)不同的參數(shù)的值，進(jìn)行TSP最優(yōu)解的尋找。每個(gè)粒子當(dāng)前找到的最優(yōu)粒子位置為Pi，整個(gè)種群當(dāng)前所找到的最優(yōu)粒子位置為Gg，按照式(5)和式(6)更新粒子的速度和位置。

Population2克服了蟻群算法參數(shù)的影響，減少了大量盲目的實(shí)驗(yàn)，實(shí)現(xiàn)了對(duì)搜索空間高效、快速的全面尋優(yōu)。

2.3 交流策略

根據(jù)文獻(xiàn)［10］和文獻(xiàn)［11］，使用粒子群優(yōu)化的參數(shù)雖然可以找出全局最優(yōu)解，但是概率偏低，故本文采用兩個(gè)種群協(xié)同交流的策略，提高了算法多樣性，同時(shí)提高了獲得全局最優(yōu)解的概率。在本算法中，Population1未使用α和β等參數(shù)和Population2的參數(shù)優(yōu)化形成路徑構(gòu)造算子之間的互補(bǔ)關(guān)系，每隔w次迭代后，兩個(gè)種群進(jìn)行交互學(xué)習(xí)，即比較每個(gè)種群中的當(dāng)前最優(yōu)解，將其中最好的解保存下來，同時(shí)替換掉另一個(gè)種群中相對(duì)較差的最優(yōu)解，從而促使兩個(gè)種群向更好的解的方向發(fā)展。式(9)描述了兩個(gè)種群的學(xué)習(xí)機(jī)制。

2.4 改進(jìn)算法(HDAP)偽代碼

用HDAP算法解決TSP問題的代碼如下。

1.Procedure HDAP()

2.Begin：

3.Initialize the parameters and the pheromone

4.Divide m into part #m as ants’number

5. for iter1←1 to T do

6. #Algorithm：Population1

6. for i←1 to m1 do#m as ants’number

7. for j←2 to n do#n as cities’number

8. Unit Distance of Path Constructor

9. end-for

10. end-for

11. Update pheromones

12. #Algorithm：Population2

13. Initialize parameters of P0，P1…PN

14. for i←1 to m2 do#m as ants’number

15. Transfer parameters of PSO to ACO

16. for j←2 to n do#n as cities’number

17. Construct ant solutions

18. Calulation GgandPi

19. Update viand xi

20. end-for

21. Update pheromones

22. end-for

23. if(mod(T，w)= =0) #T is the current iter

24. Collaborative communication

25. end-if

26. end-for

2.5 時(shí)間復(fù)雜度

通過分析上述算法流程，HDAP時(shí)間復(fù)雜度為 O((m1×(n-1)+m2×(n-1))×T)，由于 m1+m2=m，故HDAP算法最大時(shí)間復(fù)雜度為O(m×n×T)，ACS最 大 時(shí) 間 復(fù) 雜 度O(m×n×T)。由此可以看出，所提出的HDAP蟻群算法雖然產(chǎn)生了部分計(jì)算負(fù)擔(dān)，但是沒有改變算法的最大時(shí)間復(fù)雜度。

3 實(shí)驗(yàn)分析

本實(shí)驗(yàn)在Matlab R2014a的環(huán)境下仿真運(yùn)行。為了檢測(cè)改進(jìn)算法的有效性，選取eil51、eil76、KroA100、KroA150、KroB150等TSP算例來進(jìn)行算法驗(yàn)證，并與ACS、MMAS等經(jīng)典ACO算法以及多個(gè)多種群算法相對(duì)比，結(jié)果顯示所提出的HDAP有著更好的實(shí)驗(yàn)結(jié)果。同時(shí)eil51、eil76、KroA100都比較容易找到最優(yōu)解，從熵值看出改進(jìn)的HDAP算法的多樣性有著明顯的提升。

3.1 eil51問題的實(shí)驗(yàn)分析

在eil51問題上，Population1和Population2的公共參數(shù)為：螞蟻數(shù)量m=50，信息素作用度α=1，最大迭代次數(shù)iter=2000。非公共參數(shù)為：Population1的實(shí)驗(yàn)參數(shù)，包括局部揮發(fā)率ζ=0.1，全局揮發(fā)率ρ=0.4，參數(shù)q0=0.8；Population2實(shí)驗(yàn)參數(shù)取值范圍，包括β=［2，10］，q0=［0.5，0.9］，ρ=［0.2，0.7］。

每組參數(shù)不同，ACO算法都進(jìn)行了連續(xù)20次測(cè)試，采用控制變量的方法，逐漸改變?chǔ)碌闹担瑏碛^察其對(duì)實(shí)驗(yàn)的影響。設(shè)到算法所找到的最優(yōu)長(zhǎng)度為L(zhǎng)best，算法20次實(shí)驗(yàn)的平均路徑長(zhǎng)度為L(zhǎng)ave。

式中，n為實(shí)驗(yàn)次數(shù)；V為與平均解的誤差；J為誤差率。

式(10)與式(11)可以共同反映每個(gè)ACO算法的穩(wěn)定性，波動(dòng)情況以及找到最優(yōu)解的概率。標(biāo)準(zhǔn)差可以反映20次試驗(yàn)每一次找出的解與平均值的線性程度，標(biāo)準(zhǔn)差越大，這個(gè)算法的波動(dòng)程度就越大。而J可以反映出最優(yōu)值和平均值的離散的關(guān)系，用于判斷每個(gè)ACO算法找出最優(yōu)值的概率，概率與數(shù)值J大小成反比，即J的值越大，算法找到最優(yōu)解的概率就相對(duì)越小。

eil51實(shí)例的實(shí)驗(yàn)結(jié)果如表1。表1顯示了不同的β取值對(duì)最優(yōu)解、標(biāo)準(zhǔn)差V、誤差率J等實(shí)驗(yàn)結(jié)果的影響。從表1可以看出，β從2開始依次變化到5，ACS算法平均長(zhǎng)度的結(jié)果變化類似于一個(gè)二次函數(shù)。而粒子群優(yōu)化得到的參數(shù)β為4.2311，證明了粒子群優(yōu)化算法的有效性。同時(shí)由于Population1增加了螞蟻探索整個(gè)TSP測(cè)試集的能力，提高了解的質(zhì)量，從算法開始到結(jié)束，熵值都一直處于略微上升的狀態(tài)，表明算法的多樣性提升明顯，使算法容易跳出局部最優(yōu)。圖1為某次路徑長(zhǎng)度為426(最優(yōu)解)時(shí)的熵值。

表1 不同β對(duì)ACO路徑長(zhǎng)度的影響

圖1 HDAP多樣性分析

3.2 中大規(guī)模TSP問題分析

下面針對(duì) ch130、KroB150、KroA150等中大規(guī)模TSP問題進(jìn)行實(shí)驗(yàn)仿真。每種算法都進(jìn)行了20次的仿真實(shí)驗(yàn)，平均長(zhǎng)度四舍五入，具體比較結(jié)果如表2所示。

下面舉例說明3種ACO算法的收斂情況。圖3為KroB150測(cè)試集的3種算法的最優(yōu)解迭代變化。由圖可看出，ACS算法收斂的速度最快，在第216代時(shí)，相比較其他兩種算法，其結(jié)果最優(yōu)，但同時(shí)陷入局部最優(yōu)，而無法跳出；MMAS和HDAP收斂速度相對(duì)較慢，MMAS算法在1737和2000次迭代陷入局部最優(yōu)后，通過信息素的重新初始化，跳出局部最優(yōu)，但依然沒有找到全局最優(yōu)解。由于HDAP的兩個(gè)種群之間的學(xué)習(xí)交流策略，共同處理最優(yōu)解的尋找，其收斂的速度要更優(yōu)于MMAS，在1737次迭代中跳出局部最優(yōu)，同時(shí)找到全局最優(yōu)解。

表 2 反映了在 eil76、KroA100、ch130、KroB150、KroA150等大規(guī)模測(cè)試集上，3種ACO算法的最優(yōu)長(zhǎng)度、最差長(zhǎng)度、平均長(zhǎng)度、標(biāo)準(zhǔn)差V等一系列數(shù)據(jù)比較分析。從仿真實(shí)驗(yàn)結(jié)果可以看出，HDAP各方面的實(shí)驗(yàn)結(jié)果都是優(yōu)于其他兩種ACO算法的，尤其是最優(yōu)解、平均解、平均熵值等方面提升更加明顯。結(jié)合3.1節(jié)中的實(shí)驗(yàn)分析，表明HDAP無論在小規(guī)模和大規(guī)模TSP問題上，都有著比較優(yōu)的實(shí)驗(yàn)結(jié)果。

同時(shí)，比較了3種算法的J(式(11))的值，3種蟻群算法在不同的測(cè)試集中誤差率的變化曲線如圖3所示。J值越小，說明算法的穩(wěn)定性越高，其解的質(zhì)量也相對(duì)較高。由圖3的實(shí)驗(yàn)結(jié)果可以看出HDAP在多個(gè)測(cè)試集中的誤差率J都要小于ACS和MMAS算法，說明HDAP在3種算法中有著最高的穩(wěn)定性。

表2 不同算法性能對(duì)比

圖3 不同TSP測(cè)試集誤差率分析

由表2和圖3可知，改進(jìn)的HDAP算法提升是比較明顯的。為了證明本文算法的優(yōu)越性，與一些其他多種群蟻群算法也進(jìn)行了比較分析，如表3所示。其中HHACO算法的數(shù)據(jù)都來自于文獻(xiàn)［12］(SCI)，AHMACAS算法中數(shù)據(jù)來自于文獻(xiàn)［13］(CSCD)，HMACSF算法中數(shù)據(jù)來自于文獻(xiàn)［14］(CSCD)。從表3可以看出，在與其他多種群蟻群算法對(duì)比中，本文算法有著一定的優(yōu)勢(shì)，特別是在eil51和eil76測(cè)試集上，HDAP找到的最優(yōu)解要好于其他3種多種群算法。

表3 多種群之間的對(duì)比

3.3 HDAP的最優(yōu)解仿真圖

圖4給出了HDAP的最優(yōu)解仿真圖。

3.4 收斂速度對(duì)比

為了更加直觀地對(duì)比各個(gè)算法的性能，在幾個(gè)TSP實(shí)例中選取不同規(guī)模的城市，如 eil51、eil76、ch130、KroA150，用于比較算法的收斂速度，如圖5所示。從圖中可以看出，HDAP無論在小規(guī)模還是在中大規(guī)模的問題上，最優(yōu)解都要好于其他兩種算法，且收斂速度要優(yōu)于MMAS。

圖4 HDAP的最優(yōu)解仿真圖

圖5 不同測(cè)試集的收斂速度

4 結(jié)束語

提出一種基于粒子群參數(shù)優(yōu)化的同構(gòu)雙種群蟻群算法，將螞蟻均分為兩個(gè)子種群，即 Population1和Population2。Population1引入單位距離信息素路徑構(gòu)造算子，將距離因素和信息素因相統(tǒng)一，增加算法遍歷整個(gè)地圖的能力，增加算法多樣性。Population2引入粒子群優(yōu)化算法對(duì)蟻群算法中的多個(gè)參數(shù)進(jìn)行優(yōu)化，克服了蟻群算法參數(shù)的影響，實(shí)現(xiàn)了對(duì)搜索空間高效、快速的全面尋優(yōu)。Population1中由于未使用α和β等參數(shù)，與Population2的參數(shù)優(yōu)化形成優(yōu)勢(shì)互補(bǔ)關(guān)系，兩個(gè)種群相隔w次迭代進(jìn)行協(xié)同交流，提高發(fā)現(xiàn)全局最優(yōu)解的概率。接下來，將繼續(xù)研究如何在更大的測(cè)試集中找出最優(yōu)解和使算法更快的收斂。