基于蟻群算法的多目標(biāo)優(yōu)化技術(shù)研究

肖 菁， 陳鳳蓮， 湯健超

(1.華南師范大學(xué)計算機(jī)學(xué)院，廣州 510631；2.武漢大學(xué)軟件工程國家重點(diǎn)實(shí)驗(yàn)室，武漢 430072)

現(xiàn)實(shí)生活中的許多優(yōu)化問題通常存在帶有多個約束條件的多個目標(biāo)需要被同時優(yōu)化，多目標(biāo)優(yōu)化是要找到一個能同時滿足所有優(yōu)化目標(biāo)的解. 一般情況下，這些目標(biāo)之間是相互沖突的，改善了一個子目標(biāo)的性能，可能會影響其他子目標(biāo)的性能. 因此，解決多目標(biāo)優(yōu)化問題，需要找的是一組折衷解集使各目標(biāo)盡可能達(dá)到最優(yōu). 多目標(biāo)優(yōu)化問題與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于多目標(biāo)優(yōu)化的解是由多個Pareto最優(yōu)解組成的集合.

在科學(xué)研究和工程應(yīng)用等現(xiàn)實(shí)生活中，多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem，MOP)是熱門的研究課題. 進(jìn)化算法(Evolutionary Algorithms,EA)、粒子群優(yōu)化(Particle Swarm Optimization,PSO)、蟻群算法(Ant Colony Optimization,ACO)等基于種群的智能算法具有較高的并行性，在求解多目標(biāo)問題時一次運(yùn)行能求得多個Pareto最優(yōu)解. 因此，吸引了越來越多不同領(lǐng)域的學(xué)者利用這一類基于種群的算法求解多目標(biāo)優(yōu)化問題.

螞蟻算法(Ant algorithm)最早由Dorigo等[1]提出，并逐漸發(fā)展為ACO算法. ACO是一種源于生物世界的仿生優(yōu)化算法，同時也是具有高度創(chuàng)新的元啟發(fā)式算法. 基本蟻群優(yōu)化算法的搜索機(jī)制是基于轉(zhuǎn)移概率，其信息素的更新是基于解的質(zhì)量. 就單目標(biāo)優(yōu)化問題而言，這2種方式有利于螞蟻的搜索朝著信息素濃度高的區(qū)域進(jìn)行，并且更快地獲得更好的解. 以旅行商問題(Traveling Salesman Problem, TSP)為例，將此問題用圖1表示，每個點(diǎn)代表一座城市，螞蟻會在經(jīng)過的路徑上釋放信息素，越多螞蟻經(jīng)過的路徑上信息素就越多，根據(jù)信息素的分布，螞蟻較容易找到最短路徑.

自Dorigo和Gambardella[2]首次將蟻群算法成功應(yīng)用于旅行商問題后，許多學(xué)者利用蟻群算法求解多目標(biāo)優(yōu)化問題，這類算法就是多目標(biāo)蟻群算法[3](Multi-objective Ant Colony Optimization，MOACO),被應(yīng)用于科學(xué)研究、工程應(yīng)用、通信網(wǎng)絡(luò)以及生產(chǎn)管理等諸多優(yōu)化領(lǐng)域并取得了良好的效果.

圖1 蟻群算法求解旅行商問題示意圖

調(diào)度(scheduling)問題是一類經(jīng)典運(yùn)籌問題，包括3個重要的要素：任務(wù)、資源和目標(biāo)，是典型的NP-hard問題. 它廣泛應(yīng)用在離散制造工業(yè)和流程工業(yè)，目前已成為計算機(jī)集成制造系統(tǒng)(Computer Integrated Manufacturing Systems，CIMS)領(lǐng)域內(nèi)的重要研究課題. 流水車間調(diào)度問題(Flow Shop Scheduling Problem，F(xiàn)SP)在同時需要考慮最大完工時間、總流程時間和機(jī)器閑置總的時間時成了一個典型的多目標(biāo)優(yōu)化問題. Yagmahan和Yenisey[4-5]結(jié)合蟻群優(yōu)化和局部搜索的策略成功地將其問題進(jìn)行了優(yōu)化.

