朱亞琪，方建安

0 引言

車輛路徑問題（Vehicle Routing Problem, 簡稱VRP）是物流系統(tǒng)研究中的一項重要內(nèi)容，根據(jù)車輛路徑模型，可以將其轉(zhuǎn)化為TSP問題。蟻群算法在解決旅行商（TSP）等著名問題時，已得到了卓有成效的應(yīng)用，但解決大規(guī)模問題時，其收斂速度較慢且耗時較長[1]。

粒子群優(yōu)化算法（PSO）[2,3]是一種全局優(yōu)化算法，由Eberhart和Kennedy于1995年提出的。該算法的優(yōu)點：1) 具有較大范圍的全局搜索能力；2) 搜索從群體出發(fā)，具有穩(wěn)定性；3) 搜索使用評價函數(shù)值啟發(fā)；4) 收斂速度快，參數(shù)調(diào)整簡單；5) 具有可擴展性, 容易與其他算法結(jié)合。存在的缺點是：在算法后期的局部搜索能力差，反饋信息利用不充分。

差分進化法可以解決不可微分非線性函數(shù)最優(yōu)化問題，采用隨機直接搜索法，利用上、下代問的競爭原理，收斂速度快，同時族群多樣性大幅度減小，但存在收斂過早、易陷入局部最優(yōu)等問題。文獻[4]則提出改進差分進化法，稱為混合差分進化法（hybrid differential evolution method），然而，混合差分進化法的突變操作共有5種方法，本文根據(jù)蟻群算法的特點，在混合算法中使用螞蟻系統(tǒng)搜尋適當(dāng)?shù)耐蛔儾僮?，以利于加速算法搜索全局最?yōu)解。

本文提出一種雙種群蟻群算法，在蟻群的基礎(chǔ)上引入差分進化（DE）和粒子群算法（PSO）。通過在 PSOAS種群和 DEAS種群之間建立一種信息交流機制，使信息能夠在兩個種群中傳遞，以免某一方因錯誤的信息判斷而陷入局部最優(yōu)點。

1 物流配送的路徑問題

為了降低服務(wù)商的運營成本，物流系統(tǒng)都會在車輛配送路徑上做優(yōu)化。選取合適的運輸路線，可以加快對客戶需求的響應(yīng)速度，提高服務(wù)質(zhì)量，增強客戶對物流系統(tǒng)的滿意度。車輛路徑問題，一般定義為對一系列發(fā)貨點和/或收貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件下，達到一定的目標(biāo)（如路程最短、費用最小、時間盡量少、使用車輛盡量少等）。

物流配送路徑問題，實際上是旅行商(Traveling Sales-man Problem, TSP)的問題，對TSP的問題描述如下：一個貨郎要走訪 N個橙色，每個城市必須經(jīng)過一次且只能經(jīng)過一次，最后回到出發(fā)的城市，就算是完成了一次旅行，找到一條最短的路徑。其相應(yīng)數(shù)學(xué)描述如下：設(shè)有一城市集合，每對城市間的距離為。求一條經(jīng)過C中每個城市正好一次的最短路徑。

2 蟻群算法

蟻群算法（Ant Colony Algorithm, ACA）于20世紀(jì)90年代由Colony等提出，該算法模擬蟻群的群體協(xié)作覓食過程，由若干個螞蟻共同構(gòu)造解路徑，通過在解路徑上遺留并交換信息素提高解的質(zhì)量，進而達到優(yōu)化的目的。由于物流配送路徑問題實際上是一個旅行商問題，下面以 TSP為例介紹算法內(nèi)容：

設(shè)m是蟻群中螞蟻的數(shù)量，dij是城市i與j之間的距離，ηij(t)=1/dij為啟發(fā)函數(shù)；τij是t時刻路徑(i,j)上的信息量；pijk(t) 表示在t時刻螞蟻k由城市i轉(zhuǎn)移到城市j的概率，公式（1）

