一種改進的基于密度的多目標進化算法

王　鵬,張長勝,張　斌,劉婷婷

(東北大學信息科學與工程學院，遼寧沈陽 110819)

?

一種改進的基于密度的多目標進化算法

王鵬,張長勝,張斌,劉婷婷

(東北大學信息科學與工程學院，遼寧沈陽 110819)

多目標密度驅(qū)動進化算法(MODdEA)利用非支配等級信息和分區(qū)密度信息求解多目標優(yōu)化問題，該算法在與其他多目標進化算法的比較中有著出色的表現(xiàn).在其基礎(chǔ)上本文提出了一種改進的多目標進化算法MODdEA+，首先在該算法中基于搜索空間的分區(qū)機制提出了克隆操作，該操作不但能在進化前期增強算法的全局搜索能力，還能在進化后期提高算法的局部精化能力；其次引入一種基于Pareto信息表中個體支配及被支配信息的評價策略以使對信息表個體的排序結(jié)果更加精確；最后對變異操作進行了改進以降低出現(xiàn)不必要越界情況的概率.為驗證改進算法的有效性，在對其進行分析的基礎(chǔ)上針對多個測試問題將其與原算法進行了實驗比較，結(jié)果表明改進算法的求解質(zhì)量明顯優(yōu)于原算法.

進化算法;密度驅(qū)動;克隆操作;粗適應度值;變異操作

1　引言

最優(yōu)化問題是工業(yè)生產(chǎn)和科學研究中主要的問題形式之一，當多個目標函數(shù)需要同時處理時，最優(yōu)化問題稱為多目標優(yōu)化問題(MOPs).對于多目標優(yōu)化問題，通常一個解對于某個目標來說可能較好，而對于其他目標來講可能是較差的，因此多目標優(yōu)化問題通常求解一個折中解的集合，該集合稱為Pareto最優(yōu)解集.

多目標進化算法(MOEA)在每一代進化過程中精煉種群的最優(yōu)解來實現(xiàn)全局搜索，該類算法可以有效的完成對多目標優(yōu)化問題的Pareto最優(yōu)解集的搜索.自從1985年第1種多目標進化算法提出以來，MOEA已發(fā)展成為求解MOPs的主流方法之一；同時，MOEA也已成為進化算法領(lǐng)域最熱門的研究方向之一.以NSGA-II[1]，SPEA2[2]，PAES[3]，IBEA[4,5]，MOEA/D[6]等為代表的MOEA算法在眾多應用領(lǐng)域獲得了廣泛的應用.

多目標密度驅(qū)動進化算法[7](MODdEA)克服了鄰域假設(shè)，并可以有效的處理不連通問題(TYD-MOP).該算法將所有已生成過的解都存儲在BSP樹上，根據(jù)該樹存儲的對搜索空間的分區(qū)信息，經(jīng)過計算可以得到搜索空間任一點的解密度信息；算法綜合利用該密度信息配合解的非支配信息選擇交叉?zhèn)€體，然后利用多樣性變異算子和擴展算術(shù)交叉算子生成新的個體.實驗證明相比于已有的MOEA，MODdEA不僅在處理不連通問題時有著出眾的表現(xiàn)，同時在處理連通問題時也達到了高水準.

目前該算法主要在以下三個方面有待提高：

(1)算法在進化后期的局部精化能力有待改進.算法MODdEA的個體選擇操作、變異操作、交叉操作都從不同角度加強了算法在進化期間的全局多樣化能力，全局多樣化的能力對于進化算法在進化過程中的全局搜索有著至關(guān)重要的意義.但是由于搜索資源的有限性，在進化過程的后期強調(diào)全局多樣化的能力，將削弱算法的局部精化能力，局部精化能力的不足將直接影響算法求得解的精確度.因此有必要提高算法后期的局部精化能力.

(2)非支配排序算法考慮的信息不夠全面.算法MODdEA采用的非支配排序算法的核心思想計算每個解p支配的解數(shù)np，及一個該解支配的解的集合Sp，遞歸的通過操作所有解的這兩個變量計算出所有解的非支配等級.這種算法可以高效的求解出一個解集合所有解的非支配等級，但是在排序過程中該算法只考慮該解支配解的情況，并沒有考慮有多少解支配該解.這種排序產(chǎn)生的結(jié)果并不能全面的反映解與解之間的支配與被支配的關(guān)系.