多目標(biāo)最短路徑問題(Multi-Objective Shortest Problem,MOSP)是傳統(tǒng)的單目標(biāo)最短路徑的延伸，同時考慮多個相互存在沖突的目標(biāo)且計算出一條有效的最短路徑. 該問題在遠(yuǎn)程通信、運(yùn)輸和工程管理中都是最重要的問題之一. Ghoseiri和Nadjari[6]利用多目標(biāo)蟻群優(yōu)化算法解決雙目標(biāo)最短路徑問題取得了很好的效果. Sun等[7]使用自適應(yīng)算子對MOACO進(jìn)行了改進(jìn)，提出了算法分為2個階段，在前期，使用一個更高的概率對解空間進(jìn)行搜索，搜集有用的全局信息；在后期，使用自適應(yīng)算子使得搜索空間減小，從而加速收斂.

針對多目標(biāo)蟻群算法為目前研究熱點(diǎn)，本文簡要介紹了多目標(biāo)優(yōu)化問題、蟻群算法和Pareto最優(yōu)解的定義，詳細(xì)討論了目前針對求解多目標(biāo)問題所使用的蟻群優(yōu)化算法，重點(diǎn)討論了蟻群算法的內(nèi)在并行性在多目標(biāo)上的實(shí)現(xiàn)，分析了諸多學(xué)者研究多目標(biāo)蟻群優(yōu)化算法的具體情況. 最后對多目標(biāo)蟻群優(yōu)化算法的進(jìn)一步發(fā)展提出了新思路.

1 多目標(biāo)蟻群優(yōu)化算法的一般模型

多目標(biāo)優(yōu)化問題可描述為：

定義1 一個決策向量x1支配另一個決策向量x2(x1x2)，當(dāng)且僅當(dāng)?i=1，2，…，m，fi(x1)≤fi(x2)∧?j=1，2，…，N，fj(x1)

定義3 所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集P*. 表示如下：

其結(jié)構(gòu)見圖2.

圖2 Pareto解集和Pareto前沿面

2 求解多目標(biāo)蟻群優(yōu)化的新型范例研究

近年來，為解決多目標(biāo)優(yōu)化問題，學(xué)者們提出了多種蟻群算法. 本文選取了其中典型的3種多目標(biāo)蟻群優(yōu)化算法進(jìn)行討論.

2.1 基于分解的多目標(biāo)蟻群優(yōu)化

將多目標(biāo)優(yōu)化問題分解成單目標(biāo)優(yōu)化問題時，通常使用加權(quán)法、契比雪夫法(Tchebycheff approach)和邊界交集法等傳統(tǒng)數(shù)學(xué)規(guī)劃方法. 2007年，Zhang和Li[8]將這種傳統(tǒng)的策略與進(jìn)化算法相結(jié)合提出了一種新穎的基于分解的多目標(biāo)進(jìn)化算法(MOEA/D). 隨后，很多學(xué)者在該算法的基礎(chǔ)上提出了新的觀點(diǎn)以解決不同的問題. 2013年，Ke等[9]在MOEA/D的基礎(chǔ)上做了進(jìn)一步的研究工作，將蟻群算法與多目標(biāo)進(jìn)化算法結(jié)合，提出了一個多目標(biāo)進(jìn)化算法——MOEA/D-ACO. 該算法與MOEA/D算法原理一樣，首先將多目標(biāo)優(yōu)化問題分解為一定數(shù)量的單目標(biāo)優(yōu)化問題，然后用蟻群算法優(yōu)化. 同時，螞蟻由原來的一個群體被分成多個子群，并在此基礎(chǔ)上引入了鄰居螞蟻，每只螞蟻都有其鄰居，并且一只螞蟻對應(yīng)于一個子問題. 每一個子群維持一個信息素矩陣，并且都有其自己的啟發(fā)式信息矩陣. 每只螞蟻結(jié)合鄰居更新并記錄其所對應(yīng)子問題的當(dāng)前最優(yōu)解，并結(jié)合自己所在子群的信息素值和啟發(fā)式信息構(gòu)建每個子問題的解.

