一種求解多目標旅行商問題的混合進化算法

王 娜, 劉 生, 王洪峰

(1. 沈陽師范大學(xué) 計算機與數(shù)學(xué)基礎(chǔ)教學(xué)部, 沈陽 110034;2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 沈陽 110819)

一種求解多目標旅行商問題的混合進化算法

王 娜1.2, 劉 生2, 王洪峰2

(1. 沈陽師范大學(xué) 計算機與數(shù)學(xué)基礎(chǔ)教學(xué)部, 沈陽 110034;2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 沈陽 110819)

許多科學(xué)與工程優(yōu)化問題往往需要轉(zhuǎn)化為多目標旅行商問題進行求解,由于目標函數(shù)之間的沖突性,使得這類問題不存在能夠優(yōu)化所有目標函數(shù)的唯一最優(yōu)解,而是存在一個Pareto最優(yōu)解集或者Pareto Front。為了獲得一個高質(zhì)量的Pareto最優(yōu)解集,提出了一種基于蟻群優(yōu)化和差分進化的混合多目標進化算法。在提出的算法中,一方面采納分解機制利用蟻群優(yōu)化算子實現(xiàn)對Pareto最優(yōu)解的開發(fā),另一方面采納擁擠度概念利用差分進化算子實現(xiàn)對Pareto Front的探索。通過對一組標準測試算例的仿真實驗,結(jié)果表明所提出的算法比現(xiàn)有的算法能夠獲得分布性和收斂性更優(yōu)的Pareto解集。

旅行商問題; 進化多目標優(yōu)化; 蟻群優(yōu)化; 差分進化

0 引 言

旅行商問題是運籌學(xué)領(lǐng)域中一類經(jīng)典的組合優(yōu)化問題,很多科學(xué)和工程問題往往可以轉(zhuǎn)化為這類問題進行求解。由于實際應(yīng)用問題中總是需要考慮多個優(yōu)化目標,使得越來越多的學(xué)者開始關(guān)注多目標旅行商問題的研究工作[1-3]。然而由于目標函數(shù)之間通常都是相互沖突的,使得這種多目標優(yōu)化問題中不存在一個能夠優(yōu)化所有目標函數(shù)的最優(yōu)解,而是存在一組多個目標函數(shù)之間平衡解,即Pareto最優(yōu)解[5]。

近年來,進化算法被廣泛用于求解各種多目標優(yōu)化問題[5-7]。作為一種基于種群機制的元啟發(fā)式方法,多目標進化算法的目標是通過一次運行就能夠獲得一組分布均勻的Pareto最優(yōu)解。這也就意味著在整個算法迭代過程中需要考慮兩種不同的搜索,一種可以認為是對更好的非支配解的開發(fā)性(exploitation)搜索,另一種可以認為是對更優(yōu)分布的非支配解集的探索性(exploration)搜索。值得注意的是,這2種搜索行為在目前的文獻中很少同時考慮。

于是,本文將2種不同的進化算法(即蟻群優(yōu)化ACO[8]和差分進化DE[9])思想結(jié)合起來,充分利用蟻群優(yōu)化算子在旅行商問題上的高效性和差分進化算子在保持種群多樣性上的有效性,設(shè)計一種混合多目標進化算法來求解多目標旅行商問題。

1 提出的算法

1.1 基本思想

在本文所提出的算法中,2種主要的策略被采用。一方面,采納分解的機制將一個多目標優(yōu)化問題構(gòu)造出若干個單目標子問題,在借鑒文獻[10]中算法思想的基礎(chǔ)上,通過利用蟻群優(yōu)化算子對主種群進行更新迭代,以獲得所構(gòu)造的這些單目標子問題的最優(yōu)解,即是原來多目標問題的Pareto最優(yōu)解。在算法具體實現(xiàn)過程中,根據(jù)一組均勻分布的權(quán)重向量(其數(shù)量是預(yù)先設(shè)定的),利用Tchebycheff函數(shù)將一個多目標TSP問題構(gòu)造出一系列單目標子問題。

