基于非劣排序的多目標(biāo)優(yōu)化免疫遺傳算法

郭志剛, 鄒書蓉

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川成都610225)

0 引言

解決含多目標(biāo)和多約束的優(yōu)化問題稱為多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem,MOP)。MOP問題的本質(zhì)在于大多數(shù)情況下各子目標(biāo)可能是相互沖突的,某子目標(biāo)的改善可能引起其他子目標(biāo)性能的降低,因此MOP的解不是唯一,而是存在一個(gè)最優(yōu)解集合,集合中的元素稱為Pareto最優(yōu)解。傳統(tǒng)的多目標(biāo)優(yōu)化方法有加權(quán)法、約束法、目標(biāo)規(guī)劃法和極大極小法等[1]。這類算法的特點(diǎn)是將各個(gè)子目標(biāo)聚合成一個(gè)帶正系數(shù)的單目標(biāo)函數(shù),系數(shù)由決策者決定,或者由優(yōu)化方法自適應(yīng)調(diào)整,這類算法存在的一個(gè)關(guān)鍵問題就是獲得Pareto最優(yōu)解集合必須多次運(yùn)行優(yōu)化過程,由于多次優(yōu)化過程相互獨(dú)立,往往得到的結(jié)果很不一致,令決策者很難有效的決策。進(jìn)化算法的優(yōu)點(diǎn)在于可以處理大規(guī)模的搜索空間、在單輪優(yōu)化期間可以產(chǎn)生多個(gè)均衡解、能夠有效地克服傳統(tǒng)方法的局限性。典型的多目標(biāo)進(jìn)化算法主要包括MOGA、NPGA、NSGA、PAES和NSGA2[2-6]算法等。這些算法各有優(yōu)點(diǎn),但也存在不足。例如,NSGA的優(yōu)點(diǎn)是優(yōu)化目標(biāo)個(gè)數(shù)任選,非劣最優(yōu)解分布均勻,缺點(diǎn)是由于Pareto排序要重復(fù)多次,計(jì)算效率較低,未采用精英保留策略,共享參數(shù)σshare需要預(yù)先確定。

1 多目標(biāo)優(yōu)化問題

1.1 多目標(biāo)優(yōu)化問題的定義

在MOP中,抗原定義為目標(biāo)函數(shù),即尋找決策向量x=(x1,x2,…,xn)∈X?Rn(通常有多個(gè)),使向量函數(shù)f(x)最優(yōu),最優(yōu)標(biāo)準(zhǔn)一般取最小值。其數(shù)學(xué)描述為

式(1)中,x=(x1,x2,…,xn)∈X?Rn稱為決策向量,X是n維的決策空間;y=(y1,y2,…,yn)∈Y?Rm稱為目標(biāo)矢量。

1.2 Pareto最優(yōu)解的定義

對(duì)于向量 x*,當(dāng)且僅當(dāng)不存在其他 x,在滿足約束條件的情況下使式(2)成立,則稱x*為Pareto最優(yōu)解(或非劣解)。所有Pareto最優(yōu)解的集合稱為Pareto最優(yōu)集,相應(yīng)的目標(biāo)向量的圖形表示則被稱為Pareto最優(yōu)前端(Front)或曲面(Surface)。

2 免疫遺傳算法

遺傳算法(Genetic Algorithms,GA)是進(jìn)化算法中應(yīng)用最多的一種,目前已在很多復(fù)雜的工程優(yōu)化問題中得到應(yīng)用。在遺傳算法中,如果根據(jù)適應(yīng)度函數(shù)選擇的雙親基因非常相似,那么其產(chǎn)生的后代相對(duì)雙親也比較接近,所期待的改善就比較小,這樣基因模式的單一性不僅減慢進(jìn)化過程,而且可能到時(shí)進(jìn)化停滯,過早收斂于局部最優(yōu)點(diǎn)。而免疫系統(tǒng)的一個(gè)最重要的特點(diǎn)是抗體多樣性,可使用這種多樣性來(lái)提高遺傳算法的全局搜索能力而不至出現(xiàn)“早熟”現(xiàn)象。在免疫調(diào)節(jié)中,那些與抗原親和度大并且濃度較低的抗體會(huì)受到促進(jìn),而與抗原親和度小或濃度較高的抗體會(huì)受到抑制,以此保證抗體的多樣性。免疫遺傳算法(Immune Genetic Algorithm,IGA)正是結(jié)合了遺傳算法和免疫算法的優(yōu)點(diǎn),從提高種群多樣性角度來(lái)確保收斂到全局最優(yōu)點(diǎn)。為工程優(yōu)化設(shè)計(jì)中遇到的問題,不僅在局部層次提供了相當(dāng)出色的自適應(yīng)處理模型,而且在全局層次,也顯示出許多有用的性能,找到解決實(shí)際工程優(yōu)化設(shè)計(jì)的一種智能方法。

