耿煥同 李輝健 趙亞光 陳正鵬

摘要：針對(duì)經(jīng)典快速非支配排序遺傳算法（NSGAⅡ）中基于擁擠距離的種群多樣性保持策略不能客觀反映個(gè)體間真實(shí)擁擠程度的問(wèn)題，提出了一種基于自適應(yīng)混合非支配個(gè)體排序策略的改進(jìn)型NSGAⅡ算法（NSGAⅡh）。首先，設(shè)計(jì)一種新的循環(huán)聚類個(gè)體排序策略； 然后， 根據(jù)Pareto分層信息來(lái)對(duì)基于經(jīng)典擁擠距離和循環(huán)聚類的兩種個(gè)體排序策略進(jìn)行自適應(yīng)的選擇； 最終，實(shí)現(xiàn)對(duì)進(jìn)化后期的種群多樣性保持機(jī)制的改進(jìn)。通過(guò)5個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行算法驗(yàn)證，并與經(jīng)典的NSGAⅡ、多目標(biāo)粒子群優(yōu)化算法（MOPSO）和GDE3等算法進(jìn)行對(duì)比分析，NSGAⅡh算法獲得了80%的最優(yōu)反向世代距離（IGD）值，且顯著性水平為5%的雙尾t檢驗(yàn)結(jié)果表明，新算法具有明顯統(tǒng)計(jì)意義上的性能優(yōu)勢(shì)。改進(jìn)算法不僅能提高進(jìn)化種群的分布性，而且能增強(qiáng)算法的收斂性，有效提高了優(yōu)化效果。

關(guān)鍵詞：快速非支配排序遺傳算法；非支配個(gè)體排序；擁擠距離；循環(huán)聚類；自適應(yīng)

中圖分類號(hào)：TP183 文獻(xiàn)標(biāo)志碼：A

Abstract：In order to solve the problem that the population diversity preservation strategy only based on crowding distance of Nondominated Sorting Genetic AlgorithmⅡ （NSGAⅡ） cannot reflect the real crowding degree of individuals， an improved NSGAⅡ algorithm based on the adaptive hybrid nondominated individual sorting strategy （NSGAⅡh） was proposed. First， a novel loopclustering individual sorting strategy was designed. Second， according to the Pareto layersorting information the NSGAⅡh algorithm adaptively chose one from the two individual sorting strategies based on classical crowding distance and loopclustering. Finally， the diversity maintain mechanism could be improved especially during the late period of evolutionary optimization. The NSGAⅡh algorithm was compared with three classical algorithms including NSGAⅡ， MultiObjective Particle Swarm Optimization （MOPSO） and GDE3. The experiments on five multiobjective benchmark functions show that the NSGAⅡh algorithm can acquire 80% of optimal Inverted Generational Distance （IGD） values， and the corresponding twotailed ttest results at a 0.05 level of significance are remarkable. The proposed algorithm can not only improve convergence of the original algorithm， but also enhance the distribution of Pareto optimal set.

Key words：Nondominated Sorting Genetic AlgorithmⅡ （NSGAⅡ）； nondominated individual sorting； crowding distance； loopclustering； adaptive

0 引言

現(xiàn)實(shí)生產(chǎn)生活中，復(fù)雜的優(yōu)化問(wèn)題往往由多個(gè)相互沖突的優(yōu)化目標(biāo)組成，稱為多目標(biāo)優(yōu)化問(wèn)題。進(jìn)化算法已成為解決這些復(fù)雜優(yōu)化問(wèn)題的方法之一，特別是對(duì)一些傳統(tǒng)解析方法難以求解的復(fù)雜工程問(wèn)題，正越來(lái)越受到國(guó)內(nèi)外進(jìn)化算法研究學(xué)者的關(guān)注。研究表明，進(jìn)化多目標(biāo)優(yōu)化算法是解決多目標(biāo)優(yōu)化問(wèn)題的有效方法并在多項(xiàng)復(fù)雜工程優(yōu)化領(lǐng)域得到成功應(yīng)用，如航空航天技術(shù)——NASA奧德賽火星探測(cè)器自動(dòng)天線設(shè)計(jì)[1]、大型物流配送系統(tǒng)——DHL公司的貨物配送路線規(guī)劃[2]、大型建筑桁架結(jié)構(gòu)設(shè)計(jì)——鳥巢、水立方架構(gòu)優(yōu)化設(shè)計(jì)[3]等。