其中，j是尚未訪問的城市；allowedk={C-tabuk}表示螞蟻k下一步允許選擇的城市；α和β為啟發(fā)式因子；tabuk(k=1,2,…,m)用以記錄在t時刻螞蟻k已走過的城市，不允許該螞蟻在本次循環(huán)中重復(fù)經(jīng)過，本次循環(huán)結(jié)束后清空禁忌表。

螞蟻完成一次循環(huán)，更新各路徑信息素，公式（2）

其中，ρ∈[0,1)表示信息素?fù)]發(fā)系數(shù)；(1?ρ)表示信息素殘留因子；△τij表示本次循環(huán)中路徑ij上的信息量增量，初始時△τij(0)=0；△τijk表示螞蟻k在本次循環(huán)中在城市i和j之間留下的信息量，公式（3）

其中，Lk表示螞蟻k環(huán)游一周的路徑長度；Q為常數(shù)。蟻群算法中，參數(shù)的選取方法與選取原則直接影響到蟻群算法的計算效率和收斂性[5]；另外，該算法存在著初始信息素缺乏、收斂速度慢、容易陷入局部最優(yōu)等缺點。

本文采用雙種群策略，種群一采用蟻群算法與差分演化結(jié)合，可以很好地解決參數(shù)優(yōu)化問題。種群二采用蟻群混合粒子群算法，增強了大范圍全局搜索能力，很好地解決了收斂速度慢、容易陷入局部最優(yōu)問題。

3 蟻群算法與差分演化結(jié)合（DEAS）

差分演化算法擅長連續(xù)問題的優(yōu)化，并且已成功應(yīng)用于很多算法的參數(shù)控制中。由于蟻群算法的控制參數(shù)是連續(xù)變化的，因此可以利用DE 對其進行參數(shù)優(yōu)化，進而改善蟻群算法的性能。

DEAS 將蟻群算法的參數(shù)（包括種群大小m、啟發(fā)式因子α和β，信息素?fù)]發(fā)系數(shù)ρ）作為DE 解空間向量的元素，每個個體是一個四維向量。以DE 解空間中個體為參數(shù)組合的蟻群，搜尋最優(yōu)路徑Iter代中得到的最優(yōu)解作為 DE 的適應(yīng)評價函數(shù)。以解決TSP 問題為例對DEAS 作具體應(yīng)用說明，參數(shù)設(shè)置按文獻[6]所示。F=0.5，CR=0.9；NP∈[3D,8D]，本文中取 5D，算法的終止條件為滿足優(yōu)化要求或達到最大迭代數(shù)。步驟如下：

步驟1：差分演化算法初始化：

設(shè)置目前進化代數(shù)t=1，差分演化算法的F、CR、NP以及迭代次數(shù)MAX_G，隨機選擇NP個個體，每個個體包含4 個參數(shù)，是一個NP×4 的隨機數(shù)組。其中每一維各代表m、α、β、ρ，分別在[0,2N]、[0,5]、[0,10]、[0,1]隨機取值。

步驟2：若t≥MAX_G，跳轉(zhuǎn)到Step5；否則：

蟻群算法初始化：在每個參數(shù)向量下的蟻群運行的代數(shù)Iter；對每條路徑設(shè)定初始信息量，τij=τo，將M只包含各自參數(shù)的螞蟻隨機地放置在N個節(jié)點上(N為城市數(shù))，將第k只螞蟻的出發(fā)城市加入tabuk；根據(jù)各自的參數(shù)向量值，求Iter迭代后的最優(yōu)解，即求參數(shù)向量對應(yīng)的適應(yīng)值。

完成對每只螞蟻的一次路徑搜索，并找出本次搜索得到的最優(yōu)解：

1、根據(jù)公式（1）的計算方法，求所有城市作為下一個城市的概率，使用輪盤賭的方法隨機確定下一個要走向的城市，循環(huán)進行公式（1）直到只剩下一個城市未走時，直接到達那個城市，此時，表示一只螞蟻已經(jīng)完成了一次路徑求解；

2、計算得到這只螞蟻此次路徑的長度；

