王 娜, 劉 生, 王洪峰

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

一種求解多目標(biāo)旅行商問題的混合進(jìn)化算法

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

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

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

旅行商問題; 進(jìn)化多目標(biāo)優(yōu)化; 蟻群優(yōu)化; 差分進(jìn)化

0 引 言

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

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

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

1 提出的算法

1.1 基本思想

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

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

1.2 算法流程

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

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 實(shí)現(xiàn)步驟

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

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

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

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

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

Step6 停止準(zhǔn)則:如果滿足問題的停止準(zhǔn)則,停止運(yùn)算。

2 實(shí)驗(yàn)結(jié)果與分析

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

2.1 實(shí)驗(yàn)設(shè)置

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

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

為了更好的檢驗(yàn)各種算法在多目標(biāo)旅行商問題上的性能,選取文獻(xiàn)[15]中2個(gè)常用的多目標(biāo)算法性能指標(biāo)作為算法對(duì)比的評(píng)價(jià)指標(biāo)。

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

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

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

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

2.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

3 結(jié) 論

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

[ 1 ]肖曉偉,肖迪,林錦國,等. 多目標(biāo)優(yōu)化問題的研究概述[J]. 計(jì)算機(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 ]張瑞芳,王海軍. 廣義凸條件下一類多目標(biāo)優(yōu)化問題的對(duì)偶[J]. 沈陽師范大學(xué)學(xué)報(bào)(自然科學(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é)基金資助項(xiàng)目(71671032)。

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

1673-5862(2017)04-0425-05

O229

A

10.3969/ j.issn.1673-5862.2017.04.009