求解TSP 的蟻群與模糊自適應(yīng)粒子群算法

張海俊，王 波

ZHANG Haijun,WANG Bo

上海理工大學(xué) 管理學(xué)院，上海200093

School of Manage,University of Shanghai for Science and Technology,Shanghai 200093,China

1 引言

粒子群算法[1]是由Kennedy 博士與Eberhart 博士共同提出一種新興的基于群體智能[2-3]的搜索算法。它起源于對(duì)鳥群覓食行為的模擬，主要是仿照種群行為來模擬粒子們的運(yùn)動(dòng)。這種算法簡(jiǎn)單且參數(shù)易于調(diào)整，現(xiàn)在已經(jīng)廣泛應(yīng)用于重要領(lǐng)域。在處理問題時(shí)，一般采用定值慣性權(quán)重的PSO 算法，但在實(shí)際搜索過程中，容易早熟且易于陷入局部最優(yōu)。

蟻群算法[4]是Dorigo 等提出的一種仿生群體智能搜索算法，它來源于自然界中螞蟻集體覓食行為與協(xié)作過程的啟發(fā)，通過模擬螞蟻在蟻巢和食物源之間尋找最短路徑，以信息素作為媒介，最終達(dá)到尋優(yōu)的目的。目前，蟻群算法應(yīng)用已在大量領(lǐng)域中取得了多項(xiàng)突破，并產(chǎn)生不錯(cuò)的效果。盡管蟻群算法具有較強(qiáng)的尋優(yōu)能力，但在處理大規(guī)模優(yōu)化問題時(shí)，其開始搜索時(shí)信息素量比較缺乏，且搜索速度緩慢，易于陷入局部最優(yōu)。

在融合ACO 與PSO 算法中文獻(xiàn)[5]應(yīng)用粒子群算法對(duì)蟻群算法的參數(shù)進(jìn)行優(yōu)化，并運(yùn)用蟻群系統(tǒng)算法尋找最優(yōu)路徑；文獻(xiàn)[6]中為了提高收斂速度，將每隔一定代數(shù)的數(shù)據(jù)引入粒子群運(yùn)算，最終在局部與全局最優(yōu)之間取得平衡；文獻(xiàn)[7]中引入重力搜索算法來優(yōu)化蟻群算法參數(shù)和粒子群算法，并且提高了蟻群算法的優(yōu)化性能；文獻(xiàn)[8]中將蟻群分成多個(gè)螞蟻?zhàn)尤海ㄟ^粒子群算法優(yōu)化螞蟻?zhàn)尤簠?shù)，并在螞蟻?zhàn)尤褐幸虢粨Q操作對(duì)TSP 問題進(jìn)行優(yōu)化；文獻(xiàn)[9]中給出一種全局異步與精英策略相結(jié)合的信息素更新方法，從而提高算法的運(yùn)行迭代速度。

雖然上述方法對(duì)ACO-PSO 算法[10]做了一些的改進(jìn)，但隨著TSP 優(yōu)化問題不斷規(guī)模化、復(fù)雜化，預(yù)先設(shè)定的慣性權(quán)重值難以滿足復(fù)雜問題的解決。所以，本文主要對(duì)粒子群算法與蟻群算法的特點(diǎn)和性質(zhì)進(jìn)行詳細(xì)的探究，融合兩種算法的優(yōu)點(diǎn)，并且通過引入模糊技術(shù)，對(duì)PSO 中慣性權(quán)重ω[11-12]參數(shù)進(jìn)行模糊化。在ACO-PSO算法運(yùn)行初期時(shí)，需要較強(qiáng)的全局搜索能力，則采用較大的ω值；在搜索中后期，需要有很強(qiáng)的局部搜索能力，則調(diào)整為較小的ω值。

2 基本蟻群算法

首先設(shè)TSP 的城市個(gè)數(shù)為N，螞蟻總數(shù)也為N，城市i與城市j之間的路徑為dij(i≠j)。先建立TSP 問題的目標(biāo)函數(shù)式（1），其中城市序列表示為{cπ(1)，cπ(2)，…，cπ(N)}，且cπ(1)，cπ(2)，…，cπ(N)是c1，c2，…，cN的全排列。