進(jìn)化多目標(biāo)優(yōu)化算法發(fā)展至今，大致可分為三個(gè)階段[4]：

第一階段是基于Pareto個(gè)體排序和適應(yīng)度共享機(jī)制保持群體多樣性的階段。如Fonseca等[5]提出的多目標(biāo)遺傳算法（MultiObjective Genetic Algorithm， MOGA），Srinivas等[6]提出的非支配排序遺傳算法（NonDominated Sorting Genetic Algorithm， NSGA），Horn等[7]提出的帶小生境的Pareto支配遺傳算法（Niched Pareto Genetic Algorithm， NPGA）。第二階段是以精英群體保留機(jī)制為特征的階段。如Zitzler等[8-9]提出的基于Pareto支配強(qiáng)度的多目標(biāo)進(jìn)化算法（Strength Pareto Evolutionary Algorithm， SPEA）和對(duì)其改進(jìn)后的SPEA2算法。Deb等通過(guò)對(duì)NSGA算法的改進(jìn)，提出了非常經(jīng)典的快速非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm， NSGAⅡ）[10]。第三階段更關(guān)注求解高維目標(biāo)優(yōu)化問(wèn)題，衍生出許多新型Pareto支配機(jī)制和新型進(jìn)化機(jī)制。如Brockoff等[11]提出的部分支配機(jī)制，Coello等[12]提出的多目標(biāo)粒子群優(yōu)化算法（MultiObjective Particle Swarm Optimization， MOPSO）。

NSGAⅡ算法作為進(jìn)化計(jì)算領(lǐng)域最為經(jīng)典的算法之一。雖然常作為對(duì)比算法驗(yàn)證改進(jìn)后算法的優(yōu)劣，但是其自身還存在一定的缺陷，即單一采用擁擠距離大小進(jìn)行同層群體多樣性保持并不能客觀反映個(gè)體間的真實(shí)擁擠程度，特別是種群進(jìn)化后期，隨著非支配解集的增大，該缺陷愈加明顯。這就直接影響到了種群的多樣性，最終影響到尋得Pareto解集的優(yōu)劣。近年來(lái)，進(jìn)化計(jì)算領(lǐng)域針對(duì)非支配個(gè)體排序的研究已經(jīng)取得了一些成果，如羅辭勇等[13]提出了采用循環(huán)擁擠排序策略的改進(jìn)NSGAⅡ算法，該算法雖然在一定程度上提高了種群多樣性，但算法執(zhí)行效率偏低，尤其是在種群進(jìn)化后期，隨著非支配解的不斷增多，計(jì)算復(fù)雜度迅速增加。Fortin等[14]針對(duì)擁擠距離策略對(duì)非支配個(gè)體密度估計(jì)不準(zhǔn)確這一問(wèn)題，提出了新的個(gè)體排序策略，即采用新的個(gè)體適應(yīng)度算子代替擁擠距離算子對(duì)非支配解進(jìn)行排序，該算法在不增加時(shí)間復(fù)雜度的情況下，提高了算法的收斂性和分布性；但算法在解決高維目標(biāo)優(yōu)化問(wèn)題時(shí)還需要進(jìn)一步優(yōu)化驗(yàn)證。Mohapatra等[15]先通過(guò)挖掘同層非支配個(gè)體信息產(chǎn)生一組分布均勻的虛擬均值個(gè)體；然后依據(jù)原非支配個(gè)體的擁擠程度，用虛擬個(gè)體對(duì)原個(gè)體進(jìn)行有選擇的替換；進(jìn)而計(jì)算個(gè)體的適應(yīng)度值，對(duì)個(gè)體進(jìn)行排序選擇；最后將該策略代替NSGAⅡ中的擁擠距離策略，提出了基于均值個(gè)體的改進(jìn)NSGAⅡ算法，該算法有效地提高了種群的分布性。

