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

醫(yī)學實踐中經(jīng)常遇到多目標優(yōu)化問題，由于實際問題常由多個相互沖突的指標組成，問題的解通常不是單個的最優(yōu)解，而是一組非劣解，因而采用傳統(tǒng)多目標優(yōu)化方法通常無法解決〔1〕。遺傳算法是模擬生物自然進化的一種有效優(yōu)化搜索方法，在數(shù)值優(yōu)化、組合優(yōu)化、人工生命等方面解決了傳統(tǒng)方法遇到的技術難題。它可對代表整個解集的種群不斷進化，以內(nèi)在并行方式搜索多個非劣解(Pareto解集)，非常適合多目標優(yōu)化。本文旨在應用四個標準測試函數(shù)對英國Glasgow大學軟件工程師陳益提供的外掛工具箱(SGALAB)beta5008中NSGA程序進行可靠性測試，為NSGA的實際應用提供理論依據(jù)及可行的程序。

NSGA方法原理

非支配排序遺傳算法〔2〕(nondominated sorting genetic algorithm，NSGA)是由 Srinivas和Deb于1995年提出的，是一種基于Pareto排序的方法，其基本思路是對所有的個體按不同的層次分級，在執(zhí)行選擇算子之前，種群已經(jīng)根據(jù)支配與非支配關系進行了分級排序，并且種群中的所有個體都被指定一個虛擬適應度值(一般情況下和種群規(guī)模成一定比例)，同級個體的虛擬適應度值相同，這樣就保證了同級個體有同樣的復制概率。為了維持種群多樣性，這些分級后的個體共享它們的虛擬適應度值。NSGA的特點在于將多個目標函數(shù)計算轉化為虛擬適應度計算。NSGA可以處理多個目標函數(shù)的優(yōu)化問題，并且可以處理最大化或最小化問題。算法流程如圖1所示。

測試方法與步驟

1．測試函數(shù)及其特點

(1)兩目標簡單測試函數(shù)、兩目標復雜測試函數(shù)(A)與三目標測試函數(shù)及其特點見文獻〔3〕。

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

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

采用二進制編碼，取初始種群(population)=30，進化代數(shù)(generation)=100，單點交叉概率(probability-crossover)=0.90，變異概率(probability-mutation)=0.01，簡單函數(shù)兩目標和復雜函數(shù)單目標優(yōu)化均運行20次，復雜函數(shù)兩目標優(yōu)化運行100次。

3．遺傳算法性能評價

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

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

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

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

NSGA求解測試結果

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

非支配排序遺傳算法(NSGA)給出的兩目標簡單函數(shù)的20個Pareto非劣解方案見表1，從其中一個方案的世代進化曲線圖2、圖3可以看到，兩個目標函數(shù)的最大、平均適應度曲線大約在進化3代以后就穩(wěn)定在1的附近，反映了NSGA具有較好的收斂性，動態(tài)性能好;圖4為NSGA搜索的Pareto非劣解前端，非劣解沿一條曲線分布，表面大多數(shù)非劣解都可以搜索到。由表2可知，20次隨機搜索結果的平均水平為1.01，標準差為0.16，95%可信區(qū)間包含交叉點1。f1(x)的平均水平為1.04，標準差為0.34，f2(x)的平均水平為1.01，標準差為0.30。符合兩目標簡單測試函數(shù)的特點。即NSGA能夠給出合理的Pareto解集。

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

2．兩目標復雜測試函數(shù)(A)的Pareto非劣解集

利用NSGA搜索使復雜測試函數(shù) f1(x1，x2)、f2(x1，x2)同時最小，100個Pareto非劣解方案見表3，研究者可以根據(jù)實際工作的需要選擇合適的解;從其中一個方案的世代進化曲線(圖5、圖6)可知，兩個目標函數(shù)中的f1(x1，x2)的最大適應度曲線大約在進化1代以后就穩(wěn)定在函數(shù)值為0.2的水平附近，平均適應度曲線大約在進化3代以后就穩(wěn)定在函數(shù)值為0.2的水平附近，而f2(x1，x2)的最大適應度曲線大約在進化5代以后就穩(wěn)定在函數(shù)值為15的水平附近，平均適應度曲線大約在進化5代以后就穩(wěn)定在函數(shù)值為15的水平附近，圖5反映出算法具有較好的收斂性，圖6反映了算法的動態(tài)性好;圖7為NSGA非劣解前端分布，其解前端呈帶狀分布，顯示了兩目標互為沖突的特點，很好地反映了兩目標間的關系。表4給出NSGA隨機搜索100次結果的平均水平:在x1=0.89，x2=0.50 時，f1(x1，x2)、f2(x1，x2)均達到最小，分別為0.89，1.75?！±s