蟻群算法[13-14]的基本思想：螞蟻在初次尋找路徑是隨機(jī)的，且在路徑上釋放等量信息素。設(shè)τij(t)表示t時(shí)刻在城市i，j連線上殘留信息素含量，初始時(shí)刻每條路徑的信息素含量都為τij(0)=τ0。螞蟻antk(k=1，2，…，N)在爬行過程中，使用禁忌表tabuk記錄當(dāng)前已遍歷的城市，用集合allowedk來記錄下一步可選擇城市，即allowedk={C-tabuk}。表示在t時(shí)刻螞蟻antk由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率，其中ηij表示從城市i轉(zhuǎn)移到城市j的啟發(fā)信息，一般取值ηij=1/dij，參數(shù)α表示在路徑i，j上殘留信息量的相對(duì)重要程度，參數(shù)β為啟發(fā)信息的相對(duì)重要程度，如式（2）。

在所有螞蟻都完成一次周游時(shí)，各路徑上的信息素量需根據(jù)式（3）進(jìn)行更新。其中，ρ(0 ＜ρ＜1)是一個(gè)系數(shù)，且(1-ρ)表示t到t+N時(shí)刻內(nèi)的信息素?fù)]發(fā)率；Δτij表示本次迭代中路徑i，j上的信息素增量之和；Q表示螞蟻循環(huán)一周所釋放的總信息素含量，Lk表示antk螞蟻在本次周游中所走路徑的長(zhǎng)度，表示antk螞蟻在本次迭代中在路徑i，j上留下的信息素含量，如式（5）。

3 模糊自適應(yīng)粒子群算法

3.1 粒子群算法基本思想

粒子群算法是一種模擬鳥群的捕食行為群體智能算法[2-3]。在尋優(yōu)過程中，每個(gè)潛在的最好解都與粒子運(yùn)動(dòng)速度相關(guān)聯(lián)，根據(jù)粒子的歷史經(jīng)驗(yàn)以及鄰居們的經(jīng)驗(yàn)來調(diào)整其速度大小和方向，朝著最好解的方向逼近。

本文搜索空間是在平面中，設(shè)粒子群中第i個(gè)粒子位置、速度分別為xi(xi1，xi2)和vi(vi1，vi2)，以及pbesti(pi1，pi2)表示第i個(gè)粒子搜索到的最佳位置，gbest(g1，g2)表示所有粒子搜索到的最好位置，根據(jù)式（6）和（7）來更新粒子的速度和位置。

其中，學(xué)習(xí)因子c1和c2，分別表示為粒子具有自我尋優(yōu)能力和集體尋優(yōu)能力，來逼近個(gè)體和群體最優(yōu)解。R1，R2為[0，1]之間的隨機(jī)數(shù)。限制粒子速度，即|vi|＞vmax時(shí)，則|vi|=vmax。慣性權(quán)重ω表示為粒子延續(xù)當(dāng)前速度多少，其值合理地被選取使得粒子具有均衡的局部與全局搜索能力。然而如何權(quán)衡慣性權(quán)值，使其達(dá)到搜索平衡的效果，從而逼近最好解。本文主要從慣性權(quán)值的變化來提高ACO-PSO 的搜索性能。

3.2 慣性權(quán)重的自適應(yīng)調(diào)整模型

為了改善ACO-PSO 算法搜索能力，引入模糊技術(shù)，使得參數(shù)慣性權(quán)重模糊化。但問題的關(guān)鍵是在于如何構(gòu)建模糊概念的的隸屬函數(shù)。本文主要通過引入g參數(shù)，構(gòu)造具體的隸屬函數(shù)（記為u(g)）如下：