本文針對(duì)經(jīng)典NSGAⅡ算法中的基于擁擠距離策略不能客觀反映個(gè)體間的真實(shí)擁擠程度的不足，提出一種基于自適應(yīng)混合非支配個(gè)體排序策略的改進(jìn)型NSGAⅡ算法。其思想是首先設(shè)計(jì)一種新的循環(huán)聚類個(gè)體排序策略，然后根據(jù)Pareto分層信息來(lái)對(duì)基于經(jīng)典擁擠距離和循環(huán)聚類的兩種個(gè)體排序策略進(jìn)行自適應(yīng)的選擇，改進(jìn)進(jìn)化后期的多樣性保持機(jī)制，以增強(qiáng)改進(jìn)型NSGAⅡ算法的優(yōu)化效果。

2 經(jīng)典NSGAⅡ算法存在的問(wèn)題

2.1 NSGAⅡ算法回顧

2002年Deb等在NSGA基礎(chǔ)上提出了快速帶精英策略的NSGAⅡ算法。主要改進(jìn)之處有：首先，設(shè)計(jì)了基于合并父代種群和子代種群的精英保留策略；其次，通過(guò)快速非支配排序策略降低算法計(jì)算復(fù)雜度；再者，采用擁擠距離策略代替適應(yīng)度共享策略來(lái)實(shí)現(xiàn)更具可操作性的非支配個(gè)體排序方法。NSGAⅡ算法流程如下：

步驟1 群體初始化。隨機(jī)產(chǎn)生包含N個(gè)個(gè)體的初始種群Pt（t=0），Qt=。

步驟2 適應(yīng)度計(jì)算。合并Pt和Qt種群得Rt={Pt∪Qt}，依據(jù)評(píng)估函數(shù)對(duì)種群Rt進(jìn)行個(gè)體適應(yīng)度計(jì)算。

步驟3 Pareto分層非支配排序與個(gè)體擁擠距離計(jì)算。

3.1） k=1，R′t=Rt；

3.2）從種群R′t提取出Pareto最優(yōu)解集PSk，R′t=R′t-PSk，k=k+1；

3.3）若R′t≠，則轉(zhuǎn)3.2）；

3.4） 計(jì)算種群Rt中每個(gè)個(gè)體的擁擠距離。

步驟4 進(jìn)化操作。

4.1）依據(jù)每一個(gè)個(gè)體的Pareto分層數(shù)和擁擠距離，從Rt選出前N個(gè)個(gè)體作為下一代種群Pt+1；

4.2）對(duì)種群Pt+1進(jìn)行交叉操作生成群體Qt+1，并對(duì)Qt+1進(jìn)行變異操作。

步驟5 算法終止判斷。t=t+1，判斷t是否大于最大迭代次數(shù)MaxGen，若是則輸出Pt中的非支配個(gè)體作為Pareto最優(yōu)解集，且算法結(jié)束；否則，轉(zhuǎn)到步驟2。

基于群體的進(jìn)化多目標(biāo)優(yōu)化算法的關(guān)鍵所在是尋找一種合理的個(gè)體排序方法，將個(gè)體間的偏序關(guān)系轉(zhuǎn)換成利于搜索的全序關(guān)系；而NSGAⅡ算法采用Pareto分層及擁擠距離的方法來(lái)對(duì)個(gè)體排序，進(jìn)化后期個(gè)體擁擠距離成為個(gè)體排序的決定因素，因此對(duì)個(gè)體擁擠距離策略的深入分析是非常必要的。

2.2 擁擠距離策略存在的不足分析