2012年，Cheng等[10]提出了基于分解的多目標(biāo)蟻群優(yōu)化(MoACO/D)的框架求解雙目標(biāo)的旅行商問題(bTSPs). 在該算法中，第一次將bTSP使用契比雪夫法分解成一定數(shù)量的子問題，蟻群以重疊的方式被分為多個子群，每個子群獨(dú)立地、并行地使用單目標(biāo)ACO優(yōu)化其對應(yīng)的子問題. 在這個框架的基礎(chǔ)上，他們還將MoACO/D分別與螞蟻系統(tǒng)(Ant System, AS)、最大最小螞蟻系統(tǒng)(MAX-MIN Ant System, MMAS)和蟻群系統(tǒng)(Ant Colony System, ACS)對10組bTSP進(jìn)行了實(shí)驗(yàn)并與MACS[11]、BIANT[12-13]、UNBI[12-13]進(jìn)行比較，結(jié)果表明，在處理大規(guī)模的雙目標(biāo)旅行商問題時，MoACO/D的性能優(yōu)于上述3種著名的多目標(biāo)蟻群優(yōu)化算法. 同年，Gao等[14]針對使用標(biāo)量多目標(biāo)優(yōu)化技術(shù)處理多目標(biāo)優(yōu)化問題，提出了一個與概率模型結(jié)合的、基于分解的多目標(biāo)評估分布估計算法(MEDA/D). 該算法使用先驗(yàn)經(jīng)驗(yàn)和自學(xué)習(xí)的信息引導(dǎo)螞蟻搜索子問題，并通過鄰居之間的合作優(yōu)化其子問題.

2.2 基于種群的多目標(biāo)蟻群優(yōu)化

Guntsch和Middendorf[15]提出了基于種群方法的蟻群優(yōu)化算法(PACO)，該方法增加了一個存放每一次迭代最優(yōu)解的K規(guī)模的種群，當(dāng)?shù)贙+1次迭代時，產(chǎn)生的最優(yōu)解將采用先進(jìn)先出的順序替換種群中的一個解，信息素矩陣中的信息素也做相應(yīng)的更新. 此信息素模型的更新策略適合解決動態(tài)優(yōu)化問題，而且其有限的狀態(tài)空間在設(shè)計新的啟發(fā)式方法具有較高的擴(kuò)展性.

Angus[16]用一種密集種群(crowding population)替換技術(shù)擴(kuò)展基于種群的蟻群優(yōu)化算法解決多目標(biāo)問題. 該算法通過選擇性替換技術(shù)維持解的多樣性，使解收斂在Pareto前沿面上. 盡管PACO顯示了能較好地處理多目標(biāo)組合優(yōu)化問題的性能，但是尚未應(yīng)用在多目標(biāo)函數(shù)優(yōu)化問題中. 隨后，Angus[17]測試了PACO算法解決多目標(biāo)函數(shù)優(yōu)化問題的適應(yīng)性. Kurniawan等[18]對于DNA序列優(yōu)化和DNA序列的計算問題也使用了PACO算法進(jìn)行優(yōu)化.

2.3 基于Pareto最優(yōu)的蟻群優(yōu)化

在求解多目標(biāo)優(yōu)化問題的Pareto解集時，需要注意2個關(guān)鍵性的問題：(1)種群的收斂性問題，即如何使種群在各輪搜索所得解盡快地向Pareto前沿方向逼近；(2)種群的多樣性問題，即如何使非支配解在Pareto前沿面上均勻分布. 針對這2個問題，人們提出了不同的算法.