其中g(shù)表示ACO-PSO 中全局路徑極小值，N為種群規(guī)模，S1和S2為可控制參數(shù)，γ1和γ2為調(diào)整參數(shù)，這里滿足條件S1＞S2＞0，1 ＞γ1＞0，1 ＞γ2＞0。

通過上述隸屬函數(shù)的模糊映射關(guān)系，本文構(gòu)建了慣性權(quán)值的模糊自適應(yīng)調(diào)整函數(shù)[12]如下：

其中，nc為當(dāng)前迭代次數(shù)，NC為最大迭代數(shù)，ωs與ωe分別為參數(shù)慣性權(quán)重ω的初始值與結(jié)束值。

4 粒子群與蟻群混合算法

4.1 基本思想

粒子群算法和蟻群算法都是基于群體智能的搜索算法。ACO-PSO 的基本思想是綜合其兩種算法各自搜索特性，以達(dá)到逼近最佳位置。本文通過引入模糊技術(shù)，對(duì)粒子群算法中參數(shù)ω進(jìn)行模糊自適應(yīng)調(diào)整，前期讓ACO-PSO 算法進(jìn)行較強(qiáng)的全局搜索，后期進(jìn)行很強(qiáng)的局部搜索。具體算法流程如下：

步驟1設(shè)置粒子群參數(shù)并初始化粒子群，即隨機(jī)產(chǎn)生Np個(gè)粒子速度和位置。

步驟2初始化每個(gè)螞蟻的信息素和參數(shù)；將Nsa只螞蟻隨機(jī)放在N個(gè)城市上。

步驟3讓每個(gè)螞蟻遍歷所有城市，螞蟻以式（2）概念選擇所經(jīng)過的城市，更新Nsa只螞蟻的路徑長(zhǎng)度，并計(jì)算每個(gè)螞蟻的最優(yōu)路徑作為Np粒子的適應(yīng)度值。

步驟4根據(jù)粒子的適應(yīng)度值，按照式（6）和式（7）更新每個(gè)粒子個(gè)體最優(yōu)解和群體最優(yōu)解，相應(yīng)得出粒子的速度和位置。

步驟5根據(jù)式（9）模糊自適應(yīng)調(diào)整慣性權(quán)值ω，然后再次依據(jù)式（6）和式（7）更新粒子的速度和位置。

步驟5如果達(dá)到最大迭代次數(shù)時(shí)，則結(jié)束，否則，轉(zhuǎn)步驟4。

4.2 算法的改進(jìn)

為了進(jìn)一步研究，受GA 中的交叉算子[14]的思想啟示，本文引用了演化交叉[15-16]策略，即繼承父代的優(yōu)秀基因，且又能保證交叉后子代的可行性，使得搜索結(jié)果逼近最佳位置。在算法流程中，于步驟4 與5 之間添加：隨機(jī)選擇一只螞蟻，將其所走路徑與最優(yōu)螞蟻所走的路徑執(zhí)行演化交叉，生成新的路徑。演化交叉方式：將雙親X=(x1，x2，…，xN)和Y=(y1，y2，…，yN)看作環(huán)形回路，通過演化交叉產(chǎn)生子代children。步驟如下：

步驟1隨機(jī)選擇一個(gè)結(jié)點(diǎn)xi作為交叉起點(diǎn)，并加入子代children中，分別在父代中標(biāo)記xi為已訪問過的結(jié)點(diǎn)。

步驟2根據(jù)當(dāng)前結(jié)點(diǎn)xi，在X、Y中尋找下一個(gè)未訪問過的結(jié)點(diǎn)xi+1和yj+1。

步驟3若，將xi+1加到children中，記當(dāng)前結(jié)點(diǎn)為xi+1，在父代中標(biāo)記xi+1為訪問過的結(jié)點(diǎn)，否則將yi+1加入到children中，并記當(dāng)前結(jié)點(diǎn)為yi+1，在父代中標(biāo)記yi+1為訪問過的結(jié)點(diǎn)。

步驟4重復(fù)執(zhí)行步驟2，直至生成所有子代。

4.3 算法迭代圖

