一種均勻聚集距離的改進NSGA-Ⅱ算法

王明昭,王宇平,王曉麗,衛 珍

(西安電子科技大學計算機學院,陜西西安 710071)

一種均勻聚集距離的改進NSGA-Ⅱ算法

王明昭,王宇平,王曉麗,衛 珍

(西安電子科技大學計算機學院,陜西西安 710071)

遺傳算法已經在多目標優化問題中得到了廣泛應用及深入研究,NSGA-Ⅱ是求解多目標優化問題的代表算法之一,其中聚集距離在收斂性和分布均勻性上均起到了重要作用,但算法沒有充分考慮微觀的個體本身和宏觀的種群整體的作用.為了能更合理地估計區域密度,使所求解集更好更均勻地收斂于Pareto最優邊界,筆者基于均勻聚集區間和基尼權重構造了一種均勻聚集距離算子,并基于該算子提出了一種改進的NSGA-Ⅱ算法.最后,通過對6個標準多目標測試問題的實驗驗證了算法的有效性.

均勻聚集區間;基尼權重;均勻聚集距離;多目標優化

實際應用中很多問題存在多個甚至相互沖突的目標,都可以抽象為多目標優化問題[1-3].追求所求解集的多樣性和收斂性是多目標進化算法的兩個主要目標.這類問題一方面要求向Pareto最優邊界定向快速收斂,另一方面要求保持均勻分布的Pareto最優解.為保持進化群體的分布性和多樣性,目前代表性的技術有小生境技術、信息熵、聚集密度、網格方法、聚類分析等[4-5].

1995年文獻[6]提出的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm,NSGA)是一種基于Pareto最優關系的多目標優化算法.它首先根據支配關系找出種群中第1層的非劣解,將與種群規模成比例的總體適應度分配給該層,所有同層非劣解共享此總體適應度值.然后,算法開始下一層非劣解集的搜索,記第2層非劣解集為一級,賦給該層非劣解與種群規模(除去以上各層已被賦予適應度的非劣解)成比例的總體適應度.重復以上賦值過程,直到種群中每一個體被賦予適應度值.該算法的缺點是構造Pareto最優解集的時間復雜度較高,算法未采用精英保留策略,而且小生境參數大小不容易確定.

2002年文獻[7]又提出了一種改進的非支配排序遺傳算法(NSGA-Ⅱ).該算法先對種群中的個體按照支配關系形成的層級賦予一定的序值,然后依照序值從小到大選擇個體.若個體的序值相同,則選擇那些在目標空間中位于稀疏區域的個體,通過計算個體之間的聚集距離來估計區域密度,在這種區域聚集距離算子的作用下,聚集距離大的個體有更大的概率被選成交配個體并保存到下一代種群中.NSGA-Ⅱ算法的快速收斂依賴于序值和聚集距離生成的偏序集,而均勻分布依賴于聚集距離的計算.因此,聚集距離在收斂性和分布均勻性保持上都起到重要的作用.但目前聚集距離的計算存在兩點不足,一是在考慮個體局部空間的聚集密度時,沒有從更微觀的角度考慮個體本身的作用;二是算法沒有從更宏觀的角度考慮種群在不同目標函數下分布性和多樣性的差別.

綜上所述,在多目標優化問題中,為了實現解集的快速收斂和均勻分布,許多學者做了大量的研究,其中NSGA-Ⅱ就是代表性算法之一,但NSGA-Ⅱ中聚集距離的計算沒有從微觀的個體本身和宏觀的種群整體角度考慮.針對以上問題,筆者提出了一種均勻聚集距離的改進NSGA-Ⅱ算法(UGNSGA-Ⅱ).

1　均勻聚集距離設計

1.1均勻聚集區間設計

NSGA-Ⅱ通過計算群體中每個個體的聚集距離和個體所處的層級來定義偏序集,從而構造下一代種群.其中聚集距離定義為個體與其相鄰的兩個個體在每個目標上的距離差之和.由于它并沒有考慮個體與相鄰兩個個體的相對位置,從而導致個體自身的目標函數值對均勻性的影響被忽略.