回顧NSGAⅡ算法中個(gè)體擁擠距離的計(jì)算過(guò)程可知：根據(jù)群體中不同個(gè)體在同一個(gè)目標(biāo)函數(shù)上的數(shù)值大小，進(jìn)行從小到大個(gè)體排序，排序后除首、尾兩個(gè)體擁擠距離為∞外，其他個(gè)體的擁擠距離為前、后兩個(gè)體在此目標(biāo)值的差值除以該目標(biāo)上的最大值與最小值的差值；對(duì)每一個(gè)個(gè)體在每一個(gè)目標(biāo)函數(shù)上的擁擠距離進(jìn)行相加求和，就得到每個(gè)體的擁擠距離值。通過(guò)實(shí)驗(yàn)分析，發(fā)現(xiàn)基于擁擠距離策略的個(gè)體排序方法存在著不足，即單一采用擁擠距離大小進(jìn)行群體多樣性保持并不能客觀反映個(gè)體間的真實(shí)擁擠程度。

為更好地分析該策略存在的不足，以NSGAⅡ算法求解多目標(biāo)優(yōu)化標(biāo)準(zhǔn)測(cè)試函數(shù)ZDT1問(wèn)題為例，選取進(jìn)化過(guò)程中某一代的首層Pareto最優(yōu)個(gè)體集（見(jiàn)2.1節(jié)步驟3中種群Rt分層排序得到的首層Pareto最優(yōu)解集PS1）為分析對(duì)象，共有18個(gè)非支配個(gè)體，個(gè)體的分布情況見(jiàn)圖1（a）所示，所有個(gè)體的兩目標(biāo)函數(shù)值及擁擠距離值見(jiàn)表1所示。

按照基于擁擠距離策略的個(gè)體排序方法進(jìn)行選擇，現(xiàn)假設(shè)需從中選擇9個(gè)非支配個(gè)體進(jìn)入下一代群體，將得到圖1（b）中的個(gè)體，其余個(gè)體將被淘汰。從圖1（b）可看出，由于擁擠距離策略存在的不足導(dǎo)致個(gè)體f和p之間出現(xiàn)了搜索盲區(qū)，致使多樣性保持缺乏，勢(shì)必影響算法搜索效率和解集的均勻分布性。

從上述分析可知，當(dāng)NSGAⅡ算法采用基于擁擠距離策略的個(gè)體排序方法進(jìn)行篩選個(gè)體時(shí)，當(dāng)擁擠距離較小和較大的個(gè)體分布都較為聚集時(shí)，篩選后的解集分布性不夠理想，即單一采用擁擠距離大小進(jìn)行群體多樣性保持并不能客觀反映個(gè)體間的真實(shí)擁擠程度。究其原因是個(gè)體的擁擠距離計(jì)算僅依賴于其相鄰兩個(gè)體的位置信息，沒(méi)有考慮種群中其他個(gè)體的位置信息。

3 NSGAⅡh算法

為改進(jìn)基于擁擠距離策略的個(gè)體排序方法存在的不足，文中將增加基于聚類分析的個(gè)體選擇方法；在進(jìn)化過(guò)程中，根據(jù)每代首層Pareto最優(yōu)個(gè)體集的規(guī)模大小來(lái)自適應(yīng)確定采用擁擠距離策略還是聚類選擇策略。

3.1 新型個(gè)體聚類選擇策略

為克服NSGAⅡ算法中擁擠距離在保持種群多樣性上的不足，本文增加聚類排序策略來(lái)進(jìn)行個(gè)體選擇，簡(jiǎn)稱為個(gè)體聚類選擇策略。聚類分析屬于數(shù)據(jù)挖掘技術(shù)，旨在將一組同類樣本劃分為多個(gè)類簇，力求類間相異、類內(nèi)相似。常見(jiàn)的聚類算法有KMedoids和KMeans算法，為選擇能保持具有更好多樣性的個(gè)體以及不同聚類算法的特點(diǎn)，文中選用KMedoids算法作為同一層個(gè)體的聚類算法，結(jié)合Pareto非支配個(gè)體集的選擇好壞對(duì)種群多樣性保持的重要影響。為方便敘述，不妨以2目標(biāo)優(yōu)化問(wèn)題為例，聚類數(shù)設(shè)為c，要求從規(guī)模為Np的非支配群體P中選擇Nc個(gè)個(gè)體作為下一代進(jìn)化群體，主要步驟具體如下。

