基于平均距離聚類的NSGA-II

崔志華 張茂清 常 宇 張江江 王 暉 張文生

近年來,隨著復雜工程優(yōu)化問題的大量出現(xiàn),多目標優(yōu)化問題(Multi-objective optimization problems,MOP)逐漸受到許多研究人員的重視.不同于單目標優(yōu)化問題,多目標優(yōu)化問題具有高復雜性、非線性和目標函數(shù)相互沖突等特點,且不存在全局最優(yōu)解,而是一個最優(yōu)解集(Pareto optimal set).

為了有效求解多目標優(yōu)化問題,學者們引入許多解決方法,如加權和法、目標規(guī)劃法和極大極小法等.在具有一定先驗知識前提下,上述方法可以取得較好結果,但它們通常只能獲得一個Pareto 最優(yōu)解.進化算法的出現(xiàn)為解決多目標優(yōu)化問題開辟了新思路,利用進化算法并行性、智能性、自適應性和自組織性,多目標進化算法可以計算多個Pareto 最優(yōu)解[1－3].

多目標問題復雜性主要體現(xiàn)在目標函數(shù)個數(shù)上,因此,一種較為常見的研究思路是設計高效策略以減少目標函數(shù)個數(shù).Yang[4]提出采用隨機加權和方法把多個目標函數(shù)動態(tài)整合為一個單目標函數(shù),通過變化不同權重得到Pareto 最優(yōu)解集.Zhang等[5]提出的MOEA/D(Multi-objective evolutionary algorithm based on decomposition)算法將多目標優(yōu)化問題分解為一定數(shù)量的單目標優(yōu)化子問題,然后對這些子問題同步求解.鞏敦衛(wèi)等[6]將高維多目標優(yōu)化問題分解為若干子優(yōu)化問題,每一個子優(yōu)化問題除了包含原優(yōu)化問題的少數(shù)目標函數(shù)之外,還將其他目標函數(shù)相關信息融合成一個新目標函數(shù),以降低問題求解難度.Schaffer[7]把種群按照目標數(shù)量分成若干子種群,在每個子種群中按照個體適應度選擇出每個目標上最優(yōu)個體,然后將這些個體重新組合成種群.丁進良等[8]提出一種基于參考點預測策略的動態(tài)多目標優(yōu)化算法,該算法能快速跟蹤動態(tài)變化的Pareto 前沿.李文彬等[9]提出一種基于決策空間變換的最近鄰預測方法,通過屬性趨勢模型引入決策空間到目標空間的映射知識,使決策空間的最近鄰更有效反映目標空間的最近鄰,從而預測多目標優(yōu)化Pareto 支配解精度[10].

根據(jù)無免費午餐定理,每個智能優(yōu)化算法都只對某些問題有效,因此,利用不同算法優(yōu)點設計混合策略就成了一種提高算法性能的常見方法[11－14].Zitzler 等[15]利用適應度分配策略、密度估計和增強的存檔截斷方法設計了SPEA2.Yang 等[16]根據(jù)種群進化過程中支配解和非支配解比例大小,把搜索過程分割為三個階段,并在每個階段設計了不同搜索策略.徐斌等[17]和Wang 等[18]針對約束多目標優(yōu)化問題,提出了一種差分進化算法和alpha 約束支配處理的混合優(yōu)化算法,該算法在初期能有效利用不可行解所攜帶有用信息,增加種群多樣性,在后期則控制不可行解比例,使得算法朝可行域方向進化.陳志旺等[19]將高斯過程和智能進化算法進行結合提出一種融合多屬性決策的雙層種群篩選策略,并將其嵌入到遺傳算法求解高斯模型參數(shù).針對解分布性問題,林滸等[20]以免疫克隆算法為框架,引入適應度共享策略,提出了具有良好分布性的多目標優(yōu)化進化算法.Tran 等[21]、Pooja 等[22]和Wang等[23]將差分進化算法中交叉算子和人工蜂群算法結合,提出了新的混合多目標進化算法.