筆者將個體j-1、j和j+1在某一個目標函數下組成的區間稱為個體j的聚集區間.為計算聚集距離,NSGA-Ⅱ對個體的目標函數值進行了排序,因此,個體聚集區間中目標函數值形成的曲線是單調的.為使某一目標函數下每個個體與相鄰個體組成的個體聚集區間均勻化,期望個體j與j-1的目標函數值的距離同個體j與j+1的目標函數值的距離相等,此時稱個體j-1、j和j+1組成的聚集區間最為均勻.

首先,將按第i個目標函數排序后的第j個個體的函數值fi,j如式(1)所示進行隸屬度標準化操作.

其中,m是目標函數的個數,n是個體數,f′i,j是fi,j映射到[0,1]上的值.

若f′i,j+1≠f′i,j-1,則表明個體j-1、j和j+1對第i個目標函數的值不完全相同.設si,j=f′i,j+1-f′i,j,li,j=f′i,j+1-f′i,j-1,ri,j=si,jli,j,個體j在第i個目標函數下的聚集區間均勻性偏差可以用函數ui,j表示為

ui,j=是關于si,j=li,j2對稱的二次函數,在區間[-∞,li,j2]和[li,j2,+∞]上分別是單調遞增和單調遞減的.當si,j=li,j2、ri,j=0.5時,ui,j取最大值,此時個體j與j-1目標函數值的距離同個體j與j+1目標函數值的距離相等.

為有效控制ui,j的上升和下降速度,設計如下以ri,j為自變量的函數.該函數在點ri,j=0.5局部敏感.

其中,hi,j函數是關于ri,j=0.5對稱的,并在ri,j=0.5時取到最大值1,α為函數局部敏感控制系數.

定義1 個體j在第i個目標函數下的聚集區間均勻性度量函數為

當ri,j=0.5,即個體j與j-1的第i個目標函數值的距離同個體j與j+1的第i個目標函數值的距離相等時,hi,j=1,u′i,j=li,j,此時個體j-1、j和j+1組成的聚集區間最為均勻;反之,若ri,j≠0.5,即個體j與j-1的第i個目標函數值的距離同個體j與j+1的第i個目標函數值的距離不相等時,hi,j<1,ui,j

1.2基尼權重設計

NSGA-Ⅱ算法在計算聚集距離時并未考慮種群在不同目標函數下的均勻性差別,采用一定的多樣性保持策略才能得到均勻分布的Pareto最優解,較大的多樣性能夠保持較大的聚集距離.多樣性的度量一般采用方差和熵方法,筆者借鑒基尼系數與基尼權重設計了一種新的種群在多目標函數下的多樣性度量方法. 1.2.1 基尼系數度量

基尼系數是由意大利經濟學家基尼提出的定量測定收入分配差異程度的指標,在反映不同收入人群的收入分配均衡或不均衡程度方面表現突出.

定義2 若種群有n個個體,按第i個目標函數值排序后的第j個個體的函數值為fij,f′i,j為fij進行了隸屬度標準化后的函數值,si,j為按第i個目標函數值排序后的第j+1個個體的函數值與按第i個目標函數值排序后的第j個個體的函數值之差,則種群在第i個目標函數下的基尼系數可以計算如下:

1.2.2基尼權重度量

基尼系數賦權法是一種通過計算種群各目標函數的基尼系數,對各個基尼系數進行歸一化得到目標函數的基尼權重的方法.它反映了同一種群在不同目標函數下的值差異不同權重不同的思想.眾多實驗表明,常見的4種賦權方法:基尼系數賦權法、熵權法、均方差賦權法和極差賦權法中,基尼系數賦權方法的適用性最好[8],而且基尼系數賦權法簡單的計算方式也擴大了該方法的適用范圍.

首先,通過式(5)計算出第i個目標函數下的種群基尼系數Gi,用其反映該目標函數下種群之間多樣性的差異.然后,將種群在各個目標函數下的基尼系數進行歸一化處理,得到種群第i個目標函數下的基尼權重ωi,并用該值度量種群在第i個目標函數下的多樣性.