基于Pareto解集蟻群優(yōu)化算法(P-ACO)最初由Doerner等[19]提出應(yīng)用在多目標(biāo)組合優(yōu)化問題，與經(jīng)典ACS算法不同的是，每個目標(biāo)的當(dāng)代全局信息素不僅更新了最優(yōu)解，同時更新了次優(yōu)解. 在螞蟻的整個搜索過程中將找到的非支配解存入一個外部Pareto解集中. 2008年，H?ckel等[20]利用動態(tài)規(guī)劃方法改進(jìn)多目標(biāo)最短路徑問題的解逼近Pareto前沿面. 2013年，Mora等[21]引進(jìn)了一個種群之間通信通過偵查蟻的島嶼模型，并且使用了一種適合搜索空間的鄰居拓?fù)浣Y(jié)構(gòu). 在很多實(shí)際的應(yīng)用中，很多學(xué)者也利用了基于Pareto解集蟻群優(yōu)化算法，如多目標(biāo)電網(wǎng)規(guī)劃(multi-objective power network planning)[22]、多目標(biāo)拆卸線平衡(Disassembly Line Balancing Problem,DLBP)[23]等. 所有的策略都盡可能地覆蓋Pareto前沿面，因此各個子群或者島嶼在其他子群的輔助下在有限的區(qū)域內(nèi)搜索解，以找到更多高質(zhì)量的解集.

3 多目標(biāo)蟻群算法的并行化

蟻群算法在執(zhí)行過程中，單只螞蟻在一次循環(huán)中與其他螞蟻的通信是通過信息素矩陣，能夠異步更新，并且每只螞蟻之間是相互獨(dú)立的. 因此，蟻群算法本身隱含著一定的并行性，其本質(zhì)上是一個分布式的方法. 隨著問題的復(fù)雜度逐漸提高，蟻群算法需要考慮計算時間和資源，串行方式已不能滿足. 因此，很多學(xué)者提出了一些蟻群算法的并行算法.

2011年，Mora等[24]提出了一個并行的多目標(biāo)蟻群優(yōu)化算法. 該算法在將螞蟻分配在各節(jié)點(diǎn)時采用粗粒度并行，提出了2個不同的分布方式：Space Specialized Colonies(SSC)和Objective Specialized Colonies(OSC). SSC由一組獨(dú)立的蟻群組成，各自在不同的區(qū)域搜索解，最后合并他們搜索到的最優(yōu)解組成最后一組Pareto解. OSC與SSC不同的是其各子群只優(yōu)化其對應(yīng)的目標(biāo)，最后將其合并成一組Pareto解. 此方法不僅提高了運(yùn)行時間，最重要的是能夠找到一組更好的非支配解和一個更好的Pareto分布.

對于并行蟻群算法中多個子群之間的拓?fù)浣Y(jié)構(gòu)一般分為4種：環(huán)形拓?fù)浣Y(jié)構(gòu)(Ring topology)、星形拓?fù)錂C(jī)構(gòu)(Star topology)、超立方拓?fù)浣Y(jié)構(gòu)(Hypercube topology)和全連接拓?fù)浣Y(jié)構(gòu)(Fully-connected).以8個子群為例，其拓?fù)浣Y(jié)構(gòu)見圖3[25-26]. 2007年，Ellabib等[25]在子群之間的交互采用了星形結(jié)構(gòu)、環(huán)形結(jié)構(gòu)和超立方體結(jié)構(gòu)，提出了一種新的基于加權(quán)的信息交互機(jī)制，在研究這些交互機(jī)制對搜索行為的影響時采用了基于團(tuán)隊共識方法. Twomey等[26]在2010年也進(jìn)行了大量的實(shí)驗(yàn)，他們在定向環(huán)、超立方體和全拓?fù)?種不同的拓?fù)浣Y(jié)構(gòu)上考慮了4種不同的通信策略：單向環(huán)形(Unidirectional ring)策略：在p個子群中，Ci只向C(i+1)mod p傳遞最優(yōu)解并只接收C(i-1)mod p的最優(yōu)解；超立方體(Hypercube)：在這個模型中每個子群只接收和傳遞與之有邊相連的子群的最優(yōu)解；替代最差解(Replace-worst)：子群Ci分析其他p-1個子群中的最優(yōu)解，并將其代替本子群的最差解；全連接(Fully-connected)：該模型與替代最差解模型類似，差別在于找出p-1個子群中的最優(yōu)解與本子群中的最優(yōu)解比較，取兩者中的最優(yōu)解. 同時Twomey還考慮了子群數(shù)量、螞蟻的移動時間和局部搜索對算法的影響. 2010年，Jovanovic等[27]通過解決最小點(diǎn)覆蓋問題，分析了并行執(zhí)行時各子群之間不同的拓?fù)浣Y(jié)構(gòu)或通信策略對解搜索的影響.