第一步 設(shè)計(jì)一種新的聚類初始點(diǎn)選取策略來(lái)確定聚類初始點(diǎn)。已有文獻(xiàn)[16-17]表明聚類效果依賴于聚類初始點(diǎn)的選取，同時(shí)考慮到非支配個(gè)體選擇對(duì)群體多樣性保持的影響，本文專門設(shè)計(jì)了一種基于各聚類大小分布均勻新的聚類初始點(diǎn)選取策略。具體為在已知聚類數(shù)的情況下，首先選取每一個(gè)目標(biāo)函數(shù)的最大值與最小值個(gè)體直接進(jìn)入下一代進(jìn)化群體；然后依次以每個(gè)目標(biāo)的最大和最小值為邊界，將中間區(qū)域劃分為c-2等份，統(tǒng)計(jì)每等分區(qū)間中非支配個(gè)體的數(shù)目；接著依次按式（2）計(jì)算每個(gè)目標(biāo)上不同區(qū)間的均勻分布方差D（fi），以D（fi）最小的目標(biāo)函數(shù)作為劃分；最后從選定的劃分區(qū)域中隨機(jī)挑選一個(gè)作為聚類初始個(gè)體。圖2是采用基于各聚類大小分布均勻的聚類初始點(diǎn)選取策略，從20個(gè)非支配個(gè)體選取3個(gè)初始聚類個(gè)體的實(shí)現(xiàn)過(guò)程。

其中：N為種群規(guī)模，t當(dāng)前進(jìn)化代數(shù)，MaxGen為進(jìn)化過(guò)程的最大迭代次數(shù)。在進(jìn)化前期，待聚類的首層Pareto最優(yōu)解集中規(guī)模相對(duì)較少，選取較小的聚類數(shù)目c將提高算法的探索能力，增強(qiáng)算法的收斂性能；而在進(jìn)化的后期，通過(guò)逐漸增加聚類數(shù)，將提高算法的探究能力，以便更好地保持群體分布性。

3.3 自適應(yīng)混合非支配個(gè)體排序的改進(jìn)型NSGAⅡ算法

通過(guò)引入新的混合個(gè)體排序策略來(lái)改進(jìn)NSGAⅡ算法中的擁擠距離策略，本文提出了基于自適應(yīng)混合個(gè)體排序策略的改進(jìn)型NSGAⅡ算法（NSGAⅡ based on Adaptive Hybrid Individual Sorting， NSGAⅡh）。除步驟4外，該算法的主要流程與2.1節(jié)中NSGAⅡ類似，不再贅述。下面僅給出步驟4的具體實(shí)現(xiàn)過(guò)程。

步驟4 進(jìn)化操作。

4.1）判斷Pareto首層的規(guī)模是否小于種群規(guī)模N，若是則采用Pareto分層和擁擠距離策略，Rt選出前N個(gè)個(gè)體作為下一代種群Pt+1；否則，依據(jù)式（3）計(jì)算聚類數(shù)c，采用基于自適應(yīng)混合非支配個(gè)體排序策略，Rt選出前N個(gè)個(gè)體作為下一代種群Pt+1。

4.2）對(duì)種群Pt+1進(jìn)行交叉操作生成群體Qt+1，并對(duì)Qt+1 進(jìn)行變異操作。

由于3.1節(jié)中對(duì)新型個(gè)體聚類選擇策略進(jìn)行了時(shí)間復(fù)雜度的分析，當(dāng)優(yōu)化的目標(biāo)數(shù)遠(yuǎn)小于進(jìn)化群體的規(guī)模時(shí)，其時(shí)間復(fù)雜度與經(jīng)典NSGAⅡ中非支配個(gè)體Pareto分層的時(shí)間復(fù)雜度O（N2）相同。因此，基于自適應(yīng)混合非支配個(gè)體排序策略的改進(jìn)型NSGAⅡ算法的時(shí)間復(fù)雜度與經(jīng)典的NSGAⅡ算法也相同。

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