另一方面,采納文獻[11]中多目標進化算法設(shè)計思想中擁擠度的概念,通過利用差分進化算子對外部種群(即所獲得的非支配解集)進行更新,以保證所獲得的非支配解集具有更好的分布性。這里需要說明的是由于差分進化算子是針對實數(shù)編碼個體的,這就需要將實編碼個體轉(zhuǎn)化為旅行商問題的解。在算法具體實現(xiàn)過程中,根據(jù)數(shù)值的大小,將原來的實數(shù)編碼個體轉(zhuǎn)換為順序編碼個體,以獲得旅行商問題的一個解。

1.2 算法流程

圖1給出了本文所提出算法流程的偽碼圖。在算法初始化階段,首先需要根據(jù)一組預(yù)先產(chǎn)生的權(quán)重向量,將原有的多目標問題構(gòu)造出相應(yīng)數(shù)量的單目標子問題;然后根據(jù)構(gòu)造的子問題初始化對應(yīng)的螞蟻個體,并利用權(quán)重向量的相似性將所有螞蟻個體分組;最后初始化外部種群。在算法迭代過程中,首先根據(jù)每個螞蟻對應(yīng)的啟發(fā)信息矩陣和每組螞蟻共享的信息素矩陣產(chǎn)生新解,然后根據(jù)產(chǎn)生的新解更新外部種群,對外部種群執(zhí)行差分進化運算,最后根據(jù)蟻群優(yōu)化和差分進化算子的運行效果更新每組螞蟻共享的信息素矩陣。

Proceduretheproposedalgorithm:BeginGenerateanumberofsingle-objectivesubproblemsbasedonasetofNweightvectors;InitializeapopulationofNantsforeachgeneratedsubproblem;DivideNantsintoKgroupsbasedonthesimilaritiesoftheircorrespondingweightvectors;Initializeanexternalpopulation;Repeat GenerateNsolutionsviaexecutingACOoperationsonNantsinthemainpopulation; Updatetheexternalpopulationviathenewgeneratedsolutions; ExecuteDEoperationsontheexternalpopulation; Updatethepheromonematrixforeachgroupofants;Untilaterminationconditionismet.End

圖1本文所提出算法流程的偽碼
Fig.1 Pseudo-code for the proposed algorithm in this paper

1.3 實現(xiàn)步驟

Step1 初始化,構(gòu)造一組子問題(i=1,…,N);隨機產(chǎn)生一組螞蟻,螞蟻i對應(yīng)子問題i,初始化每個螞蟻對應(yīng)的啟發(fā)信息矩陣ηi;根據(jù)螞蟻對應(yīng)權(quán)重向量的相似性,將螞蟻分成K組,初始化每個小組j(j=1,…,K)的信息素矩陣τj;初始化外部種群。

Step2 構(gòu)造解,對于每個螞蟻(i=1,…,N),用概率函數(shù)(表示為xi,ηi,τj的函數(shù))求出解yi,計算其目標函數(shù)向量。對于每個螞蟻i,更新當前最好解xi。y是在所有鄰近螞蟻找到的解中使得g(.|λi)的值最小的解。如果y沒被用于更新其他舊解,且g(y|λi)

Step3 更新外部種群,對于每個yi,如果外部種群中沒有解支配yi,把yi添加到外部種群,移除其中所有被yi所支配的解。

Step4 差分進化運算:對外部種群進行N′次差分進化,利用每次產(chǎn)生新解xp更新外部種群,計算擁擠距離,擁擠距離大的被添加進外部種群,擁擠距離小的被刪除,限定外部種群大小。

Step5 更新對應(yīng)小組信息素:對于每個小組j,更新信息素矩陣τj,小組j中的螞蟻在Step 2中獲得的解,且在Step 3中被添加到外部種群,則該螞蟻的解用來更新信息素;如果產(chǎn)生的新解xp,對每個小組j,找出使得g(xp|λj)值最小的小組q,用xp更新小組q的信息素。

Step6 停止準則:如果滿足問題的停止準則,停止運算。

2 實驗結(jié)果與分析

為了驗證本文所提出的算法(后文稱之為ACO-DE)在求解多目標旅行商問題時的性能,選擇了文獻中4種具有代表性的多目標進化算法作為比較算法,其中:MODE屬于早期的多目標差分進化算法[12],MOSADE是一種采用自適應(yīng)策略的多目標差分進化算法[13],NSGA-II[11]和MOEA/D[14]是2種最為經(jīng)典的多目標進化算法,上述算法均可以被用于求解本文所研究的多目標旅行商問題。