2008年，Xiong等[28]從蟻群算法并行化過程中粒度處理標(biāo)準(zhǔn)和信息素的交互策略角度出發(fā)，提出了一個新的并行蟻群優(yōu)化算法.該算法主要考慮了2個方面：一是如何將單個串行蟻群劃分成多個相互獨(dú)立的子群分配在多線程處理機(jī)中;二是在子群中如何管理和控制信息素的更新. 實(shí)驗(yàn)表明，對于解決大規(guī)模的TSP問題，PACO中節(jié)點(diǎn)的計算時間明顯減少，性能優(yōu)于串行蟻群算法.Yu等[29]提出了一個采用粗粒度并行、加權(quán)和變異操作的改進(jìn)蟻群優(yōu)化算法解決多車場路徑問題.

因此，在研究蟻群算法的并行化時，需要解決對蟻群算法的分解、分解之后各子群直接地交互，同時還得考慮并行化過程中粒度處理的標(biāo)準(zhǔn).

圖3 4種不同的子群拓?fù)浣Y(jié)構(gòu)

4 多目標(biāo)蟻群算法的發(fā)展展望

為了提高解決多目標(biāo)優(yōu)化問題的性能，很多學(xué)者對原有多目標(biāo)蟻群算法針對解決不同問題進(jìn)行了相應(yīng)的改進(jìn). 對算法的改進(jìn)一般都是針對2個問題：一是提高Pareto解的多樣性，二是使Pareto最優(yōu)解覆蓋最優(yōu)前沿面. 自Bilchev和Parmee[30]提出CACO解決單目標(biāo)問題，采用將遺傳算法與蟻群算法結(jié)合來提高算法的性能. 2008年，Lee等[31]在求解多目標(biāo)優(yōu)化問題時，也采用此方法，遺傳算法具有快速全局搜索能力，而蟻群算法具有較好的收斂速度，提高了解搜索的多樣性和解的收斂速度. 提出與其他算法的結(jié)合，實(shí)現(xiàn)2個算法的優(yōu)缺點(diǎn)互補(bǔ)的還有Thanushkodi和Deeba[32]，他們將粒子群優(yōu)化與蟻群優(yōu)化結(jié)合，對于多機(jī)處理任務(wù)調(diào)度問題同樣表現(xiàn)出優(yōu)良的性能. Liu和Chen[33]則提出了一個基于多蟻群的方法來提高Pareto解的多樣性.Chica等[34]引進(jìn)了一種新的機(jī)制避免陷入局部收斂，并且使用由Middendorf等[35]提出的在解的構(gòu)建過程中使用不同的狀態(tài)更新規(guī)則的多目標(biāo)蟻群方法引導(dǎo)每一代搜索多樣性更好的解.

