基于非支配排序遺傳算法的效果評(píng)價(jià)及程序測(cè)試*

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

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

NSGA方法原理

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

測(cè)試方法與步驟

1．測(cè)試函數(shù)及其特點(diǎn)

(1)兩目標(biāo)簡(jiǎn)單測(cè)試函數(shù)、兩目標(biāo)復(fù)雜測(cè)試函數(shù)(A)與三目標(biāo)測(cè)試函數(shù)及其特點(diǎn)見文獻(xiàn)〔3〕。

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

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

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

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

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

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

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

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

NSGA求解測(cè)試結(jié)果

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

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

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

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

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

圖2 兩目標(biāo)簡(jiǎn)單函數(shù)NSGA max fitness—generation

圖3 兩目標(biāo)簡(jiǎn)單函數(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 兩目標(biāo)簡(jiǎn)單函數(shù)NSGA Pareto非劣解前端分布

圖5 NSGA max fitness-generation

圖6 NSGA mean fitness-generation

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

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

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

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

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

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

圖8 NSGA max fitness-generation

圖9 NSGA mean fitness-generation

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

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

4．兩目標(biāo)復(fù)雜測(cè)試函數(shù)(B)的Pareto非劣解集

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

圖11 NSGA max fitness-generation

圖12 NSGA mean fitness-generation

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

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

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

討 論

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

1．謝濤，陳火旺，康立山．多目標(biāo)優(yōu)化的演化算法．計(jì)算機(jī)學(xué)報(bào)，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.李飛瑩，陳益，師先鋒，等．基于小生境遺傳算法的多目標(biāo)藥物提取條件優(yōu)化分析應(yīng)用．中國(guó)衛(wèi)生統(tǒng)計(jì)，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)．