基于自適應(yīng)多目標(biāo)指數(shù)罰函數(shù)的NSGA-II算法

王　聰， 趙文玲

(山東理工大學(xué) 理學(xué)院， 山東 淄博 255049)

?

基于自適應(yīng)多目標(biāo)指數(shù)罰函數(shù)的NSGA-II算法

王聰， 趙文玲

(山東理工大學(xué) 理學(xué)院， 山東 淄博 255049)

摘要：為求解多目標(biāo)優(yōu)化問(wèn)題，將快速非支配進(jìn)化算法(NSGA-II)進(jìn)行了推廣，構(gòu)造了一種新的多目標(biāo)指數(shù)罰函數(shù)，將其作為NSGA-II算法的適應(yīng)度函數(shù)，通過(guò)每次自適應(yīng)更新罰因子，以此獲得多目標(biāo)規(guī)劃問(wèn)題的有效解(Pareto解).仿真結(jié)果表明，該算法在快速收斂的情況下，能夠獲得更加均勻的Pareto前沿.

關(guān)鍵詞：多目標(biāo)規(guī)劃； 罰函數(shù)； NSGA-II算法； 自適應(yīng)罰因子； 約束優(yōu)化

工程中的很多問(wèn)題被描述為數(shù)學(xué)優(yōu)化問(wèn)題，可以根據(jù)目標(biāo)函數(shù)的數(shù)目將其分為單目標(biāo)優(yōu)化問(wèn)題和多目標(biāo)優(yōu)化問(wèn)題.但在實(shí)際中，很多問(wèn)題都被描述為帶有復(fù)雜約束的多目標(biāo)規(guī)劃問(wèn)題，因此研究求解此類(lèi)問(wèn)題的算法具有重要的意義.

目前處理帶有復(fù)雜約束的多目標(biāo)規(guī)劃，主要用到罰函數(shù)方法與NSGA-II算法結(jié)合[1-2]以及一些改進(jìn)的NSGA-II算法[3-5].罰函數(shù)法是處理帶有約束的優(yōu)化問(wèn)題常用的方法之一，其中包括序列無(wú)約束極小化技術(shù)法(SUMT)，增廣拉格朗日罰函數(shù)法，精確罰函數(shù)法等[6].由于這些算法所構(gòu)造的罰函數(shù)以及罰因子的選取不當(dāng)，很大程度上降低了NSGA-II算法效率，使得罰函數(shù)法在處理帶有約束的多目標(biāo)規(guī)劃問(wèn)題時(shí)略顯無(wú)力.而對(duì)于改進(jìn)NSGA-II算法，雖然避開(kāi)了罰因子的選取問(wèn)題，但是由于需要引進(jìn)了輔助算子，在一定程度上丟失了NSGA-II算法的原有的優(yōu)點(diǎn).

鑒于以上缺陷，本文提出了一種自適應(yīng)多目標(biāo)指數(shù)罰函數(shù)的NSGA-II算法，構(gòu)造新的指數(shù)罰函數(shù)，將該指數(shù)罰函數(shù)作為NSGA-II算法的適應(yīng)度函數(shù)，在迭代過(guò)程中結(jié)合NSGA-II算法的特點(diǎn)，自適應(yīng)更新罰因子，將帶有約束的多目標(biāo)規(guī)劃模型轉(zhuǎn)化為無(wú)約束多目標(biāo)指數(shù)罰函數(shù)模型.這種算法不僅成功地解決了罰因子的選取問(wèn)題，而且最大程度的保留了NSGA-II算法原有的優(yōu)點(diǎn)，增加了該算法的適用性.

1一種新的多目標(biāo)指數(shù)罰函數(shù)模型

對(duì)于單目標(biāo)規(guī)劃問(wèn)題(P):

(1)

其中，目標(biāo)函數(shù)和約束函數(shù)都是連續(xù)可微.1994年，R.Cominetti等人提出了指數(shù)罰函數(shù)[7]，形式如下:

(2)

其中，λ>0.并且指出，這一類(lèi)罰函數(shù)是簡(jiǎn)單光滑，但不是精確的.