目前多目標(biāo)蟻群算法的研究大部分集中在優(yōu)化2個目標(biāo)上，Bezerra等[36]提出了一個新的蟻群算法稱為GRACE用于解決多目標(biāo)最短路徑問題. 該算法利用了Raith和Ehrgott[37]提出的兩階段策略. 在第一階段的搜索過程中，引入了稱為Logos的搜索策略，Logos-2和Logos-3分別對應(yīng)于雙目標(biāo)和三目標(biāo)，這個階段的搜索減小了第二階段的搜索空間，從而加快了第二階段的收斂速度. 第二階段采用單蟻群，螞蟻將繼續(xù)在相同的Pareto前沿面處搜索，目的是為了使大量的螞蟻在相同的區(qū)域探索，提升第一階段的搜索. 2013年，Bezerra等[38]對GRACE又進(jìn)行了擴(kuò)展，引申出7個不同的變體，他們之間的區(qū)別體現(xiàn)在螞蟻提供的信息素在數(shù)值向量上不同.

多目標(biāo)蟻群優(yōu)化算法在解決眾多實(shí)際問題時表現(xiàn)出較好的性能，對于現(xiàn)存的諸多方法按不同的標(biāo)準(zhǔn)可將其分為多種不同類. 如螞蟻在當(dāng)前決策點(diǎn)如何選擇下一個節(jié)點(diǎn)，通常是依據(jù)信息素結(jié)構(gòu)和啟發(fā)式函數(shù)的定義[13]. 在處理多目標(biāo)優(yōu)化問題時，對于信息素結(jié)構(gòu)通常會考慮2種不同的策略：第1種策略考慮使用一個信息素結(jié)構(gòu)，螞蟻釋放信息素的量要集成多個目標(biāo)的期望；第2種策略考慮用多個信息素結(jié)構(gòu)，通常將蟻群分成多個子群對應(yīng)不同的目標(biāo)，每個子群擁有自己的信息素結(jié)構(gòu)[9-10，16-17，24].多目標(biāo)問題啟發(fā)式函數(shù)的定義也有2種：一是不同的目標(biāo)聚合成單一的啟發(fā)式函數(shù)[16]；二是不同的目標(biāo)有其各自對應(yīng)的啟發(fā)式函數(shù)[9-10，24]. 關(guān)于解的獎勵[39](Solutions to reward)，在更新信息素時，需要考慮更新哪些解邊上的信息素. 第1種是獎勵當(dāng)前迭代中最好的那個解[16]. 第2種是獎勵當(dāng)前的每一個非支配解[20]. 因此，可能會獎勵所有在Pareto最優(yōu)解集中的解，或者只獎勵當(dāng)前循環(huán)中最新加入的非支配解.

如前所述的基于分解的多目標(biāo)蟻群優(yōu)化則是將蟻群分成多個子群分配在各個目標(biāo)上，每個子群共同維持一個信息素矩陣，每只螞蟻都有其各自的啟發(fā)式信息矩陣；基于Pareto的蟻群優(yōu)化(P-ACO)使用了多個信息素矩陣和單一的啟發(fā)式信息矩陣；基于種群的多目標(biāo)蟻群優(yōu)化(PACO)則是使用了多個信息素矩陣和多個啟發(fā)式信息矩陣.

雖然多目標(biāo)蟻群優(yōu)化算法已被用來解決了生活中許多的多目標(biāo)優(yōu)化問題，但仍然存在一些缺陷. 單目標(biāo)的蟻群優(yōu)化算法在收斂分析方面有眾多的研究，但是對多目標(biāo)的收斂分析卻很少，特別對Pareto解域的收斂性分析. 另外，多目標(biāo)蟻群算法的實(shí)驗(yàn)分析通常是對二維的多目標(biāo)進(jìn)行，對于復(fù)雜的高維多目標(biāo)優(yōu)化問題的研究卻很少，然而實(shí)際生活中的多目標(biāo)問題通常是高維的.因此這些都將是多目標(biāo)蟻群優(yōu)化算法有待提高的地方，需要進(jìn)一步開展研究.