2.1 實驗設(shè)置

本文實驗中所采用的測試函數(shù)均是根據(jù)TSPLIB中benchmark問題構(gòu)造的,選擇了5個100個城市的旅行商benchmark問題,即KroA100、KroB100、KroC100、KroD100、KroE100。通過兩兩組合的方式構(gòu)造出多目標旅行商問題,例如KroAB100是由KroA100和KroB100這2個benchmark問題組合而成,其他的以此類推。

本文所提出的ACO-DE算法參數(shù)設(shè)置如下:螞蟻總數(shù)N=24,小組總數(shù)K=3,鄰近螞蟻數(shù)量T=10,信息素揮發(fā)系數(shù)ρ=0.95,信息啟發(fā)式因子α=1,期望啟發(fā)因子β=2,r=0.9(隨機數(shù)大于r,用輪盤賭方式選擇下一個城市),ε=1/2n(信息素最小值與信息素最大值的比),Δ=0.05×τmax(反應(yīng)當前最優(yōu)值在狀態(tài)轉(zhuǎn)移概率中的作用),變異算子范圍是0.1～0.9,交叉算子范圍是0.1～1.0。所有對比算法的相關(guān)參數(shù)均采用其初始設(shè)置方法。所有算法均利用Win7系統(tǒng)下Eclipse環(huán)境下實現(xiàn),算法測試的硬件環(huán)境為3.30GHz的因特爾處理器、4GB內(nèi)存的HP臺式機。

為了更好的檢驗各種算法在多目標旅行商問題上的性能,選取文獻[15]中2個常用的多目標算法性能指標作為算法對比的評價指標。

1) IGD指標(Inverted generational distance):該指標通過從真實Pareto最優(yōu)解集到算法獲得的非支配解集的平均距離來評估該算法的性能。假定p*是理想Pareto front上的一組均勻采樣,是由算法獲得的一組非支配解集,則IGD指標定義如下:

其中:d(v,P)為v與解集P中與之距離最近點之間的Euclidean距離;|p*|為p*中Pareto最優(yōu)解的個數(shù)。

2) Hypervolume指標:該指標利用算法獲得的非支配解集中所有點與參考點在目標空間所圍成的超立方體體積來評估算法的性能。若P={p1,p2,…,pN}為算法獲得的一組非支配解,r為參考點,滿足pir,?i=1,2,…,N,則Hypervolume指標定義如下:

其中:N為非支配解的個數(shù);Leb(S)為解集S的勒貝格測度;vi為第i個非支配解和參考點圍成的超立方體體積。

2.2 實驗結(jié)果分析

為了公平合理地比較本文所提出的算法與比較算法的性能,所有算法均以3 000次估值作為停止條件,每種算法分別對每一算例求解30次,取30次運行結(jié)果的平均值作為其性能指標。

表1給出了所有算法在IGD指標方面的實驗結(jié)果,從中可以看出,本文所提出的ACO-DE算法的性能遠遠優(yōu)于其他4種對比算法的性能。例如,在KroAB100算例中,ACO-DE算法的IGD性能指標的均值為4 220,遠遠小于其他4種對比算法的平均性能,分別為18 254、35 198、55 395和8 772。

表1 5種算法在不同算例上IGD指標的實驗結(jié)果Tab.1 Experimental results of five algorithms in test instances with IGD index

表2給出了所有算法在Hypervolume指標方面的實驗結(jié)果,從表中能夠發(fā)現(xiàn)本文所提出的ACO-DE算法在所有算例上Hypervolume指標的均值都是1.0,這也就意味著ACO-DE算法總是能夠比其他4種對比算法獲得收斂性和分布性更好的非支配解集。

表2 5種算法在不同算例上Hypervolume指標的實驗結(jié)果Tab.2 Experimental results of five algorithms in test instances with Hypervolume index

3 結(jié) 論