定義3 若種群有n個個體和m個目標函數,則種群在第i個目標函數下的基尼權重度量如下:

ωi越大,表明種群的目標函數值越不均勻,函數值在擁擠距離計算時的比重應盡量減少,因此,將1-ωi作為權重反映不同種群在第i函數下的均勻性度量值.基尼權重作為多樣性度量值,消除了某一種群不同目標函數量綱的影響,較好地反映了不同目標函數下同一種群之間的差異性.

1.3均勻聚集距離設計

定義4 若種群有n個個體和m個目標函數,則個體j的均勻聚集距離定義為

其中,u′i,j表示個體j-1、j和j+1在第i個目標函數下組成的聚集區間均勻程度.u′i,j函數值越大,代表聚集區間越均勻.1-ωi表示個體j所在種群在第i個目標函數下的均勻情況.1-ωi越大,代表種群在第i函數下越均勻.Dj綜合了u′i,j和1-ωi的意義,當個體j所在的聚集區間越均勻且個體j所在種群的整體越均勻時,個體j的均勻聚集距離也越大,則個體j有更大的概率被選中.

新設計的均勻聚集距離Dj與NSGA-Ⅱ算法中的聚集距離f′i,j+1-f′i,j-1相比,Dj不僅考慮了個體j在微觀聚集區間中的分布情況,而且考慮了個體j所在種群整體的分布情況,在個體微觀和種群宏觀兩個層面同時實現了對聚集距離的改進,使得區域密度的估計更加合理.

2　一種均勻聚集距離的改進NSGA-Ⅱ算法(UGNSGA-Ⅱ)

鑒于NSGA-Ⅱ的聚集距離計算未考慮個體與相鄰兩個個體的相對位置和種群在不同目標函數下的均勻性差別,筆者基于均勻聚集區間和基尼權重設計了一種新的均勻聚集距離算子,并在該算子的基礎上,提出了新的改進的NSGA-Ⅱ算法(UGNSGA-Ⅱ).

在UGNSGA-Ⅱ算法中,選擇過程采用基于局部競爭機制的二元聯賽選擇算子,先在種群中隨機選擇2個個體進行比較,然后依據等級和擁擠距離選出一個個體.交叉采用模擬二進制交叉(Simulated Binary Crossover,SBX)算子,該算子可以把父代個體中的優良基因保留到下一代某子串中[9],從而確保遺傳算法跳出局部最優解收斂于全局最優解.變異采用多項式變異算子[10].

在UGNSGA-Ⅱ算法中,序值計算采用NSGA-Ⅱ中的快速非支配排序算法,對種群中的個體按Pareto進行排序.快速非支配排序算法既減小了計算復雜度,又能將父代與子代種群進行合并,使下一代個體從合并后的空間中進行選取,擴大選擇范圍,從而使得最優秀的個體得以保留.聚集距離采用上節提出的均勻聚集距離.

2.1算法過程

基于均勻聚集區間和基尼權重的改進NSGA-Ⅱ算法(UGNSGA-Ⅱ)步驟如下:

Step1 令t=0,種群個數為N,初始化種群P(t);計算P(t)中每個個體的序值和均勻聚集距離.

Step2 依據個體的序值和均勻聚集距離,采用二元聯賽選擇算子從種群P(t)中選擇N/2個個體.

Step3 對選擇的N/2個個體進行模擬二進制交叉操作和多項式變異操作以產生N個后代.

Step4 將N個后代同種群P(t)的N個個體合并成規模為2N的種群P′(t);計算P′(t)中每個個體的序值和均勻聚集距離;依據個體的序值和均勻聚集距離生成偏序集,依據偏序集從P′(t)中選擇N個個體進入下一代種群P(t+1).

Step5 如果滿足終止條件,則算法停止;否則,轉Step2,令t=t+1.

2.2算法性能分析

文中將從收斂性和分布性兩方面對算法進行評價.

2.2.1收斂性評價

2.2.2分布性評價

