小型微型計(jì)算機(jī)系統(tǒng)2007年4月第4期Journal of Chinese Computer SystemsVol. 28 No.4 2007可求解多目標(biāo)優(yōu)化問(wèn)題的演化博弈優(yōu)化算法徐敏，張敏，王煦法(中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,安徽合肥230027)E-mail:minny@mail. ustc. edu. cn摘要:借鑒演化博弈的思怒和選擇機(jī)制,提出了一種新的基于演化博弈的優(yōu)化算法(EGOA)用于多目標(biāo)問(wèn)題的求解.算法框架具備對(duì)該類(lèi)問(wèn)題的通用性.為了對(duì)算法性能進(jìn)行評(píng)估,采用了一組多目標(biāo)優(yōu)化問(wèn)題(MOPs)的測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,使用本算法搜索得到的演化穩(wěn)定策略集合能夠很好地逼近多目標(biāo)優(yōu)化問(wèn)題的帕累托前沿，與一些經(jīng)典的演化算法相比具有良好的問(wèn)題求解能力.關(guān)鍵詞:多目標(biāo)優(yōu)化問(wèn)題;演化博弈理論;復(fù)制者動(dòng)態(tài);演化算法中圖分類(lèi)號(hào): TP18文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1000-1220(2007)04-0640-05Evolutionary Game Based Optimization Algorithm for Multi objective Optimization ProblemsXU Min, ZHANG Min, WANG Xu-fa(Department of Computer Science & Technology, University of Science & Technology of China, Hefei 230027, China)Abstract:Used the idea and the selection mechanism called replicator dynamics of evolutionary game theory for reference, andproposed an evolutionary game based optimization algorithm (EGOA) to solve multiobjective optimization problems (MOPs).The frame of algorithm has universal character for MOPs. To evaluate the newly designed approach, solved a group of testfunctions. The experiment results showed that the evolutionary stable strategy (ESS) set searched by EGOA is very close tothe Pareto front of MOPs. Compared with some classic evolutionary algorithm, has a good ability of problem solving.Key words :multiobjective optimization problem; evolutionary game theory; replicator dynamics; evolutionary algorithm1引言個(gè)目標(biāo)函數(shù)的向量函數(shù)f.形式化描述如下:min/max:y= f(x)= (f,(x),f2(x),.,fm(x)) (1)演化博弈理論是博弈論的-一個(gè)分支,它在假定演化的變這里x= (x,.x.)∈X,y= (yre...yn∈Y.化是由群體內(nèi)的自然選擇引起的基礎(chǔ)上,通過(guò)具有頻率依賴(lài)x為決策向量,y為目標(biāo)向量. X稱(chēng)作決策變量空間,Y為目效應(yīng)的選擇行為進(jìn)行演化以搜索演化穩(wěn)定策略凹,并研究該標(biāo)空間.演化過(guò)程.這里的選擇行為一般使用稱(chēng)為"復(fù)制者動(dòng)態(tài)"的方多目標(biāo)優(yōu)化問(wèn)題存在一個(gè)解集合,集合中的決策向量無(wú)去法在任何一個(gè)維度上進(jìn)一步優(yōu)化,我們稱(chēng)該集合為多目標(biāo)優(yōu)多目標(biāo)優(yōu)化問(wèn)題是近年來(lái)演化計(jì)算領(lǐng)域研究的熱點(diǎn)之化問(wèn)題的帕累托(Pareto)最優(yōu)集合.帕累托最優(yōu)集合的數(shù)學(xué)-.,研究者發(fā)展了-些演化算法用于多目標(biāo)問(wèn)題的求解,Zit-表達(dá)如下:不妨假設(shè)一個(gè)最大化問(wèn)題有兩個(gè)決策變量a,b∈zler的文章[5]中給出了一些典型算法的詳細(xì)比較.值得- -提x.當(dāng)且僅當(dāng)(2)式成立時(shí)我們稱(chēng)a支配(dominate)b,記作a的是,有研究者提出了一種基于演化博弈理論的協(xié)同進(jìn)化算>b:法來(lái)解多目標(biāo)優(yōu)化問(wèn)題回。該算法巧妙地結(jié)合了演化博弈理Vi∈{1,2...n}:f,(a)≥ f;(6) ^論和協(xié)同演化算法,實(shí)驗(yàn)結(jié)果說(shuō)明其具有良好的性能.但是文3 j∈{1,2... ,m)}:f;(a)> f;(b)(2)章中給出的算法框架并不具有良好的通用性,只能用于兩目進(jìn)- -步地,當(dāng)且僅當(dāng)a>b或者f(a)=f(b)時(shí),我們稱(chēng)a標(biāo)優(yōu)化問(wèn)題的求解.本文提出了一種新的基于演化博弈的演覆蓋(cover)b,記作aZb.整個(gè)搜索空間中所有互相無(wú)法支配化算法(EGOA),具有良好的通用性,并針對(duì)多目標(biāo)優(yōu)化問(wèn)題的決策向量組成帕累托最優(yōu)集合(或稱(chēng)作帕累托最優(yōu)前沿，的求解給出了實(shí)驗(yàn)結(jié)果和分析.Pareto -optimal front). .2.2求解多目標(biāo)優(yōu)化問(wèn)題的經(jīng)典演化算法2多目標(biāo)優(yōu)化問(wèn)題演化算法具有對(duì)多目標(biāo)優(yōu)化向題求解的優(yōu)勢(shì).早在19672.1定義年,R中國(guó)煤化工到使用遺傳算法求解多多目標(biāo)優(yōu)化問(wèn)題可以表示為一個(gè)將n個(gè)變量映射m到目標(biāo)基于向量評(píng)估的VEGA:MYHCNMHG收稿日期:2006-01-06基金項(xiàng) 目;國(guó)家自然基金委員會(huì)海外青年學(xué)者合作研究基金(60428202)資助，作者簡(jiǎn)介:徐 敏,女.1980 年出生,博士.研究方向?yàn)橛?jì)算智能,基于主體的計(jì)算經(jīng)濟(jì)學(xué).4期徐敏等:可求解多 目標(biāo)優(yōu)化問(wèn)題的演化博弈優(yōu)化算法641算法,這是第一個(gè)多目標(biāo)演化算法,但其本質(zhì)仍是加權(quán)方個(gè)條件之- - :法[0,且在搜索中會(huì)對(duì)某些個(gè)體或區(qū)域產(chǎn)生偏向,進(jìn)而影響(1) F(s,s)>F(s' ,s)解的分布性.另一種非Pareto方法是Hajela和Lin提出的(2) F(s,s)=F(s' ,s), and F(Ss+s' )>F(s' ,s')。HLGA05,其對(duì)每個(gè)目標(biāo)設(shè)置權(quán)重,通過(guò)目標(biāo)加權(quán)計(jì)算個(gè)體而復(fù)制者動(dòng)態(tài)的概念體現(xiàn)了優(yōu)勝劣汰的觀點(diǎn)，即使用某的適應(yīng)度,雖然權(quán)重也參與進(jìn)化,但仍不適合對(duì)解集的搜一策略的人數(shù)的增長(zhǎng)率與使用該策略得到的支付正相關(guān),具索[5].在Pareto方法研究領(lǐng)域，F(xiàn)onseca和Fleming提出了體表現(xiàn)為特定策略在一個(gè)群體中被采用的頻度的動(dòng)態(tài)微分方MOGA算法00), Horn和Nafpliotis提出了NPGA算法[2),程.有結(jié)論:ESS總是一一個(gè)純策略復(fù)制者動(dòng)態(tài)的漸進(jìn)穩(wěn)定點(diǎn)Srinivas 和Deb也提出了NSGA算法([13. MOGA執(zhí)行相對(duì)容3.2算法框架及描述易且效率高,缺點(diǎn)是易受小生境大小影響;NPGA采用聯(lián)賽在EGOA中,每個(gè)個(gè)體記錄-一個(gè)決策向量.而群體中同法選擇個(gè)體,但聯(lián)賽群體的規(guī)模難以確定;NSGA根據(jù)Pareto時(shí)存在m個(gè)不同的種群,每個(gè)種群表示一個(gè)個(gè)體集合,將種支配關(guān)系對(duì)群體進(jìn)行分層,并引進(jìn)基于決策向量的共賞函數(shù)群i記作X. X.滿(mǎn)足X:UX:..UXm=X,并且X∩X;=法,其中優(yōu)化目標(biāo)個(gè)數(shù)無(wú)限制且非劣最優(yōu)解分布均勻,但計(jì)算φ,i,j∈<1,2,.. ,m}.個(gè)體在記錄決策向盤(pán)的同時(shí),還記錄一復(fù)雜度較高.2002年,Deb和Pratap提出了NSA-104,該個(gè)信息標(biāo)記著個(gè)體所屬的種群.方法降低了計(jì)算復(fù)雜度,并引入了精英保留策略,同時(shí)利用排X;以f;為優(yōu)化目標(biāo).我們的算法借鑒了演化博弈的思想擠距離避免了共賞參數(shù)的設(shè)置1999年,Zitzler和Thiele首和選擇機(jī)制.群體中廣泛存在資源競(jìng)爭(zhēng)行為,當(dāng)兩個(gè)個(gè)體相遇次提出了采用精英保留策略的多目標(biāo)優(yōu)化進(jìn)化算法時(shí),它們?yōu)榱送?份資源進(jìn)行博弈.設(shè)最大化多目標(biāo)優(yōu)化問(wèn)題SPEA[5,利用外部群體保存進(jìn)化中發(fā)現(xiàn)的非劣解,并通過(guò)支中個(gè)體x(x∈X;)與x' (x'∈X)進(jìn)行博弈紅得到的效用(或配關(guān)系設(shè)置適應(yīng)度函數(shù),但維護(hù)外部群體的復(fù)雜度高且在保稱(chēng)作支付)如(3)式所示.(f,(x) - min,留非劣解集的邊界上存在問(wèn)題.為此,Zitzler等提出了max; - min,i=jSPEA-II算法[I5],較好地解決了SPEA中的問(wèn)題.在非群體U(x)=(3)搜索研究方面,Knowles和Corne提出了- -種類(lèi)似(1+1)-ES1 (f,(x) = f,(x'》)一(min, 二max)i≠j(max;一min;) - (min; 一max;)的進(jìn)化策略的多目標(biāo)進(jìn)化算法PAESLIlo,只采用一個(gè)親本和.其中,min; = min(f)表示群體中最小的f;值,max;= max一個(gè)子代個(gè)體,并維護(hù)-一個(gè)非劣解檔案.此外,還有一- 些基于(f)則為群體中最大的f, 值. (3)式表示的效用函數(shù)是針對(duì)決策者預(yù)期目標(biāo)的目標(biāo)向盤(pán)方法[,如目標(biāo)規(guī)劃,目標(biāo)實(shí)現(xiàn)最大化問(wèn)題的,而當(dāng)問(wèn)題為最小化多目標(biāo)優(yōu)化問(wèn)題時(shí),效用函及最小最大方法等,其計(jì)算效率高,但各優(yōu)化指標(biāo)的預(yù)期目標(biāo)數(shù)需要一些調(diào)整.見(jiàn)(4)式.難以確定,且對(duì)非凸搜索空間不適用.f,(x)一min;也有研究者提出了--些協(xié)同演化算法用于多目標(biāo)優(yōu)化問(wèn)max; 一min;題的求解.如:Lohn提出了協(xié)同遺傳算法CGA用于求解_(f.(x)- f,(x'))- (min, = max)i≠j4)MOPs,并將其與一些演化算法的性能作了比較[1]. Sim提出(max; - min;) 一(min; 一max;)了一種基于演化博弈理論的協(xié)同演化算法GCEA0.該算法在min,=max;并且min;=maxj時(shí),也即群體中所有個(gè)中,參與者通過(guò)與對(duì)手陣營(yíng)的個(gè)體進(jìn)行博弈來(lái)優(yōu)化它們自己體的f,值均相等并且f;值也相等時(shí),(3)和(4)式中的分母的目標(biāo)函數(shù).為0.這樣的特殊情況下,我們令U(x)=1在演化算法的每-一代,隨機(jī)挑選成對(duì)的個(gè)體進(jìn)行若干次3演化博弈 優(yōu)化算法重復(fù)博弈.當(dāng)所有博弈完成之后,由個(gè)體x參與的N次博弈所得到的平均效用決定個(gè)體x的基本適應(yīng)度,見(jiàn)(5)式.其中, .3.1演化博弈理論在演化博弈中,每個(gè)參與者都是隨機(jī)地從群體中抽取并BF(x)表示x的基本適應(yīng)度.進(jìn)行重復(fù)，匿名的博弈.它假設(shè)博弈的參與者只具有有限的理BF(x)= 100x Ux)(5)性.演化博弈理論最早源于生態(tài)學(xué)家對(duì)動(dòng)植物的沖突和合作為了使群體中各個(gè)種群在每一代中的分布穩(wěn)定不變,我行為的博弈分析.Smith和Price提出演化穩(wěn)定策略(ESS)的們還需要對(duì)基本適應(yīng)度作一個(gè)修正,得到個(gè)體的適應(yīng)度,修正概念標(biāo)志演化博弈論的正式誕生.而Taylor和Jonker首公式如(6)式所示.其中,F(x)表示x的適應(yīng)度.次提出復(fù)制者動(dòng)態(tài)(RD)這一基本概念凹,標(biāo)志著演化博弈論2 BF(x' ).p,的又一次突破性發(fā)展. ESS和RD構(gòu)成演化博弈理論最核心2 BF(x' ). BF(x)(6)的一對(duì)基本概念,它們分別表征演化博弈的穩(wěn)定狀態(tài)和向這種穩(wěn)定狀態(tài)的動(dòng)態(tài)收斂過(guò)程.中國(guó)煤化工* X的概率.由(6)式可演化穩(wěn)定策略定義為:“如果群體中所有的成員都采取這得::MYHCNMHG1用輪盤(pán)賭選擇,X中的種策略,那么在自然選擇的影響下,將沒(méi)有突變策略可以侵犯?jìng)€(gè)體這個(gè)群體”.記F(s,s' )為當(dāng)對(duì)手策略為s'時(shí)采取策略s獲得在生成下一-代的過(guò)程中,子個(gè)體除了從父?jìng)€(gè)體處繼承策的效用.根據(jù)推導(dǎo)叫可得:一個(gè)策略s是ESS必須滿(mǎn)足以下兩略信 息之外,還需要繼承父?jìng)€(gè)體的種群信息.如果兩個(gè)父?jìng)€(gè)體642小型微型計(jì)算機(jī)系統(tǒng)2007年均屬于x,則孩子個(gè)體也屬于X,如果父?jìng)€(gè)體一個(gè)屬于X,步驟2.隨機(jī)挑選成對(duì)個(gè)體進(jìn)行博弈,按照(3),(4)式計(jì)另一個(gè)屬于X;,則孩子個(gè)體有50%的概率屬于X,50%的概算個(gè)體所得效用. .率屬于X,假設(shè)第t代群體中個(gè)體屬于X;的概率為p;,我們步驟3.重復(fù)步驟2直至博弈次數(shù)達(dá)到重復(fù)博弈最大次有2p:=1,則在t+1代,個(gè)體屬于X;的概率為:數(shù).步驟4.根據(jù)(5) ,(6)式計(jì)算每個(gè)個(gè)體的適應(yīng)度值.p',=pi+ t(2pp)=p>Sp=p(7)步驟5.根據(jù)個(gè)體適應(yīng)度用輪盤(pán)賭選擇生成下一代.由歸納法可知,該演化方案能夠保證群體中各個(gè)種群的步驟6.重復(fù)步驟2-5直到整個(gè)群體到達(dá)ESS或達(dá)到最分布穩(wěn)定.我們的算法描述如下,流程圖見(jiàn)圖1.大演化代數(shù).4實(shí)驗(yàn)結(jié)果及分析隨機(jī)初始化群體[結(jié)果 輸出結(jié)果4.1 測(cè)試函數(shù)初始化群體數(shù)據(jù):否達(dá)到ESS7SumU+=;X.n++;本文采取Zitzler給出的0幾組多目標(biāo)優(yōu)化問(wèn)題的測(cè)試函數(shù)來(lái)進(jìn)行算法測(cè)試.這里,每組測(cè)試函數(shù)的結(jié)構(gòu)類(lèi)似,由三排選成對(duì)個(gè)體進(jìn)行博弈|生成下x.SumU+=U(x);x.N++; I個(gè)函數(shù)構(gòu)成: fi,g,h.優(yōu)化目標(biāo)為最小化f(x) = (f:(x)，fz(x)).其中,工由n個(gè)決策變量組成,函數(shù)fi是僅與第-個(gè)查達(dá)到重復(fù)博弈最大團(tuán)數(shù)些葉選金倒決策變量相關(guān)的函數(shù),g函數(shù)與剩余的n-1個(gè)變量相關(guān),h是fi和g的函數(shù).并且:圖1 EGOA 算法流程圖f,(x) = g(.,",n) .h(f,(x),g(...") .(8)Fig.1 Flow chart of EGOA這里,x= (z1,.. ,x) .測(cè)試函數(shù)如表1所示.步驟1.隨機(jī)生成初始群體.表1測(cè)試函數(shù)集Table 1 Test functionsTF f(x)g(x2:,中,n)h(fi.g)n_工Ti到z30 x;∈[0,1]1+9.Tz工30 z;∈[0,1]Ts石30 x∈[0,1}唇(4 )n(0<())1+ 10(n-1)+xn∈[0.1]x..,T.工E(x-10cos(rx;))1~醫(yī)30 2xn∈[-5,5]Zo(u(z), .xn∈{0,1)0Ts 1+u(x)，0v(u(x))=11 x,*,x.∈u(xu) :位向量劃中1的個(gè)數(shù)F(2+u(x,)if u(x;)<5{0,1}*1if u(x)=5T。1-exp(-4x1 )sin'(6rx)1+9. ()a.2510 x;∈[0,1]這些測(cè)試函數(shù)中,T,具有凸的帕累托最優(yōu)前沿,而Tz的托前沿上的.其次,越靠近它的帕累托前沿,解的密度就越小.是非凸的.T:具有一定的離散特性,它的帕累托最優(yōu)前沿由4.2演化穩(wěn)定策略集合及分析幾段不連續(xù)的凸曲線(xiàn)組成T,具有21°個(gè)局部帕累托最優(yōu)中國(guó)煤化工.對(duì)以上6個(gè)測(cè)試函數(shù)進(jìn)解,可用來(lái)驗(yàn)證演化算法處理多峰性函數(shù)的性能. Ts具有一行計(jì)天驗(yàn)均重復(fù)200次.參數(shù)定的欺騙性,與其他幾個(gè)測(cè)試函數(shù)不同,Ts中的xi為一個(gè)二設(shè)置MHCN MH G.率為0.01.除了T。和進(jìn)制位串.由于目標(biāo)空間的不均勻性,測(cè)試函數(shù)Ts的求解有Ts之外,其余四組的群體大小為100,最大運(yùn)行代數(shù)為500.兩點(diǎn)困難之處.首先，它的帕累托最優(yōu)解不是-致分布在帕累這些參數(shù)與Zitzler使用的參數(shù)相同.重復(fù)博弈次數(shù)為群體大4期徐敏等:可求解多 目標(biāo)優(yōu)化問(wèn)題的演化博弈優(yōu)化算法643小的10倍.T,和Ts的群體大小為500,最大運(yùn)行代數(shù)為為了直觀地比較本文算法與-些經(jīng)典演化算法的性能，1000.這里我們引用了- -些文獻(xiàn)中的實(shí)驗(yàn)結(jié)果.圖8為Zitzler使用8種不同的演化算法對(duì)這-系列測(cè)試函數(shù)進(jìn)行計(jì)算得到的結(jié)4f果[5].圖中從左到右依次為T(mén),T2,T。(第-一排),T,Ts,7。(第二排)的實(shí)驗(yàn)結(jié)果.4' o 0.10.20.30.40.50.60.70.80.9 t“ 0 0102030.4050.60.70.80.9 十C2.5圖2用EGOA計(jì)算出的圖3用EGOA計(jì)算出的函數(shù)T的ESS集合函數(shù)T:的ESS集合Fig.2 ESSset of Ti searched Fig. 3 ESS set of Tr searched051015202530°0 0.10.20.30.40.50.6 0.7 0.809by EGOAfl圖6用EGOA計(jì)算出的圖7用EGOA計(jì)算出的函數(shù)Ts的ESS集合函數(shù)T。的ESS集合4tFig.6 ESS set of Ts searched Fig.7 ESS set of Ts searched:2C 2.將我們計(jì)算得到的ESS集合與之比較可以看到,使用本算法搜索得到的演化穩(wěn)定策路集合基本上能夠很好地通近多目標(biāo)優(yōu)化問(wèn)題的帕累托前沿.在原文獻(xiàn)中,沒(méi)有-一個(gè)算法能夠o 0.10.2 0.30.4050.6070.809 0.30.40.30.60.70.80.91有效逼近問(wèn)題T.的帕累托最優(yōu)前沿,同時(shí)在Ts的解的搜索上也有-些困難.我們使用EGOA在相同參數(shù)條件下進(jìn)行實(shí)驗(yàn)時(shí)得到類(lèi)似的結(jié)果,但是在增大了群體大小和最大運(yùn)行代圖4用EGOA計(jì)算出的圖5用EGOA計(jì)算出的數(shù)之后,可以看到EGOA成功地得到了和T。的帕累托最優(yōu)前沿相符合的ESS集合.并且大部分T。的ESS集合中大部Fig.4 ESS set of Ts searched Fig.5 ESS Set of Ts searched分的點(diǎn)都落在帕累托最優(yōu)前沿上.Tr,0.204_0.60.8 106020.40.60.800.20.40.60.8f1T,8樓f2f2400.20.40.60.8行051012025300.3 0.4 0.5 0.60.7 0.80.9 1圖8用8種不同的演化算法搜索得到的中國(guó)煤化工Fig. 8 Pareto fronts of T--Ts searche:fHCNMHG4.3種群在群體中 所占比例對(duì)演化穩(wěn)定策略的影響概率.事實(shí)上,在我們的算法中,最終達(dá)到的演化穩(wěn)定策略在.在上述試驗(yàn)中,我們隨機(jī)給定各個(gè)種群在群體中的分布很大程度上與初始的種群分布是相關(guān)的.我們針對(duì)種群在群644小型微型計(jì)算機(jī)系統(tǒng)2007年體中所占比例對(duì)演化穩(wěn)定策略的影響做了實(shí)驗(yàn),結(jié)果如圖9 References:所示.試驗(yàn)的測(cè)試函數(shù)為T(mén)1,參數(shù)與4. 2小節(jié)中的實(shí)驗(yàn)參數(shù)- - [ 1 ] Maynard Smith J, Price G R. Evolution and the theory of gamesM]. Cambridge University Press, 1982.致.圖9中橫坐標(biāo)表示的是pn,即以fi為優(yōu)化目標(biāo)的種群在整[2] Taylor P D, Jonker L B. Evolutionarily stable strategies and個(gè)群體中所占的比例,取值為從0到1,間隔為0.05的20個(gè)game dynamics[J] Math. Bio. sci. ，1978, (40):145-156.實(shí)數(shù).實(shí)驗(yàn)重復(fù)10次,圖9中標(biāo)出的點(diǎn)為10次重復(fù)實(shí)驗(yàn)的平[3] Zitzler E. Evoluionery algitoms for multobietire optimiza-tion: methods and applications[D]. A Dissertation Aubmitted to均結(jié)果.the Swiss Federal Institute of Technology Zurich for the degreeof Doctor of Technical Sciences, Nov. 11, 1999.0.9-。EFunction }[ 4] Maynard Smith J, Price G R. The logic of animal conflict[J]. .0.8Nature 246; 16- 18.[5] Zitzler E, Thiele L. Multibjective evolutionary algorithms: acomparative case study and the strength pareto approach [J]. .g0.5IEEE Trans. On Evolutionary Computation, 1999, 3(4); 257-271.E0.3[6] Kwee-Bo Sim, Dong-Wook Lee, Jji-Yoon Kim. Game theory0.2based coevolutionary algorithm; a new computational coevolu-0.1tionary approach[UJ]. International Journal of Control, Automa-00 0.1 0.2 0.30.40.5 0.60.7 0.80.9 1tion, and Systems ,2004,2(4): 463-474，Rate ofagents using function[ 7 ] Rosenberg R s. Simulation of genetic populaions with biochemi-1as optimization objeetcal prosperities [D]. University of Michigan, Ann Harbor,Michigan, 1967.圖9種群所占 比例對(duì)演化穩(wěn)定策略的影響[ 8] Schaffer J D. Multiple objective optimization with vector evaluat-Fig. 9 Relationship of and ESSsed genetic algorithms[C]. In; Proceedings of lst International從圖9中我們可以看到,隨著pr的增加,演化穩(wěn)定策略的Conferenceon Genetic Algorithms, Lawrence Erlbaum, 1985,93-100.目標(biāo)函數(shù)1的值有明顯的下降趨勢(shì),而目標(biāo)函數(shù)2的值則有明[9] Xie Teo, Chen Ho. wang, Kang Lishan. Evluionary algorithms of multi2 objective optimization problems [J]. Chinese顯上升趨勢(shì).通過(guò)對(duì)EGOA算法的分析,我們可以對(duì)這種現(xiàn)象Journal of Computers. Aug. 2003, 26(8); 997-1003.作出合理的解釋.當(dāng)群體中以函數(shù)fi為優(yōu)化目標(biāo)的個(gè)體數(shù)量[10] Hajela P. LinC-Y. Genetic search sratgies in mulicriterion op-較多時(shí),該函數(shù)具有- -定的優(yōu)勢(shì)可以首先尋優(yōu)到一個(gè)較低的timal design[M]. Structural Optimization, New York: Springer,June 1992, 4: 99-107.水平,面其他函數(shù)在此基礎(chǔ)上進(jìn)行優(yōu)化,從而導(dǎo)致最終的ESS [1FsaCM Fleming P J. Centic lorihms for mioieeie的分布偏向于f.optimization; formulation, discussion and genelization[ion[C]. In;s. Forrest (Ed. ), Proceedings of the Fifth International Confer-5總結(jié)ence on Genetic Algorithms, San Mateo, California, 1993, 416-本文提出了一種新的基于演化博弈的優(yōu)化算法(EGOA),[12] Horn J, Nafpliotis N, Goldberg D E. A niched pareto genetic al-gorithm for multiobjective optimization[C]. Proceedings of the用于多目標(biāo)優(yōu)化問(wèn)題的求解.在該算法中,每個(gè)個(gè)體記錄了個(gè)First IEE Conference on Evolutionary Computation, IEEE體所采用的策略的同時(shí),還記錄一個(gè)信息標(biāo)記著個(gè)體所屬的World Congress on Computational Computation, Piscataway,NJ, IEEE Press, 1994, 1:82-87.種群,種群信息對(duì)應(yīng)個(gè)體的優(yōu)化目標(biāo).它借鑒了演化博弈的思[13] Srinivas N K. Deb multiobjective optimization using nondominat-想和選擇機(jī)制,在每一代時(shí),隨機(jī)從群體中抽取成對(duì)個(gè)體并進(jìn)ed sorting in genetic algorithms[J]. Evolutionary Computation,行重復(fù)博弈,以在博弈中取得的效用來(lái)確定個(gè)體的適應(yīng)度函[14] Deb J, Amit Pratap, Sameer Agarwal T. Meyarivan a fast and1994, 2(3): 221-248.數(shù)值.在下一代的生成過(guò)程中,子個(gè)體除了從父?jìng)€(gè)體處繼承策elitist multiobjective genetic algorithm; NSGA-II[J]. IEEE略信息之外,還繼承了父?jìng)€(gè)體的種群信息.我們采用了特殊的Transactions on Evolutionary Computation, April. 2002, 6(2):適應(yīng)度修正方案來(lái)確保整個(gè)群體中種群的分布穩(wěn)定.相對(duì)于[15] Zitzler E. Laumanns M，Thiele L. SPEA2: improving the182-197.文獻(xiàn)[6]中的基于演化博弈理論的協(xié)同進(jìn)化算法,我們的算法strength pareto evolutionary algorithm for multiobjective opti-具有更強(qiáng)的通用性.為了對(duì)EGOA的性能進(jìn)行評(píng)估,我們采用mization[R]. Research Report ,2001.了一組多目標(biāo)優(yōu)化問(wèn)題(MOPs)的測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)[16] Knowles J, Corne D. The pareto archieved evolution strategy: anew baseline algorithm for multiobjective optimization[C]. In;果表明,使用本算法搜索得到的演化穩(wěn)定策路集合能夠很好Proceedings of the 1999 Congress on Evolutionary Computation,地過(guò)近多目標(biāo)優(yōu)化問(wèn)題的帕累托前沿.Washington DC, 1999, 98-105.雖然用于多目標(biāo)優(yōu)化問(wèn)題的實(shí)驗(yàn)結(jié)果比較成功，但是本[17] LohnJ, Kraus w, Haith G. Comparing a coevolutionary geneticalgorithm for multiobjective optimization[C]. Proceedings of the算法的應(yīng)用仍有需要完善的地方.EGOA算法基于演化博弈2002 IEEE Congress on Evolutionary Computation, May 2002,理論,它最終求得的解為博弈達(dá)到的ESS.但事實(shí)上在演化博中國(guó)煤化工弈中,ESS表示的是演化的均衡解.另-方面,從我們的實(shí)驗(yàn)附中文結(jié)果中可以看出使用本算法求得問(wèn)題的ESS集合與帕累托最[9] 謝MHC N M H G計(jì)算機(jī)學(xué)報(bào)2003.26(8);優(yōu)集合一致,呈現(xiàn)該結(jié) 果的理論基礎(chǔ)還有待研究.997-1003.