4.1 測(cè)試函數(shù)

實(shí)驗(yàn)時(shí)，選取當(dāng)前進(jìn)化多目標(biāo)優(yōu)化領(lǐng)域普遍使用的標(biāo)準(zhǔn)測(cè)試函數(shù)ZDT（ZitzlerDebThiele）[18]系列和SCH[19]來(lái)檢驗(yàn)算法的優(yōu)化效果，具體的函數(shù)描述見(jiàn)表2。這些函數(shù)包含了連續(xù)函數(shù)、非連續(xù)函數(shù)、凹函數(shù)、凸函數(shù)等多種復(fù)雜類型。

4.2 實(shí)驗(yàn)設(shè)計(jì)與主要參數(shù)設(shè)置

為了測(cè)試NSGAⅡh算法的優(yōu)化性能，分別與經(jīng)典的NSGAⅡ算法、MOPSO算法、GDE3算法[20]進(jìn)行對(duì)比，檢驗(yàn)算法的改進(jìn)效果。算法均采用相同的參數(shù)設(shè)置：種群規(guī)模N=100，運(yùn)行代數(shù)MaxGen=300；交叉概率設(shè)置為Pm=0.9，變異概率設(shè)置為Pc=0.1；每個(gè)算法對(duì)每個(gè)問(wèn)題獨(dú)立運(yùn)行30次。

4.3 評(píng)價(jià)指標(biāo)IGD

為更科學(xué)地比較不同算法得到的Pareto解集的收斂性和多樣性，文中采用多目標(biāo)優(yōu)化領(lǐng)域普遍使用的綜合性指標(biāo)反向世代距離（Inverted Generational Distance， IGD）來(lái)進(jìn)行比較算法，此指標(biāo)是度量真實(shí)Pareto前沿到算法得到的近似Pareto前沿之間距離，指標(biāo)值越小，說(shuō)明算法得到的Pareto解集的收斂性和多樣性越好，越接近真實(shí)Pareto前沿。IGD計(jì)算公式如下：

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

為了對(duì)比NSGAⅡh和各對(duì)比算法的優(yōu)劣，圖3～圖7分別是兩個(gè)算法在各個(gè)測(cè)試函數(shù)上獲得的最優(yōu)解集，算法設(shè)置相同參數(shù)和相同初始種群。

從圖3～圖7可以直觀地看出，NSGAⅡh算法無(wú)論在分布性還是收斂性上都取得了更為理想的結(jié)果，而MOPSO的分布性和收斂性均表現(xiàn)最差。例如，對(duì)于ZDT1測(cè)試問(wèn)題，NSGAⅡh和GDE3算法具有最好的分布性和收斂性，NSGAⅡ具有較好的收斂性，但是部分區(qū)域沒(méi)有被Pareto最優(yōu)解覆蓋，分布性方面出現(xiàn)了不均勻現(xiàn)象，而MOPSO算法并沒(méi)有收斂，分布性也不夠理想。再如，對(duì)于ZDT2測(cè)試問(wèn)題，GDE3算法具有最好收斂性和分布性，雖然本算法在個(gè)別點(diǎn)上分布性稍有遜色，但同樣具有良好的收斂性。而NSGAⅡ算法雖然收斂性較好，但分布性略顯不夠；而MOPSO收斂性和分布性均最差。因此從實(shí)驗(yàn)結(jié)果來(lái)看NSGAⅡh不僅具有較強(qiáng)的尋優(yōu)能力，而且能保持較好的最優(yōu)前沿分布性。

