可求解多目标优化问题的演化博弈优化算

小型微型计算机系统2007年4月第4期Journal of Chinese Computer SystemsVol. 28 No.4 2007可求解多目标优化问题的演化博弈优化算法徐敏，张敏，王煦法(中国科学技术大学计算机科学与技术系,安徽合肥230027)E-mail:minny@mail. ustc. edu. cn摘要:借鉴演化博弈的思怒和选择机制,提出了一种新的基于演化博弈的优化算法(EGOA)用于多目标问题的求解.算法框架具备对该类问题的通用性.为了对算法性能进行评估,采用了一组多目标优化问题(MOPs)的测试函数进行实验.实验结果表明,使用本算法搜索得到的演化稳定策略集合能够很好地逼近多目标优化问题的帕累托前沿，与一些经典的演化算法相比具有良好的问题求解能力.关键词:多目标优化问题;演化博弈理论;复制者动态;演化算法中图分类号: TP18文献标识码:A文章编号: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引言个目标函数的向量函数f.形式化描述如下:min/max:y= f(x)= (f,(x),f2(x),.,fm(x)) (1)演化博弈理论是博弈论的-一个分支,它在假定演化的变这里x= (x,.x.)∈X,y= (yre...yn∈Y.化是由群体内的自然选择引起的基础上,通过具有频率依赖x为决策向量,y为目标向量. X称作决策变量空间,Y为目效应的选择行为进行演化以搜索演化稳定策略凹,并研究该标空间.演化过程.这里的选择行为一般使用称为"复制者动态"的方多目标优化问题存在一个解集合,集合中的决策向量无去法在任何一个维度上进一步优化,我们称该集合为多目标优多目标优化问题是近年来演化计算领域研究的热点之化问题的帕累托(Pareto)最优集合.帕累托最优集合的数学-.,研究者发展了-些演化算法用于多目标问题的求解,Zit-表达如下:不妨假设一个最大化问题有两个决策变量a,b∈zler的文章[5]中给出了一些典型算法的详细比较.值得- -提x.当且仅当(2)式成立时我们称a支配(dominate)b,记作a的是,有研究者提出了一种基于演化博弈理论的协同进化算>b:法来解多目标优化问题回。该算法巧妙地结合了演化博弈理Vi∈{1,2...n}:f,(a)≥ f;(6) ^论和协同演化算法,实验结果说明其具有良好的性能.但是文3 j∈{1,2... ,m)}:f;(a)> f;(b)(2)章中给出的算法框架并不具有良好的通用性,只能用于两目进- -步地,当且仅当a>b或者f(a)=f(b)时,我们称a标优化问题的求解.本文提出了一种新的基于演化博弈的演覆盖(cover)b,记作aZb.整个搜索空间中所有互相无法支配化算法(EGOA),具有良好的通用性,并针对多目标优化问题的决策向量组成帕累托最优集合(或称作帕累托最优前沿，的求解给出了实验结果和分析.Pareto -optimal front). .2.2求解多目标优化问题的经典演化算法2多目标优化问题演化算法具有对多目标优化向题求解的优势.早在19672.1定义年,R中国煤化工到使用遗传算法求解多多目标优化问题可以表示为一个将n个变量映射m到目标基于向量评估的VEGA:MYHCNMHG收稿日期:2006-01-06基金项 目;国家自然基金委员会海外青年学者合作研究基金(60428202)资助，作者简介:徐 敏,女.1980 年出生,博士.研究方向为计算智能,基于主体的计算经济学.4期徐敏等:可求解多 目标优化问题的演化博弈优化算法641算法,这是第一个多目标演化算法,但其本质仍是加权方个条件之- - :法[0,且在搜索中会对某些个体或区域产生偏向,进而影响(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,其对每个目标设置权重,通过目标加权计算个体而复制者动态的概念体现了优胜劣汰的观点，即使用某的适应度,虽然权重也参与进化,但仍不适合对解集的搜一策略的人数的增长率与使用该策略得到的支付正相关,具索[5].在Pareto方法研究领域，Fonseca和Fleming提出了体表现为特定策略在一个群体中被采用的频度的动态微分方MOGA算法00), Horn和Nafpliotis提出了NPGA算法[2),程.有结论:ESS总是一一个纯策略复制者动态的渐进稳定点Srinivas 和Deb也提出了NSGA算法([13. MOGA执行相对容3.2算法框架及描述易且效率高,缺点是易受小生境大小影响;NPGA采用联赛在EGOA中,每个个体记录-一个决策向量.而群体中同法选择个体,但联赛群体的规模难以确定;NSGA根据Pareto时存在m个不同的种群,每个种群表示一个个体集合,将种支配关系对群体进行分层,并引进基于决策向量的共赏函数群i记作X. X.满足X:UX:..UXm=X,并且X∩X;=法,其中优化目标个数无限制且非劣最优解分布均匀,但计算φ,i,j∈<1,2,.. ,m}.个体在记录决策向盘的同时,还记录一复杂度较高.2002年,Deb和Pratap提出了NSA-104,该个信息标记着个体所属的种群.方法降低了计算复杂度,并引入了精英保留策略,同时利用排X;以f;为优化目标.我们的算法借鉴了演化博弈的思想挤距离避免了共赏参数的设置1999年,Zitzler和Thiele首和选择机制.群体中广泛存在资源竞争行为,当两个个体相遇次提出了采用精英保留策略的多目标优化进化算法时,它们为了同-份资源进行博弈.设最大化多目标优化问题SPEA[5,利用外部群体保存进化中发现的非劣解,并通过支中个体x(x∈X;)与x' (x'∈X)进行博弈红得到的效用(或配关系设置适应度函数,但维护外部群体的复杂度高且在保称作支付)如(3)式所示.(f,(x) - min,留非劣解集的边界上存在问题.为此,Zitzler等提出了max; - min,i=jSPEA-II算法[I5],较好地解决了SPEA中的问题.在非群体U(x)=(3)搜索研究方面,Knowles和Corne提出了- -种类似(1+1)-ES1 (f,(x) = f,(x'》)一(min, 二max)i≠j(max;一min;) - (min; 一max;)的进化策略的多目标进化算法PAESLIlo,只采用一个亲本和.其中,min; = min(f)表示群体中最小的f;值,max;= max一个子代个体,并维护-一个非劣解档案.此外,还有一- 些基于(f)则为群体中最大的f, 值. (3)式表示的效用函数是针对决策者预期目标的目标向盘方法[,如目标规划,目标实现最大化问题的,而当问题为最小化多目标优化问题时,效用函及最小最大方法等,其计算效率高,但各优化指标的预期目标数需要一些调整.见(4)式.难以确定,且对非凸搜索空间不适用.f,(x)一min;也有研究者提出了--些协同演化算法用于多目标优化问max; 一min;题的求解.如:Lohn提出了协同遗传算法CGA用于求解_(f.(x)- f,(x'))- (min, = max)i≠j4)MOPs,并将其与一些演化算法的性能作了比较[1]. Sim提出(max; - min;) 一(min; 一max;)了一种基于演化博弈理论的协同演化算法GCEA0.该算法在min,=max;并且min;=maxj时,也即群体中所有个中,参与者通过与对手阵营的个体进行博弈来优化它们自己体的f,值均相等并且f;值也相等时,(3)和(4)式中的分母的目标函数.为0.这样的特殊情况下,我们令U(x)=1在演化算法的每-一代,随机挑选成对的个体进行若干次3演化博弈 优化算法重复博弈.当所有博弈完成之后,由个体x参与的N次博弈所得到的平均效用决定个体x的基本适应度,见(5)式.其中, .3.1演化博弈理论在演化博弈中,每个参与者都是随机地从群体中抽取并BF(x)表示x的基本适应度.进行重复，匿名的博弈.它假设博弈的参与者只具有有限的理BF(x)= 100x Ux)(5)性.演化博弈理论最早源于生态学家对动植物的冲突和合作为了使群体中各个种群在每一代中的分布稳定不变,我行为的博弈分析.Smith和Price提出演化稳定策略(ESS)的们还需要对基本适应度作一个修正,得到个体的适应度,修正概念标志演化博弈论的正式诞生.而Taylor和Jonker首公式如(6)式所示.其中,F(x)表示x的适应度.次提出复制者动态(RD)这一基本概念凹,标志着演化博弈论2 BF(x' ).p,的又一次突破性发展. ESS和RD构成演化博弈理论最核心2 BF(x' ). BF(x)(6)的一对基本概念,它们分别表征演化博弈的稳定状态和向这种稳定状态的动态收敛过程.中国煤化工* X的概率.由(6)式可演化稳定策略定义为:“如果群体中所有的成员都采取这得::MYHCNMHG1用轮盘赌选择,X中的种策略,那么在自然选择的影响下,将没有突变策略可以侵犯个体这个群体”.记F(s,s' )为当对手策略为s'时采取策略s获得在生成下一-代的过程中,子个体除了从父个体处继承策的效用.根据推导叫可得:一个策略s是ESS必须满足以下两略信 息之外,还需要继承父个体的种群信息.如果两个父个体642小型微型计算机系统2007年均属于x,则孩子个体也属于X,如果父个体一个属于X,步骤2.随机挑选成对个体进行博弈,按照(3),(4)式计另一个属于X;,则孩子个体有50%的概率属于X,50%的概算个体所得效用. .率属于X,假设第t代群体中个体属于X;的概率为p;,我们步骤3.重复步骤2直至博弈次数达到重复博弈最大次有2p:=1,则在t+1代,个体属于X;的概率为:数.步骤4.根据(5) ,(6)式计算每个个体的适应度值.p',=pi+ t(2pp)=p>Sp=p(7)步骤5.根据个体适应度用轮盘赌选择生成下一代.由归纳法可知,该演化方案能够保证群体中各个种群的步骤6.重复步骤2-5直到整个群体到达ESS或达到最分布稳定.我们的算法描述如下,流程图见图1.大演化代数.4实验结果及分析随机初始化群体[结果 输出结果4.1 测试函数初始化群体数据:否达到ESS7SumU+=;X.n++;本文采取Zitzler给出的0几组多目标优化问题的测试函数来进行算法测试.这里,每组测试函数的结构类似,由三排选成对个体进行博弈|生成下x.SumU+=U(x);x.N++; I个函数构成: fi,g,h.优化目标为最小化f(x) = (f:(x)，fz(x)).其中,工由n个决策变量组成,函数fi是仅与第-个查达到重复博弈最大团数些叶选金倒决策变量相关的函数,g函数与剩余的n-1个变量相关,h是fi和g的函数.并且:图1 EGOA 算法流程图f,(x) = g(.,",n) .h(f,(x),g(...") .(8)Fig.1 Flow chart of EGOA这里,x= (z1,.. ,x) .测试函数如表1所示.步骤1.随机生成初始群体.表1测试函数集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~医30 2xn∈[-5,5]Zo(u(z), .xn∈{0,1)0Ts 1+u(x)，0v(u(x))=11 x,*,x.∈u(xu) :位向量划中1的个数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]这些测试函数中,T,具有凸的帕累托最优前沿,而Tz的托前沿上的.其次,越靠近它的帕累托前沿,解的密度就越小.是非凸的.T:具有一定的离散特性,它的帕累托最优前沿由4.2演化稳定策略集合及分析几段不连续的凸曲线组成T,具有21°个局部帕累托最优中国煤化工.对以上6个测试函数进解,可用来验证演化算法处理多峰性函数的性能. Ts具有一行计天验均重复200次.参数定的欺骗性,与其他几个测试函数不同,Ts中的xi为一个二设置MHCN MH G.率为0.01.除了T。和进制位串.由于目标空间的不均匀性,测试函数Ts的求解有Ts之外,其余四组的群体大小为100,最大运行代数为500.两点困难之处.首先，它的帕累托最优解不是-致分布在帕累这些参数与Zitzler使用的参数相同.重复博弈次数为群体大4期徐敏等:可求解多 目标优化问题的演化博弈优化算法643小的10倍.T,和Ts的群体大小为500,最大运行代数为为了直观地比较本文算法与-些经典演化算法的性能，1000.这里我们引用了- -些文献中的实验结果.图8为Zitzler使用8种不同的演化算法对这-系列测试函数进行计算得到的结4f果[5].图中从左到右依次为T,T2,T。(第-一排),T,Ts,7。(第二排)的实验结果.4' o 0.10.20.30.40.50.60.70.80.9 t“ 0 0102030.4050.60.70.80.9 十C2.5图2用EGOA计算出的图3用EGOA计算出的函数T的ESS集合函数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计算出的图7用EGOA计算出的函数Ts的ESS集合函数T。的ESS集合4tFig.6 ESS set of Ts searched Fig.7 ESS set of Ts searched:2C 2.将我们计算得到的ESS集合与之比较可以看到,使用本算法搜索得到的演化稳定策路集合基本上能够很好地通近多目标优化问题的帕累托前沿.在原文献中,没有-一个算法能够o 0.10.2 0.30.4050.6070.809 0.30.40.30.60.70.80.91有效逼近问题T.的帕累托最优前沿,同时在Ts的解的搜索上也有-些困难.我们使用EGOA在相同参数条件下进行实验时得到类似的结果,但是在增大了群体大小和最大运行代图4用EGOA计算出的图5用EGOA计算出的数之后,可以看到EGOA成功地得到了和T。的帕累托最优前沿相符合的ESS集合.并且大部分T。的ESS集合中大部Fig.4 ESS set of Ts searched Fig.5 ESS Set of Ts searched分的点都落在帕累托最优前沿上.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种不同的演化算法搜索得到的中国煤化工Fig. 8 Pareto fronts of T--Ts searche:fHCNMHG4.3种群在群体中 所占比例对演化稳定策略的影响概率.事实上,在我们的算法中,最终达到的演化稳定策略在.在上述试验中,我们随机给定各个种群在群体中的分布很大程度上与初始的种群分布是相关的.我们针对种群在群644小型微型计算机系统2007年体中所占比例对演化稳定策略的影响做了实验,结果如图9 References:所示.试验的测试函数为T1,参数与4. 2小节中的实验参数- - [ 1 ] Maynard Smith J, Price G R. Evolution and the theory of gamesM]. Cambridge University Press, 1982.致.图9中横坐标表示的是pn,即以fi为优化目标的种群在整[2] Taylor P D, Jonker L B. Evolutionarily stable strategies and个群体中所占的比例,取值为从0到1,间隔为0.05的20个game dynamics[J] Math. Bio. sci. ，1978, (40):145-156.实数.实验重复10次,图9中标出的点为10次重复实验的平[3] Zitzler E. Evoluionery algitoms for multobietire optimiza-tion: methods and applications[D]. A Dissertation Aubmitted to均结果.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种群所占 比例对演化稳定策略的影响[ 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的增加,演化稳定策略的Conferenceon Genetic Algorithms, Lawrence Erlbaum, 1985,93-100.目标函数1的值有明显的下降趋势,而目标函数2的值则有明[9] Xie Teo, Chen Ho. wang, Kang Lishan. Evluionary algorithms of multi2 objective optimization problems [J]. Chinese显上升趋势.通过对EGOA算法的分析,我们可以对这种现象Journal of Computers. Aug. 2003, 26(8); 997-1003.作出合理的解释.当群体中以函数fi为优化目标的个体数量[10] Hajela P. LinC-Y. Genetic search sratgies in mulicriterion op-较多时,该函数具有- -定的优势可以首先寻优到一个较低的timal design[M]. Structural Optimization, New York: Springer,June 1992, 4: 99-107.水平,面其他函数在此基础上进行优化,从而导致最终的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总结ence on Genetic Algorithms, San Mateo, California, 1993, 416-本文提出了一种新的基于演化博弈的优化算法(EGOA),[12] Horn J, Nafpliotis N, Goldberg D E. A niched pareto genetic al-gorithm for multiobjective optimization[C]. Proceedings of the用于多目标优化问题的求解.在该算法中,每个个体记录了个First IEE Conference on Evolutionary Computation, IEEE体所采用的策略的同时,还记录一个信息标记着个体所属的World Congress on Computational Computation, Piscataway,NJ, IEEE Press, 1994, 1:82-87.种群,种群信息对应个体的优化目标.它借鉴了演化博弈的思[13] Srinivas N K. Deb multiobjective optimization using nondominat-想和选择机制,在每一代时,随机从群体中抽取成对个体并进ed sorting in genetic algorithms[J]. Evolutionary Computation,行重复博弈,以在博弈中取得的效用来确定个体的适应度函[14] Deb J, Amit Pratap, Sameer Agarwal T. Meyarivan a fast and1994, 2(3): 221-248.数值.在下一代的生成过程中,子个体除了从父个体处继承策elitist multiobjective genetic algorithm; NSGA-II[J]. IEEE略信息之外,还继承了父个体的种群信息.我们采用了特殊的Transactions on Evolutionary Computation, April. 2002, 6(2):适应度修正方案来确保整个群体中种群的分布稳定.相对于[15] Zitzler E. Laumanns M，Thiele L. SPEA2: improving the182-197.文献[6]中的基于演化博弈理论的协同进化算法,我们的算法strength pareto evolutionary algorithm for multiobjective opti-具有更强的通用性.为了对EGOA的性能进行评估,我们采用mization[R]. Research Report ,2001.了一组多目标优化问题(MOPs)的测试函数进行实验.实验结[16] Knowles J, Corne D. The pareto archieved evolution strategy: anew baseline algorithm for multiobjective optimization[C]. In;果表明,使用本算法搜索得到的演化稳定策路集合能够很好Proceedings of the 1999 Congress on Evolutionary Computation,地過近多目标优化问题的帕累托前沿.Washington DC, 1999, 98-105.虽然用于多目标优化问题的实验结果比较成功，但是本[17] LohnJ, Kraus w, Haith G. Comparing a coevolutionary geneticalgorithm for multiobjective optimization[C]. Proceedings of the算法的应用仍有需要完善的地方.EGOA算法基于演化博弈2002 IEEE Congress on Evolutionary Computation, May 2002,理论,它最终求得的解为博弈达到的ESS.但事实上在演化博中国煤化工弈中,ESS表示的是演化的均衡解.另-方面,从我们的实验附中文结果中可以看出使用本算法求得问题的ESS集合与帕累托最[9] 谢MHC N M H G计算机学报2003.26(8);优集合一致,呈现该结 果的理论基础还有待研究.997-1003.