最近，張連生等[8]在文獻(xiàn)中對(duì)單目標(biāo)規(guī)劃提出一種新的指數(shù)罰函數(shù):

(3)

其中，μ>0，λi≥0，這種指數(shù)罰函數(shù)是簡(jiǎn)單的、光滑的、精確的.

本文將這種思路引入到多目標(biāo)規(guī)劃中，構(gòu)造新的多目標(biāo)指數(shù)罰函數(shù).

考慮多目標(biāo)規(guī)劃問(wèn)題(VP):

(4)

對(duì)(VP)構(gòu)造了一種新的指數(shù)罰函數(shù)，將其轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題(VP1):

(5)

其中，μ>0是罰因子. 將該模型作為NSGA-II算法的適應(yīng)度函數(shù)，結(jié)合NSGA-II算法的特點(diǎn)對(duì)罰因子進(jìn)行自適應(yīng)更新，進(jìn)行求解.

2NSGA-II算法

考慮如下只帶有線性約束的多目標(biāo)規(guī)劃模型(LVP)

minF(x)={f1(x),f2(x),…,fp(x)}

其中，x,l,u為n維向量，a為m維向量，b為p維向量，A為m×n維矩陣，B為p×n維矩陣.

NSGA-II是求解(LVP)常用的進(jìn)化算法，該算法主要包括非支配排序算子，擁擠度算子，選擇算子，精英保留算子[9].

快速非支配排序算子根據(jù)偏序的定義，初步判斷種群中個(gè)體的優(yōu)劣程度.

算法步驟:

Step1初始化集合Sp，用來(lái)保存被p所支配的個(gè)體，初始化np=0，用來(lái)記錄被p所支配個(gè)體的數(shù)目；

Step2對(duì)于每個(gè)在種群中個(gè)體q，若個(gè)體p支配個(gè)體q，則將q包含在Sp中，若q支配p，則np=np+1；

Step3若np=0，則表示沒(méi)有個(gè)體可以支配p,將p放入第一前端F1，并且令p的序值為1，若遍歷完種群的每個(gè)個(gè)體，則進(jìn)行Step2，否則，返回Step1，繼續(xù)尋找序值為1的個(gè)體，并且更新集合F1.

在對(duì)整個(gè)種群進(jìn)行完遍歷后，可以得到第一前端F1，然后在集合Sp中尋找剩余的前端.

算法步驟:

Step1初始化前端計(jì)數(shù)i=1.

Step2初始化集合Q為空集，將其作為第i+1個(gè)前端中個(gè)體的存儲(chǔ)集合.

Step3遍歷Fi中的個(gè)體p，對(duì)于在Sp中的每個(gè)個(gè)體q，nq=nq-1，若nq=0，則表示在子集中，沒(méi)有個(gè)體可以支配q，令q的序值為i+1，將q放入集合Q.

Step4令i=i+1，F(xiàn)i=Q，并且返回Step2.

通過(guò)以上操作，可以確定種群中每個(gè)個(gè)體的序值，和每個(gè)個(gè)體支配的集合，以及支配個(gè)體的數(shù)目.

擁擠距離算子是計(jì)算種群中屬于同一序值的每個(gè)個(gè)體之間的歐式距離，只有在序值相同時(shí)，才有距離比較的意義.首先，將位于某前端兩個(gè)端點(diǎn)的個(gè)體的擁擠距離設(shè)為無(wú)窮大，對(duì)于不是端點(diǎn)的個(gè)體，計(jì)算方法是求得該個(gè)體和前后兩個(gè)目標(biāo)函數(shù)值大小接近的個(gè)體的目標(biāo)函數(shù)值之差.

選擇算子采用錦標(biāo)賽選擇算法，對(duì)于種群中的每個(gè)個(gè)體，有兩個(gè)屬性可以判斷其優(yōu)劣程度.在整個(gè)種群中，首先根據(jù)序值選擇出序值小的個(gè)體，對(duì)于屬于同一序值的個(gè)體，選擇擁擠距離大的個(gè)體，這樣既能使得種群中優(yōu)秀的個(gè)體保存下來(lái)，又能增加種群的多樣性.