根據(jù)公式（2）對全局信息素進行更新，并找到本次求解所找到的最優(yōu)解，記錄最優(yōu)解對應(yīng)的參數(shù)向量；將本次迭代產(chǎn)生最優(yōu)解，即得到參數(shù)向量對應(yīng)的適應(yīng)值，與歷史記錄最優(yōu)解進行比較，選取較小的一個解來更新歷史最優(yōu)解；

步驟3：將尋徑后的每個蟻群的最短路徑作為相應(yīng)參數(shù)向量的適應(yīng)函數(shù)值。根據(jù)公式（4）～公式（6）進行差分運算的變異、交叉和選擇運算（在選擇操作中的求解適應(yīng)值函數(shù)即以新的解向量為參數(shù)，進行步驟2 中的內(nèi)兩層循環(huán)），生成新一代種群。t值加1，跳轉(zhuǎn)至步驟2；在執(zhí)行公式（6）進行選擇的時候，如果發(fā)現(xiàn)出現(xiàn)比歷史最優(yōu)解好的解，也要進行歷史最優(yōu)值的更新。

其中：j∈[1,D],randb(j) ≥[0,1]是同一隨機數(shù)發(fā)生器的第 j個值；CR∈[0,1]是變異概率；randr(j)∈[1,2,…,D]是隨機選擇指數(shù)，它確保能從中得到至少一個參數(shù)。

（c）選擇操作，采用貪婪策略，得公式（6）

其中Φ(x)代表適應(yīng)函數(shù)。

步驟 4：最后輸出全局最優(yōu) TSP 路徑值以及全局最優(yōu)參數(shù)向量[m,α,β,ρ]。

4 蟻群算法與粒子群算法結(jié)合（PSOAS）

蟻群算法利用了信息素進行傳遞信息，而粒子群優(yōu)化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導(dǎo)粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發(fā)式算法的有機結(jié)合，容易出現(xiàn)早熟現(xiàn)象以及陷入局部最優(yōu)解?；旌系乃悸肥亲屛浵佉簿哂小傲Ｗ印钡奶匦?，首先螞蟻按照蟻群算法，完成一次遍歷后，再讓螞蟻根據(jù)局部最優(yōu)解和全局最優(yōu)解進行調(diào)整。

解TPS問題的混合算法如下：

步驟 1：nc←0，（nc為迭代步數(shù)或搜索次數(shù)），初始化，產(chǎn)生大量的路徑（如100條），從中選擇比較優(yōu)的（如30條），使這些路徑留下信息素，將m個螞蟻置于n個頂點上；

步驟2：根據(jù)當(dāng)前位置計算適應(yīng)值（各路徑的長度）ltsp0，設(shè)置當(dāng)前適應(yīng)值為個體極值Ptbest，當(dāng)前位置為個體極值位置pbcest，根據(jù)各個粒子的個體極值Ptbest找出全局極值bgtest和全局極值位置gcbest；

步驟3：將各螞蟻的初始出發(fā)點置于當(dāng)前解集中，對每個螞蟻k(k=1，2，…，m)，按概率移至下一頂點j，將頂點j置于當(dāng)前解集；

步驟4：對每個螞蟻進行如下操作，第j個螞蟻路徑Co(j)與gcbest交叉得到與pbcest交叉得到，對產(chǎn)生變異得到，根據(jù)當(dāng)前位置計算路徑長度ltsp1，若新的目標(biāo)函數(shù)變好，接受新值，否則就拒絕，第j個粒子路徑仍然為Co(j)。重新找出各個螞蟻子的個體極值ptbest和極值位置pbcest，找出全局極值gtbest和全局極值位置gcbest；

步驟5：計算各螞蟻的路徑長度Lk(k=1,2,…,m)，記錄當(dāng)前的最好解；

步驟6：對路徑長度Lk小于給定值的路徑，按公式（2）中的更新方程修改軌跡強度：

步驟7：nc←nc＋1；

步驟8：若nc< 預(yù)定的迭代次數(shù)且無退化行為（即找到的都是相同解）則轉(zhuǎn)步驟2；

步驟9：輸出目前最好解。

5 雙種群混合算法