除了算法的收斂性,解集中非支配個體在目標函數空間分布的均勻程度和寬廣程度也是衡量算法非常重要的指標.文中采用U度量[12]來作為FPknown均勻性和寬廣性的度量.

設T={F1,F2,…,Fn}是算法求得的Pareto解集在目標空間中的集合,其中n是Pareto解的個數,Fj=(f1,j,f2,j,…,fm,j),fi,j是第j個Pareto解的第i個目標函數值.

3　仿真實驗及分析

文中通過測試6個典型的多目標優化函數(Binh1、Fonseca2、Poloni、Laumanns、Lis和Rendon函數),對比算法NSGA-Ⅱ和UGNSGA-Ⅱ,從而驗證所提算法的有效性.

3.1參數設置

由于α決定了均勻聚集距離對ri,j=0.5點的敏感程度,因此,首先需要確定α的取值.設定α∈[0,780],α從0開始增加的步長為20,對下面的多目標優化問題求Pareto最優解:

3.2測試結果

設種群大小為100,進化200代后算法終止.對每個測試函數,將算法NSGA-Ⅱ和UGNSGA-Ⅱ獨立運行T=30次,并在表1中記錄收斂程度平均值(CAvg)、收斂速度平均值(CVAvg)、分布性度量平均值(UAvg)、分布性度量標準差(UStd).

表1　各算法的計算結果比較

從表1可以看出,UGNSGA-Ⅱ算法相對于NSGA-Ⅱ算法,其收斂性程度平均值(CAvg)、收斂速度平均值(CVAvg)、分布性度量平均值(UAvg)和分布性度量標準差(UStd)都有不同程度的改善.可見,UGNSGA-Ⅱ算法通過均勻聚集距離使得Pareto解集的收斂性和分布性同時得到了提高.表2給出了UGNSGA-Ⅱ算法相對于NSGA-Ⅱ算法的改善百分比.從收斂性程度平均值(CAvg)看,對于所有函數,UGNSGA-Ⅱ算法趨近Pareto最優邊界的程度優于NSGA-Ⅱ算法至少30%以上,并且具有較好的穩定性.從收斂速度平均值(CVAvg)看,對于函數Poloni,UGNSGA-Ⅱ算法顯著優于NSGA-Ⅱ算法;對于函數Binh1、Fonseca2和Rendon,UGNSGA-Ⅱ算法優于NSGA-Ⅱ算法;從分布性度量平均值(UAvg)看,對于函數Binh1、Fonseca2和Laumanns,UGNSGA-Ⅱ算法較優于NSGA-Ⅱ算法;從分布性度量標準差(UStd)看,對于所有函數,UGNSGA-Ⅱ算法顯著優于NSGA-Ⅱ算法.

表2　UGNSGA-Ⅱ算法相對于NSGA-Ⅱ算法的改善百分比%

綜上可知,與NSGA-Ⅱ算法相比,UGNSGA-Ⅱ算法求出的Pareto最優解更接近Pareto最優邊界,其收斂速度更快更穩定,且這些Pareto最優解在整個Pareto最優邊界上分布更均勻.因此,算法UGNSGA-Ⅱ在解決多目標函數優化問題時優于算法NSGA-Ⅱ.實驗結果表明了所提算法UGNSGA-Ⅱ的有效性.

4　結 論

文中基于均勻聚集區間和基尼權重提出了一種改進的NSGA-Ⅱ算法.主要創新包括:①通過均勻聚集區間實現了個體局部空間的均勻化,促使算法向Pareto最優邊界定向快速收斂;②通過基尼系數與基尼權重更好地維持種群在目標函數下的多樣性,使得Pareto最優解分布更均勻;③結合基尼權重和均勻聚集區間,設計了一種新的均勻聚集距離度量,并在此基礎上提出了一種改進的NSGA-Ⅱ算法(UGNSGA-Ⅱ);④對比算法NSGA-Ⅱ,算法UGNSGA-Ⅱ具有更好的收斂性和分布性,能求得更高質量的Pareto最優解,實驗結果表明了所提算法UGNSGA-Ⅱ的有效性.

