改進(jìn)非劣分類(lèi)遺傳算法多目標(biāo)優(yōu)化效果評(píng)價(jià)及程序測(cè)試*

張曉麗 陳 益 韓榮榮 周建淞 李飛瑩 師先鋒 仇麗霞△

多目標(biāo)優(yōu)化問(wèn)題〔1－6〕即尋找一組既滿足約束條件又使總目標(biāo)函數(shù)最優(yōu)化的決策變量的取值，其中組成總目標(biāo)函數(shù)的元素是子目標(biāo)函數(shù)。進(jìn)行多目標(biāo)優(yōu)化時(shí)我們希望找到一組可供選擇、非受控的解方案集，即當(dāng)考慮所有目標(biāo)時(shí)，搜索空間中沒(méi)有其他方案能優(yōu)于它，這樣的解方案集我們稱(chēng)為Pareto最優(yōu)解集;Pareto最優(yōu)解集不是由人來(lái)主觀判斷而是根據(jù)多目標(biāo)問(wèn)題優(yōu)化解的自身特性來(lái)搜索的多目標(biāo)有效解集的范圍，為決策者提供不止一種可供選擇的方案。在醫(yī)藥學(xué)研究領(lǐng)域中存在大量的多目標(biāo)優(yōu)化分析問(wèn)題，如藥物有效成分最優(yōu)提取條件、分子生物學(xué)最優(yōu)試驗(yàn)條件、公共衛(wèi)生資源的最優(yōu)分配、診斷試驗(yàn)最優(yōu)決策值、疾病最優(yōu)治療方案等。經(jīng)典的多目標(biāo)進(jìn)化算法主要有加權(quán)法、約束法和目標(biāo)規(guī)劃法等，這些優(yōu)化分析都是將多目標(biāo)問(wèn)題轉(zhuǎn)化為一個(gè)或一系列的單目標(biāo)優(yōu)化問(wèn)題〔7〕，從而利用已經(jīng)成熟的單目標(biāo)優(yōu)化方法來(lái)間接地加以解決。但這些方法都存在明顯的缺陷，主要表現(xiàn)在:(1)權(quán)值系數(shù)的選取主觀性較強(qiáng)，優(yōu)化結(jié)果受該系數(shù)的影響較大;(2)不同性質(zhì)的目標(biāo)具有不同的量綱，很難做比較;(3)各個(gè)目標(biāo)函數(shù)之間通過(guò)決策變量相互關(guān)聯(lián)，拓?fù)浣Y(jié)構(gòu)十分復(fù)雜，往往在某一個(gè)目標(biāo)上是最優(yōu)的，而在另一個(gè)目標(biāo)上可能是最差的，不能保證所有目標(biāo)都存在最優(yōu)解;(4)最終只能得到一個(gè)最優(yōu)解，沒(méi)有可供選擇的方案。另外，還要求對(duì)多目標(biāo)問(wèn)題本身有較深入的了解，然后人為地確定一些重要的參數(shù)。顯然，這些方法的優(yōu)化結(jié)果一般不會(huì)很理想。改進(jìn)非劣分類(lèi)遺傳算法(nondominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ)〔8〕是2002年Deb等人對(duì)算法NSGA的改進(jìn)，它是迄今為止最優(yōu)秀的進(jìn)化多目標(biāo)優(yōu)化算法之一，具有計(jì)算簡(jiǎn)單、利用擁擠距離來(lái)代替適應(yīng)度共享、引入精英策略等優(yōu)點(diǎn)，可以為決策者提供一系列的Pareto非劣解，解決了困擾運(yùn)籌學(xué)理論界的多目標(biāo)優(yōu)化問(wèn)題。但大多數(shù)應(yīng)用者對(duì)其方法的效果尚不清楚，也沒(méi)有方便可行的程序，限制了該方法的推廣。本文旨在應(yīng)用測(cè)試函數(shù)對(duì)NSGA-Ⅱ的效果進(jìn)行評(píng)價(jià)，對(duì)課題組成員英國(guó)Glasgow大學(xué)軟件工程師陳益利用Matlab2009a編寫(xiě)的外掛SGALAB工具箱beta5008進(jìn)行可靠性測(cè)試，為NSGA-Ⅱ的實(shí)際應(yīng)用提供理論依據(jù)及可行的程序。