對比分析 PSO 和 DE 兩種算法的特點可以發(fā)現(xiàn)，DE算法具備的記憶能力使其可以跟蹤當(dāng)前的搜索情況，以調(diào)整其搜索策略，具有較強的全局收斂能力和魯棒性；PSO 算法簡單，具有運算速度快、搜索能力強等特點。本文提出基于蟻群算法的差分進化混合粒子群算法的本質(zhì)，是基于一種雙種群策略，其中一個種群中的個體按照 PSOAS 操作進化，另一個種群中的個體按照 DEAS操作進化，在進化過程中，通過引入一種信息交流機制，使信息能夠在兩個種群中傳遞，有助于個體避免錯誤的信息判斷而陷入局部最優(yōu)點。采用非線性動態(tài)自適應(yīng)慣性權(quán)重策略，以提高算法的性能，其更新狀態(tài)如公式（7）

其中，k為控制因子，控制w與t變化曲線的平滑度。

6 算法仿真

利用實例對雙種群混合算法性能進行測試，并將結(jié)果與單一的DEAS算法、單一的PSOAS算法的結(jié)果進行對比。實驗獨立進行30次，統(tǒng)計結(jié)果，如表1所示：

表1 獨立試驗30次的統(tǒng)計結(jié)果

結(jié)果表明，雖然蟻群算法與粒子群算法結(jié)合能夠提高收斂速度，但是PSOAS算法得到的最差解較多，表明算法極易收斂到局部最小解。而蟻群算法與差分進化相結(jié)合能夠改善算法全局優(yōu)化能力，能得到較解且相對穩(wěn)定。雙蟻群混合算法則吸收了兩種算法的優(yōu)點，該算法達到最好解的次數(shù)最多，增加了最優(yōu)解的概率；另外，由于兩個種群中的通信機制，PSOAS種群提高了DEAS種群的搜索效率。

圖1和圖2分別為PSOAS種群與DEAS種群得到的最優(yōu)路徑，其中種群2的解優(yōu)于種群1，因此最終解為種群2的運算結(jié)果。由圖3，圖4可以看出，原本收斂較慢的DEAS算法由于通信機制，收斂速度與PSOAS算法比較接近。

圖1 種群1(PSOAS混合算法)計算結(jié)果

圖2 種群2(DEAS混合算法)計算結(jié)果

圖3 種群1中最佳路徑隨迭代的變化

圖4 種群2中最佳路徑隨迭代的變化

7 結(jié)束語

本文針對物流過程中配送路徑最優(yōu)問題，設(shè)計了基于蟻群算法的雙種群混合算法，種群一采用蟻群算法與差分演化結(jié)合，種群二采用蟻群混合粒子群算法，在進化過程中通過引入一種信息交流機制使信息能夠在兩個種群中傳遞，提高了螞蟻在選路時的協(xié)同合作能力。仿真實驗表明，該算法能較好地發(fā)現(xiàn)全局最優(yōu)解，并且有較快的收斂速度和較高的穩(wěn)定性，在綜合性能上遠(yuǎn)遠(yuǎn)高于 DEAS算法，并在計算效率上優(yōu)于PSOAS算法。

[1]Colorni A, Dorigo M, Theraulaz G. Swarm intelligence:From natural to artificial systems[M]. New York: Oxford University Press, 1999.

[2]KENNEDY J, EBERHART R C. Particle Swarm optimization[C]//IEEE International Conference on Neural Network. Perth, Australia:[s.n.], 1995.

[3]SHI Y, EBERHART R C. A modified swarm optimizer[C]//IEEE International Conference of Evolutionary Computation. Anchorage, Alaska:[s.n.], 1998.

[4]CHIOU J P, WANG F S, A Hybrid method of differential evolution with application to optimal control problems of a bioprocess system[J]．Proc l 998 IEEE on Evolutionary Computation Conf, 1998, l：627—632．

[5]崔嬌，黃少榮．基于差分演化的自適應(yīng)參數(shù)控制蟻群算法[J]．計算機工程，2011,37(6):190-193．

[6]KENNEDY J，EBERHART R． Particle swarm optimization［C］/ /Proc of IEEE International Conference on Neural Networks． 1995:1942-1948．