圖2 兩目標簡單函數(shù)NSGA max fitness—generation

圖3 兩目標簡單函數(shù)NSGA mean fitness—generation

95%

分布范圍

Lower upper

最小值 最大值

x 1．01 ±0．16 0．93 1．08 0．80 1．41

f1(x) 1．04 ±0．34 0．88 1．20 0．64 1．99

f2(x) 1．01 ±0．30 0．87 1．15 0．35 1．44

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

圖5 NSGA max fitness-generation

圖6 NSGA mean fitness-generation

圖7 兩目標復雜函數(shù)NSGA Pareto非劣解前端分布

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

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

3．三目標復雜測試函數(shù)的Pareto非劣解集

NSGA搜索使三目標測試函數(shù)f1(x1，x2)，f2(x1，x2)，f3(x1，x2)同時最小，100個 Pareto非劣解方案見表5，研究者可以根據(jù)實際工作的需要選擇合適的解;從其中一個方案的世代進化曲線(圖8、圖9)可知，三目標函數(shù)中的f1(x1，x2)的最大適應度曲線大約在進化5代以后就穩(wěn)定在函數(shù)值為2的水平附近，平均適應度曲線大約在進化4代以后就穩(wěn)定在函數(shù)值為2的水平附近;f2(x1，x2)的最大適應度曲線大約在進化1代以后就穩(wěn)定在函數(shù)值為15的水平附近，平均適應度曲線大約在進化3代以后就穩(wěn)定在函數(shù)值為15的水平附近;而f3(x1，x2)的最大適應度曲線大約在進化2代以后就穩(wěn)定在函數(shù)值為0的水平附近，平均適應度曲線大約在進化1代以后就穩(wěn)定在函數(shù)值為0的水平附近，圖8的最大適應度曲線反映出算法具有較好的收斂性，圖9的平均適應度曲線反映了算法的動態(tài)性好;圖10為NSGA非劣解前端分布，其解前端是一個非線性的，非對稱的三維曲面，符合三目標理論解集的分布情況。表6是NSGA對三目標函數(shù)100次隨機搜索結果的平均水平:x1=0.44，x2=－0.03時，三目標函數(shù)值 f1(x1，x2)、f2(x1，x2)、f3(x1，x2)均達到了最小值，平均水平分別為 1.74，20.10，0.19。

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

圖8 NSGA max fitness-generation

圖9 NSGA mean fitness-generation

圖10 三目標復雜函數(shù)NSGA Pareto非劣解前端分布

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

4．兩目標復雜測試函數(shù)(B)的Pareto非劣解集

利用 N SGA 使測試函數(shù) f1(x1，x2，x3)、f2(x1，x2，x3)同時最小的前30個Pareto非劣解方案見表7，第

圖11 NSGA max fitness-generation

圖12 NSGA mean fitness-generation

圖13 兩目標復雜函數(shù)(B)NSGA Pareto非劣解前端分布

表7 NSGA求解復雜函數(shù)(B)的Pareto非劣解

表8 兩目標復雜函數(shù)(B)的值及Pareto非劣解平均水平

討 論

本文利用Matlab2009a外掛SGALAB工具箱beta5008，分別對簡單測試函數(shù)、兩個復雜測試函數(shù)與三目標測試函數(shù)進行多目標尋優(yōu)。結果表明NSGA進行多目標優(yōu)化效果理想，程序可行，搜索到的Pareto非劣解合理，為實際應用提供了合理的選擇空間。NSGA為多目標尋優(yōu)問題提供了可行的方法，可與均勻試驗設計相結合，尋求最優(yōu)試驗條件，達到節(jié)省人力、物力、提高有效成分提取效率、降低研究成本的目的。

1．謝濤，陳火旺，康立山．多目標優(yōu)化的演化算法．計算機學報，2003，8(26):997-1003．

2.Srinivas N，Deb K．Multi-Objective function optimization using nondominated sorting genetic algorithms．Evolutionary Computation，1995，2:221-248．

3.李飛瑩，陳益，師先鋒，等．基于小生境遺傳算法的多目標藥物提取條件優(yōu)化分析應用．中國衛(wèi)生統(tǒng)計，2010，27(6):577-581．

4.Deb K，Pratap A，Agarwal S，et al．A fast and elitist multi-objective Genetic Algorithm:NSGA-Ⅱ．Kanpur Genetic Algorithms Laboratory(Kan-GAL)．