針對求解問題特點設計策略,能得到較好滿意解[24－26].劉潭等[27]針對單位產(chǎn)油量綜合能耗模型輸出與實際值存在較大誤差的問題,利用高斯混合模型(Gaussian mixture model,GMM)對單位產(chǎn)油量綜合能耗混合模型誤差特性進行描述,實現(xiàn)對模型的誤差補償,并將誤差補償后的單位產(chǎn)油量綜合能耗引入到已建優(yōu)化模型中,使得優(yōu)化結果更接近實際最優(yōu)值.付亞平等[28]針對生產(chǎn)工序的合并造成一種串并聯(lián)共存的生產(chǎn)布局,建立了混合整數(shù)規(guī)劃模型.針對模型特點,他們設計了一種改進的非支配排序遺傳算法,同時采用基于啟發(fā)式方法的種群初始方式提高種群多樣性,并引入一種局域搜索策略以改善算法所獲得非支配解及分布性[29－30].喬俊飛等[31]針對污水處理過程控制能耗過大和水質(zhì)超標嚴重等問題,通過記憶多目標智能優(yōu)化算法的動態(tài)處理信息,建立環(huán)境變量參數(shù)與最優(yōu)解之間的知識模型.利用定向局部區(qū)域?qū)?yōu)以及隨機全局尋優(yōu)策略,提高了算法收斂性,獲得了更高質(zhì)量的解[32－33].

NSGA-II[34]是Deb 等在2002 年提出的多目標優(yōu)化算法,其具有較低計算復雜性且在相同時間內(nèi)能獲得較優(yōu)的求解性能.為了得到汽車制動器中多目標參數(shù)優(yōu)化問題,張屹等[35]提出了基于正交設計的NSGA-II,得到了分布更優(yōu)的Pareto 前沿面.為了解決多目標柔性作業(yè)車間調(diào)度問題,Yuan等[36]把分層策略融入了NSGA-II,提出了混合局部搜索的NSGA-II.路艷雪等[37]嘗試把多輸入多輸出的反向傳播(Back-propagation,BP)神經(jīng)網(wǎng)絡和NSGA-II 融合,提高了算法運算速度和計算精度.

為了進一步提升NSGA-II 性能,近年來許多研究者嘗試把聚類思想融入該算法中.例如,Mukhopadhyay 等[38]提出將模糊聚類思想應用于NSGA-II,并基于該方法從所求Pareto 前沿面中獲得了較優(yōu)的聚類結果.不同于以往單個標準聚類方法,Handl 等[39]提出兩標準的聚類方法,并進一步將其與進化算法結合;與一些單標準聚類算法相比,該改進方法具有較優(yōu)效果[40－41].類似地,劉叢等[42]利用使用歐氏距離和Path 距離設計出新的聚類框架,并融合多目標進化算法有效提升了算法性能.

上述聚類思想與多目標進化算法融合大多根據(jù)已有聚類聚方法進行改進.與以上對NSGA-II 改進不同,本文受聚類思想啟發(fā),針對算法多樣性方面存在的缺陷[43－44]設計了新的平均距離聚類的多樣性指標.基于平均距離聚類多樣性指標,整個種群可均勻劃分成若干個小種群,并可將NSGA-II 的選擇和交叉算子等操作應用在小種群中,從而保證算法所求結果均勻分布在Pareto 前沿面上,稱改進后算法為基于平均距離聚類的NSGA-II 算法(NSGA-II with average distance clustering,ADCNSGA-II).

本文組織如下:第1 節(jié)介紹多目標優(yōu)化領域中的基本概念及NSGA-II 基本框架;第2 節(jié)詳細介紹了基于平均距離聚類的NSGA-II,包括選擇和交叉算子的設計;第3 節(jié)利用SCH 及ZDT 測試集,將所提算法與常用多目標優(yōu)化算法進行對比實驗,并分析了參數(shù)S 對算法性能影響;最后給出了本文結論和未來研究方向.