根據(jù)上述算法思想，整理得出ACO-GA-PSO 算法的運(yùn)算迭代圖如下（而ACO-PSO 迭代圖中缺少“演化交叉”步驟）。

圖1 ACO-GA-PSO算法迭代圖

4.4 算法的擴(kuò)展應(yīng)用

隨著現(xiàn)代物流業(yè)的快速發(fā)展，我們所遇到的VRP問題[17-18]更加貼近實(shí)際。所以通常會(huì)引入虛擬配送中心的概念，把VRP 問題轉(zhuǎn)化為帶有約束性的TSP 問題。利用本文的算法思想，然后在完善模型約束條件下，建立相應(yīng)的VRP 優(yōu)化模型。

依據(jù)文中的思想，假設(shè)以起始點(diǎn)城市作為配送中心，且每個(gè)城市包含用戶的需求量。首先對(duì)參數(shù)配送車最大載重MaxLoading、數(shù)量CarNum和初始載重Loading進(jìn)行初始化。然后在算法步驟3 中添加：如果用戶的需求量沒有超過當(dāng)前能承載的重量，則選擇此用戶，且將用戶的需求量加入Loading中；然后判斷是否Loading＜MaxLoading，如果是則繼續(xù)選擇下一個(gè)用戶點(diǎn)，否則返回配送中心，直至所有用戶的需求量被滿足為止。

5 實(shí)驗(yàn)仿真對(duì)比分析

為了驗(yàn)證參數(shù)模糊自適應(yīng)調(diào)整混合算法的搜索性能，文中ω參數(shù)變化形式分別為定值、線性變化和模糊變化，然后將ACO-PSO 和ACO-GA -PSO 分別在eil48，rat99 和ch130 問題上進(jìn)行測(cè)試。最后對(duì)變化的ω算法所得數(shù)據(jù)進(jìn)行對(duì)比分析。

本文采用Matlab7.10 語言編程實(shí)現(xiàn)，電腦的主要配置有3.4 GHz 主頻，酷睿i7 處理器和4 GB 內(nèi)存。參數(shù)Np，Nsa與N相等，vmax=7，c1=c2=2，γ1=0.5，γ2=0.5，ωs=0.9，ωe=0.4，ρ=0.4，參數(shù)S1和S2由定值慣性權(quán)重AC-PSO 中參數(shù)g和N值共同決定的。實(shí)驗(yàn)仿真次數(shù)為20 次，迭代次數(shù)NC=100（當(dāng)增加迭代次數(shù)達(dá)到200、500 和1 000 時(shí)，程序運(yùn)行解的質(zhì)量沒有得到顯著提高）。

圖2 ACO-PSO 算法仿真圖

圖3 ACO-GA-PSO 算法仿真圖

圖2 表示rat99 問題在ACO-PSO 算法仿真實(shí)驗(yàn)圖，其定值ω時(shí)minTd=1 467.4；模糊ω時(shí)minTd=1 442.6。圖3 表示rat99 問題在ACO-GA-PSO 算法仿真實(shí)驗(yàn)圖，其定值ω時(shí)minTd=1 327.3；模糊ω時(shí)minTd=1 286.5。

從如表1、表2 和表3 的仿真實(shí)驗(yàn)結(jié)果中，可以看出不同變化方式的參數(shù)ω，所產(chǎn)生的效果值也是不同的。從各自的表中對(duì)比，可以看出模糊變化ω參數(shù)模型的平均解與最好解都明顯好于參數(shù)ω定值和線性變化模型的對(duì)應(yīng)值。而且把演化交叉引入到ACO-PSO 混合算法中，其相應(yīng)的平均解與最好解都優(yōu)于ACO-PSO 的對(duì)應(yīng)值。綜上分析，本文算法的搜索性能優(yōu)越于同類算法。

表1 eil48 問題

表2 rat99 問題

表3 ch130 問題

6 結(jié)論與展望