為更細(xì)致地定量分析算法優(yōu)劣，表3列出了NSGAⅡh和對(duì)比算法在各個(gè)測(cè)試問(wèn)題上的IGD性能指標(biāo)值，同時(shí)參考文獻(xiàn)[21]做法給出ttest指標(biāo)值，其中，IGD的平均值（mean）和方差值（std）是同一算法在同一測(cè)試問(wèn)題上獨(dú)立運(yùn)行30次的統(tǒng)計(jì)結(jié)果，同時(shí)ttest值是本文算法與3種對(duì)比算法在同一測(cè)試問(wèn)題上進(jìn)行t檢驗(yàn)時(shí)的t值（“+”“=”和“-”表示本文算法獲得的IGD 值在顯著性水平為5%的雙尾t檢驗(yàn)中分別優(yōu)于、等于和劣于對(duì)應(yīng)列的對(duì)比算法在對(duì)應(yīng)行的測(cè)試問(wèn)題上的顯著性區(qū)分結(jié)果）。

分析表3的IGD指標(biāo)數(shù)據(jù)可知，NSGAⅡh算法在5個(gè)測(cè)試函數(shù)上獲得了4個(gè)最優(yōu)IGD值，GDE3獲得了1個(gè)最優(yōu)IGD值，NSGAⅡ與MOPSO算法均未獲得最優(yōu)IGD值。同時(shí)，對(duì)t檢驗(yàn)結(jié)果分析可知，NSGAⅡh算法在上述測(cè)試函數(shù)上具有明顯統(tǒng)計(jì)意義上的性能優(yōu)勢(shì)。綜上分析可知，與NSGAⅡ、MOPSO和GDE3算法相比，NSGAⅡh算法獲得的解集具有更好的收斂性和分布性。這說(shuō)明通過(guò)本文提出的混合個(gè)體排序策略不僅能提高種群分布性，而且能提高算法的收斂性。

5 結(jié)語(yǔ)

通過(guò)對(duì)NSGAⅡ算法中基于擁擠距離個(gè)體排序策略在進(jìn)化后期多樣性保持不足的分析，設(shè)計(jì)并提出了一種基于自適應(yīng)混合非支配個(gè)體排序策略的改進(jìn)型NSGAⅡ算法。算法實(shí)現(xiàn)上提出了新型個(gè)體聚類選擇策略和自適應(yīng)混合非支配個(gè)體排序策略等，以實(shí)現(xiàn)對(duì)進(jìn)化后期的多樣性保持機(jī)制的改進(jìn)。在實(shí)驗(yàn)部分，選取了5個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試，并與NSGAⅡ、MOPSO、GDE3算法進(jìn)行對(duì)比，NSGAⅡh算法獲得了80%的最優(yōu)IGD值；并從顯著性水平為5%的雙尾t檢驗(yàn)結(jié)果可知，NSGAⅡh算法具有明顯統(tǒng)計(jì)意義上的性能優(yōu)勢(shì)。NSGAⅡh算法在不提高算法時(shí)間復(fù)雜度的情況下，不僅有效提高了解集的分布性，而且具有更好的收斂性；與此同時(shí)，文中提出的自適應(yīng)混合非支配個(gè)體排序策略由于不受優(yōu)化目標(biāo)維數(shù)影響，因此可用于高維目標(biāo)優(yōu)化問(wèn)題求解中，實(shí)現(xiàn)對(duì)進(jìn)化高維目標(biāo)優(yōu)化算法中的非支配個(gè)體排序進(jìn)行有益的探索。

參考文獻(xiàn)：

[1]HORNBY G S， GLOBUS A， LINDEN D S， et al. Automated antenna design with evolutionary algorithms[C]// SPACE Conferences and Exposition. San Jose： AIAA， 2006： 19-21.

[2]WEISE T， PODLICH A， REINHARD K， et al. Evolutionary Freight Transportation Planning[M]. Berlin： Springer， 2009： 768-777.

[3]HOVESTADT L， DANAHER T. Beyond the Grid： Architecture and Information Technology Applications of a Digital Architectonic[M]. Boston： Birkhauser， 2010：273-274.