參考文獻(xiàn)：

[1] Dorigo M,Maniezzo V, Colorni A.Antsystem:Optimization by colony of cooperating agents[J].IEEE Transactions on Systems Man and Cybernetics Part B-Cybernetics, 1996, 26(1): 29-41.

[2] Dorigo M, Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation, 1997, 1 (1): 53-66.

[3] Angus D, Woodward C. Multiple objective ant colony optimization[J]. Swarm Intelligence, 2009, 3(1): 69-85.

[4] Yagmahan B, Yenisey M M. Ant colony optimization for multi-objective flowshop scheduling problem[J].Computers & Industrial Engineering, 2008, 54(3): 411-420.

[5] Yagmahan B, Yenisey M M. A multi-objective ant colony system algorithm for flow shop scheduling problem[J].Expert Systems with Applications, 2010, 37(2): 1361-1368.

[6] Ghoseiri K, Nadjari B. An ant colony optimization algorithm for the bi-objective shortest path problem[J].Applied Soft Computing, 2010, 10(4): 1237-1246.

[7] Sun X K, You X M, Liu S. Multi-objective ant colony optimization algorithm for shortest route problem[C]∥International conference on machine vision and human-machine interface (MVHI10).Kaifeng, China, 2010:769-798.

[8] Zhang Q F, Li H.MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6):712-731.

[9] Ke L J, Zhang Q F, Battiti R. MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and ant colony[J]. IEEE Transactions on Systems Man and Cybernetics Part A-Systems and Human, 2013(99): 1-15.

[10] Cheng J, Zhang G X, Li Z D, et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems[J].Soft Computing, 2012, 16 (4):597-614.

[12] Iredi S, Merkle D, Middendorf M. Bi-criterion optimization with multi colony ant algorithms[M]∥Evolutionary multi-criterion optimization.New York:Springer,2001,1993:359-372.

[13] García-Martínez C,Cordón O,Herrera F. A taxonomy and an empirical analysis of multiple objectiveant colony optimization algorithms for the bi-criteria TSP[J]. European Journal of Operational Research, 2007, 180(1): 116-148.

[14] Gao F, Zhou A, Zhang G X. An estimation of distribution algorithm based on decomposition for the multiobjective TSP[C]∥International conference on natural computation (ICNC12).Chongqing, China, 2012: 817-821.

[15] Guntsch M, Middendorf M.A population based approach for ACO[M]∥Applications of evolutionary computing.New York: Springer-Verlag,2002, 2279: 72-81.

[16] Angus D. Crowding population-based ant colony optimisation for the multi-objective travelling salesman problem[C]∥IEEE symposium on computational intelligence in multicriteria decision making(MCDM07).Honolulu, HI, 2007: 333-340.

[17] Angus D. Population-based ant colony optimisation for multi-objective function optimization[M]∥Progress in artificial life. New York:Springer-Verlag, 2007, 4828: 232-244.

[18] Kurniawan T B, Ibrahim Z, Khalid N K, et al. A population-based ant colony optimization approach for DNA sequence optimization[C]∥Asia international conference on modeling & simulation (AMS 09). Bali, Indonesia, 2009:246-251.

[19] Doerner K, Gutjahr W J, Hartl R F, et al. Pareto ant colony optimization: A metaheuristic approach to multiobjective portfolio selection[J].Annals of Operations Research, 2004, 131(1-4): 79-99.

[20] H?ckel S, Fischer M,Zechel D, et al.Amulti-objective ant colony approach for pareto-optimization using dynamic programming[C]∥Proceedings of the 10thannual conference on Genetic and evolutionary computation(GECCO08).Atlanta, GA, USA,2008: 33-40.

[21] Mora A M, García-Snchez P, Merelo J J, et al.Pareto-based multi-colony multi-objective ant colony optimization algorithms: An island model proposal[J].Soft Computing, 2013, 17(7):1175-1207.

