張麗麗，許　峰

(安徽理工大學(xué)理學(xué)院，安徽　淮南　232001)

?

基于聚集密度的約束多目標(biāo)進(jìn)化算法

張麗麗，許峰

(安徽理工大學(xué)理學(xué)院，安徽淮南232001)

摘要：對(duì)基于群體聚類的約束多目標(biāo)進(jìn)化算法進(jìn)行了改進(jìn)，引入了聚集密度以度量群體中個(gè)體間的關(guān)系，保持種群的多樣性。其基本思想為：首先將初始群體按多判據(jù)聚類方法分為適應(yīng)度值不同的四類，然后計(jì)算類內(nèi)群體中個(gè)體的聚集密度，根據(jù)適應(yīng)度值和聚集密度定義一個(gè)偏序集，最后采用比例選擇原則依次從偏序集中選擇個(gè)體，更新精英集。通過(guò)數(shù)值實(shí)驗(yàn)用量化指標(biāo)研究了改進(jìn)算法的收斂性和分布性，結(jié)果表明：改進(jìn)算法的收斂性與常規(guī)約束多目標(biāo)進(jìn)化算法相當(dāng)，但分布性有了明顯的提高。

關(guān)鍵詞：約束多目標(biāo)進(jìn)化算法；種群聚類；聚集密度；分布性

約束多目標(biāo)優(yōu)化問(wèn)題的關(guān)鍵是對(duì)約束條件的處理，目前已有一些典型的帶約束多目標(biāo)進(jìn)化算法和約束處理機(jī)制：文獻(xiàn)[1]提出的COMOGA算法，將向量評(píng)估遺傳算法和Pareto排序分級(jí)的方法結(jié)合起來(lái)處理約束問(wèn)題。文獻(xiàn)[2]提出的約束VEGA，將群體劃分成幾個(gè)子群體來(lái)處理。文獻(xiàn)[3]提出的約束MOGA，將基于Pareto優(yōu)勝的選擇方案用來(lái)處理遺傳算法中的約束方程。文獻(xiàn)[4]提出了一種基于群體分類的復(fù)雜約束多目標(biāo)進(jìn)化算法，根據(jù)聚類方法來(lái)處理復(fù)雜約束，算法的基本思想是：按照類內(nèi)距離平方和最小，類間距離平方和最大等多種判據(jù)將種群聚類處理，再按類賦以適當(dāng)?shù)倪m應(yīng)度值。這種算法對(duì)于處理Pareto邊界比較光滑的三目標(biāo)的優(yōu)化問(wèn)題效果較好，收斂速度較快，基本上二百代即已達(dá)到較好的優(yōu)化效果，但在維持種群的多樣性和分布性方面欠佳，現(xiàn)將此算法做了改進(jìn)，在進(jìn)化過(guò)程中引入聚集密度以調(diào)控種群，可以達(dá)到維持種群多樣性的目的，并根據(jù)量化評(píng)價(jià)指標(biāo)和數(shù)值實(shí)驗(yàn)結(jié)果對(duì)改進(jìn)算法的性能特別是分布性進(jìn)行了評(píng)測(cè)。

1多目標(biāo)優(yōu)化問(wèn)題的相關(guān)概念

1.1多目標(biāo)優(yōu)化問(wèn)題及其最優(yōu)解

多目標(biāo)優(yōu)化問(wèn)題可表述為[5]

(1)

式中：x為決策向量，f(x)為目標(biāo)向量，X表示決策向量x形成的決策空間，Y表示目標(biāo)向量y形成的目標(biāo)空間，約束條件e(x)≤0確定決策向量的可行取值范圍。

定義1[6]滿足式(1)中的約束條件e(x)的決策向量x的集合，即

Xf={x∈X|e(x)≤0}

(2)

稱為可行解集。

定義2[7]設(shè)xA，xB是兩個(gè)可行解，若f(xA)≤f(xB)， 則稱xA比xB優(yōu)越； 若f(xA)

定義3若可行解x*滿足：比x*更優(yōu)越的可行解不存在，則稱x*為弱Pareto最優(yōu)解；

比x*優(yōu)越的可行解不存在，則稱x*為強(qiáng)Pareto最優(yōu)解。

