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

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

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

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

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

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

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

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

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

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

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

1 基本NSGA-II 框架

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

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

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

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

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

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

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

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

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

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

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

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

2.1 匹配選擇

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

算法1.匹配選擇算子

2.2 平均距離聚類的多樣性指標(biāo)

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

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

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

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

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

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

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

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

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

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

算法2.平均距離多樣性指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

表2 Friedman 測試結(jié)果Table 2 Comparison results of Friedman test

表3 Wilcoxon 檢測測試結(jié)果Table 3 Comparison results of Wilcoxon test

3.2 與其他算法實(shí)驗(yàn)結(jié)果對比

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

表4 實(shí)驗(yàn)性能均值和方差對比Table 4 Means and variances of the performance metrics

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

圖6 測試結(jié)果對比Fig.6 Comparisons of obtained solutions

4 結(jié)論與展望

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