(3)變異操作可能出現(xiàn)不必要的越界.MODdEA中的變異操作DM在選定變異維度pd后，生成步長的規(guī)則如下：生成一個隨機準步長，從準步長、上界-原值、原值-下界中選擇一個最小值，作為步長；隨后從值與步長之間生成一個高斯隨機數(shù)作為變異維度上的最終值.這種設(shè)置可以使變異操作在全局搜索與局部精化間相互切換，保持算法在整個進化過程中的全局搜索能力.但是由于一旦生成的準步長過大，即使選擇上下界作為步長也很容易出現(xiàn)越界的情況.

針對上述不足，本文進行三處改進，從而提出改進算法MODdEA+：

(1)提出了一種克隆操作，并將其結(jié)合到該算法中.由于該操作以BSP樹存儲系統(tǒng)的分區(qū)機制為基礎(chǔ)，所以能夠在進化前期增強算法的全局搜索能力，在進化后期增強算法的局部精化能力，從而提高算法的求解精度.

(2)針對非支配排序算法考慮的信息不夠全面問題，本文根據(jù)個體的粗適應度值(raw fitness)對進行排序.在計算每個個體的粗適應度值的過程中充分考慮了該個體支配與被支配的信息.因此這種方法所產(chǎn)生的排序結(jié)果可以全面的反映解與解之間的支配關(guān)系.

(3)針對變異操作可能出現(xiàn)不必要的越界，對變異操作進行改進，提出了一種新的越界處理策略.一旦隨機生成的準步長越界，不再將上下界與原值的差作為備選步長，而是將越界的步長減去上下界與原值的差，使越界的后的替換步長減小，降低變異操作越界的概率.

2　問題描述

不失一般性，一個具有n個決策變量m個目標函數(shù)的多目標優(yōu)化問題(MOP)可以定義為：

minF(x)=[f1(x),…,fm(x)]T,forallx∈S?Rn

其中,S是n維決定空間(decisionspace)；F：S → Ω屬于Rm包含m個目標函數(shù)(objectiveproblems)；Ω是m維目標空間(objectivespace).MOP的目標函數(shù)之間通常相互沖突，這種情況下往往不存在一個最優(yōu)解滿足所有的目標函數(shù).因此，MOP的最優(yōu)解并不是一個解，而是一個解集，相關(guān)定義如下.

定義lPareto強支配：設(shè)u，v∈Ω，對于一個最小化問題，當且僅當ui

定義2Pareto最優(yōu)解：對于上述多目標優(yōu)化問題的解集P，對解集中的一點x0∈P，如果x0不被P中的其他點x∈P所強支配的話，則稱x0為P的Pareto最優(yōu)解(Paretooptimalsolution).

定義3Pareto最優(yōu)解集：所有Pareto最優(yōu)解的集合稱為解集P的Pareto最優(yōu)解集(Paretoset，PS).

定義4Pareto最優(yōu)向量：解集P的Pareto最優(yōu)解集在目標空間的映射稱為解集P的Pareto最優(yōu)向量(Paretooptimalvector).

定義5Pareto最優(yōu)前沿：所有Pareto最優(yōu)向量的集合稱為解集P的Pareto最優(yōu)前沿(Paretofront，PF).

3　相關(guān)工作

MOEA的目標是找到一個對應的解向量集接近、密集并且均勻的分布于實際Pareto最優(yōu)前沿的逼近前沿.這就要求MOEA在進化過程中既需要不斷的精化已存在的優(yōu)秀解，同時還必須在搜索空間中搜索新的解.受限于進化次數(shù)，好的MOEA應該在精化已有解與搜索新解這兩項工作之間得到理想的平衡.為了實現(xiàn)這一平衡，大多數(shù)MOEA都在個體選擇的過程中兼顧局部收斂及全局多樣化.

根據(jù)MOEA采用的基本思想的不同，大致可以分為以下四類：基于Pareto占優(yōu)關(guān)系的MOEA；基于評估指標的MOEA；基于分解技術(shù)的MOEA和基于運行過程中歷史信息的MOEA算法.

