求解TSP 的蟻群與模糊自適應粒子群算法

張海俊，王 波

ZHANG Haijun,WANG Bo

上海理工大學 管理學院，上海200093

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

1 引言

粒子群算法[1]是由Kennedy 博士與Eberhart 博士共同提出一種新興的基于群體智能[2-3]的搜索算法。它起源于對鳥群覓食行為的模擬，主要是仿照種群行為來模擬粒子們的運動。這種算法簡單且參數易于調整，現在已經廣泛應用于重要領域。在處理問題時，一般采用定值慣性權重的PSO 算法，但在實際搜索過程中，容易早熟且易于陷入局部最優。

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

在融合ACO 與PSO 算法中文獻[5]應用粒子群算法對蟻群算法的參數進行優化，并運用蟻群系統算法尋找最優路徑；文獻[6]中為了提高收斂速度，將每隔一定代數的數據引入粒子群運算，最終在局部與全局最優之間取得平衡；文獻[7]中引入重力搜索算法來優化蟻群算法參數和粒子群算法，并且提高了蟻群算法的優化性能；文獻[8]中將蟻群分成多個螞蟻子群，通過粒子群算法優化螞蟻子群參數，并在螞蟻子群中引入交換操作對TSP 問題進行優化；文獻[9]中給出一種全局異步與精英策略相結合的信息素更新方法，從而提高算法的運行迭代速度。

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

2 基本蟻群算法

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

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

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

3 模糊自適應粒子群算法

3.1 粒子群算法基本思想

粒子群算法是一種模擬鳥群的捕食行為群體智能算法[2-3]。在尋優過程中，每個潛在的最好解都與粒子運動速度相關聯，根據粒子的歷史經驗以及鄰居們的經驗來調整其速度大小和方向，朝著最好解的方向逼近。

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

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

3.2 慣性權重的自適應調整模型

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

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

通過上述隸屬函數的模糊映射關系，本文構建了慣性權值的模糊自適應調整函數[12]如下：

其中，nc為當前迭代次數，NC為最大迭代數，ωs與ωe分別為參數慣性權重ω的初始值與結束值。

4 粒子群與蟻群混合算法

4.1 基本思想

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

步驟1設置粒子群參數并初始化粒子群，即隨機產生Np個粒子速度和位置。

步驟2初始化每個螞蟻的信息素和參數；將Nsa只螞蟻隨機放在N個城市上。

步驟3讓每個螞蟻遍歷所有城市，螞蟻以式（2）概念選擇所經過的城市，更新Nsa只螞蟻的路徑長度，并計算每個螞蟻的最優路徑作為Np粒子的適應度值。

步驟4根據粒子的適應度值，按照式（6）和式（7）更新每個粒子個體最優解和群體最優解，相應得出粒子的速度和位置。

步驟5根據式（9）模糊自適應調整慣性權值ω，然后再次依據式（6）和式（7）更新粒子的速度和位置。

步驟5如果達到最大迭代次數時，則結束，否則，轉步驟4。

4.2 算法的改進

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

步驟1隨機選擇一個結點xi作為交叉起點，并加入子代children中，分別在父代中標記xi為已訪問過的結點。

步驟2根據當前結點xi，在X、Y中尋找下一個未訪問過的結點xi+1和yj+1。

步驟3若，將xi+1加到children中，記當前結點為xi+1，在父代中標記xi+1為訪問過的結點，否則將yi+1加入到children中，并記當前結點為yi+1，在父代中標記yi+1為訪問過的結點。

步驟4重復執行步驟2，直至生成所有子代。

4.3 算法迭代圖

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

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

4.4 算法的擴展應用

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

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

5 實驗仿真對比分析

為了驗證參數模糊自適應調整混合算法的搜索性能，文中ω參數變化形式分別為定值、線性變化和模糊變化，然后將ACO-PSO 和ACO-GA -PSO 分別在eil48，rat99 和ch130 問題上進行測試。最后對變化的ω算法所得數據進行對比分析。

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

圖2 ACO-PSO 算法仿真圖

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

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

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

表1 eil48 問題

表2 rat99 問題

表3 ch130 問題

6 結論與展望

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

從單回路的TSP 問題擴展到大規模客戶集的配送路徑優化問題、帶有約束性的復雜VRP 問題，可以考慮利用多種算法相結合來尋求其最優解。在物流配送系統中，合理選取路徑與使用車輛數是減少浪費、提高經濟效益的重要手段，所以研究優化路徑問題有著重要的現實意義。

[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] 袁德平.用于多目標數據關聯的群智能混合算法[J].華南理工大學學報：自然科學版，2012，40（9）：97-99.

[3] 郭靜.系統發生樹構建方法綜述[J].計算機應用研究，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] 柴寶杰.基于粒子群優化的蟻群算法在TSP 中的應用[J].計算機仿真，2009（8）：89-91.

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

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

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

[9] 李擎.一種基于粒子群參數優化的改進蟻群算法[J].控制與決策，2013，28（6）：873-878.

[10] 張超.一種基于粒子群參數優化的改進蟻群算法及其應用[J].北京科技大學學報，2013，35（7）：955-960.

[11] 李長榮.水聲信道盲均衡優化仿真研究[J].計算機仿真，2013，30（7）：183-186.

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

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

[14] 王登科.基于粒子群優化與蟻群優化的云計算任務調度算法[J].計算機應用與軟件，2013，30（1）：290-293.

[15] 石利平.改進型遺傳算法求解TSP 問題[J].實驗技術與管理，2014，31（7）：61-64.

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

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

[18] 張錦等.基于TSP 的軍交VRP 優化模型及其求解[J].數學的實踐與認識，2012，41（22）：161-166.