粒子群優化的多群螞蟻算法

喻學才，張田文

(1.哈爾濱工業大學計算機科學與技術學院，哈爾濱 150001，yuxuecai@zjnu.cn;2.浙江師范大學交通學院，浙江金華 321004)

粒子群優化的多群螞蟻算法

喻學才1，2，張田文1

(1.哈爾濱工業大學計算機科學與技術學院，哈爾濱 150001，yuxuecai@zjnu.cn;2.浙江師范大學交通學院，浙江金華 321004)

設計多蟻群算法的關鍵是群間的信息交換規則.利用粒子群優化中粒子移動的基本思想研究了蟻群間信息交換的新規則，定義了新的多蟻群優化算法.新算法的信息交換所占用的數據通信量要遠低于現有的信息交換方法.將新算法用于求解帶時間窗的車輛路由問題并和以前的最好的多蟻群算法做比較，計算結果表明:新算法的性能超過了已有的方法.采用群體智能中個體的移動思想來設計群間信息交換規則能改進多蟻群算法的求解性能.

蟻群優化;粒子群優化;帶時間窗的車輛路由問題

蟻群優化(Ant Colony Optimization，ACO)是一種廣泛應用于各種困難組合優化問題求解的元啟發式方法［1］.將蟻群分成若干組能改進ACO的求解能力，且更易于實現并行化［2－4］.多群 ACO算法的分組關鍵技術是蟻群組間的信息交換規則的設計.本文將粒子群優化(Particle swarm optimization，PSO)［5］中的粒子移動的基本思想引入多群蟻群算法中群之間的信息交換，從而開發出新的多群蟻群算法.

1 帶時間窗約束的車輛路由問題

2 VRPTW的單群ACO算法

蟻群的每只螞蟻k構造VRPTW的一個可行解.首先，螞蟻k從中心倉庫0出發，選擇滿足問題所有約束的客戶作為下一個服務的對象.如此反復進行，直到一輛車h沒有可服務的客戶為止.如果還有客戶沒有被任何一輛車服務，則螞蟻k新增加一輛車，重復上述的構造過程，直到所有的客戶都恰好被一輛車提供了一次運輸服務為止.設螞蟻k當前服務的客服為i，則根據規則概率地選擇從未被任何一輛車服務的客戶j作為下一個服務對象.

式中:pkij(t)為螞蟻k在迭代步t服務完客戶i之后選擇客戶j為下一個服務對象的概率.Tk(t)為螞蟻k在迭代步t正在構建的部分解，J(Tk(t))為該部分解仍未提供服務的客戶的集合.τij∈τ為頂點i與頂點j的連接邊eij對應的信息素值.由于螞蟻經過邊eij時，會對其對應的信息素值進行局部更新，所以螞蟻k在迭代步t時邊eij對應的信息素值τij會變化.ηij為頂點i與頂點j的連接邊eij的啟發式信息.設Wij=Ckj－(Cki+si)為到達客戶j與服務完客戶i之間的時間差，Uij=lj－(Cki+si)為客戶j要求服務的緊迫性，則信息素值ηij定義為ηij=1/(WijUij)注意到Cki是一個與螞蟻k正構造的部分解相關的變量.這個定義實際上是說時間差越小，緊迫性越高的客戶應該被優先服務.q~為一個［ 0，1］區間上均勻分布的隨機數，q~0為式(1)中平衡使用與探索的選擇閾值.

螞蟻k選擇頂點j加入到其當前構造的部分解Tk(t)后，對信息素值τkij(t)進行局部更新.

式中:ρ為信息素值的減少率，τ0為信息素的初始值.信息素的初始值與VRPTW實例的最近鄰算法(Nearest-Neighbor Algorithm)最優解的代價相關即τ0=1/(n×fc(TNN)).

一個解的代價:

式中:L為所有車輛行程之和，Cf為一個大到足以偏置兩個目標函數值的數.

當所有的螞蟻構造了一個可行解后，利用從算法開始搜索到的最優解Tg對信息素矩陣進行全局更新.更新規則為

式中:Δτ=1/fc(Tg).注意到fc(Tg)≤fc(TNN)，所以Δτ＞τ0.

一個蟻群求解VRPTW的算法描述為:

算法1 求解VRPTW的單ACO算法(Vrptw-sAco).

輸入 實例:位置，時間窗，服務時間，需求量，車輛容量，最大迭代步Nt，螞蟻數Na，q0

輸出 搜索到的實例的最優解Tg

S1計算頂點間距離;

S2根據ηij用最近鄰(Near-Neighbor)算法求TNN;

3 VRPTW的多群ACO算法

多群ACO求解VRPTW實例是在單群算法的基礎上直接構建的.具體地說，每個蟻群仍像單群一樣求解VRPTW，然后每隔一定的迭代步數之后，群間交換積累的搜索信息.不同的多群ACO算法的區別在于群之間交換信息的差別.本文構造的多群ACO算法即將PSO中位置點移動的思想應用于群間信息的交換.

算法2 求解VRPTW的多群ACO算法(Vrptw－DAco).

輸入 實例:位置，時間窗，服務時間，需求量，車輛容量，最大迭代步Nt，螞蟻數Na，q0，群數Nc.

輸出 搜索到的實例的最優解Tg

最優解更新信息素矩陣的規則為

