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

王明昭,王宇平,王曉麗,衛(wèi) 珍

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

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

王明昭,王宇平,王曉麗,衛(wèi) 珍

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

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

均勻聚集區(qū)間;基尼權(quán)重;均勻聚集距離;多目標優(yōu)化

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

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

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

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

1　均勻聚集距離設(shè)計

1.1均勻聚集區(qū)間設(shè)計

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

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

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

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

若f′i,j+1≠f′i,j-1,則表明個體j-1、j和j+1對第i個目標函數(shù)的值不完全相同.設(shè)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個目標函數(shù)下的聚集區(qū)間均勻性偏差可以用函數(shù)ui,j表示為

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

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

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

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

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

1.2基尼權(quán)重設(shè)計

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

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

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

1.2.2基尼權(quán)重度量

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

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

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

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

1.3均勻聚集距離設(shè)計

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

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

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

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

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

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

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

2.1算法過程

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

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

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

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

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

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

2.2算法性能分析

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

2.2.1收斂性評價

2.2.2分布性評價

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

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

3　仿真實驗及分析

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

3.1參數(shù)設(shè)置

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

3.2測試結(jié)果

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

表1　各算法的計算結(jié)果比較

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

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

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

4　結(jié) 論

文中基于均勻聚集區(qū)間和基尼權(quán)重提出了一種改進的NSGA-Ⅱ算法.主要創(chuàng)新包括:①通過均勻聚集區(qū)間實現(xiàn)了個體局部空間的均勻化,促使算法向Pareto最優(yōu)邊界定向快速收斂;②通過基尼系數(shù)與基尼權(quán)重更好地維持種群在目標函數(shù)下的多樣性,使得Pareto最優(yōu)解分布更均勻;③結(jié)合基尼權(quán)重和均勻聚集區(qū)間,設(shè)計了一種新的均勻聚集距離度量,并在此基礎(chǔ)上提出了一種改進的NSGA-Ⅱ算法(UGNSGA-Ⅱ);④對比算法NSGA-Ⅱ,算法UGNSGA-Ⅱ具有更好的收斂性和分布性,能求得更高質(zhì)量的Pareto最優(yōu)解,實驗結(jié)果表明了所提算法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]李蕊,史小衛(wèi),徐樂,等.競爭差分進化算法及其在共形陣綜合中的應用[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]郭金維,蒲緒強,高祥,等.一種改進的多目標決策指標權(quán)重計算方法[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);中央高?；究蒲袠I(yè)務費專項資金資助項目(BDZ021430)

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

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