將各個(gè)算子結(jié)合到一起，得到NSGA-II算法.

算法步驟:

Step1初始化種群，設(shè)定種群數(shù)目，變異參數(shù)，交叉參數(shù)，初始迭代代數(shù)i=0，最大代數(shù)G.

Step2計(jì)算個(gè)體的序值，擁擠距離，進(jìn)行選擇操作.

Step3對(duì)選擇出來(lái)的子種群進(jìn)行交叉和變異操作，將子種群與父代種群合并.

Step4對(duì)合并后的種群進(jìn)行裁剪操作，產(chǎn)生與初始種群數(shù)目相同的新種群，并且，令i=i+1:若i等于G，則終止迭代，輸出結(jié)果，否則，轉(zhuǎn)Step2.

3自適應(yīng)算法步驟及數(shù)值仿真

現(xiàn)有算法的普通罰因子更新策略為

μk=Kk+μk-1

(6)

其中K為大于0的常數(shù)，k是迭代次數(shù)，在初始化時(shí)，很難選擇合適的K，若K選擇過(guò)小，會(huì)影響罰因子的增加速度，若K選擇過(guò)大，會(huì)使得迭代末期整個(gè)種群中可行解個(gè)體的比例降低，所以通常采取試探的方法，尋找合適的K，這樣大大降低了算法的運(yùn)行效率，增加了運(yùn)行時(shí)間.

下面提出一種新的自適應(yīng)罰因子更新策略:

μk=μk-1(1+eρ+1)

(7)

其中ρ表示在前一次迭代后，整個(gè)種群中，可行解個(gè)體所占的比例.因此，0≤ρ≤1，并且隨著迭代的進(jìn)行，種群中可行解比例越來(lái)越高，即ρ趨近于1.在算法運(yùn)行初期，由于可行解比例比較小，罰因子較大，因此可以搜索盡可能多的可行解，在算法后期，罰因子減小，因此可以在可行解中搜索盡可能多的最優(yōu)解，由于引進(jìn)了自適應(yīng)搜索，使得當(dāng)種群中可行解比例趨近于1時(shí)，罰因子更快速趨近于0，提升了算法效率，成功地解決了K的選取問(wèn)題.

下面給出本文的算法.

基于自適應(yīng)多目標(biāo)指數(shù)罰函數(shù)的NSGA-Ⅱ算法步驟:

Step1給定罰函數(shù)參數(shù)向量μ0，λ0，終止條件ε，以及初始次數(shù)k=1.

Step2構(gòu)造多目標(biāo)指數(shù)罰函數(shù)序列:

將其作為適應(yīng)度函數(shù)，用NSGA-II算法求解該模型，計(jì)算每一次迭代后種群中可行解比例ρ，若‖Xk-Xk-1‖≤ε，則輸出結(jié)果，否則轉(zhuǎn)Step3.

下面應(yīng)用此算法求解算例1、算例2.

算例1

表1可行解比例與罰參數(shù)關(guān)系

1234ρ0.31000.80500.97000.9980μ4.706233.319272.242279.84.706233.319272.242279.8

圖1　例1迭代過(guò)程與Pareto解

下面對(duì)算例1利用普通罰因子更新策略式(6)進(jìn)行數(shù)值仿真，并與自適應(yīng)罰因子更新策略式(7)進(jìn)行比較.在式(6)中分別選擇當(dāng)K=1,10,40,100,得到表2.

表2普通罰因子與自適應(yīng)罰因子比較

K=1K=10K=40K=100自適應(yīng)迭代次數(shù)147534運(yùn)行時(shí)間/s4922.912.99.8711.9可行解比例0.9900.9930.9890.9550.998

圖2　例1最終迭代與Pareto解

由表2可以看出，若初始值K選擇過(guò)小，則增加了算法的迭代次數(shù)和程序運(yùn)行時(shí)間；若K選擇過(guò)大，雖然迭代次數(shù)減少了，但是在最后的Pareto解中，可行解比例明顯下降.從表2中可以看出自適應(yīng)更新策略不僅在迭代次數(shù)和運(yùn)行時(shí)間，以及最終可行解比例方面，都優(yōu)于非自適應(yīng)罰因子.

