基于聚集密度的約束多目標進化算法

張麗麗+許峰

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

關鍵詞：約束多目標進化算法；種群聚類；聚集密度；分布性

中圖分類號：TP3016文獻標志碼：A文章編號：1672-1098（2016）01-0050-06

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

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

1多目標優化問題的相關概念

11多目標優化問題及其最優解

多目標優化問題可表述為[5]

min y=f（x）=（f1（x），f2（x），…，fk（x））

s.t e（x）=（e1（x），e2（x），…，em（x））≤0

x=（x1，x2，…，xn）T∈X

y=（y1，y2，…，yn）∈Y

（1）

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

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

Xf={x∈X|e（x）≤0} （2）

稱為可行解集。

定義2[7]設xA，xB是兩個可行解，若f（xA）≤f（xB）， 則稱xA比xB優越； 若f（xA）

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

比x*優越的可行解不存在，則稱x*為強Pareto最優解。

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

定義5Pareto最優解集P*中的所有Pareto最優解集對應的目標向量組成的曲面稱為Pareto最優前沿或Pareto最優前端，記為

兩目標優化問題的Pareto最優前沿是一條平面曲線，三目標優化問題的Pareto最優前沿則為一張空間曲面。多目標優化問題的結果習慣上多采用Pareto最優前沿表示。

12最優解集的評價標準

多目標優化算法性能的評價包括算法的效率和最優解集的質量。算法的效率主要指算法的復雜性即算法占用的CPU時間，而最優解集的質量包括算法的收斂性和最優解集的分布性。

評價多目標優化算法性能主要依靠量化評價標準和有代表性的測試問題。

常用的量化評價指標有：

1） 世代距離[8]（GD）

GD=∑ni=1d2i n （4）

式中：n為算法所得最優前端PFknown中向量個數，di為PFknown中每一維向量到最優前端PFtrue中最近向量的距離。

GD主要反映了PFknown對PFtrue的逼近程度。

2） 錯誤率[9]（ER）

ER=∑ni=1ein （5）

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

ei=0， Xi∈PFtrue

1， 其它（6）

ER描述了PFknown對PFtrue的覆蓋程度，即最優解集的分布性。

3） 分散性（SP） [10]

SP=1n-1∑ni=1（di-）2 （7）

式中：n和di同GD。

顯然，SP即為di的均方差。根據方差的含義，SP反映的是最優解集的均勻性。

2基于聚集密度的約束多目標算法

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

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

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

21聚集密度

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

如圖1所示，設有兩個子目標f1（x）和f2（x），Pm[i]為個體i在子目標m上的函數值，則個體i的聚集距離P[i]d是圖中四邊形的長與寬之和，即

計算出聚集距離后，再按照個體間的聚集距離越大，則個體的聚集密度就越小的原則，即可定義個體的聚集密度。這里，為了簡單起見，定義聚集密度為聚集距離的倒數。

22基于聚集密度的約束多目標進化算法

基于聚集密度的約束多目標進化算法的步驟如下

1） 用多判據聚類方法將整個群體分成四類，不可行群體、可行非Pareto群體、聚類Pareto群體以及聚類Pareto最優群體。分別賦以適應度：R（不可行群體）≤R（可行非Pareto群體） ≤R（聚類Pareto群體）≤R（聚類Pareto最優群體）。

2） 當迭代次數小于最大迭代次數時，構造如下偏序集：① 計算種群中個體的目標函數值；② 計算每個個體的聚集密度；③ 根據目標函數值和聚集密度定義一個偏序集，該偏序集中的元素有兩個屬性：個體的目標函數值和聚集距離。

3） 根據比例選擇原則，依次從偏序集中選擇個體。

4） 對群體進行交叉運算。

5） 對群體進行均勻變異運算。

6） 條件終止判斷。不滿足終止條件，則進行新一輪運算，若滿足終止條件，則輸出計算結果，算法結束。

算法流程圖如下

下面用基于聚集密度的約束多目標進化算法對兩個標準約束多目標測試函數Binh4和Viennet 4進行了優化，并將計算結果與文獻[12]中的原算法的計算結果進行了比較，從而檢驗改進算法的性能。

1） Binh4測試函數

F=（f1（x，y），f2（x，y），f3（x，y））

f1（x，y）=15-x（1-y）

f2（x，y）=225-x（1-y2）

f3（x，y）=2625-x（1-y2） （10）

約束條件為

-10≤x，y≤10

x2+（y-05）2≥9

（x-1）2+（y-05）2≤625 （11）

Binh4測試函數的PFlocal如圖3所示。

2） Viennet4測試函數

Viennet4測試函數的PFlocal如圖4所示。圖4Viennet4 PFtrue 圖圖5Binh4 PFknown 圖（改進算法）圖6Binh4 PFknown 圖（原算法）圖7Viennet4 PFknown 圖（改進算法）圖8Viennet4 PFknown 圖（原算法）

圖5～圖8分別是用改進算法和原算法求出的Binh4和Viennet4的Pareto最優邊界。可以很直觀地看出，改進算法在解的分布性和均勻性方面均明顯優于原算法。

為了更進一步定量地評價改進算法的性能，下面給出改進算法和原算法的世代距離、錯誤率和分散性指標的對比數據。

考慮到計算結果的隨機性，表中給出的是20次實驗結果的平均值。

從表1和表2中可以很清楚地看出，原算法和改進算法的GD指標相差不大，但改進算法的ER和SP指標與原算法相比明顯占優。

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

4結束語

本文根據聚集密度的特點，將聚集密度引入群體聚類約束多目標進化算法，數值實驗結果和量化指標表明：與原算法相比，改進算法解的分布性有了明顯的提高。

由于多目標進化算法的理論基礎目前還很薄弱，收斂性和分布性等關鍵理論問題無法從理論層次進行證明，所以算法的改進驗證只能基于對比實驗。

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

參考文獻：

[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]張麗麗， 許峰. 基于群體分類的復雜約束多目標優化遺傳算法[J]. 教育技術導刊， 2009（12）：38-41.

[5]催遜學. 多目標進化算法及其應用[M].北京：國防工業出版社，2008：6.

[6]催遜學. 多目標進化算法及其應用[M].北京：國防工業出版社，2008：7.

[7]鄭金華. 多目標進化算法及其應用[M].北京：科學出版社，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]鄭金華. 多目標進化算法及其應用[M]. 北京： 科學出版社， 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.