2.1 免疫遺傳算法的基本概念

(1)抗體:一般指問題的候選解,與進(jìn)化算法中的個(gè)體相似。一個(gè)抗體代表一個(gè)候選解,即a=(a1,a2,…,an)。

(2)抗體-抗原親和度:表示抗體對(duì)抗原的識(shí)別程度。

(3)信息熵:算法為了表明種群中全體抗體的多樣性引入了信息熵[7]H(N)(N為抗體個(gè)數(shù))。

(4)抗體-抗體親和度:這一概念反映了抗體與抗體之間的結(jié)合能力。根據(jù)熵的定義,得到兩個(gè)抗體Xi和Xj的親和度,其中Aij的取值范圍是(0,1],Aij越大表示抗體間相似度越高,Aij等于1表示兩者完全相同。

(5)抗體濃度Ci是指群體中相似個(gè)體所占的比例,即其中N表示抗體總數(shù),為抗體之間的親和度,Tacl為設(shè)定的抗體親和力閾值,一般取值0.9≤Tacl≤1。

2.2 免疫遺傳算法的執(zhí)行過程

免疫遺傳算法的一般流程如圖1所示。免疫遺傳算法是在遺傳算法中引入了抗體濃度概率計(jì)算、抗體抑制與促進(jìn)以提供算法的全局收斂性。圖1中,抗原為待優(yōu)化問題及其約束。免疫遺傳算法的具體執(zhí)行步驟如下:

(1)確定編碼方案、初始化參數(shù)。當(dāng)決策變量的取值范圍明確時(shí),可采用二進(jìn)制編碼;當(dāng)決策變量的取值范圍不明確或精度要求高時(shí),應(yīng)采用實(shí)值編碼。

(2)抗原識(shí)別,即輸入工程優(yōu)化問題及其約束。確定初始種群規(guī)模 N、算法迭代次數(shù)最大值 MaxT、交叉概率Pc、變異概率Pm、決策變量的取值范圍及其維數(shù)和子目標(biāo)函數(shù)的個(gè)數(shù)。

(3)產(chǎn)生初始抗體種群Pt,令t=0。首先編碼產(chǎn)生抗體a(問題的候選解)a=(a1,a2,…,an)。然后產(chǎn)生規(guī)模為N的抗體種群Pt。采用小區(qū)間生成法:首先把每個(gè)待優(yōu)化參數(shù)的取值范圍分成群體總數(shù)即N個(gè)小區(qū)間,再在各個(gè)小區(qū)間中分別隨機(jī)生成一個(gè)初始個(gè)體。這樣生成的初始群體將會(huì)均勻地分布在整個(gè)解空間上,并能保證隨機(jī)產(chǎn)生的各個(gè)個(gè)體間有明顯的差別,保證了初始群體含有較豐富的模式,增強(qiáng)了搜索收斂于全局最優(yōu)解的可能。

圖1 免疫遺傳算法流程圖

(4)種群非劣排序和抗體濃度的計(jì)算對(duì)種群Pt按非劣解的定義(對(duì)多目標(biāo)最小優(yōu)化問題采用式(2)進(jìn)行排序,每個(gè)抗體被賦予秩r(r=1,2,…,N);計(jì)算種群Pt中每個(gè)抗體的濃度。

(5)保留種群Pt并優(yōu)選Pt執(zhí)行免疫克隆操作。優(yōu)選及克隆過程為:對(duì)初始種群Pt進(jìn)行二元錦標(biāo)賽選擇,得到種群 Qt(抗體個(gè)數(shù) NQ=「N/2」);對(duì) Qt進(jìn)行免疫克隆操作[8]RPC得到種群Q′t(抗體個(gè)數(shù)為 NQ′,NQ′=2NQ)。其中,二元錦標(biāo)賽選擇的過程為:①?gòu)腜t中隨機(jī)選擇2個(gè)個(gè)體a1和a2;②選擇 a1和a2中秩較小、濃度較低者進(jìn)入 Qt:比較 a1和 a2的秩 r1和 r2。若 r1＜r2,則選擇 a1;若 r1＞r2則選擇 a2;若 r1=r2則選擇 a1和 a2中濃度較小者(如果r1=r2且a1和a2的濃度相等則隨機(jī)選擇二者中的一個(gè))。③重復(fù)上述①和②直到Qt中的個(gè)體總數(shù)等于NQ。對(duì)種群Qt={a1(t),a1(t),…,aNQ(t)}執(zhí)行克隆操作RPC定義為:

(6)對(duì)種群 Q′t執(zhí)行交叉、變異操作得到種群 St(抗體個(gè)數(shù)NS=2NQ′)。具體操作為:從 Q′t中隨機(jī)選擇2個(gè)個(gè)體按交叉概率Pc進(jìn)行交叉,交叉方式為模擬二進(jìn)制交叉(Simulated Binary Crossover,SBX)[9];從種群 Q′t中隨機(jī)選擇一個(gè)抗體,按變異概率Pm進(jìn)行變異操作,變異方式為實(shí)數(shù)編碼的變異方式[6]。

(7)生成匹配池。將群體Pt和St放入匹配池,得到新的群體Rt=Pt∪St(抗體個(gè)數(shù)NR=N+NS),對(duì)種群Rt進(jìn)行非劣排序,并計(jì)算Rt中每個(gè)抗體的濃度,得到非劣前端F1,F2,…。

(8)生成子代群體P(t+1)優(yōu)先選擇非劣前端Fi(i=1,2,…)小的個(gè)體進(jìn)入子代群體;對(duì)相同F(xiàn)i按抗體濃度排序,選擇其中抗體濃度較小的個(gè)體進(jìn)入子代群體,直到得到規(guī)模為N的子代種群P(t+1)。

(9)終止條件判斷,如果終止條件 t=MaxT成立,則結(jié)束;否則,t=t+1,轉(zhuǎn)到(5)。

3 免疫遺傳算法的仿真實(shí)驗(yàn)及其分析

為評(píng)價(jià)算法的性能,分別對(duì)文中算法與NSGA-II多目標(biāo)優(yōu)化算法進(jìn)行仿真實(shí)驗(yàn),最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。測(cè)試函數(shù)選用2個(gè)著名的兩目標(biāo)問題:KUR[10]和ZDT1[11]。在多目標(biāo)優(yōu)化的文獻(xiàn)中經(jīng)常選用這些測(cè)試問題對(duì)算法的性能進(jìn)行測(cè)試[12-14]。

3.1 實(shí)驗(yàn)設(shè)置

表1給出了實(shí)驗(yàn)中用到的2個(gè)測(cè)試函數(shù)的數(shù)學(xué)定義。第一個(gè)目標(biāo)測(cè)試函數(shù)分別由Kursawe提出,第二個(gè)目標(biāo)測(cè)試函數(shù)由Zitzler,Thiele和Deb提出。

表1 文中用到的測(cè)試函數(shù)

為了評(píng)估解的分布性與收斂性,采用文獻(xiàn)[14]、[15]中的Spacing metric指標(biāo)、Convergence metric指標(biāo)。

3.2 文中算法與NSGA-II的性能比較

文中算法與NSGA-II算法的參數(shù)設(shè)置見表2。

表2 文中算法與NSGA-II算法參數(shù)設(shè)置

3.2.1 關(guān)于測(cè)試問題KUR的性能比較

圖2給出了由文中算法和NSGA-II得到的測(cè)試問題-KUR的最優(yōu)解。

對(duì)比圖2(a)和圖2(b)可以看出,對(duì)于子目標(biāo)函數(shù) f1,NSGA-II算法所得的最優(yōu)解在區(qū)間(-19,-18.5)出現(xiàn)了缺失,而對(duì)于子目標(biāo)函數(shù)f2,NSGA-II算法所得的最優(yōu)解在區(qū)間(-1,0)出現(xiàn)了缺失。從而說明NSGA-II算法所得的最優(yōu)解較好地保持了所得的最優(yōu)解在Pareto-前端上分布的均勻性,但是不能很好的保持分布的寬廣性;而文中算法很好的保持了所得最優(yōu)解在Pareto-前端上分布的寬廣性和均勻性。

利用盒圖[16]來(lái)表示各算法對(duì)每個(gè)測(cè)試函數(shù)的統(tǒng)計(jì)結(jié)果。盒圖在判斷數(shù)據(jù)的分布性方面具有重要作用,能形象地表示數(shù)據(jù)的分布情況。使用工具統(tǒng)計(jì)文中算法和NSGA-II算法得到的解的特性。

圖3(a)給出了文中算法與NSGA-II算法的分布性指標(biāo)spacing metric的統(tǒng)計(jì)盒圖。可以看出算法得到的S值的上四分位數(shù)和中位數(shù)比NSGA-II得到的結(jié)果小,算法得到的S值的下四分位數(shù)與NSGA-II得到的結(jié)果相同。這說明算法得到的最優(yōu)解的分布比NSGA-II得到的最優(yōu)解的分布的均勻性稍好。

圖3(b)給出了文中算法與NSGA-II算法的收斂性指標(biāo)convergence metric的統(tǒng)計(jì)盒圖?？梢钥闯鏊惴ǖ玫降腟值的下四分位數(shù)、上四分位數(shù)和中位數(shù)小于NSGA-II得到的結(jié)果。這說明算法得到的最優(yōu)解的收斂性優(yōu)于NSGA-II。

3.2.2 關(guān)于測(cè)試問題ZDT1的性能比較