NSGA-Ⅱ方法原理

改進(jìn)非劣分類(lèi)遺傳算法(NSGA-Ⅱ)是在非劣分類(lèi)遺傳算法(nondominated sorting genetic algorithm，NSGA)的基礎(chǔ)上提出來(lái)的，它針對(duì)NSGA的三個(gè)弊端(計(jì)算復(fù)雜度較高，為O(mN3)，沒(méi)有采用精英策略，需要特別指出共享半徑)提出了改進(jìn)方法:(1)提出了快速非支配排序方法，降低了算法的計(jì)算復(fù)雜度，由原來(lái)的O(mN3)降到O(mN2)，其中，m為目標(biāo)函數(shù)的個(gè)數(shù)，N為種群大小。(2)提出了擁擠度和擁擠度比較算子，代替了需要指出共享半徑的適應(yīng)度共享策略，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn)Pareto域中的個(gè)體能擴(kuò)展到整個(gè)Pareto域，并均勻分布，保持了種群的多樣性。(3)引入精英策略，擴(kuò)大采樣空間。將父代種群與其產(chǎn)生的子代種群組合，共同競(jìng)爭(zhēng)產(chǎn)生下一代種群，有利于父代種群中的優(yōu)良個(gè)體進(jìn)入下一代，并通過(guò)對(duì)種群中所有個(gè)體分層存放，使得最佳個(gè)體不會(huì)丟失，迅速提高種群水平。NSGA-Ⅱ流程見(jiàn)圖 1〔8〕。

首先將第t代產(chǎn)生的新種群Qt與父代Pt合并組成Rt，種群大小為2N。然后Rt進(jìn)行非支配排序，產(chǎn)生一系列非支配集Fi并計(jì)算擁擠度。由于子代和父代個(gè)體都包含在Rt中，則經(jīng)過(guò)非支配排序以后的非支配集F1中包含的個(gè)體是Rt中最好的，所以先將F1放入新的父代種群Pt+1中。如果F1的大小小于N，則繼續(xù)向Pt+1中填充下一級(jí)非支配集F2，直到添加F3時(shí)，種群的大小超出N，對(duì)F3中的個(gè)體進(jìn)行擁擠度排序，取前N－|Pt+1|個(gè)個(gè)體，使Pt+1個(gè)體數(shù)量到達(dá)N。然后通過(guò)遺傳算子(選擇、交叉、變異)產(chǎn)生新的子代種群Qt+1。

圖1 NSGA-Ⅱ流程

測(cè)試方法與步驟

圖2 兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)F1曲線圖

2．遺傳算法參數(shù)設(shè)置

采用二進(jìn)制編碼，取初始種群(population)=30，進(jìn)化代數(shù)(generation)=100，單點(diǎn)交叉概率(probabili-時(shí)決策變量x的取值水平。

由圖2直觀分析可見(jiàn)，f1(x)是增函數(shù)、f2(x)是減函數(shù)，這兩個(gè)目標(biāo)是相互沖突的。當(dāng)x=2時(shí)，f1(x)有最大值4，f2(x)有最小值為0;當(dāng)x=0時(shí)，f1(x)有最小值0，而f2(x)有最大值4;在交叉點(diǎn)x=1處，兩目標(biāo)函數(shù)值均為1。決策變量在1附近時(shí)，兩目標(biāo)函數(shù)值均較大。

(2)兩目標(biāo)復(fù)雜測(cè)試函數(shù)〔8〕及其特點(diǎn)

在xi∈［－4，4］范圍內(nèi)，求解當(dāng)兩個(gè)目標(biāo)函數(shù)均最小時(shí)決策變量xi的取值水平。由于兩目標(biāo)函數(shù)都含有三個(gè)自變量，我們無(wú)法畫(huà)出它們的三維圖，因此不能直觀地觀察目標(biāo)函數(shù)的解空間，但是通過(guò)查文獻(xiàn)我們知道函數(shù)F2的優(yōu)化解空間為:

ty-crossover)=0.90，變異概率(probability-mutation)=0.01，簡(jiǎn)單測(cè)試函數(shù)優(yōu)化運(yùn)行20次，復(fù)雜函數(shù)優(yōu)化運(yùn)行100次。