[22] Yang F, Rong H, Cao J L, et al. Multi-objective power network planning based on improved pareto ant colony algorithm[C]∥Asia-pacific power and energy engineering conference(APPEEC09).Wuhan,China, 2009:1-4.

[23] 丁力平，譚建榮，馮毅雄，等. 基于Pareto 蟻群算法的拆卸線平衡多目標(biāo)優(yōu)化[J]. 計算機(jī)集成制造系統(tǒng),2009, 15(7):1406-1413,1429.

Ding L P, Tan J R, Feng Y X, et al. Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm[J].Computer Integrated Manufacturing Systems,2009, 15(7):1406-1413,1429.

[24] Mora A M, Merelo J J, Castillo P A, et al. A study of parallel approaches in MOACOs for solving the bicriteria TSP[M]∥Advances in computational intelligence.New York: Springer, 2011, 6692:316-324.

[25] Ellabib I, Calamai P, Basir O. Exchange strategies for multiple ant colony system[J].Information Sciences, 2007, 177(5): 1248-1264.

[26] Twomey C, Stützle T, Dorigo M, et al. An analysis of communication policies for homogeneous multi-colony ACO algorithms[J]. Information Sciences, 2010, 180 (12):2390-2404.

[27] Jovanovic R, Tuba M, Simian D. Comparison of different topologies for island-based multi-colony ant algorithms for the minimum weight vertex cover problem[J]. IEEE Transactions on Computers, 2010, 9(1):83-92.

[28] Xiong J, Liu C Y, Chen Z. A new parallel ant colony optimization algorithm based on message passing interface[C]∥Pacific-Asia workshop on computational intelligence and industrial application(PACIIA08).Wuhan, China,2008:178-182.

[29] Yu B, Yang Z Z, Xie J X. A parallel improved ant colony optimization for multi-depot vehicle routing problem[J]. Journal of the Operational Research Society, 2011, 62: 183-188.

[30] Bilchev G, Parmee I C. The ant colony metaphor for searching continuous design spaces[M]∥Evolutionary computing.New York: Springer, 1995, 993:25-39.

[31] Lee Z J, Su S F, Chuang C C, et al. Genetic algorithm with ant colony optimization (GA-ACO)for multiple sequence alignment[J]. Applied Soft Computing, 2008, 8(1):55-78.

[32] Thanushkodi K, Deeba K. Hybrid intelligent algorithm[improved particle swarm optimization (PSO) with ant colony optimization (ACO)] for multiprocessor job scheduling[J].Scientific Research and Essays,2012, 7(20): 1935-1953.

[33] Liu D H, Chen G P. A new method for multi-objective optimization problem based on multi-ant-colony algorithm[C]∥International conference on computer application and system modeling(ICCASM10).Taiyuan,China. 2010: V7605-V7609.

[34] Chica M, Cordón O, Damas S, et al. A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing problem[J].Memetic Computing, 2011, 3(1): 15-24.

[35] Middendorf M, Reischle F,Schemeck H. Multi colony ant algorithms[J]. Journal of Heuristics, 2002, 8(3): 305-320.

[36] Bezerra L C T, Goldbarg E F G, Buriol L S, et al. GRACE: A generational randomized ACO for the multi-objective shortest path problem[J].Lecture Notes in Computer Science, 2011, 6576: 535-549.

[37] Raith A, Ehrgott M. A comparison of solution strategies for the biobjective shortest path problem[J].Computers & Operations Research, 2009, 36(4): 1299-1331.

[38] Bezerra L C T, Goldbarg E F G, Goldbarg M C, et al. Analyzing the impact of MOACO components: An algorithmic studyon the multi-objective shortest path problem[J]. Expert Systems with Applications, 2013, 40(1): 345-355.

[39] Alaya I. Ant colony optimization for multi-objective optimization problems[C]∥IEEE international conference on tools with artificial intelligence (ICTAI10). Patras, Greece, 2010:450-457.