4　改進的MODdEA

針對算法MODdEA的三處不足，本節(jié)提出的三處改進，并提出改進算法.本小節(jié)將詳述這三處改進與算法MODdEA+的算法描述.

4.1變異克隆算子

算法MODdEA所提到的多樣變異算子和擴展的算術(shù)交叉算子，在進化過程中都在全局搜索與局部精化之間隨機變動.但是在整個的進化的過程中，尤其是進化后期，局部精化比全局搜索更能提高求解精度.本文在使用原有交叉變異操作的基礎(chǔ)上，提出一種新的操作稱為克隆操作.

該操作以BSP樹結(jié)構(gòu)存儲的搜索空間分區(qū)信息為基礎(chǔ)，每輪進化在種群的優(yōu)秀個體的子區(qū)域內(nèi)隨機生成一個新的個體.由于搜索空間整體的超體積不變，BSP樹結(jié)構(gòu)的分區(qū)數(shù)量隨著進化的進行逐漸增加，因此分區(qū)的平均超體積在進化過程中由大到小遞減.進化前期，在較大的區(qū)域進行克隆操作可以增強算法的全局搜索能力；進化后期，在較小的區(qū)域進行克隆操作可以提高搜索的局部精化能力.

具體操作如下：對每一個本代優(yōu)秀個體m=population size，pi屬于P={p1,p2,…,pm}，在交叉變異生成新一代的同時.在BSP樹存儲系統(tǒng)搜索pi的區(qū)域，并在該區(qū)域內(nèi)隨機生成一個pi的克隆解ci，得到P的克隆解集C={c1,c2,…,cn}，并將插入BSP樹存儲系統(tǒng).將C與N一同加入到PIL中，更新PIL.

具體的變異克隆算子算法描述如算法1.

其中函數(shù)Random(a，b)是在實數(shù)a、b之間生成一個隨機數(shù).實際上，克隆算子所做的對上一代所選出的種群進行操作：對每一個種群中的個體，從BSP樹系統(tǒng)中搜索該個體所在的子區(qū)域，并在該區(qū)域內(nèi)隨機生成一個新的個體，并將該個體插入到BSP樹系統(tǒng).由于在進化過程中，BSP樹系統(tǒng)中的子區(qū)域由少到多，整個的區(qū)域的超體積是不變化的，易見在進化過程中子區(qū)域的超體積是一個由小到大的過程，克隆操作所做的操作針對本代種群所做的操作在進化前期由于子區(qū)域的超體積相對較大，使用克隆算子可以增強算法的全局搜索能力；而在進化后期，由于子區(qū)域已經(jīng)變小，對優(yōu)秀解進行克隆操作可以精煉這些優(yōu)秀解，增加算法的局部精化能力.

4.2PIL的支配關(guān)系排序方法

PIL表結(jié)構(gòu)是算法MODdEA+維護的一個外部集合，該表保存進化過程中產(chǎn)生的優(yōu)秀個體，避免個體選擇的隨機性丟失這些個體.在進化過程中每當有新的個體產(chǎn)生時，算法MODdEA+都要都要將這些個體并入PIL中然后與PIL中原有的個體重新根據(jù)支配關(guān)系排序.上文提到算法MODdEA采用的非支配排序方法考慮的信息不夠全面，下面將介紹算法MODdEA+采用的支配關(guān)系排序方法.

排序方法如下：

(1)計算所有解支配的個體數(shù)，即力度(strength)值，公式如下:

其中，?表示支配關(guān)系；

(2)根據(jù)力度值，計算所有解的粗適應度值，如下:

(3)按raw fitness(i)從小到大對所有個體排序，值相同的為一級.

易見，與算法MODdEA采用的非支配排序算法不同，算法MODdEA+根據(jù)個體的粗適應度值進行的排序.個體的粗適應度值不僅考慮了個體支配個體的數(shù)量信息，同時也考慮了支配該個體的個體的數(shù)量信息，全面的考慮這兩種信息可以更全面的產(chǎn)生排序結(jié)果.根據(jù)粗適應度值排序產(chǎn)生的排序結(jié)果可以更全面的反映個體間支配的優(yōu)先關(guān)系.

