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

王 娜, 劉 生, 王洪峰

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

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

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

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

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

旅行商問題; 進化多目標優化; 蟻群優化; 差分進化

0 引 言

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

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

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

1 提出的算法

1.1 基本思想

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

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

1.2 算法流程

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

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 實現步驟

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

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

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

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

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

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

2 實驗結果與分析

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

2.1 實驗設置

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

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

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

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

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

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

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

2.2 實驗結果分析

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

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

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

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

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

3 結 論

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

[ 1 ]肖曉偉,肖迪,林錦國,等. 多目標優化問題的研究概述[J]. 計算機應用研究, 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 ]張瑞芳,王海軍. 廣義凸條件下一類多目標優化問題的對偶[J]. 沈陽師范大學學報(自然科學版), 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。

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

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

1673-5862(2017)04-0425-05

O229

A

10.3969/ j.issn.1673-5862.2017.04.009