王　鵬,張長(zhǎng)勝,張　斌,劉婷婷

(東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng) 110819)

?

一種改進(jìn)的基于密度的多目標(biāo)進(jìn)化算法

王鵬,張長(zhǎng)勝,張斌,劉婷婷

(東北大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng) 110819)

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

進(jìn)化算法;密度驅(qū)動(dòng);克隆操作;粗適應(yīng)度值;變異操作

1　引言

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

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

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

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

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

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

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

針對(duì)上述不足，本文進(jìn)行三處改進(jìn)，從而提出改進(jìn)算法MODdEA+：

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

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

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

2　問(wèn)題描述

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

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

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

定義lPareto強(qiáng)支配：設(shè)u，v∈Ω，對(duì)于一個(gè)最小化問(wèn)題，當(dāng)且僅當(dāng)ui

定義2Pareto最優(yōu)解：對(duì)于上述多目標(biāo)優(yōu)化問(wèn)題的解集P，對(duì)解集中的一點(diǎn)x0∈P，如果x0不被P中的其他點(diǎn)x∈P所強(qiáng)支配的話，則稱(chēng)x0為P的Pareto最優(yōu)解(Paretooptimalsolution).

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

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

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

3　相關(guān)工作

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

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

4　改進(jìn)的MODdEA

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

4.1變異克隆算子

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

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

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

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

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

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

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

排序方法如下：

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

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

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

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

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

4.3改進(jìn)的多樣變異算子

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

處理過(guò)程如下：

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

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

(3)從[0,Ud-Ld]隨機(jī)生成步長(zhǎng)標(biāo)準(zhǔn)差r，當(dāng)r>max(pd-Ld,Ud-pd)時(shí)，r=r-max(pd-Ld,Ud-pd).

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

改進(jìn)后的多樣化變異算法如算法2.

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

4.4主循環(huán)

算法MODdEA+主要由進(jìn)化算法模塊和存儲(chǔ)器模塊兩部分組成.

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

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

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

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

(4)DC的作用是在進(jìn)化過(guò)程的前期增強(qiáng)擴(kuò)張，后期針對(duì)已選出的優(yōu)秀解，加強(qiáng)收斂能力.

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

本算法的處理過(guò)程如下：

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

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

4.5復(fù)雜度分析

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

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

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

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

因?yàn)楹蟠鷤€(gè)體的子區(qū)域在基本操作1中已經(jīng)獲得，所以基本操作3與基本操作5不需要額外的操作.

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

5　仿真實(shí)驗(yàn)

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

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

5.1測(cè)試問(wèn)題

在實(shí)驗(yàn)過(guò)程中，本文采用3類(lèi)問(wèn)題作將提出的算法與算法MODdEA進(jìn)行比較實(shí)驗(yàn)：文獻(xiàn)[1]中提出的TDY1-TDY6；文獻(xiàn)[8]中提出的ZDT1-ZDT4，ZDT6；文獻(xiàn)[9]中提出的UcP1-UcP10.從中選取有代表性的10個(gè)問(wèn)題作為本文的測(cè)試問(wèn)題：TYD01，TYD02，TYD05，ZDT1，ZDT2，ZDT6，CEC02，CEC03，CEC04，CEC05.

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

5.2IGD值比較

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

表1　兩種算法針對(duì)10個(gè)問(wèn)題IGD值對(duì)比(最大/最小/均值(標(biāo)準(zhǔn)差))

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

5.3收斂性比較

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

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

6　結(jié)語(yǔ)

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

[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年生于山東煙臺(tái).東北大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專(zhuān)業(yè)博士研究生.研究方向?yàn)榉?wù)計(jì)算、人工智能算法.

張長(zhǎng)勝男，1980年生于吉林長(zhǎng)春.東北大學(xué)信息科學(xué)與工程學(xué)院副教授、碩士生導(dǎo)師.主要研究方向?yàn)橹悄苄畔⑻幚?

張斌(通信作者)男，1964年出生，東北大學(xué)信息科學(xué)與工程學(xué)院教授、博士生導(dǎo)師.主要研究方向?yàn)榉?wù)計(jì)算.

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；責(zé)任編輯：藍(lán)紅杰

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

TP311

A

0372-2112 (2016)05-1071-07

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.009