4.3改進的多樣變異算子

針對變異操作可能出現(xiàn)不必要的越界問題，本小節(jié)對變異操作如下改進：一旦隨機生成的準步長越界，不再將上下界與原值的差作為備選步長，而是將越界的步長減去上下界與原值的差，使越界的步長減小.

處理過程如下：

(1)首先給定父代p=[p1,p2,…,pn]；將子代o初始化為p，即o=p.

(2)從{1,2,…,n}中隨機生成一個變異維度d；

(3)從[0,Ud-Ld]隨機生成步長標準差r，當r>max(pd-Ld,Ud-pd)時，r=r-max(pd-Ld,Ud-pd).

(4)最后在pd與r之間生成一個高斯隨機數(shù)，將子代d維度替換為該隨機數(shù)，完成多樣變異.

改進后的多樣化變異算法如算法2.

其中函數(shù)GaussianRandom(a，b)是在實數(shù)a、b之間生成一個高斯隨機數(shù).盡管只是在步長越界的替換策略做了改進，但是這種處理方式首先保證了變異操作在進化過程中仍然可以在全局搜索與局部精化隨機切換；其次，易見算法只會在準步長越界之后出現(xiàn)步長越界情況，降低準步長越界后替換準步長的上界可以有效的降低步長越界的概率，減少不必要的資源浪費.

4.4主循環(huán)

算法MODdEA+主要由進化算法模塊和存儲器模塊兩部分組成.

進化算法模塊包括：多樣化變異操作(DM)、擴展的算術(shù)交叉操作(EAX)、克隆操作(Clone)和個體選擇操作(SDPD).

(1)經(jīng)典的變異算子的步長由大到小，使算法在進化過程中從前期的擴張到后期的收斂；DM在一定范圍內(nèi)隨機生成步長，使在算法進化過程中在擴張與收斂之間隨機切換，算法在進化后期收斂的同時兼顧擴張.

(2)經(jīng)典的交叉算子的交叉權(quán)重從0到1取值，使子代相較于父代越來越收斂，影響了算法后期的收斂能力；EAX的交叉權(quán)重從-1到2取值，使算法在進化過程中都可以在擴張和收斂之間相互切換.

(3)經(jīng)典的個體選擇操作僅在目標空間根據(jù)當前代的解信息估計解密度，并且一旦Pareto最優(yōu)解集超過種群容量就將舍棄一部分，浪費這部分搜索到的優(yōu)秀解；SDPD根據(jù)所有以生成解得信息在搜索空間估計解密度，并且將超過種群容量的解存儲在PIL中，供下一代繼續(xù)使用.

(4)DC的作用是在進化過程的前期增強擴張，后期針對已選出的優(yōu)秀解，加強收斂能力.

存儲器模塊包括：BSP樹結(jié)構(gòu)和PIL表結(jié)構(gòu).BSP樹結(jié)構(gòu)存儲著進化過程中已生成的所有解的空間分割信息，根據(jù)空間分割信息中可以求得決定空間任意一點的解密度.PIL表結(jié)構(gòu)存儲著進化過程中已經(jīng)生成的優(yōu)秀解，并按非支配等級排序，該結(jié)構(gòu)可以保證生成的優(yōu)秀解不會因為選擇配對池(mating pool)的隨機性而丟失.

本算法的處理過程如下：

(1)進行一系列的初始化工作：首先，隨機生成一個種群P；然后，將BSP樹初始化為一棵只含根節(jié)點的樹；最后，將PIL初始化為一個空表；(2)算法調(diào)用用交叉變異算子生成子代；(3)算法調(diào)用用克隆算子生成克隆代；(4)將子代和克隆代存入BSP樹，并且更新PIL；(5)算法調(diào)用ISDPD從PIL中選取個解；(6)重復2、3、4和5直至迭代次數(shù)足夠.