[4]公茂果， 焦李成， 楊咚咚， 等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào)， 2009， 20（2）：271-289.（GONG M G， JIAO L C， YANG D D， et al. Research on evolutionary multiobjective optimization algorithms[J]. Journal of Software， 2009， 20（2）：271-289.）

[5]FONSECA C M， FLEMING P J. Genetic algorithms for multiobjective optimization： formulation discussion and generalization[C]// Proceedings of the 5th International Conference on Genetic Algorithms. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 1993： 416-423.

[6]SRINIVAS N， DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation， 1994， 2（3）： 221-248.

[7]HORN J， NAFPLIOTIS N， GOLDBERG D E. A niched Pareto genetic algorithm for multiobjective optimization[C]// Proceedings of the 1st IEEE Conference on Evolutionary Computation. Piscataway， NJ： IEEE， 1994： 82-87.

[8]ZITZLER E， THIELE L. Multiobjective evolutionary algorithms： a comparative case study and the strength Pareto approach [J]. IEEE Transactions on Evolutionary Computation， 1999， 3（4）： 257-271.

[9]ZITZLER E， LAUMANNS M， THIELE L. SPEA2： improving the strength Pareto evolutionary algorithm[C]// Evolutionary Methods for Design， Optimization and Control with Applications to Industrial Problems. Berlin： SpringerVerlag， 2002： 95-100.

[10]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.

[11]BROCKHOFF D， ZITZLER E. Are All Objectives Necessary on Dimensionality Reduction in Evolutionary Multiobjective Optimization[M]. Berlin： Springer， 2006， 4193：533-542.

[12]COELLO C A C， PULIDO G T， LECHUGA M S. Handling multiple objectives with particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

[13]羅辭勇，陳民鈾，張聰譽(yù). 采用循環(huán)擁擠排序策略的改進(jìn)NSGAⅡ算法[J]. 控制與決策，2010，25（2）：227-231.（LUO C Y， CHEN M Y， ZHANG C Y. Improved NSGAⅡ algorithm with circular crowded sorting[J]. Control and Decision， 2010， 25（2）： 227-231.）

[14]FORTIN F A， PARIZEAU M. Revisiting the NSGAⅡ crowdingdistance computation[C]// Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. New York： ACM， 2013： 623-630.

[15]MOHAPATRA P， ROY S. APNSGAⅡ： an evolutionary multiobjective optimization algorithm using averagepointbased NSGAⅡ[C]// Proceedings of 4th International Conference on Soft Computing for Problem Solving. Berlin： Springer， 2015： 565-575.

[16]PATEL G K， DABHI V K， PRAJAPATI H B. Study and analysis of particle swarm optimization for improving partition clustering[C]// Proceedings of the 2015 IEEE International Conference on Advances in Computer Engineering and Applications. Piscataway， NJ： IEEE， 2015： 218-225.

[17]LI Q， LIU X. A Kmedoids Clustering Algorithm with Initial Centers Optimized by a P System[M]. Berlin： Springer International Publishing， 2015： 488-500.

[18]ZITZLER E， DEB K， THIELE L. Comparison of multiobjective evolutionary algorithms： empirical results[J]. IEEE Transactions on Evolutionary Computation， 2000， 8（2）： 173-195.

[19]SCHAFER J D. Multiobjective optimization with vector evaluated genetic algorithm[C]// Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale， NJ： L. Erlbaum Associates Inc.， 1985： 93-100.

[20]KUKKONEN S， LAMPINEN J. Performance assessment of generalized differential evolution 3 with a given set of constrained multiobjective test problems[C]// Proceedings of the 11th Conference on Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2009：1943-1950.

[21]胡旺，YEN G G，張?chǎng)? 基于Pareto熵的多目標(biāo)粒子群優(yōu)化算法[J]. 軟件學(xué)報(bào)，2014，25（5）：1025-1050.（HU W， YEN G G， ZHANG X. Multiobjective particle swarm optimization based on Pareto entropy[J].Journal of Software， 2014， 25（5）： 1025-1050.）