1 基本NSGA-II 框架

本文考慮如下多目標優(yōu)化問題:

其中,fi(x)表示第i 個目標函數(shù),i=1,2,···,M,x=(x1,x2,···,xD)∈RD為決策變量空間.

定義1.若變量x 的目標函數(shù)為f(x)=(f1(x),f2(x),···,fM(x))T,變量x′的目標函數(shù)為f(x′)=(f1(x′),f2(x′),···,fM(x′))T,當且僅當對于?i ∈{1,2,···,M},fi(x)≤fi(x′)成立,且存在k ∈{1,2,···,M},使得fk(x)＜fk(x′)嚴格成立,則稱x 支配x′,記作:x ?x′.

定義2.決策空間上所有Pareto 最優(yōu)解構成的集合稱為Pareto 最優(yōu)解集(ParetoSet,PS)

定義3.Pareto 最優(yōu)解集在目標空間上對應的點集稱為Pareto 前沿面(ParetoFront,PF).

NSGA-II[34]主要采用了快速非支配排序(Fast non-dominated sorting)和擁擠度距離(Crowding distance)的概念.快速非支配排序主要思想如下:首先,對種群P 中所有個體計算兩個參數(shù),支配個體p 的個體數(shù)量(np)和個體p 所支配的個體集合(Sp).對于任意個體p,若np=0,則其被放入第1層非支配前沿面F1.對np=0 的個體,遍歷其所支配的個體集合Sp中每一個個體(q)并執(zhí)行nq-1,此時若nq=0,則放入臨時集合Q 中.遍歷完F1所有個體的支配集合之后,此時Q 所有個體組成第2 層非支配前沿面F2.重復上述步驟,直到所有個體都被識別出其所在前沿面.

擁擠度距離用于衡量種群多樣性,設fk(xi),k=1,2,···,M,i=1,2,···,N 為目標函數(shù),基于每個目標函數(shù)值對所有個體進行升序排列,排在第一位(即函數(shù)值最小)的個體,其擁擠度距離為d1=∞,排在最后一位(即函數(shù)值最大)的個體,其擁擠度距離為dL=∞,其余個體的擁擠度距離按照下式計算:

其中,di表示個體xi的擁擠度距離,fk(xi+1)表示個體xi+1的第k 個目標函數(shù).

擁擠度距離計算過程可通過圖1 簡要說明如下.假設圖1 中有A 點、B 點及其相鄰的鄰居,且A 與B 互不支配.根據(jù)式(2),可以得出B 點的擁擠度距離為與B 點相鄰的兩點的每個函數(shù)維度距離之和,即B 點的擁擠度為8l ;同樣,可得A 點擁擠度距離為9l .從數(shù)值結果上看,B 點比A 點更加擁擠;從圖1 可以直觀看出A 點比B 點更加擁擠.根據(jù)擁擠度距離的定義,算法應該去掉B 點,保留A 點.如果交叉的父代選擇了A 點和C 點,由于A和C的距離過近,會導致子代個體與父代A和C 沒有明顯差異,進而導致算法收斂到某一局部最優(yōu)解而不能均勻地分布在整個Pareto 前沿面上.這顯然不符合我們對擁擠度距離的預期.

圖1 熔化率與比例、積分系數(shù)之間的關系Fig.1 Comparing melting rate with proportion and integral parameters of the consarc controller

2 基于平均距離聚類的NSGA-II

為更清楚地介紹基于平均距離聚類的NSGAII,第2.1 節(jié)首先介紹匹配選擇,然后在第2.2 節(jié)中詳細介紹平均距離聚類的多樣性指標,之后在第2.3節(jié)中將其應用于NSGA-II 的選擇算子,第2.4 節(jié)將其應用于交叉算子,最后總結本文所提算法的基本框架.