其中函數(shù)BSPTreeNodeInsert(xi,T)是將個體xi插入到BSP樹T中，并為該個體劃分出新區(qū)域；函數(shù)ExtendedArithmeticCrossover(S,{a,b})是在搜索空間S中，對個體a，b進行算術(shù)擴展交叉操作；函數(shù)PILUpdate(Ψ∪N∪C)是將集合Ψ∪N∪C加入到PIL表中，并對表進行更新和如果成員個數(shù)超過規(guī)定容量則調(diào)用表的截斷操作；函數(shù)SDPD(Ψ,T,μ)的功能是根據(jù)BSP樹T中的信息從種群Ψ中選出μ個個體.與本文沒有詳述的部分與算法MODdEA一致，詳細內(nèi)容參考文獻[7].

4.5復雜度分析

計算算法MODdEA+每一輪迭代的復雜度需要考慮以下基本操作：

(1)將產(chǎn)生的u個后代個體插入BSP樹系統(tǒng)；(2)根據(jù)產(chǎn)生的u個后代個體更新PIL表系統(tǒng)；(3)在運行SDPD過程中搜索PIL表中的子區(qū)域；(4)SDPD的概率選擇模式；(5) 運行克隆算子過程中搜索上一代種群的子區(qū)域；

設(shè)已經(jīng)產(chǎn)生的解的數(shù)量為ne，種群容量為u，PIL表長為np，目標數(shù)為M.基本操作1的算法復雜度為O(ulog(ne)).

在基本操作1，對所有個體的粗適應度值排序，u個個體的目標向量的為得到非支配等級所做的比較是u2M.在基本操作2中，u個解每個解都要與PIL表中的解進行一次比較，額外需要npu2M.基本操作2的時間復雜度O(u(u+np)M).

因為后代個體的子區(qū)域在基本操作1中已經(jīng)獲得，所以基本操作3與基本操作5不需要額外的操作.

