基于非支配排序遺傳算法的效果評價及程序測試*

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

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

NSGA方法原理

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

測試方法與步驟

1．測試函數及其特點

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

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

2．遺傳算法參數設置

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

3．遺傳算法性能評價

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

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

4．軟件及統計分析

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

NSGA求解測試結果

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

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

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

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

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

圖2 兩目標簡單函數NSGA max fitness—generation

圖3 兩目標簡單函數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 兩目標簡單函數NSGA Pareto非劣解前端分布

圖5 NSGA max fitness-generation

圖6 NSGA mean fitness-generation

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

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

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

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

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

表5 NSGA求解三目標函數的Pareto非劣解

圖8 NSGA max fitness-generation

圖9 NSGA mean fitness-generation

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

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

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

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

圖11 NSGA max fitness-generation

圖12 NSGA mean fitness-generation

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

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

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

討 論

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

1．謝濤，陳火旺，康立山．多目標優化的演化算法．計算機學報，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.李飛瑩，陳益，師先鋒，等．基于小生境遺傳算法的多目標藥物提取條件優化分析應用．中國衛生統計，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)．