2.1 匹配選擇

為加快整個種群的收斂速度和保證種群多樣性,本文引入了匹配選擇操作對種群進行選擇.在匹配選擇中,本文借鑒SPEA2 賦值方法對種群個體適應值進行重新賦值,該賦值方法不僅考慮種群個體之間的支配關系,也考慮種群個體間的被支配關系(其中種群個體賦值方法可參考SPEA2,不再詳細說明).基于以上賦值的適應度值,將非支配個體保存到一個初始為空的一個種群P0中,為防止種群P0大小超出邊界,這里采用聚類截斷方法使得整個種群大小達到要求的種群大小值N,最后將得到種群作為匹配選擇算子的子代輸出.具體匹配選擇算子的偽代碼如下.

算法1.匹配選擇算子

2.2 平均距離聚類的多樣性指標

平均距離聚類的多樣性指標 (Averagedistance-clustering diversity index)主要采用聚類思想,把平均距離內(nèi)多個個體劃分為一個小種群.

假設種群P=(x1,x2,···,xN)有N 個個體,f(xi)=(f1(xi),f2(xi),···,fM(xi))為個體xi的目標函數(shù),則種群P 中第j 個目標函數(shù)最大值fj,max和最小值fj,min分別為

定義群體在第j 個目標函數(shù)的平均距離fj,step為

其中,S 表示每個小種群所含個體數(shù)量.由于在實際算法運行中,個體之間相對位置具有隨機性,因此實際小種群中個體數(shù)量需要根據(jù)問題的特點設置.

如圖2 所示,若在目標空間中有點A、B和C,對應在坐標軸f1上投影分別為A′、B′和C′,且D為A′和B′中間點,E 為B′和C′中間點.若要在f1上形成以B′為中心的小種群,且不能與相鄰小種群有交集,則此時B′點所在小種群的選擇半徑只能為兩個相鄰點距離一半.

圖2 式(5)中參數(shù)說明Fig.2 Illustration of parameter in (5)

上述小種群劃分過程可用算法2 描述,其中xi為隨機選擇個體.在初始階段,首先確定目標函數(shù)平均距離(第1～2 行),在此基礎上進一步確定xi所在小種群,并對小種群內(nèi)未被標記個體進行逐一標記(第5～7 行).需要注意的是,在小種群劃分過程中,平均距離和小種群劃分的數(shù)量由種群在運算過程中確定.

根據(jù)式(5)～(7)可知,較大S 取值(例如當S取值為種群規(guī)模大小)會直接導致fj,step取值較大,從而導致fmax(xi)-fmin(xi)增大.由上述小種群劃分過程可知,fmax(xi)-fmin(xi)較大取值不僅會導致更多個體包括在一個小種群中,而且也會減少小種群數(shù)量,并進一步減弱種群多樣性.因此,在后續(xù)實驗中,本文將采用較小S 值,且將驗證不同S 取值對算法影響.

如圖3 所示,通過以上方法可以將整個種群劃分為若干小種群.每個小種群范圍根據(jù)種群平均距離確定,且每個小種群相對于原始整個種群呈現(xiàn)大致均勻分布特點.正是上述特點才能保證最后所求結果均勻分布在Pareto 前沿面上,同時小種群有限的搜索空間也能保證整個小種群內(nèi)部所有個體對前沿面進行有效探索.

圖3 小種群劃分示意圖Fig.3 Illustration of small populations

算法2.平均距離多樣性指標

算法3.基于平均距離聚類選擇算子

2.3 基于平均距離聚類選擇算子

如算法3 所示,在對小種群SP 執(zhí)行選擇時,首先判斷隨機選擇個體aj與ai的支配關系.若可以確定支配關系,則較優(yōu)個體被選擇(第5～8 行).若aj與ai互不支配,則比較平均距離內(nèi)個體數(shù)量,平均距離內(nèi)個體數(shù)量少的個體被優(yōu)先選擇(第9～12行).如果aj與ai具有相同個體數(shù)量,則隨機選擇兩者其一(第13～16 行).