圖4給出了由文中算法和NSGA-II得到的測(cè)試問題-ZDT1的最優(yōu)解。

對(duì)比圖4(a)和圖4(b)可以看出,對(duì)于子目標(biāo)函數(shù) f2,NSGA-II算法所得的最優(yōu)解在區(qū)間(0.84,0.85),(0.61,0.62),(0.44,0.45)出現(xiàn)了嚴(yán)重缺失。而算法所得到的解沒有出現(xiàn)嚴(yán)重缺失現(xiàn)象,從而說明算法所得到的最優(yōu)解的均勻性優(yōu)于NSGA-II。

圖5(a)給出了文中算法與NSGA-II算法的分布性指標(biāo)spacing metric的統(tǒng)計(jì)盒圖。從圖5(a)中可以看出算法得到的S值的上四分位數(shù)、中位數(shù)和下四分位數(shù)比NSGA-II得到的結(jié)果小。這說明算法得到的最優(yōu)解的分布的均勻性比NSGA-II得到的最優(yōu)解的分布的均勻性好。

圖5(b)給出了文中算法與NSGA-II算法的收斂性指標(biāo)convergence metric的統(tǒng)計(jì)盒圖。從圖5(b)中可以看出算法得到的S值的下四分位數(shù)、上四分位數(shù)和中位數(shù)小于NSGA-II得到的結(jié)果。這說明算法得到的最優(yōu)解的收斂性優(yōu)于NSGA-II。

3.3 實(shí)驗(yàn)結(jié)論

綜合以上實(shí)驗(yàn)分析,得到以下結(jié)論:文中算法得到的最優(yōu)解在分布的均勻性方面比NSGA-II稍好;算法在所得到的最優(yōu)解的收斂性方面明顯好于NSGA-II。

4 結(jié)束語(yǔ)

基于非劣排序提出了一種多目標(biāo)免疫遺傳算法,算法模擬生物免疫系統(tǒng)的克隆繁殖過程提高了算法的搜索效率和收斂性;基于濃度對(duì)個(gè)體生成進(jìn)行促進(jìn)與抑制,保持了問題解的多樣性,能避免早熟現(xiàn)象。算法只與NSGA-II算法進(jìn)行了比較,還需與其他典型的多目標(biāo)優(yōu)化算法進(jìn)行比較,以期進(jìn)一步完善算法。

致謝:感謝成都信息工程學(xué)院科研項(xiàng)目(KYTZ200901)對(duì)本文的支持

[1] Steuer,R E.Multiple Criteria Optimization:Theory,Computation,and Application[M].New York:Wiley,1986.

[2] Fonseca C M,Fleming P J.Genetic algorithmsfor multi-objective optimization:Formulation,discussionand generalization//Proceedings of the Fifth International Conference on Genetic Algorithms[M].San Mateo and California,1993:416-423.

[3] Zitzler E,Thiele L.Multi-objective evolutionary algorithms:A comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271.

[4] Srinivas N,Deb K.Multi-objective optimization using non-dominated in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248.

[5] Knowles J D,Corne D W.Approximating the non-dominated front using the Pareto archive evolutionary strategy[J].Evolutionary Computation,2000,8(2):149-172.

[6] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multi-objective genetic algorithms:NSGA2[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[7] Dasgupta D.Artificial Immune Systems and their Applications[M].New York:Springer-Verlag,1999.

[8] 焦李成,尚榮華,公茂果,等.多目標(biāo)優(yōu)化免疫算法、理論和應(yīng)用[M].北京:科學(xué)出版社,2010.

[9] Deb K,Agrawal,R B Simulated binary crossover for continuous search space[J].Complex Systems,1995,9:115-148.

[10] Kursawe F.A variant of evolution strategies for vector optimization.In:Schwefel HP,Manner R.Parallel Problem Solving from Nature-PPSN I[M].Berlin:Spring-Verlag,1991.193-197.

[11] Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[12] Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems//Congress on Evolutionary Computation[J].Piscataway:IEEE Press,2002:825-830.

[13] Deb K.Multi-objective genetic algorithms:Problem difficulties and construction of test problem[J].Evolutionary Computation,1999,7(3):205-230.

[14] Zitler E,Thiele L,Laumanns M,et al.Performance assessment of multi-objective optimizers:An analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

[15] Schott,JR.Fault tolerant design using single and multicriteria genetic algorithm optimization[M].Cambridge:Massachusetts Institute of Technology,1995.

[16] Deb K,Jain S.Running performance metricsfor evolutionary multi-objective optimization[R].Technical Report,No.2002004,Kanpur:Indian Institute of Technology Kanpur,2002.

[17] Chambers J M,Cleveland W S,Kleiner B,et al.Graphical Methods for Data Analysis[M].Pacific Grover:Wadsworth Brooks/Cole,1983.