基本操作4的平均時間復雜度為O(ulog(np)).一種合理的估計是設(shè)np≈10u.因此，基本操作2和基本操作4的時間復雜度分別是O(11u2M) 和O((ulog(10u)).因此算法MODdEA+的時間復雜度為O(ulog(ne)+u2M).

5　仿真實驗

由于算法MODdEA與已有的大部分進化算法已經(jīng)進行了實驗比較分析，結(jié)果表明在絕大部分測試問題上算法MODdEA明顯優(yōu)于其他相比較的算法[7].因此，本文在實驗部分只將提出的算法與算法MODdEA進行比較分析.為了評價算法的有效性，本文采用IGD[10]作為評估指標.IGD(PA,P′)可以計算所得解集PA與最優(yōu)解集P′之間的距離，從而反映兩種算法的求解效果.

測試的兩種算法均為少參數(shù)算法，可設(shè)置的參數(shù)只有種群規(guī)模(population size)，在測試中兩個算法的種群規(guī)模與文獻[7]相同均設(shè)置為10.

5.1測試問題

在實驗過程中，本文采用3類問題作將提出的算法與算法MODdEA進行比較實驗：文獻[1]中提出的TDY1-TDY6；文獻[8]中提出的ZDT1-ZDT4，ZDT6；文獻[9]中提出的UcP1-UcP10.從中選取有代表性的10個問題作為本文的測試問題：TYD01，TYD02，TYD05，ZDT1，ZDT2，ZDT6，CEC02，CEC03，CEC04，CEC05.

為與算法MODdEA保持一致,本文的關(guān)于問題的參數(shù)設(shè)置與終止條件與文獻[7]相同.TYD01，TYD02，TYD05問題的維度為30,適應度進化次數(shù)設(shè)定為30000.ZDT1，ZDT2問題的維度為30，ZDT6問題的維度為10，適應度進化次數(shù)都設(shè)定為30000.每一個問題都獨立運行100次，統(tǒng)計其運行結(jié)果.CEC02，CEC03，CEC04，CEC05問題的維度為30，適應度進化次數(shù)設(shè)定為300000.每一個問題都獨立運行30次，統(tǒng)計其運行結(jié)果.

5.2IGD值比較

將兩個算法算法在3類的10個測試問題中進行實驗測試，對測試結(jié)果的IGD值進行比較.表1給出了兩個算法在所有問題上所得實驗結(jié)果的最大值、最小值和均值，加粗字體顯示的是兩算法中較小的數(shù)據(jù).圖1給出了10個問題中具有代表性的6個問題(每類2個)實驗結(jié)果的盒子圖.

表1　兩種算法針對10個問題IGD值對比(最大/最小/均值(標準差))

從表中易見算法MODdEA+在是10個測試問題中的IGD平均值都好于算法MODdEA.因此認為算法MODdEA+比算法MODdEA有更好的收斂能力，可以看做是增加了克隆算子的結(jié)果.在問題ZDT1、CEC02、CEC03、CEC05、TYD02和TYD05中算法MODdEA+的IGD最大值、最小值和平均值均小于算法MODdEA，其他4個問題也至少有兩個值小于，因此可以認為算法MODdEA+相比算法MODdEA有更好的穩(wěn)定性.同樣如表2所示，算法MODdEA+所求解集的IGD值的各統(tǒng)計量比算法MODdEA的相應值更優(yōu)，所以認為算法MODdEA+比算法MODdEA更有效.兩個算法的穩(wěn)定性在圖1中得到進一步的顯示，圖中選取了10個問題中具有代表性的3類6個問題，明確顯示了兩個算法的IGD值分布圖.它給出了兩種算法的IGD值分布，包括最小觀察值、低四分位值、中位值、高四分位值、最大觀察值和平均值.易見算法MODdEA+在所顯示問題上IGD值的顯著優(yōu)越性.產(chǎn)生這種優(yōu)勢的原因是：克隆算子的加入增強了算法后期的收斂能力與前期的探索能力，整體上提高了算法的尋優(yōu)能力；更新的非支配排序策略提高了算法的求解效率.

5.3收斂性比較

收斂性是進化算法的一個重要特征，當算法收斂后其各個性能指標都將趨于穩(wěn)定.隨著迭代次數(shù)的積累到一定程度，算法都將會收斂于某一處.為了客觀地評價本文中提出的新算法在收斂后的各種性能，本小節(jié)通過IGD指標值來分析算法的收斂性，最終獲取新算法在代表測試用例上的最大迭代次數(shù)(或最大評估次數(shù)).在收斂性分析中，本小節(jié)選取2個算法算法對于3類的10個測試問題中具有代表性的6個問題(每類2個)進行收斂性比較和分析.在迭代過程中每隔一定的代數(shù)，計算其運行結(jié)果的IGD值.圖2給出了兩種算法在規(guī)定的迭代次數(shù)內(nèi)IGD值的變化情況.

6個問題中算法MODdEA+均比算法MODdEA收斂到了一個更低的IGD值上，說明算法MODdEA+有更好的收斂能力.除問題ZDT6外，兩種算法均在25(*1000迭代)左右收斂，問題ZDT6的IGD值已經(jīng)降到1.0e-4的數(shù)量級上，可以視為已經(jīng)收斂.除問題CEC5之外的5個問題，算法MODdEA+的IGD值基本一直處于優(yōu)勢地位.因此可以認為算法MODdEA+相比算法MODdEA更加有效.主要原因是算法MODdEA+在算法MODdEA的基礎(chǔ)上加入克隆算子，提高了收斂能力.

6　結(jié)語

針對MODdEA存在的三處不足，本文針對MODdEA進行了三處改進，并提算法MODdEA+.針對算法后期缺乏收斂能力的問題，提出一種新的算子稱為變異克隆算子.針對非支配排序算法求解效率問題，引入的粗適應度值，求出所有解的粗適應度值后，按粗適應度值排序.針對變異操作可能出現(xiàn)的越界問題，修改參數(shù)，降低出現(xiàn)越界的可能性.根據(jù)實驗結(jié)果可以發(fā)現(xiàn)，相比算法MODdEA，算法MODdEA+有著更好的求解精度，更快速的收斂到更精確的位置.由BSP樹結(jié)構(gòu)帶來的時間空間資源的消耗過多，是下一步要解決的問題.

[1]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].Evolutionary Computation,IEEE Transactions on,2002,6(2):182-197.

[2]Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the strength Pareto evolutionary algorithm for multiobjective optimization[A].Proc of the Evolutionary Methods for Design,Optimisation and Control.Athens:International Center for Numerical Methods in Engineering[C].Siitzerland:Technical report TIK-Report，2002.95-100.