圖3 三目標(biāo)測(cè)試函數(shù)F3三維圖

3．遺傳算法性能評(píng)價(jià)

(1)在線性能評(píng)價(jià) 采用平均適應(yīng)度進(jìn)化曲線評(píng)價(jià)算法的動(dòng)態(tài)性能。

(2)離線性能評(píng)價(jià) 采用最大適應(yīng)度進(jìn)化曲線反映解的變化，評(píng)價(jià)算法的收斂性。

4．軟件及統(tǒng)計(jì)分析

選用數(shù)學(xué)功能較強(qiáng)的美國(guó)矩陣實(shí)驗(yàn)Matlab2009a軟件繪制函數(shù)圖形;課題組成員英國(guó)Glasgow大學(xué)軟件工程師陳益利用Matlab2009a編寫(xiě)的外掛SGALAB工具箱beta5008完成遺傳算法尋優(yōu);SPSS13.0軟件進(jìn)行統(tǒng)計(jì)分析。

測(cè)試結(jié)果

1．NSGA-Ⅱ求解兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)F1的Pareto非劣解集

利用NSGA-Ⅱ給出的兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)F1的20個(gè)Pareto非劣解方案見(jiàn)表1，其中6、8、13號(hào)方案與兩函數(shù)交叉點(diǎn)解的近似度較好，其他方案為研究者提供了很好選擇機(jī)會(huì);圖4、圖5為其中一個(gè)方案的世代進(jìn)化曲線圖，可以看出，最大適應(yīng)度、平均適應(yīng)度曲線大約在進(jìn)化5代以后就穩(wěn)定在1的附近，反映了NSGA-Ⅱ具有較好的收斂性，動(dòng)態(tài)性能好;圖6為NSGA-Ⅱ搜索的Pareto非劣解前端圖，非劣解前沿呈一條光滑曲線分布，表面大多數(shù)非劣解都可以搜索到，體現(xiàn)了兩個(gè)相互矛盾的目標(biāo)函數(shù)解的關(guān)系。由表2可知，20次隨機(jī)搜索結(jié)果決策變量的平均水平為1.08，標(biāo)準(zhǔn)差為0.16，95%非劣解分布范圍在0.75～1.35，包含交叉點(diǎn)1，兩目標(biāo)函數(shù)均最大的非劣解在1的附近，符合兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)的特點(diǎn)。因此，NSGA-Ⅱ能夠給出合理的Pareto解集。

圖4 兩目標(biāo)簡(jiǎn)單函數(shù)NSGA-ⅡMAX Fitness-Generation

圖5 兩目標(biāo)簡(jiǎn)單函數(shù)NSGA-ⅡMEAN Fitness-Generation

2．NSGA-Ⅱ求解兩目標(biāo)復(fù)雜測(cè)試函數(shù)F2的Pareto非劣解集

圖6 NSGA-Ⅱ求解兩目標(biāo)簡(jiǎn)單函數(shù)Pareto非劣解前端分布

表1 NSGA-Ⅱ求解兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)的Pareto非劣解

表2 兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)的目標(biāo)函數(shù)值及Pareto非劣解平均水平

利用NSGA-Ⅱ搜索使復(fù)雜測(cè)試函數(shù)F2的兩個(gè)目標(biāo)函數(shù)同時(shí)最小的100個(gè)Pareto非劣解方案見(jiàn)表3。從其中一個(gè)方案的世代進(jìn)化曲線(圖7、圖8)可知，目標(biāo)函數(shù)f1(x1，x2，x3)最大適應(yīng)度曲線大約在進(jìn)化10代以后就穩(wěn)定在函數(shù)值為0.65的水平附近，平均適應(yīng)度曲線大約在進(jìn)化10代以后就穩(wěn)定在函數(shù)值為0.85的水平附近，而f2(x1，x2，x3)的最大適應(yīng)度曲線大約在進(jìn)化10代以后就穩(wěn)定在函數(shù)值為0.7的水平附近，平均適應(yīng)度曲線大約在進(jìn)化10代以后就穩(wěn)定在函數(shù)值為0．9的水平附近，圖7反映出算法具有較好的收斂性，圖8反映了算法的動(dòng)態(tài)性好;圖9為NSGA-Ⅱ非劣解前端圖，其解前端在小于1的范圍內(nèi)呈下降趨勢(shì)分布，顯示了兩目標(biāo)互為沖突的特點(diǎn)，很好地反映了兩目標(biāo)間的關(guān)系。表4給出NSGAⅡ100次隨機(jī)搜索結(jié)果的平均水平:在x1=0.29，x2=0.25，x3=0.41時(shí)，f1(x1，x2，x3)、f2(x1，x2，x3)均較小，分別為 0.20，0.91。NSGA-Ⅱ給出的Pareto解集中，使得兩個(gè)目標(biāo)都達(dá)到較小的解均在標(biāo)準(zhǔn)的非劣解范圍內(nèi)。研究者可以根據(jù)實(shí)際情況進(jìn)行合理的選擇。