利用上述策略對圖1 進一步分析.由于點A 與點B 互不支配(第5～8 行),因此無法判斷兩者優(yōu)劣.若將其所在小種群平均距離內(nèi)個體數(shù)量作為進一步評判指標,則可有效區(qū)分兩者優(yōu)劣(第9～12行).由于A 非常靠近其鄰居節(jié)點,因此在A 點平均距離范圍至少有一個節(jié)點.對于B 而言,由于其與前后兩個鄰居距離適中,因此其平均距離內(nèi)節(jié)點數(shù)為零.從上述分析中可以看出,利用本文所提的基于平均距離聚類選擇策略可以有效避免選擇擁擠度大的個體.

2.4 基于平均距離聚類交叉算子

與常規(guī)交叉算子不同,本文將小種群決策變量的平均距離加入到交叉算子計算過程中,即引入了擾動操作,從而可以進一步增加種群個體多樣性.

一般交叉過程如圖4 所示.在決策空間中,假設點A (小圓中心位置)和點B (小圓中心位置)為隨機選擇的交叉父代.按照標準交叉原則,A 與B 交叉子代一定落在小矩形框內(nèi)(這里僅討論交叉算子,不涉及變異,因此后代產(chǎn)生范圍可以確定).如果引入基于平均距離聚類,則可以確定A 點所在的小種群范圍(對應A 點所在小圓圈區(qū)域),同時確定B 點所在小種群范圍(對應B 點所在小圓圈區(qū)域).通過隨機選擇A 點所在區(qū)域的個體A′和B 點所在區(qū)域的個體B′,A 與B 交叉產(chǎn)生的子代范圍(實際是A′和B′進行交叉運算)將比標準交叉算子產(chǎn)生的子代范圍更大(大矩形框所在區(qū)域).根據(jù)以上分析,可以看出采用基于平均距離聚類之后的子代區(qū)域搜索范圍擴大了許多.

圖4 交叉算子示意圖Fig.4 Illustration of crossover operator

其中,xnew表示產(chǎn)生的子代,r1和r2分別是[-1,1]內(nèi)的隨機數(shù).分別為A 點和B 點所在小種群每維決策變量的平均距離.

設A 點所在小種群為SPA,其個體數(shù)量為|SPA|,表示A 點所在小種群SPA第i 個個體第j 維決策變量,則小種群SPA中第j 維決策變量最大值與最小值分別為

進而,可得A 點所在小種群第j 維決策變量的平均距離為

在每一維決策變量上計算決策變量的平均距離,可得到A 點所在小種群SPA在每維決策變量的平均距離,同理可以得到

2.5 基于平均距離聚類的NSGA-II 基本框架

基于平均距離聚類的NSGA-II 本質(zhì)上是把平均距離聚類策略融入到NSGA-II 的選擇和交叉算子中.它由5 個操作組成:平均距離聚類多樣性指標、基于平均距離聚類的選擇算子、基于平均距離聚類的交叉算子、變異算子和環(huán)境選擇.

基于平均距離聚類的NSGA-II 主要過程如算法4 所示.在初始化種群和相關參數(shù)之后,首先對所有個體進行快速非支配排序,然后通過平均距離聚類的多樣性指標把整個種群按照平均距離聚類劃分為若干小種群,并根據(jù)小種群范圍進一步確定每個個體所屬小種群;利用基于平均距離聚類的選擇算子在每個小種群內(nèi)執(zhí)行選擇算子.根據(jù)個體支配等級和其所在小種群個體數(shù)量確定較優(yōu)個體,并基于平均距離聚類交叉算子對小種群內(nèi)部較優(yōu)個體執(zhí)行交叉運算.變異算子表示對所有個體進行變異操作,然后利用環(huán)境選擇對整個種群個體更新.重復上述步驟,直到滿足終止條件.需要說明的是,此處變異算子不涉及平均距離聚類,因此本文不再詳述.環(huán)境選擇為從父代種群和子代種群中選擇較優(yōu)個體,其主要涉及的選擇算子與上面所述相同,因此也不再贅述.ADCNSGA-II 詳細流程圖如圖5 所示.

