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

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

NSGA-Ⅱ方法原理

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

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

圖1 NSGA-Ⅱ流程

測試方法與步驟

圖2 兩目標簡單測試函數(shù)F1曲線圖

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

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

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

(2)兩目標復(fù)雜測試函數(shù)〔8〕及其特點

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

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

圖3 三目標測試函數(shù)F3三維圖

3．遺傳算法性能評價

(1)在線性能評價 采用平均適應(yīng)度進化曲線評價算法的動態(tài)性能。

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

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

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

測試結(jié)果

1．NSGA-Ⅱ求解兩目標簡單測試函數(shù)F1的Pareto非劣解集

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

圖4 兩目標簡單函數(shù)NSGA-ⅡMAX Fitness-Generation

圖5 兩目標簡單函數(shù)NSGA-ⅡMEAN Fitness-Generation

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

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

表1 NSGA-Ⅱ求解兩目標簡單測試函數(shù)的Pareto非劣解

表2 兩目標簡單測試函數(shù)的目標函數(shù)值及Pareto非劣解平均水平

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

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

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

圖7 NSGA-ⅡMAX Fitness-Generation

圖8 NSGA-ⅡMEAN Fitness-Generation

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

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

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

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

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

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

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

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

結(jié)論與討論

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

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．吳新余，馬敏肖．遺傳算法在多目標規(guī)劃中的應(yīng)用．南京郵電學(xué)院學(xué)報，1996(2):22-25．

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

7．崔遜學(xué)．多目標進Z化算法及應(yīng)用．北京:國防工業(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)多目標遺傳算法的研究．南陽師范學(xué)院學(xué)報(自然科學(xué)版)，2004，(3):62-64．