表3 NSGA-Ⅱ求解兩目標(biāo)復(fù)雜函數(shù)的Pareto非劣解

表4 兩目標(biāo)復(fù)雜函數(shù)解及Pareto非劣解平均水平

圖7 NSGA-ⅡMAX Fitness-Generation

圖8 NSGA-ⅡMEAN Fitness-Generation

圖9 NSGA-Ⅱ求解兩目標(biāo)復(fù)雜函數(shù)Pareto非劣解前端分布

3．NSGA-Ⅱ求解三目標(biāo)復(fù)雜測(cè)試函數(shù)F3的Pareto非劣解集

利用NSGA-Ⅱ搜索的使復(fù)雜測(cè)試函數(shù)F3三個(gè)目標(biāo)同時(shí)最小的100個(gè)Pareto非劣解方案見(jiàn)表5;從其中一個(gè)方案的世代進(jìn)化曲線(圖10、圖11)可知，目標(biāo)函數(shù)f1(x1，x2)最大適應(yīng)度曲線大約在進(jìn)化3代以后就穩(wěn)定在函數(shù)值為0的水平附近，平均適應(yīng)度曲線大約在進(jìn)化5代以后就穩(wěn)定在函數(shù)值為0的水平附近;f2(x1，x2)的最大適應(yīng)度曲線大約在進(jìn)化5代以后就穩(wěn)定在函數(shù)值為17的水平附近，平均適應(yīng)度曲線在進(jìn)化5代之前就穩(wěn)定在函數(shù)值為17的水平附近;而f3(x1，x2)的最大適應(yīng)度曲線大約在進(jìn)化1代以后就穩(wěn)定在函數(shù)值為0的水平附近，平均適應(yīng)度曲線在進(jìn)化5代之前就穩(wěn)定在函數(shù)值為0的水平附近，圖10的最大適應(yīng)度曲線反映出算法具有較好的收斂性，圖11的平均適應(yīng)度曲線反映了算法的動(dòng)態(tài)性好;圖12為NSGA-Ⅱ非劣解前端圖，其解前端是一個(gè)非線性的，非對(duì)稱(chēng)的三維曲面，符合三目標(biāo)理論解集的分布情況。表6是NSGA-Ⅱ?qū)θ繕?biāo)函數(shù)100次隨機(jī)搜索結(jié)果的平均水平:x1=－0.21，x2=－0.30時(shí)，三目標(biāo)函數(shù)值 f1(x1，x2)、f2(x1，x2)、f3(x1，x2)均較小，平均水平分別為0.20，15.96，－0.08。標(biāo)95%非劣解分布范圍為:(－2.27，1.44)，(－1.64，2.06)，(－0.10，0.18)與三目標(biāo)復(fù)雜測(cè)試函數(shù)三維圖(圖3給出的Pareto非劣解集xi∈(－2，1))基本一致，因此，NSGA-Ⅱ給出了三個(gè)目標(biāo)函數(shù)均較小的Pareto解集，同時(shí)，研究者可以根據(jù)研究問(wèn)題的實(shí)際需要，在NSGA-Ⅱ給出Pareto解集中進(jìn)行合理的選擇。

圖10 三目標(biāo)函數(shù)NSGA-ⅡMAX Fitness-Generation

圖11 三目標(biāo)函數(shù)NSGA-ⅡMEAN Fitness-Generation

圖12 NSGA-Ⅱ求解三目標(biāo)函數(shù)Pareto非劣解前端分布