圖3　例2迭代過(guò)程與Pareto解

圖4　例2最終迭代與Pareto解

本文提出的多目標(biāo)指數(shù)罰函數(shù)，將其作為NSGA-II的適應(yīng)度函數(shù)，并且結(jié)合多目標(biāo)遺傳算法的特點(diǎn)，對(duì)罰因子進(jìn)行了自適應(yīng)更新，避免了因?yàn)榱P因子選取不當(dāng)造成的麻煩.最后通過(guò)數(shù)值仿真，可以看出本文的算法不僅迭代次數(shù)少，而且可以得到更優(yōu)的Pareto前沿.本文提出的算法將NSGA-II算法推廣到了帶有非線性約束的多目標(biāo)規(guī)劃領(lǐng)域，擴(kuò)大了該算法的適用范圍.

參考文獻(xiàn)：

[1]劉濤, 蘇成利, 李平. 基于外點(diǎn)懲罰函數(shù)與NSGA-II算法的氣體分餾裝置多目標(biāo)優(yōu)化[J]. 江南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 12(6):658-665.

[2]鄒宏濤. 網(wǎng)格獨(dú)立任務(wù)的新型多目標(biāo)安全模型及遺傳算法求解[D]. 西安: 西安電子科技大學(xué), 2012.

[3]黃冀卓， 王湛， 馬人樂(lè). 一種新的求解約束多目標(biāo)優(yōu)化問(wèn)題的遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2006， 42(23): 47-51.

[4]陳志旺， 陳林. 求解約束多目標(biāo)區(qū)間優(yōu)化問(wèn)題的改進(jìn)NSGA-Ⅱ[J].小型微型計(jì)算機(jī)系統(tǒng)， 2014，35(11):2 502-2 506.

[5]王瓏, 王同光, 羅源. 改進(jìn)的NSGA-II算法研究風(fēng)力機(jī)葉片多目標(biāo)優(yōu)化[J]. 應(yīng)用數(shù)學(xué)和力學(xué), 2011, 32(6):693-701.

[6]李政. 非線性規(guī)劃中的兩種罰函數(shù)[D]. 上海：上海大學(xué)， 2007.

[7]CominettiR，DussaultJP.Stableexponential-penaltyalgorithmwithsuperlinearconvergence[J].JournalofOptimizationTheory&Applications， 1994， 83(2):285-309.

[8]張連生，顧燕紅. 簡(jiǎn)單光滑精確指數(shù)乘子罰函數(shù)[J]. 數(shù)學(xué)年刊(中文版), 2010， 31(4):475-486.

[9]K?ppenM,YoshidaK.Substitutedistanceassignmentsinnsga-IIforhandlingmany-objectiveoptimizationproblems[C]//ShigeruO,KalyanmoyD,CarloP,etal.EvolutionaryMulti-CriterionOptimization.Germany:SpringerBerlinHeidelberg, 2007:727-741

(編輯：劉寶江)

NSGA -II based on adaptive multi-objective exponential penalty function

WANG Cong, ZHAO Wen-ling

(School of Science, Shandong University of Technology, Zibo 255049, China)

Abstract:In order to solve multi-objective programming problem，this paper extended the NSGA-II algorithm，and constructed a new multi-objective exponential of penalty function as the fitness function of NSGA-II algorithm.It could to obtain the Pareto solutions of multi-objective programming problem through dynamic updating penalty factor. Finally，the simulation results showed that the algorithm not only converged fastly，but also obtained more uniform Pareto frontier.

Key words:multi-objective programming problem； penalty method； NSGA-II； adaptive penalty factor； constrained optimization

中圖分類(lèi)號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-6197(2016)03-0011-04

作者簡(jiǎn)介：王聰, 男, 596520206@qq.com; 通信作者：趙文玲, 女, zwlsdj@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(11271233); 山東省自然科學(xué)基金項(xiàng)目(ZR2012AM016)

收稿日期：2015-09-10