[1]BANDYOPADHYAY S,MAULIK U,COELLO C A,et al.Guest Editorial:Special Issue on Advances in Multiobjective Evolutionary Algorithms for Data Mining[J].IEEE Transactions on Evolutionary Computation,2014,18(1):1-3.

[2]SINDHYA K,MIETTINEN K,DEB K.A Hybrid Framework for Evolutionary Multiobjective Optimization[J]. IEEE Transactions on Evolutionary Computation,2013,17(4):495-511.

[3]LIAO H L,WU Q H.Multi-objective Optimization by Learning Automata[J].Journal of Global Optimization,2013,55(2):459-487.

[4]李蕊,史小衛,徐樂,等.競爭差分進化算法及其在共形陣綜合中的應用[J].西安電子科技大學學報,2012,39(3): 114-119. LI Rui,SHI Xiaowei,XU Le,et al.Synthesis of a Conformal Antenna Array Using the Competition Differential Evolution Strategy[J].Journal of Xidian University,2012,39(3):114-119.

[5]郭金維,蒲緒強,高祥,等.一種改進的多目標決策指標權重計算方法[J].西安電子科技大學學報,2014,41(6): 118-125 GUO Jinwei,PU Xuqiang,GAO Xiang,et al.Improved Method on Weights Determination of Indexes in Multiobjective Decision[J].Journal of Xidian University,2014,41(6):118-125.

[6]SRINIVAS N,DEB K.Muiltiobjective Optimization Using Nondominated Sorting In Genetic Algorithms[J].Evolutionary Computation,1994,2(3):221-248.

[7]DEB K,PRATAP A,AGARWAL S,et al.A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.[8]RODRíGUEZ J G,SALAS R.The Gini Coefficient:Majority Voting and Social Welfare[J].Journal of Economic Theory,2014,152:214-223.

[9]THAKUR M,MEGHWANI S S,JALOTA H.A Modified Real Coded Genetic Algorithm for Constrained Optimization[J]. Applied Mathematics and Computation,2014,235:292-317.

[10]KIM H,LIOU M S.Adaptive Directional Local Search Strategy for Hybrid Evolutionary Multiobjective Optimization [J].Applied Soft Computing,2014,19:290-311.

[11]DEB K,JAIN S.Running Performance Metrics for Evolutionary Multiobjective Optimization[R].KanGAL Report,Kanpur:Indian Institute of Technology,2002.

[12]LEUNG Y W,WANG Y P.U-measure:A Quality Measure for Multiobjective Programming[J].IEEE Transacions on Systems,Man,and Cybernetics:Part C,2003,33(3):337-343.

(編輯:李恩科)

Improved NSGA-Ⅱalgorithm based on the uniformly crowding distance

WANG Mingzhao,WANG Yuping,WANG Xiaoli,WEI Zhen
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

With the wide application and further study of the genetic algorithm in multi-objective optimization problems,the NSGA-Ⅱhas been one of the representative evolutionary algorithms for multiobjective optimization problems.Crowding distance in the NSGA-Ⅱplays an important role in convergence and uniform distribution of the solutions,but the NSGA-Ⅱdoes not fully take the effect of each individual and the whole population into consideration.To estimate the region density more reasonably so as to make the solution set more uniformly converge to the Pareto optimal front,we design a uniformly crowding distance operator based on the uniformly crowding range and Gini weight,and propose an improved NSGA-Ⅱalgorithm.Finally,the effectiveness of the proposed algorithm is verified by experiments on six multiobjective optimization test functions.

uniformly crowding range;Gini weight;uniformly crowding distance;multi-objective optimization

TP311

A

1001-2400(2016)03-0049-06

10.3969/j.issn.1001-2400.2016.03.009

2015-03-10

時間:2015-07-27

國家自然科學基金資助項目(61402350,U1404622);中央高校基本科研業務費專項資金資助項目(BDZ021430)

王明昭(1978-),男,西安電子科技大學博士研究生,E-mail:whaoazj@vip.sina.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20150727.1952.009.html