定義4Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集或非支配解集，記為P*。

定義5Pareto最優(yōu)解集P*中的所有Pareto最優(yōu)解集對(duì)應(yīng)的目標(biāo)向量組成的曲面稱為Pareto最優(yōu)前沿或Pareto最優(yōu)前端，記為

PF*{f(x*)=(f1(x*)，f2(x*)，…，

fm(x*))T|

x*∈P*}

(3)

兩目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿是一條平面曲線，三目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)前沿則為一張空間曲面。多目標(biāo)優(yōu)化問(wèn)題的結(jié)果習(xí)慣上多采用Pareto最優(yōu)前沿表示。

1.2最優(yōu)解集的評(píng)價(jià)標(biāo)準(zhǔn)

多目標(biāo)優(yōu)化算法性能的評(píng)價(jià)包括算法的效率和最優(yōu)解集的質(zhì)量。算法的效率主要指算法的復(fù)雜性即算法占用的CPU時(shí)間，而最優(yōu)解集的質(zhì)量包括算法的收斂性和最優(yōu)解集的分布性。

評(píng)價(jià)多目標(biāo)優(yōu)化算法性能主要依靠量化評(píng)價(jià)標(biāo)準(zhǔn)和有代表性的測(cè)試問(wèn)題。

常用的量化評(píng)價(jià)指標(biāo)有：

1) 世代距離[8](GD)

(4)

式中：n為算法所得最優(yōu)前端PFknown中向量個(gè)數(shù)，di為PFknown中每一維向量到最優(yōu)前端PFtrue中最近向量的距離。

GD主要反映了PFknown對(duì)PFtrue的逼近程度。

2) 錯(cuò)誤率[9](ER)

(5)

式中：n為PFknown中的向量個(gè)數(shù)，且PFknown={X1，X2，…，Xn，ei定義如下

(6)

ER描述了PFknown對(duì)PFtrue的覆蓋程度，即最優(yōu)解集的分布性。

3) 分散性(SP)[10]

(7)

式中：n和di同GD。

顯然，SP即為di的均方差。根據(jù)方差的含義，SP反映的是最優(yōu)解集的均勻性。

2基于聚集密度的約束多目標(biāo)算法

上述群體分類的復(fù)雜約束多目標(biāo)進(jìn)化算法具有較好的收斂性，但在分布性方面存在著的一定的缺陷，原因是算法僅考慮了群體中個(gè)體的R適應(yīng)度，并沒有考慮群體中個(gè)體間的距離，即群體的擁擠程度，這極有可能降低種群的多樣性，影響解的分布性。

在進(jìn)化算法中，保持解的分布性的常用方法有：小生境技術(shù)，信息熵，聚集密度，聚類分析等[11]。

本文將聚集密度引入選擇過(guò)程，改善解的多樣性和分布性。

2.1聚集密度

聚集密度的概念是Deb在[12]中提出來(lái)的。聚集密度可以從個(gè)體的相似度，影響因子或者聚集距離幾個(gè)方面來(lái)度量，本文選擇從聚集距離角度度量。聚集密度與聚集距離成反比關(guān)系，聚集距離大的聚集密度小。一個(gè)個(gè)體的聚集距離可以通過(guò)計(jì)算其與相鄰的兩個(gè)個(gè)體在每個(gè)子目標(biāo)上的距離差之和來(lái)求取。

如圖1所示，設(shè)有兩個(gè)子目標(biāo)f1(x)和f2(x)，Pm[i]為個(gè)體i在子目標(biāo)m上的函數(shù)值，則個(gè)體i的聚集距離P[i]d是圖中四邊形的長(zhǎng)與寬之和，即

P[i]d=P1[i+1]-P1[i-1]+P2[i+1]-P2[i-1]

(8)

圖1　個(gè)體間的聚集距離

當(dāng)有r個(gè)子目標(biāo)時(shí)，個(gè)體i的聚集距離

(9)

計(jì)算出聚集距離后，再按照個(gè)體間的聚集距離越大，則個(gè)體的聚集密度就越小的原則，即可定義個(gè)體的聚集密度。這里，為了簡(jiǎn)單起見，定義聚集密度為聚集距離的倒數(shù)。