圖5 ADCNSGA-II 算法流程圖Fig.5 The flowchart of ADCNSGA-II

算法4.基于平均距離聚類的NSGA-II(ADCNSGA-II)

3 實驗及結果分析

本實驗分為兩部分:1)分析ADCNSGA-II 中參數(shù)S 取不同值時對算法性能的影響;2)驗證ADCNSGA-II 算法性能.為了綜合測試算法性能,本文采用ZDT 測試函數(shù)集和SCH 測試函數(shù).ZDT測試函數(shù)集[45]由Zitzler 等在2000 年提出,有6 個測試函數(shù),本文采用其中5 個測試函數(shù),SCH[46]由Schaffer 提出.這些測試函數(shù)具有凸、凹、連續(xù)、非連續(xù)和具有多重局部最優(yōu)點等特點.

在多目標優(yōu)化領域有很多評價指標,本文采用GD 值和SP 值作為評價標準,其中,GD[47]用于評價最終解集逼近真實前沿面程度,SP[47]用于評價種群分布多樣性.通過對兩個指標分別測試,可清楚地反映算法的整體性能.

3.1 參數(shù)SSS 對算法的影響

本小節(jié)研究參數(shù)對算法ADCNSGA-II 性能的影響.實驗所用計算機為Inter Core i 5-2400 3.10 GHz CPU,6.00 GB 內(nèi)存,Windows7 操作系統(tǒng),運行環(huán)境為MATLAB7.9.每個算法獨立運行30 次,算法最大迭代100 次,種群個體為50,分別取值為1,2,3,4,5和6.

不同S 取值對算法ADCNSGA-II 性能的影響如表1 所示.其中,mean(GD)和mean(SP)分別表示算法運行30 次后GD 值和SP 值平均值.同樣,std(GD)和std(SP)分別表示算法運行30 次后GD和SP 方差.表中最優(yōu)結果用粗體標注.從表1 可以看出,在ZDT4 測試函數(shù)上,不同S 取值對算法分布多樣性和收斂效率有較大影響.但就整個測試函數(shù)而言,S=1 比S 取其他值時在算法性能上具有較大優(yōu)勢.就測試結果的數(shù)值變化范圍而言,不同S 取值對算法性能并無明顯差異.上述現(xiàn)象表明,較小S 取值(即每個小種群中個體數(shù)量較少),可以有效限制小種群內(nèi)部個體變化范圍;同時,也使多個小種群之間保持相對均勻的分布,進而保證整個種群的多樣性.

表1 參數(shù)S 對算法ADCNSGA-II 性能影響Table 1 Influence of parameter S on ADCNSGA-II

為分析不同S 取值對算法的影響,本文利用Friedman 檢驗和Wilcoxon 檢驗進一步分析上述結果.Friedman 檢驗用于分析多個樣本之間的差異,根據(jù)秩均值大小排名,秩均值越小說明算法性能越好.Wilcoxon 檢驗用于分析兩樣本是否具有顯著性差異.若p-value 小于0.05,則認為兩個算法具有顯著性差異.表2和表3 中所有數(shù)據(jù)根據(jù)算法運行30次平均GD 值求出.從表2 中可以看出,S=1 相對于S 取其他值時在ADCNSGA-II 上具有一定優(yōu)勢;從表3 中可進一步得出,不同的S 取值并沒有導致算法具有明顯的差異.從上述分析中可以得出,ADCNSGA-II 算法對于參數(shù)S 變化不敏感,即ADCNSGA-II 對參數(shù)S 具有較強的魯棒性.