[3]Knowles J D,Corne D W.Approximating the nondominated front using the Pareto archived evolution strategy[J].Evolutionary Computation,2000,8(2):149-172.

[4]Zitzler E,Künzli S.Indicator-based selection in multiobjective search[A].Parallel Problem Solving from Nature-PPSN VIII[C].Berlin Heidelberg:Springer.2004.832-842.

[5]Bader J,Zitzler E.HypE:An algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation,2011,19(1):45-76.

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

[7]Chow C K,Yuen S Y.A multiobjective evolutionary algorithm that diversifies population by its density[J].Evolutionary Computation,IEEE Transactions on,2012,16(2):149-172.

[8]Zitzler E,Deb K,Thiele L.Comparison of multiobjective evolutionary algorithms:Empirical results[J].Evolutionary computation,2000,8(2):173-195.

[9]Zhang Q,Zhou A,Zhao S,et al.Multiobjective optimization test instances for the CEC 2009 special session and competition[R].University of Essex,Colchester,UK and Nanyang Technological University,2008.1-30.

[10]Bandyopadhyay S,Bhattacharya R.NSGA-II based multi-objective evolutionary algorithm for a multi-objective supply chain problem[A].Advances in Engineering,Science and Management (ICAESM),2012 International Conference on.IEEE[C].Nagapattinam,Tamil Nadu:IEEE,2012.126-130.

[11]He J,Mitavskiy B,Zhou Y.A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem[A].Evolutionary Computation (CEC) 2014 IEEE Congress on[C].Beijing:IEEE,2014.141-148.

[12]Chow C K,Yuen S Y.A dynamic history-driven evolutionary algorithm[A].Evolutionary Computation (CEC),2014 IEEE Congress on.IEEE.[C].Beijing:IEEE.2014.1558-1564.

[13]Wang B,Xu H,Yuan Y.Quantum-inspired evolutionary algorithm with linkage learning[A].Evolutionary Computation (CEC),2014 IEEE Congress on[C].Beijing:IEEE,2014.2467-2474.

王鵬男，1987年生于山東煙臺.東北大學計算機應用技術(shù)專業(yè)博士研究生.研究方向為服務計算、人工智能算法.

張長勝男，1980年生于吉林長春.東北大學信息科學與工程學院副教授、碩士生導師.主要研究方向為智能信息處理.

張斌(通信作者)男，1964年出生，東北大學信息科學與工程學院教授、博士生導師.主要研究方向為服務計算.

E-mail:zhangbin@ise.neu.edu.cn

An Improved Density-Driven Multi-objective Evolutionary Algotithm

WANG Peng,ZHANG Chang-sheng,ZHANG Bin,LIU Ting-ting

(CollegeofInformationScience&Engineering,NortheasternUniversity,Shenyang,Liaoning110819,China)

Multi-objective evolutionary algorithm that diversifies population by its density (MODdEA) solve multi-objective optimization problem according to the non-dominated sorting information and spatial density information,the algorithm has a good performance in the comparison with other multi-objective evolutionary algorithm.In this paper,we propose an improved multi-objective evolutionary algorithm MODdEA + based on MODdEA.Firstly,we propose a operator named clone operator based on the partition mechanism in search space,this operator could not only improve the global search capabilities in the early stage of evolution,but also enhance the local refinement capabilities in the late stage of evolution;secondly,we introduce a evaluation strategy which evaluate the individuals in Pareto information list based on the dominate and dominated information,this strategy provide a more accurate sorting result;finally,we improve the mutation operator in order to reduce the probability of overstep of the boundary.To demonstrate the effectiveness of the improved algorithm,we compare it with MODdEA on multiple testing problems,the experimental results show that the improved algorithm’s solving quality is much better than the original algorithm’s.

evolutionary algorithm;density-driven;clone operator;raw fitness;mutation operator

2014-10-28;

2015-03-26；責任編輯：藍紅杰

寧夏回族自治區(qū)自然科學基金(No.NZ13265);中央高校東北大學基本科研專項基金(No.N120804001，No.N120204003)

TP311

A

0372-2112 (2016)05-1071-07

電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.009