將PSO中粒子移動的基本思想引入群之間的信息交換可以設計一種新穎的交換信息模塊，即稱之為EXHGPSO.將多蟻群中的群對應為PSO中的粒子，根據文獻［2］，EXHGPSO的目的就是使群搜索向自算法開始的最好解Tg和群自己的最好解Tbh移動.為此需要使用兩個最好解Tg和Tbh更新群h的信息素.給每個最優解向信息素矩陣更新的增加值加以權衡→—εbh，其維數等于對應解Tbh的長度，每個分量ωj～U( 0，1).更新規則為

從數據通信量的角度看，兩種信息交換模塊中，一般情況下，EXHGPSO占用的通信資源較少.蟻群之間要交換信息:1)需要將各個群的最好解的代價發送到某個群;2)比較其大小;3)根據交換規則，由某些群向另一些群發送最好解的信息.就EXHGIB而言，注意到在相同的迭代步，各個蟻群構造的解的代價不會相差太遠，可以假設最好解代價低于平均代價的解為蟻群數的一半.這樣，平均而言，有Nc/2的蟻群會向除自身外的每個群發送其最好解的信息.整體看，解信息的發送次數為Nc(Nc－1)/2.除了解信息外，EXHGIB還需要發送每個群最好解相應的更新信息素權重，但與發送解相比，通信量則小了許多，可以忽略不計.再看EXHGPSO，在知道擁有最低代價的最好解的群之后，只需該群向其它每個群發送最好解的信息即可.整體看，發送次數為Nc－1.所以EXHGPSO在并行運行時具有很大的優勢，特別是在問題規模很大，解長度很長的情況下更適用.

從信息素更新的復雜性來看，EXHGPSO交換模塊下的每個群需要兩個解更新;而EXHGIB平均需要Nc/2個.所以EXHGPSO交換模塊下的每個群更新信息素模塊的計算量最低.

4 試驗

為了比較兩種交換模塊下的多蟻群算法求解VRPTW問題的性能，用C++語言實現了這些算法并在Solomon標準測試算例上執行.

表1報告每個小組的平均車輛數、平均路由長度和群間信息交換耗用的時間.試驗參數設置為:β = 2，ρ=0. 1，~q0=0.9.每群螞蟻數為 10，群數為8.最大迭代步數為1 500.這些參數是根據大量試驗結果進行設置，也有可能存在更好的設置.每個單群算法在局域網的一個節點上運行，局域網的實際平均帶寬為83.6 Mbps.

表1顯示，兩種信息交換模塊EXHGIB和EXHGPSO下的多蟻群算法求解主目標函數的能力在大多數算例組上相同，僅在組R上基于EXHGPSO模塊的多蟻群算法稍有優勢.另一方面，基于模塊EXHGIB的多蟻群算法求解次目標函數的優化能力所有算例組上比新算法有較為明顯的優勢.但是，當與局部優化結合時，新算法求解次目標函數能力比較弱的問題能得到充分的解決.再考慮到EXHGPSO比EXHGIB少得多的信息交換量(從表1中的時間上可知，EXHGIB用于信息交換耗用的時間比EXHGPSO要大一個數量級)，基于EXHGPSO設計多群蟻群優化應該是一個好的選擇.

表1 兩種多群ACO求解VRPTW的性能比較

5 結論

1)引入粒子群優化(PSO)中粒子移動的思想到多蟻群算法的群間信息交換設計中，得到了新的多蟻群算法.

2)新算法的交換數據量遠低于目前的方法.而且在帶時間窗約束的車輛路由問題上的計算結果顯示，新方法的求解性能優于原來的方法.

［1］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.

［2］ELLABIB I，CALAMAI P，BASIR O.Exchange strategies for multiple ant colony system［J］.Information Sciences， 2007，177(5):1248 －1264.

［3］MIDDENDORF M，REISCHLE F，SCHMECK H.Multi colony ant algorithms［J］.Journal of Heuristics， 2002，8(3):305－320.

［4］CHU S C，RODDICK J F，PAN J S.Ant colony system with communication strategies［J］.Information Sciences， 2004，167(1/4):63 －76.

［5］KENNEDY J，EBERHART R.Particle swarm optimization［C］//In:Neural Networks.Nagoya:IEEE International Conference on Proceedings，1995:1942－1948.

［6］GAMBARDELLA L M，TAILLARD E，AGAZZI G.MACS-VRPTW:A multiple ant colony system for vehicle routing problems with time windows［C］//In:New Ideas in Optimization.London:Advanced Topics In Computer Science Series，1999:63－76.

Multiple colony ant algorithm based on particle swarm optimization

YU Xue-Cai1，2，ZHANG Tian-wen1

(1.School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China，yuxuecai@zjnu.cn;2.Transportation College，Zhejiang Normal University，Jinhua 321004，China)

This work suggested a new multi-ACO algorithm by introducing the basic idea in the particle swarm optimization(PSO)into solution information exchange between ant colonies.The new algorithm takes much less cost for exchanging solution information than those existing methods.The new algorithm was used to solve the VRPTW benchmark instances and was compared with one existing algorithm.The results show that the new algorithm out performs the existing methods.Exploiting the idea of individual moving in the swarm intelligence to design the rule of information exchange between ant colonies can improve the performance of multi-ACO algorithm.

ant colony optimization;particle swarm optimization;vehicle routing problem with time windows

TP18

A

0367－6234(2010)05－0766－04

2009－01－10.

喻學才(1975—)，男，博士，講師;

張田文(1940—)，男，教授，博士生導師.

(編輯 張 紅)