表2 Friedman 測試結果Table 2 Comparison results of Friedman test

表3 Wilcoxon 檢測測試結果Table 3 Comparison results of Wilcoxon test

3.2 與其他算法實驗結果對比

為了進一步分析ADCNSGA-II (即參數(shù)S=1)的性能,本文將其與NSGA-II[34]、PNIA[48]、SPEA2[15]和g-NSGA-II[49]進行比較,其中g-NSGA-II 是Molinac 等對NSGA-II 的進一步改進算法.從表4 可以看出,在ZDT1、ZDT3和ZDT4對比結果中,ADCNSGA-II 的性能明顯優(yōu)于其他四個算法;且在ZDT2 函數(shù)上,ADCNSGA-II和SPEA2 有相似的收斂性和分布性.對于SCH 測試函數(shù),本文提出算法也具有相對較好的性能.在ZDT1～ZDT4 函數(shù)上,ADCNSGA-II 算法在分布多樣性和逼近真實前沿面方面優(yōu)于NSGA-II,在ZDT6 中,改進算法的收斂性明顯優(yōu)于NSGA-II.對比NSGA-II (此時相當于S 取值大小為種群數(shù))和表1 中S=1,2,3,4,5,6 的實驗數(shù)據(jù),可以進一步驗證前述結論.當S 取較大值時(例如S 為種群數(shù)量大小或者接近種群數(shù)量),由于每個個體在整個種群所在空間或者接近整個種群空間中變化,會導致整個種群多樣性受到減弱;較小的S 值則可以有效限制小種群內(nèi)部個體變換范圍,且使多個小種群保持相對均勻分布,從而進一步增強種群多樣性.從上述分析結果可以看出,ADCNSGA-II 有效地提高了算法多樣性.同時,解集多樣性又進一步提高了算法的收斂效率.

表4 實驗性能均值和方差對比Table 4 Means and variances of the performance metrics

為了進一步分析ADCNSGA-II 與NSGA-II 差異,本文給出了兩者之間的直觀比較.從圖6 可以看出,就解集分布多樣性和逼近真實前沿面的能力而言,NSGA-II和ADCNSGA-II 算法在函數(shù)SCH、ZDT1和ZDT2 上具有相似求解結果;但在ZDT3函數(shù)上,ADCNSGA-II 在算法逼近最優(yōu)前沿面方面明顯優(yōu)于NSGA-II,說明本文采用的基于平均距離聚類的多樣性指標能有效提高算法收斂效率.ZDT4函數(shù)是幾個測試函數(shù)中較為復雜的測試函數(shù),它具有多個局部極值點.從ZDT4 及ZDT6 的對比效果來看,ADCNSGA-II 收斂效率明顯優(yōu)于NSGA-II.從上述分析中可以看出,ADCNSGA-II 不僅能提升解集分布性,而且可以間接提高算法收斂效率;出現(xiàn)上述現(xiàn)象的原因是由于種群多樣性方面的提高使得個體間差異性變大,進而改善了全局搜索的效果.

圖6 測試結果對比Fig.6 Comparisons of obtained solutions

4 結論與展望

NSGA-II 具有較優(yōu)收斂效率,但是其采用的擁擠度距離在某些情況下不能有效保持選擇多樣性.為了解決該問題,本文借鑒聚類思想,提出了基于平均距離聚類的多樣性度量指標,并將其與NSGA-II融合,提出了ADCNSGA-II 算法.該方法利用平均距離將種群劃分為若干個小種群,根據(jù)個體支配等級和平均距離內(nèi)的個體數(shù)量選擇較優(yōu)個體,并在小種群內(nèi)進行個體交叉和變異操作.實驗結果表明,ADCNSGA-II 不僅有利于保持種群分布多樣性,還可以間接提高種群收斂效率.在后續(xù)工作中,將會進一步完善平均距離聚類的多樣性度量指標,引入其他聚類方法,使之適用于更多優(yōu)化問題.