粒子群優(yōu)化的多群螞蟻算法

喻學(xué)才，張?zhí)镂?/p>

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

粒子群優(yōu)化的多群螞蟻算法

喻學(xué)才1，2，張?zhí)镂?

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

設(shè)計(jì)多蟻群算法的關(guān)鍵是群間的信息交換規(guī)則.利用粒子群優(yōu)化中粒子移動(dòng)的基本思想研究了蟻群間信息交換的新規(guī)則，定義了新的多蟻群優(yōu)化算法.新算法的信息交換所占用的數(shù)據(jù)通信量要遠(yuǎn)低于現(xiàn)有的信息交換方法.將新算法用于求解帶時(shí)間窗的車輛路由問(wèn)題并和以前的最好的多蟻群算法做比較，計(jì)算結(jié)果表明:新算法的性能超過(guò)了已有的方法.采用群體智能中個(gè)體的移動(dòng)思想來(lái)設(shè)計(jì)群間信息交換規(guī)則能改進(jìn)多蟻群算法的求解性能.

蟻群優(yōu)化;粒子群優(yōu)化;帶時(shí)間窗的車輛路由問(wèn)題

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

1 帶時(shí)間窗約束的車輛路由問(wèn)題

2 VRPTW的單群ACO算法

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

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

螞蟻k選擇頂點(diǎn)j加入到其當(dāng)前構(gòu)造的部分解Tk(t)后，對(duì)信息素值τkij(t)進(jìn)行局部更新.

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

一個(gè)解的代價(jià):

式中:L為所有車輛行程之和，Cf為一個(gè)大到足以偏置兩個(gè)目標(biāo)函數(shù)值的數(shù).

當(dāng)所有的螞蟻構(gòu)造了一個(gè)可行解后，利用從算法開(kāi)始搜索到的最優(yōu)解Tg對(duì)信息素矩陣進(jìn)行全局更新.更新規(guī)則為

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

一個(gè)蟻群求解VRPTW的算法描述為:

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

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

輸出 搜索到的實(shí)例的最優(yōu)解Tg

S1計(jì)算頂點(diǎn)間距離;

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

3 VRPTW的多群ACO算法

多群ACO求解VRPTW實(shí)例是在單群算法的基礎(chǔ)上直接構(gòu)建的.具體地說(shuō)，每個(gè)蟻群仍像單群一樣求解VRPTW，然后每隔一定的迭代步數(shù)之后，群間交換積累的搜索信息.不同的多群ACO算法的區(qū)別在于群之間交換信息的差別.本文構(gòu)造的多群ACO算法即將PSO中位置點(diǎn)移動(dòng)的思想應(yīng)用于群間信息的交換.

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

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

輸出 搜索到的實(shí)例的最優(yōu)解Tg

最優(yōu)解更新信息素矩陣的規(guī)則為

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

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

從信息素更新的復(fù)雜性來(lái)看，EXHGPSO交換模塊下的每個(gè)群需要兩個(gè)解更新;而EXHGIB平均需要Nc/2個(gè).所以EXHGPSO交換模塊下的每個(gè)群更新信息素模塊的計(jì)算量最低.

4 試驗(yàn)

為了比較兩種交換模塊下的多蟻群算法求解VRPTW問(wèn)題的性能，用C++語(yǔ)言實(shí)現(xiàn)了這些算法并在Solomon標(biāo)準(zhǔn)測(cè)試算例上執(zhí)行.

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

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

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

5 結(jié)論

1)引入粒子群優(yōu)化(PSO)中粒子移動(dòng)的思想到多蟻群算法的群間信息交換設(shè)計(jì)中，得到了新的多蟻群算法.

2)新算法的交換數(shù)據(jù)量遠(yuǎn)低于目前的方法.而且在帶時(shí)間窗約束的車輛路由問(wèn)題上的計(jì)算結(jié)果顯示，新方法的求解性能優(yōu)于原來(lái)的方法.

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

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

張?zhí)镂?1940—)，男，教授，博士生導(dǎo)師.

(編輯 張 紅)