表5 NSGA-Ⅱ求解三目標(biāo)函數(shù)的Pareto非劣解

表6 三目標(biāo)函數(shù)解及Pareto非劣解平均水平

結(jié)論與討論

本文利用Matlab2009a外掛SGALAB工具箱beta5008，分別對(duì)簡(jiǎn)單兩目標(biāo)測(cè)試函數(shù)、復(fù)雜兩目標(biāo)測(cè)試函數(shù)與復(fù)雜三目標(biāo)測(cè)試函數(shù)進(jìn)行多目標(biāo)優(yōu)化。結(jié)果表明:兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)NSGA-Ⅱ搜索的Pareto非劣解集中目標(biāo)函數(shù)值f1(x)、f2(x)基本接近于1，而且95%可信區(qū)間包含1，解前沿呈光滑曲線分布，說(shuō)明該法搜索的Pareto非劣解方案合理;兩目標(biāo)復(fù)雜測(cè)試函數(shù)NSGA-Ⅱ搜索的Pareto非劣解集中較好的方案均在標(biāo)準(zhǔn)的優(yōu)化解空間內(nèi)，且分布均勻多樣性好，給決策者提供了合理的選擇空間;三目標(biāo)復(fù)雜測(cè)試函數(shù)NSGA-Ⅱ搜索的Pareto非劣解集結(jié)合其三維空間圖可知，NSGA-Ⅱ搜索的Pareto非劣解集分布在三個(gè)目標(biāo)均較小的區(qū)域內(nèi)，而且解前沿呈非線性，非對(duì)稱(chēng)的曲面分布，解集是合理的。三類(lèi)測(cè)試函數(shù)的最大適應(yīng)度歷代進(jìn)化曲線反映出了NSGA-Ⅱ具有較好的收斂性，平均適應(yīng)度的歷代進(jìn)化曲線圖均反映了算法的動(dòng)態(tài)性能好。由上述測(cè)試過(guò)程可知NSGA-Ⅱ進(jìn)行低維多目標(biāo)優(yōu)化效果理想，程序可行，可以應(yīng)用于解決實(shí)際問(wèn)題。NSGA-Ⅱ?qū)τ诟呔S多目標(biāo)優(yōu)化的效果如何還有待進(jìn)一步的測(cè)試。

1．Storn R，Price K．Differential Evolution—a Simple and Efficien tAdaptive Scheme for Global Optimization over Continuous Spaces．Technical Report，Intemational Computer Science Institute，1995(8):22-25．

2．Schittowski K．NLQPL:A FORTRAN-subroutine solving constrained non-linear Programming problems，Annals of Operations Research，1985(5):485-500．

3．Li RX，Li YU．A real time control for multi-objective optimization ofmix proportion of concrcte．Joumal of Hydraulic Engineering，1996(4):363-369．

4．De Larrardf，Sedran T．Mixture proportioning of high-performance concrete．Cement and Conerete Research，2002，32(11):1699-1704．

5．吳新余，馬敏肖．遺傳算法在多目標(biāo)規(guī)劃中的應(yīng)用．南京郵電學(xué)院學(xué)報(bào)，1996(2):22-25．

6．謝敬東，王磊，唐國(guó)慶．遺傳算法在多目標(biāo)電網(wǎng)優(yōu)化規(guī)劃中的應(yīng)用．電力系統(tǒng)自動(dòng)化，1998，22．

7．崔遜學(xué)．多目標(biāo)進(jìn)Z化算法及應(yīng)用．北京:國(guó)防工業(yè)出版社，2006．

8．Deb K，Agrawal S，Pratap A，et al．A fast elitist non-dominated sorting algnrithm for multi-objective optimization:NSGA-Ⅱ，Proc of the Prallel Problem Soving from Nature VI Conf，pairs，2002:182-197．

9．仇麗霞．基于遺傳算法的最優(yōu)決策值選擇及醫(yī)藥學(xué)應(yīng)用研究．山西醫(yī)科大學(xué)博士論文，2007．

10．盧香清，譚迎軍．有關(guān)多目標(biāo)遺傳算法的研究．南陽(yáng)師范學(xué)院學(xué)報(bào)(自然科學(xué)版)，2004，(3):62-64．