為了有效求解多目標旅行商問題,本文提出了一種基于蟻群優(yōu)化和差分進化的混合多目標進化算法。在這種算法中,一方面采納分解的機制利用蟻群優(yōu)化算子搜索一組非支配解,另一方面采用擁擠度的思想利用差分進化算子對所獲得非支配解進行充分開發(fā),以保證獲得更好的分布性,通過利用一組標準測試函數(shù)進行仿真實驗,實驗結(jié)果表明本文所提出的算法比文獻中現(xiàn)有算法具有更好的性能。

[ 1 ]肖曉偉,肖迪,林錦國,等. 多目標優(yōu)化問題的研究概述[J]. 計算機應(yīng)用研究, 2011,28(3):805-809.

[ 2 ]CHENG Jixang,ZHANG Gexiang,LI Zhidan,et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems[J]. Soft Computing, 2012,16(4):597-614.

[ 4 ]張瑞芳,王海軍. 廣義凸條件下一類多目標優(yōu)化問題的對偶[J]. 沈陽師范大學(xué)學(xué)報(自然科學(xué)版), 2014,32(4):482-485.

[ 5 ]ANGUS D,WOODWARD C. Multiple objective ant colony optimization [J]. Swarm intelligence, 2009,3(1):69-85.

[ 6 ]WANG Hongfeng,FU Yaping,HUANG Min,et al. Multiobjective optimization design for enterprise system operation in the case of schedulingproblem with deteriorating jobs[J]. Enterprise Information Systems, 2016,10(3):268-285.

[ 7 ]ZHOU Aimin,QU Boyang,LI Hui,et al. Multiobjective evolutionary algorithms: a survey of the state of the art[J]. Swarm Evolutionary Computation, 2011,1:32-49.

[ 8 ]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.

[ 9 ]STORN R,PRICE K.Different evolution-A simple and efficient adaptive scheme for global optimization over continuous spaces[R]. International Computer Science Institute, Berkley, 1995.

[10]KE Liangjun,ZHANG Qqingfu,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.

[11]DEB K,PRATAP A,AGARWALl S,et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002,6(2):182-197.

[12]BABU B,CHAKOLEP G,MUBEENJH S. Multiobjective differential evolution (MODE) for optimization ofadiabatic styrene reactor[J]. Chemical Engineering Science, 2005,60(17):4822-4837.

[13]WANG Yaonan,WU Lianghong,YUAN Xiaofang. Multi-objective self-adaptive differential evolution with elitist archive and crowding entropy-based diversity measure[J]. Soft Computing, 2009,14 (3):193-209.

[14]ZHANG Qingfu,LI Hui. MOEA D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007,11(6):712-731.

[15]HUBAND S,HINGSTON P,BARONE L,et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006,10(5):477-506.

Ahybridevolutionaryalgorithmformultiobjectivetravellingsalesmanproblem

WANGNa1.2,LIUSheng2,WANGHongfeng2

(1. Department of Computer and Mathematical Teaching, Shenyang Normal University, Shenyang 110034, China; 2.Information Science and Engineering College, Northeastern University, Shenyang 110819, China)

Many scientific and engineering problems can always transfer to multiobjective travelling salesman problems (TSPs), where there is only a set of Pareto optimal solution or Pareto front, rather than one single optimal solution that can optimize all objective functions simultaneously, due to the existence of multiple conflicting objectives. In this paper, a hybrid multiobjective evolutionary algorithm, which hybridizes the mechanism of ant colony optimization (ACO) and differential evolution (DE), is proposed for solving multiobjective TSP. Two different strategies are employed in the proposed algorithm, that is, ACO operators are used to make an exploration for a set of Pareto optimal solutions based on a decomposition mechanism and DE operators are used to makean exploitation to obtain a better Pareto front. Based on the experiments on a series of test instances, the proposed algorithmshows a Pareto solution set with better distribution and convergence than those from several state-of-the-art algorithms.

traveling salesman problem; evolutionary multiobjective optimization; ant colony optimization; differential evolution

2017-06-19。

國家自然科學(xué)基金資助項目(71671032)。

王 娜(1979-),女,遼寧盤錦人,沈陽師范大學(xué)講師,東北大學(xué)博士研究生。

1673-5862(2017)04-0425-05

O229

A

10.3969/ j.issn.1673-5862.2017.04.009