本文主要融合蟻群算法和粒子群算法各自的搜索特點(diǎn)，組合成一種新的算法，并在算法迭代過程中添加了參數(shù)自動(dòng)調(diào)節(jié)機(jī)制環(huán)節(jié)。混合算法在搜索初期為了避免陷入局部最優(yōu)解，通過引入模糊技術(shù)，使得慣性權(quán)重自適應(yīng)調(diào)整為較大值，有利于全局搜索。在搜索后期，搜索范圍已達(dá)到全局最優(yōu)區(qū)域，為了尋求局部最優(yōu)解，此時(shí)讓慣性權(quán)重自適應(yīng)調(diào)整為較小值。實(shí)驗(yàn)仿真結(jié)果表明參數(shù)自動(dòng)調(diào)節(jié)的ACO-PSO 算法優(yōu)于同類算法。慣性權(quán)重的模糊自適應(yīng)調(diào)整混合算法使其在局部尋優(yōu)和全局尋優(yōu)之間取得平衡，從而得出滿意的實(shí)驗(yàn)結(jié)果。

從單回路的TSP 問題擴(kuò)展到大規(guī)模客戶集的配送路徑優(yōu)化問題、帶有約束性的復(fù)雜VRP 問題，可以考慮利用多種算法相結(jié)合來尋求其最優(yōu)解。在物流配送系統(tǒng)中，合理選取路徑與使用車輛數(shù)是減少浪費(fèi)、提高經(jīng)濟(jì)效益的重要手段，所以研究?jī)?yōu)化路徑問題有著重要的現(xiàn)實(shí)意義。

[1] Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Perth，Australia：IEEE Piscataway，1995：1942-1948.

[2] 袁德平.用于多目標(biāo)數(shù)據(jù)關(guān)聯(lián)的群智能混合算法[J].華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，40（9）：97-99.

[3] 郭靜.系統(tǒng)發(fā)生樹構(gòu)建方法綜述[J].計(jì)算機(jī)應(yīng)用研究，2013，30（3）：647-655.

[4] Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B，1996，26（1）：29-41.

[5] 柴寶杰.基于粒子群優(yōu)化的蟻群算法在TSP 中的應(yīng)用[J].計(jì)算機(jī)仿真，2009（8）：89-91.

[6] 高博.改進(jìn)型粒子蟻群算法的應(yīng)用研究[J].計(jì)算機(jī)安全，2010（11）：11-13.

[7] 谷文祥.一種求解TSP 問題的混合算法[J].東北師大學(xué)報(bào)：自然科學(xué)版，2011，43（3）：60-64.

[8] 孫凱.蟻群與粒子群混合算法求解TSP 問題[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（34）：60-63.

[9] 李擎.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J].控制與決策，2013，28（6）：873-878.

[10] 張超.一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法及其應(yīng)用[J].北京科技大學(xué)學(xué)報(bào)，2013，35（7）：955-960.

[11] 李長(zhǎng)榮.水聲信道盲均衡優(yōu)化仿真研究[J].計(jì)算機(jī)仿真，2013，30（7）：183-186.

[12] 郭文忠.求解TSP 問題的模糊自適應(yīng)粒子群算法[J].計(jì)算機(jī)科學(xué)，2006，33（6）：161-162.

[13] 楊帆.基于蟻群系統(tǒng)的參數(shù)自適應(yīng)粒子群算法及其應(yīng)用[J].控制理論與應(yīng)用，2010，27（11）：1479-1488.

[14] 王登科.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（1）：290-293.

[15] 石利平.改進(jìn)型遺傳算法求解TSP 問題[J].實(shí)驗(yàn)技術(shù)與管理，2014，31（7）：61-64.

[16] 胡志軍.基于求解TSP 問題的ACA-GA-PSO 算法[J].科技通報(bào)，2012，28（4）：82-84.

[17] 鄭峰峻.改進(jìn)的蟻群算法在物流配送路徑問題中的實(shí)現(xiàn)[J].物流科技，2010，2：22-24.

[18] 張錦等.基于TSP 的軍交VRP 優(yōu)化模型及其求解[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，41（22）：161-166.