2.2基于聚集密度的約束多目標(biāo)進(jìn)化算法

基于聚集密度的約束多目標(biāo)進(jìn)化算法的步驟如下

1) 用多判據(jù)聚類方法將整個(gè)群體分成四類，不可行群體、可行非Pareto群體、聚類Pareto群體以及聚類Pareto最優(yōu)群體。分別賦以適應(yīng)度：R(不可行群體)≤R(可行非Pareto群體) ≤R(聚類Pareto群體)≤R(聚類Pareto最優(yōu)群體)。

2) 當(dāng)?shù)螖?shù)小于最大迭代次數(shù)時(shí)，構(gòu)造如下偏序集：① 計(jì)算種群中個(gè)體的目標(biāo)函數(shù)值；② 計(jì)算每個(gè)個(gè)體的聚集密度；③ 根據(jù)目標(biāo)函數(shù)值和聚集密度定義一個(gè)偏序集，該偏序集中的元素有兩個(gè)屬性：個(gè)體的目標(biāo)函數(shù)值和聚集距離。

3) 根據(jù)比例選擇原則，依次從偏序集中選擇個(gè)體。

4) 對(duì)群體進(jìn)行交叉運(yùn)算。

5) 對(duì)群體進(jìn)行均勻變異運(yùn)算。

6) 條件終止判斷。不滿足終止條件，則進(jìn)行新一輪運(yùn)算，若滿足終止條件，則輸出計(jì)算結(jié)果，算法結(jié)束。

算法流程圖如下

圖2　改進(jìn)算法流程圖

3數(shù)值實(shí)驗(yàn)與算法性能評(píng)測(cè)

下面用基于聚集密度的約束多目標(biāo)進(jìn)化算法對(duì)兩個(gè)標(biāo)準(zhǔn)約束多目標(biāo)測(cè)試函數(shù)Binh4和Viennet 4進(jìn)行了優(yōu)化，并將計(jì)算結(jié)果與文獻(xiàn)[12]中的原算法的計(jì)算結(jié)果進(jìn)行了比較，從而檢驗(yàn)改進(jìn)算法的性能。

1) Binh4測(cè)試函數(shù)

(10)

約束條件為

(11)

Binh4測(cè)試函數(shù)的PFlocal如圖3所示。

圖3　Binh4 PFtrue 圖

2) Viennet4測(cè)試函數(shù)

(12)

約束條件為

(13)

Viennet4測(cè)試函數(shù)的PFlocal如圖4所示。

圖4　Viennet4 PFtrue 圖

圖5　Binh4 PFknown 圖(改進(jìn)算法)

圖6　Binh4 PFknown 圖(原算法)

圖7　Viennet4 PFknown 圖(改進(jìn)算法)

圖8　Viennet4 PFknown 圖(原算法)

圖5～圖8分別是用改進(jìn)算法和原算法求出的Binh4和Viennet4的Pareto最優(yōu)邊界?？梢院苤庇^地看出，改進(jìn)算法在解的分布性和均勻性方面均明顯優(yōu)于原算法。

為了更進(jìn)一步定量地評(píng)價(jià)改進(jìn)算法的性能，下面給出改進(jìn)算法和原算法的世代距離、錯(cuò)誤率和分散性指標(biāo)的對(duì)比數(shù)據(jù)。

考慮到計(jì)算結(jié)果的隨機(jī)性，表中給出的是20次實(shí)驗(yàn)結(jié)果的平均值。

表1　Binh4的原算法/改進(jìn)算法優(yōu)化指標(biāo)結(jié)果

表2　Viennet 4的原算法/改進(jìn)算法優(yōu)化指標(biāo)結(jié)果

從表1和表2中可以很清楚地看出，原算法和改進(jìn)算法的GD指標(biāo)相差不大，但改進(jìn)算法的ER和SP指標(biāo)與原算法相比明顯占優(yōu)。

綜合圖5～圖8和表1～表2，可以得出明確的結(jié)論：基于聚集密度的改進(jìn)約束多目標(biāo)進(jìn)化算法的收斂性與原算法相當(dāng)，但分布性和均勻性有了明顯的提高。

4結(jié)束語(yǔ)

本文根據(jù)聚集密度的特點(diǎn)，將聚集密度引入群體聚類約束多目標(biāo)進(jìn)化算法，數(shù)值實(shí)驗(yàn)結(jié)果和量化指標(biāo)表明：與原算法相比，改進(jìn)算法解的分布性有了明顯的提高。

由于多目標(biāo)進(jìn)化算法的理論基礎(chǔ)目前還很薄弱，收斂性和分布性等關(guān)鍵理論問(wèn)題無(wú)法從理論層次進(jìn)行證明，所以算法的改進(jìn)驗(yàn)證只能基于對(duì)比實(shí)驗(yàn)。

提高多目標(biāo)優(yōu)化算法解的分布性和均勻性的方法有多種，如小生境技術(shù)，信息熵，聚集密度，聚類分析等。本文采用的聚集密度方法與其它方法相比，優(yōu)點(diǎn)是既能從宏觀上刻畫群體的多樣性與分布性，也能從微觀上描述個(gè)體間的內(nèi)在關(guān)系，缺點(diǎn)是計(jì)算復(fù)雜度偏高。這完全符合優(yōu)化中的“沒有免費(fèi)的午餐定理(No Free Lunch， NFL)”。

參考文獻(xiàn)：

[1]SURRY P D， RADCLIFFE N J. The COMOGA Method： Constrained Optimisation by Multi-objective Genetic Algorithms[J].Control and Cybernetics，1997，26：391-412.

[2]COELLO CAC. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization[J].Engineering Optimization，2000，32：275-308.

[3]COELLO C A C.Constraint-handling using an evolutionary multi-objective optimization technique[J].Civil Engineering and Environmental System，2000，17：319-346.

[4]張麗麗， 許峰. 基于群體分類的復(fù)雜約束多目標(biāo)優(yōu)化遺傳算法[J]. 教育技術(shù)導(dǎo)刊， 2009(12)：38-41.

[5]催遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2008：6.

[6]催遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2008：7.

[7]鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京：科學(xué)出版社，2010：3-4.

[8]VELDHUIZEN D A， LAMONT G B. Evolutionary computation and convergence to a Pareto front[C]// In John R Koza. Late breaking papers at the genetic programming 1998 conference， Stanford University， California. Stanford Bookstore：221-228.

[9]COELLO COELLO C A. Evolutionary algorithms for solving muli-objective problems [M]. Kluwer Acedemic， 2002：14-18.

[10]E ZITZLER，K DEB，L THIELE.Comparison of multiobective eveolutionary algorithms：Empirical results[J]. Evolutionary Computation，2002，8(2)：173-195.

[11]鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M]. 北京： 科學(xué)出版社， 2007：118-124.

[12]DEB KALYANMOY， SAMIR AGRAWAL， AMRIT PRATAB, et al. Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimiztion：NSGA-II[C]//Kan GAL Report 200001.Indian Institute of Technooogy， Kanpur，India，2000.

(責(zé)任編輯：李麗)

Constrained Multi-objective Evolutionary Algorithm Based on Crowding Density

ZHANG Li-li, XU Feng

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China)

Abstract:The constrained multi-objective evolutionary algorithm based on group clustering was improved, and crowding-density was introduced to measure the relationship among individuals and maintain the diversity of population. The basic idea is that the initial population is divided into four groups with different fitness by multi-criterion clustering method, and the crowding-density of each group is calculated. A poset is defined according to the objective function value and crowding-density, and the individuals are selected from poset by the principle of proportion selection, then the elite set is updated. The convergence and distribution of improved algorithm were studied by means of numerical experiments, and the results showed that the convergence of improved algorithm is roughly equal to the conventional multi-objective evolutionary algorithm, but the distribution of improved algorithm is significantly improved.

Key words:constrained multi-objective evolutionary algorithm; group clustering; crowding density; distribution

收稿日期：2015-05-28

基金項(xiàng)目：安徽省教育廳自然科學(xué)基金資助項(xiàng)目(2012kb236)

作者簡(jiǎn)介：張麗麗(1979-)， 女， 安徽鳳臺(tái)人，講師，碩士，研究方向：進(jìn)化計(jì)算、群智能計(jì)算。

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098(2016)01-0050-06