外文翻译-一种基于树结构的快速多目标遗传算法

附录4附录4一种基于树结构的快速多目标遗传算法介绍：一般来讲，解决多目标的科学和工程问题，是一个非常困难的任务。在这些多目标优化问题(MOPS)中，这些目标往往在一个高维的问题空间发生冲突，而且多目标优化也需要更多的计算资源。一些经典的优化方法表明将多目标优化转化成为单目标优化问题，其中许多运行被要求找到多个解决方案。这使得一种算法返回一组候选解，这比只返回一个基于目标的权重解的算法更好。由于这个原因，在过去20年中，人们越来越感兴趣把进化算法(EAs)应用到多目标优化中。许多多目标进化算法(MOEAs)已经被提出，这些多目标进化算法使用Pareto占优的概念来引导搜索，并返回一组非支配解作为结果。与在单目标优化中找到最优解作为最终的解不同，在多目标优化中有二个目标：(1)收敛到Pareto最优解集(2)在Pareto最优解集中保持解的多样性。为了解决在多目标优化中这两个有时候会冲突的任务，许多策略和方法被提出。这些方法的一个共同的问题是，它们往往是错综复杂的。对于这两项任务，为了得到更优秀的解，一些复杂的策略通常被使用，并且许多参数需要依据经验和已经得到的问题信息进行调整。另外，许多多目标进化算法有高达oQmN2)的计算复杂度或者需要更多的处理时间(G是代数，M是目标函数的数量，N是种群大小。这些符号在下文也保持相同的含义)。在这篇文章中，我们提出了一种基于树结构的快速多目标遗传算法。(这个数据结构是一个二进制树，它保存了在多目标优化中解的三值支配关系(例如，正在支配、被支配和非支配)，因此，我们命名它为支配树(DT)。由于一些独特的性能，使支配树能够含蓄地包含种群个体的密度信息，并且很明显地减少了种群个体之间的比较。计算复杂度实验也表明，支配树是一种处理种群有效的工具。基于支配树的进化算法(DTEA)统一了在支配树中的收敛性和多样性策略，即多目标进化算法中的两个目标，并且由于只有几个参数，这种算法很容易操作。另外，基于支配树的进化算法(DTEA)使用附录4了一种特别设计的基于支配树(DT)的消除策略。这种策略不仅维护自然种群的多样性，但也意识到精英主义没有额外的消耗。六个基准测试函数和三个著名的MOEAs(如NSGA-II,SPEA2,和Jensen的改进版本的NSGA-II)被用来检验DTEA算法的效率和效果。程序运行时间实验表明，DTEA算法总是远远快于基准算法,尤其是在人口规模很大的时候。另一方面,通过检测三个评价解质量的标准，我们发现，整体上对于收敛到真正Pareto最优前沿和维护种群多样性来讲,DTEA算法的解决方案质量并不比NSGA-II和SPEA2差，但是DTEA算法的计算所时间要短得多。本文的其余部分安排如下。论文第二节简要回顾了先进的MOEAs，第三节详细描述DTEA，第四部分给出并讨论了实验结果，最后，第五节总结本文。概述MOEAs本节简要调查当代MOEA研究。第一部分将给出在本文中使用的一些概念。第二部分将简要分析当前最先进的多目标进化算法。2.1在多目标优化中的定义许多研究人员都给出了类似的定义。我们在这介绍两个重要概念的定义为了不是一般性，我们在本文中只考虑最小化问题，它很容易将一个最大化问题转换成一个最小化问题。定义1：一般的多目标优化：一般来说，最小化一组多目标优化函数F(X)=(f(x),...,f(x))，约束函数g(x)<0,i=l,...k,xgQ(0是决策变量空1mi间)一个多目标优化的解可以使m维的目标向量F(X)的一部分达到最小，其中X=x)是空间Q的n维决策变量向量。定义2：Pareto占优：一个向量u=C，…,u)是占优向量v=C，…,v)(记lmlm作uAv)，当且仅当U部分小于v，即SmJu<v，并且丑gU,...,mJiiu<v。ii当前，大多数多目标优化的研究都是基于Pareto占优。(在一些文献中，

Pareto占优也被定义为严格的y，这里我们并不讨论他们的区别。)一个决

策变量向量xgQ被称作Pareto最优解，当且仅当不存在ygQ，使得

F(x)yF(y)。所有Pareto最优决策向量被称为Pareto最优解集。相应的目

标向量解集被称作非支配集，或者Pateto前沿。根据Pareto占优的定义，我

们可以发现在MOPs和SOPs的解之间的关系中一个截然不同的差异oSOPs附录4的解在目标空间中是标量数字，并且它们的关系有两种可能性：小于和大于（包含等于，为了简单起见，经常称之为大于）。然而，MOPs的解是向量，并且它们之间的关系有三种可能：Uav，UyV和非支配。这些差异要求MOEAs要有更复杂的适应度评价规则。2.2先进的MOEAs一个良好的MOEA必须满足以下两个点：（1）得到的非支配集要收敛到真正的Pareto最优前沿；（2）一个均匀分布的解决方案是可取的。这两个目标往往是大多数MOEAs的性能指标。许多方法被设计用来满足这两个目标。为了解决第一个方面，一个基于Pareto的适应度评价方法通常被设计为指导朝向真正Pareto前沿进行搜索。其基本思想是根据它们的支配关系对解进行排序。Goldberg第一次提出了一个普遍的方法，解集按照不同的支配序分成不同的前沿。Fonseca和Fleming提出了一种方法，在这种方法中，一个解集的支配序被解的数量和当前支配它的种群赋值。另一个排序在SPEA2中被提出，在这种方法中，每一个个体都被分配一个强度值。对于第二方面中，一些成功的多目标进化算法提供的密度估计方法以保存种群的多样性。Pareto小生境和适应度共享技术在许多多目标进化算法中得到广泛地使用，例如，在NSGA,NPGA和MOGA中。在SPEA2中，第k个最近邻密度估算方法被应用于获得每一个个体的密度指数，NSGA-II的定义了一个新的密度估计度量，它不需要任何用户定义的参数。另一种流行的策略是使用超网格把目标空间划分成单元格。此外，一个新的eliminating多样性的方法也被提出。最近，一些新的进化范例成功应用于多目标优化，例如，粒子群优化，人工免疫系统，估计分配和分散搜索。张和李提出了一种新的基于分解的多目标优化。这种方法将一个多目标雨花问题分解成为多个标量优化的子问题，并且在同一时间优化它们。此外，为了得到良好的解，一些有效的技术也被采用。目前的研究表明，目前的研究表明，精英主义可以显著地提高多目标进化算法的性能，它有助于防止优秀解个体的丢失。对于避免过早收敛和不必要的计算复杂性，一个动态的人口规模，在线自主调整人口折衷和密度分布信息的特性，已被认为是比恒定的人口规模更有效和效率更高的方法。此外，使用不受约束的精英归档可避免被估计的Pareto附录4前沿收缩。虽然有很多的多目标进化算法在采用这些策略和技术的一些基准问题上取得了良好的表现，但是这些算法还是有一些不足。一方面，许多多目标进化算法错综复杂。为了获得优秀的解，许多多目标进化算法的收敛性和多样性使用单独的技术，即使这两方面在大多数多目标进化算法中最终融入个人的适应度评价。此外，在多目标进化算法中，许多参数需要根据问题域的知识和经验进行调整。例如，在DMOEA中，使用6个策略和四个参数需要进行调整。另一方面，许多多目标进化算法耗时。由于与单目标优化相比，多目标有优化通常是一个难计算的问题(比如三值关系)，所以，由于大多数发表的多目标进化算法有高计算的需求。还有一种解释是MOEA的研究往往忽略了问题的计算复杂性，幸运的是，许多研究人员已经开始注意到这个问题。Deb等人提出了一种快速非支配排序算法来减少计算复杂度，在NSGA-II算法中，非支配排序的计算复杂度从O(MN3)降到0(MN2)。Jensen系统地分析许多当代多目标进化算法的计算复杂度，并提出了一些有效的非支配排序算法。此外，为了减小难度，一些数据结构也被引入。四叉树被检验作为把精英个体存储到非支配解中，这个不可约的支配图(IDG)被提出以用来管理种群。为了促进带精英策略的非支配排序，引入被支配和非支配的树结构。这些新算法和数据结构在某些程度上加快了适应度评价的处理。然而，它仍然需要进一步调查这个重要问题并且设计简单而又有效的适应度评价方法。基于支配树的进化算法支配树支配树的结构正如我们所知道的，适用度评价是多目标进化算法的重要组成部分，它高度影响算法的性能；并且它在处理时间上非常耗时。大多数基于Pareto的适应度评价要求每个解应该与其他大量的解进行比较，这使得大多数的MOEAs计算复杂度限制在OQmN2)。请注意oQ2)因子意味着随着种群数量的增长，使得计算复杂度增加非常快。然而，在许多情况下，MOEAs使用种群规模非常大的，特别是当相互冲突的目标非常多的时候。因此，这种困难需要解决。附录4附录4通过分析一些常用的适应度评价处理过程，我们可以发现在这些过程中有很多不必要的比较。个体之间的占优关系可以在一个图中看出，每个节点代表一个个体并且每条边代表相邻节点之间的关系。例如，图1显示了五个节点之间的占优关系。我们我们直观地观察可能有一些冗余的关系在图1(b)减少这些冗余的关系可能是一个有效的策略来减少适应度评价的计算复杂度。因为Pareto占优关系是可传递的，一些关系可以基于现有的关系来推导。以图1为例，如果我们知道N4Pareto占优N3,N3Pareto占优N2,,那么不用通过比较我们也可以得出N4Pareto占优N2。因此，N4与N2之间的比较可以避免。我们也注意到了另一个现象,我们只需要获得种群中每一代的Pareto最优解集,即使那些占优的解仍然对于进化过程有用。这样的原因是决策者经常基于最优解做出决定,而不在其他解上花费更多的功夫。也正是由于这个原因,许多解之间的关系(例如,解之间的占优关系)是不必要的知道，因此这些关系可以去除。在图1(b)这个示例中，很明显N1和N4构成Pareto最优解集。我们可以观察N4占优N3,N1占优N2。因此，我们并不对N2和N3之间的关系感兴趣并且这可能不值得花费时间来比较或推断它们。通过以上分析，我们能找到两个原则来减少不必要的计算时间：(1)避免冗余比较(例如依靠推理来推断这些关系)；(2)只保留必要的关系(即，忽略那些不是非常重要的关系)正如我们提到的，不同于SOPs的解之间的关系，MOPs的解有三值关系。它可以归纳成一个叫做Better的函数。定义3：Better的函数卩，F(X)yF(x)Better=GX)=<一1,F(X)yF(X)1，2210,nondominnate这个Better函数是一个三值函数。当x的目标向量占优x的目标向量，Better(x,X)=1；当X的目标向量占优X的目标向量Better.,X)=-1；当122/、112X、X互不占优时，Better(X,X)=0。我们知道，对于排列标量数的二值1212关系来说，二进制排列树(BST)是一个非常有效的工具。在二进制排列树中，一个节点的左子树所连接的节点其值小于它本身，一个节点的右子树所连接的节点其值大于它本身。我们考虑多目标优化的三值的关系也可以被存储在一个扩展的二叉树中。接下来是作者早期在Ref工作时提出来的关于结构树的思想，为此目的,我们设计了一个特殊的二叉树。图2中的一个例子表明图1中节点之间的关系。在图中，Pareto最优解集是｛Nl、N4｝，主要的关系被保留，许多不重要的关系（例如，被支配节点之间的关系）被忽略。作为一个新型的二叉树，我们称之为支配树。定义4：支配树（DT）。一个支配树是一种二叉树，定义如下。1）一个支配树一个外部节点或者一个内部节点，其连接到被称为左子树节点和右子树节点的一对支配树上。2）每个节点在支配树有中四个域：id、计数器、左连接和右连接。其中，个体节点代表id域表示所代表的哪个个体节点，计数器域表示左子树的大小（包括它自己），左连接域连接到其左子树，该节点占优它的左子树的根节点，右连接域连接到它的右子树，该节点不占优它的右子树的根节点。DT的定义与BST的定义相似，DT和BST也拥有近似的性能。例如，在DT和BST中，一个节点的子代是它左子树的根节点；相应地，这个节点是父代节点。DT也还有一些不同的特点。一个新术语“同级链”在DT中被使用。DT的同级链被定义为由它的根节点和它的右连接节点构成的链条。因为每个DT只有一个根节点，DT根节点的同级链有时在下面章节的部分被简单地叫做DT的同级链。通过跟踪右连接域，可以获得同级链。以图2为例，N1和N4构成DT的同级链，其根节点是N4。此外，N3和N5也构成DT的同级链，其根节点是N3。值得注意的是，虽然具有相同的名字，在DT中一个节点的左子树和右子树与在传统的BST中一个节点的左子树和右子树有着不同的含义，因此，他们的属性也不相同。这一部分将在第3.1.3部分中讨论。附录4附录4」」56ST&WE-seetrcralnTlSEr.trawn£cpinj：lxE?2dO9RiblhbudbyHsuvitrBLV..^Mlrij;hbrtibcrwd.附录5AppiralSoflXficnpEJinj;10[2UJ0-；刪屮恥HSHAKERCorrtmlslistsis™iliaWedtScScnccDinsctHSHAKERApplied5oftComputingji7ijrndllhonnEt^agE：www.eIIxeivihr.edm^ldcEkas*a匚AfastmuRi-objectiveevolutionaryalgorithmbasedonatreestructureChuanShi*ZhenyuYanbpZhongzhi駅巴LeiZhang，Rhji'i^K-rjF^-uril&i'nritjn-il-rfJ^niTTi-'ks'ljrnruuljii■ad'L'rij网陪WiJ血Ltriif^hji'brnriiMABt-i/rijtAn^rT'iCyPuif<iuudTii-iniirnriiunH■d'liiri'i.fi-ying?(IKSill.「.biiim^LMr1Nn!nTni:ofSd<rrz0』Fn.Qrmatiai切阳11冈口碉Lrtuvrmlyof诂間ma占!虫CAA^FnsSituIc于C^TTJuSiiirIcr.tnohjp.Ch'neSrAroderrsf"So<™e±j«O由.thiruAEfI1匚LEINFOAHSTELACT.^rndfhffiory:Ihispaperpraposes屛角代nwluti-wiaryalfiDrirhmba曲onatreestrartureformolti^Dhjrctivttecumd15J^D-uar^-RtthVtdinrt^iZhfffl30jurt-1009血疋口1就J3AtjbuJ2009ftiniildNeMilinc21轨翅问q3[lml2J.iKjrLTh^if鸵scnMiiir^,fumvd塔erve(DFi,比abktopre^ruedhe门自―丹巧FarewdtxnijndiitE-rekuonsjehieeindividuak-elleciDVElY.口diedensitymJkinnalianimplick.lyaandreducesciie-numhwnltnnpjnsan^dinfingiindivid口』凶u^niFwdntly.Thenolutiiwiijry■alMrithmb/fE^Ion"Drnifiam昭ircttD'ltAjint££racesthe代nveiEeiK在strareE^'^nd也wzrsrtyHrare^Yintcthe-UTandJCrywhdsrMulri-T<iji!,ibW,C^WilufiMrtiiyAljfwithinPjcifrodamrurKrFitM-^sdsgnnienlLlirrnruEinf处削国丫enqployt□UTba^edelJammcin.^^crac^gyttucreakie^-efukmandpr^rve^popubikMidivecsirywithouteckIrdtimejndipdre-匸□盘i.Nurwricj1■rfl.perirn-fnts.showthatDTEAismuchL吐轄itthdnbfeGAD吕ndaniimgirDVEdveisi-DnofNStA-ll.wliilerufaluncnquahb*tscompemw-ewiiththoseof占PEA2andNSGA-I.CrwnCqpyri^ht■S2009ftjblislhedtiyEhrtfierfl.V.ftIIn£htsrrwrvrd.1.hltiXhdiicdlWkSolvingmiulti-flbjMrive呂匚i)enl~ifirandenginBeringproblem旨冶.generalJ^saverydifficultInthesemulN-objectiveoptimizationpnobleniistheobjectivescttencontiicract<ksah塚h-dimensiondillprobiem^paceandtheoptiiEnizairioj)ofMDPwma^rjIsorequiremtensivecoinputaLianaljesoumegCljsskdloptL-niizdtLonme(lL«lEsuggestcomverdnglli€HOPt«j.singleobjectiveDpijjnLzjtLDnproblem(SOP；,inwhichntanyruns-arereqiuiredlLuHjhIthenidtiplesolLLtjojks.Ulism^kes且口algorithmthditjetiniisaEetDtcjiLdidatesadilionspretenbLeta-ji)aLgorithmthdiireturnsonlyonesolutionkisedonsujneweightsoftheobjectives.Forthis-reasonPthere])mbeenanLncreasin,gint-eresti\iapplyingevolutionary^IgaridimsiJEAa)to1(01^inthepjst20years|1丄Mdiiiy[Gmlti-u4bjc!CLivuwukiLiOikiiy刖呂uri【hw(MOEAf)Imvcbeen屮upusudl.Tht^c：MOEAsumjPaivCijduiiiickuircelu-guidetheL-vdirch.AildreEurnd张liiLH：i£kji]]iiuiLvd^uliutimii^血direcoilLUhtikcLil血维Le-DbjMtin€pLi[Tii2dEjoi]rwhmHiidiiogtheDplLtiidls&luLiDii茁(heuLduLdlvgOdl,山tiretwoinmulti~ubja：LiMupLiEGii^ddua]：〔1)wia^M^eiaci!lu山亡卩山低询DpiLtiidl梵1diidl[2)iiULiiii3]iiiiQjofdi^ersiLyiondiuPiihMODplLCIIdlsulutic>]l!!iSdL[2].Mdliydlldll]UltNLl€hluvebeenintroducedt&addressrherwosomenmeconflictlFig^ojilsinMOPsm，AcommiDnproblemwiththosemethodsisrhartheyareoftenintricate.Toaihie^'ebetterEotudoinsinreinnsofthetworbe£0<n卩lierhistrafegiesareuiujlhyusedandanciiiiberofpdramerersneedbeadjustedaccordingtorheexperieficesandpriorknowledgeofgivenproblems.Besides,nunyMOEAshaverhehighcomputahnruIcomplexitywithfli；dcmareprocessingHee(GisdiejnuntberofgeneratianiE.Misdienumberofobjectives^ndNisthepopulaticmsize.The&e^ymboilsmdjjUinthes-amemeanjjigsthr<JL^]]outdieloUowijng：sectioriE}[*lInthispaper;weproposeafastmulti-abjeclLveevotutiandiya[£crithmbjBedjon]atreestru-cture.Thij-dl^UstructurejsdbiiLdiytreethjlpreseru'esthetlnee-valueddomindmeensljtio-ns(i.e.PdomiiLMing,dominatedJiidn-ondoininatedIajnongtliesolutionsofaMOPindthuswcjijivh?Lti/orRiiriutiRg[他(DT).Wkhmecui]icfui!piupeitL^SrjOTiydbkLtKim【日i】】LlL^dlEJiEsiiyiitfuniidtlLOiiuT[iidivitlud.LsimpLiCLdy.jillIredoesdx:£Qiiiip-ariSQi]!!iimioiig[udividuaLsdL^liiHidy..】lieLmikputiilLCinjIwiiipS^Kil^1・nii!]]ib<lL*£Qiifii[Gitlid[jOTls朋vffititnctoollqnidiiidg^ih£pupuUlLun.TlievululicMidirydiLg-uriltiiciib日乂clmUurNinudr^[irefDTEA)iiJLugRiI悟Ll比£uflu-CiCfirreEpiudjngduihorI-nmJoddnss£$;^hKhuan^bupLcdiixni[匚左hH3'u^lwlrruiLcani(Z,¥aiP,LShi?u-Sj(s.ktJC.Lft[7.5hiXi-Cdu.Cii(LJJidnjJ.giCiKC,dis!divti^ilyftidiLc^icS.m』i:n吧lythetwogtMlsindMOEA,iniu山亡DZJiiLdas启luci^^quuiirLX!.itw?dl^uniliniisEdsylqpupul-dit:wlti\onlly<ll<iwparameters.!naddlQon.DTEA.employsrnElinrnMln雾sirjregyhputidllyckHgn已1bd^<?d.uiiDLThisSLidilrgyituEciilvJiauiLciiLiiiJS血亡diversityofpopuljflcinnj[uralily.buifalsorealizesriirismwiLliuutrxtidicofiLfiaSixbei}£luiidiiktestfu[i£Lioii!!i<lihl1dneewull-knowiiM0EAi=NSCA-II[2LSPEA2fi).CfirreEpiudjngduihorI-nmJoddnss£$;^hKhuan^bupLcdiixni[匚左hH3'u^lwlrruiLcani(Z,¥aiP,LShi?u-Sj(s.ktJC.Lft[7.5hiXi-Cdu.Cii(LJJidnjJ.附录4附录4C5hJFlaL/^,pr«f.刚rEmpufl■吧1PfSHd)硕7閒eflici^nQfandeffectiveness(4DTEA.TherunningtrmeexperimentsshowthatI7TFAisalwaysnnxhfasterthanrhebenchmarkaliflrirhms,especiallywhenrhepapuibiricmsizeislarge.Omrheotherhand,byexaminingrhethrwcriteriaforfudilluatrngthequality1ofsoluthn^,wefindrhjEttwsdulianqualiryofDTEAingenerallsnotworsethanHSGA-IIandSPEA2intwins,dfbothconvergingto[hetiuePanetooipiiiiialfrontandmaintdiiniingthediu-eci【y亚『[He?p£jpuldlimi,JlllnjughH址匚卄nuputi：!坍EiiiNfi啊皿iEtlbyDTEAisniixhshoner.TlielucGkiicid.-eroft\mpjptii9l£jrrju^d册IbDcnv^.気Clkm2bnelVreviewsritesute-oMhe-inofmdeas.sknon3.血丸DTEAindeuiLs.Stcnan4presentsjnddiscussschcexperimentJlr&sidlES.Finally,Sccdm5conduds[lusp^per2.AilcwervlcwofMOEAsThisGKnongivesabriefsurvey-onconrcmp&rjirymoea「出£占[仇Thefirsip^nwillgivemmeKnons⑷Eku^edlinmepaper.TheSKondlpjrtwillhrietlyAnalyzethecurfcnrstjtfetheartofMOEAs.2LM诚rtsiit.MDPManyresearchershavegiv^n§imilLairdelinitons|36,7jforMDPsWeintroducethedetinirionsolhwimpoftantconcepCshere.Withoutlossofg^neolily.weanljrconsiderminimizationprablemsin伽衽paper,anditisedsytoconvertaimwKimiza丽onprobleminli)niiinimiza.t]DjipnshleiTLDdaniflim]I.MOP[3|:InanMOPi]iii^.[ili2e£即0=(齐熔L…Jrfl窗)£昨口址dmdHMLihHJiivjridbL^AnMOPiuhitioiiLliefoniponfinGofanm-dm^enslonalobjectivevecrcwF<t?«Pwherej?=ini；%i店qnrt-diitKyn^ionjdd^cLaonvana&JewererfromsonicuniverseflLlefiilionXf'jretodominante|3|:AvectorJ-fUi,.…umjissdiidtddomLfuireP-rF…汗用i(denotedbyit'^ndonlyifif時测盹幡厂碍杓旧1..叫心脇⑴MckCconteniporjiyresearchanMOPisbasedonParetodomiiunce.(Insomel^raryreiraretodoniirunceisdsodefinedwithstrict呎17||.HerewedonordiscusisrhediItenence.1AdeciswnvectorxeS2is站idtobeParetoQptimalifandonlyifthereisnojF«J?forwhichF(j?lfilesetof3*PdietooiptimddecisionvectorsisfilledthePjretooptri™!lsetThecofnespondingofri)eobjedLvevectors订railedtheitDixIomijiatEdspt,orParetDinxit|E]AiHuftfingktditdeiiG'iiiEkii]uf卩也佢[bduiikiwfCjiidi^uvei*j遗、由忙【diffifreiM.1!b帆w•虽!nMOPb机砧SOPsiiiiE^iiii^oldieidjiLKHii^dciioi]gbulutkiiB.TIiebulutioi]^id【I卅ubjtrdlivEi)fSOP^jre丸did】iiuiikb^rji：jndlIlnarIacimBluve阳。po乌lEtm區：smilermanand.lir^er【tun(Including"equalro,pPfor幻nipb忙ly沱isciliensimplycalledlargerrhan).However,mesoluclonsofmops』rc讥乂旳rs朗打thoirrclanonshave[hiecpo第曲iMies:amdnondomlnaredLThisdifferencerequirestintMOEA5tuvemorecocmplicdtefitnessassignmentrules.22Srare曲fbeart時M0£躬AgoodMOEAmustsatisfythefollowingtwoaspects:⑴rheresulringnondominatedcomergestortetrue卩anetooptimalIront:(2打uiniformlydistributirnofrhe^Muilfon515desirable[2J[Thesetwog-ojisj-meofcenih-eperfonrorKemetritsformostMOE^is[2,5-G]Ma呵methock和芒de&i算阳dIn-r?achthes?tWD£：aale(1|.Tddddressflielir^taspect,a卩anehkb^edfitness^signmentmethodisusuallydesignedreguidethe^ejrchtowardrhetruePanet&front[B]ThebaacideaistorankthesotuilionBdocoirdingtotbeiirdoinioa^cerdatiDns.GoldbergfirstproposedapoplWmethodthatthe^kirLonsrtledmdlKlIintodiff?rentiTontsWLlhdiffprenE「边rilesp].Fbnse匚aaiidEymiDgproposedimBthodwheretherajikofaailiitjain治日退i卯edlhenLimbeiofsolutidns血中wiMedwiEh[hgcurreiiiEpopuldEbiidumihirii]^iv|]Q].Duenwreniediodwaspiupcwd.inSPEA2[5|血叱诧ejd]indl祁idudl[£d^^i^ewd.d£l诧【1莒L】i甘出1口吐FurItm尝tunlltiHne^iJcc^sf口IMUEAsprovidethediRitiiyesonunonmethodsropreserverhepopLilj[iK>nd^'crycy[邛PJUferDnichingindfimssstunnj;werepopuurlyusedinnnnyMaEAsJorcx^mpte,insga|]1],NPGA112]andMDGA[W]LJnSP£/i2(5]|.akrhncjrcsrnflgtibordcnslcyestinutkmnwrliodwasdppliedtoD^tJanthedensityindex-ofe<Khimdiividua].NSGAIIdefinedanoveldensityestimahonmedicthatdoesnotrequirejnyuserdlefincd!pMjmeter|2丄Anotherpopulartacticdividedtheobjectiveapj.eeintocdlsusing』hyp芒rgridlMoreo\!erPanewE-tliminatingdivei或tydpproachwd&ahoproposed|14J5|.Recently,somenewevolurionarj^1paradigmshavebeensuccessful^appliedroMOI^.forffiampie.particleswjrmopEimizatiof)[16|!sartifkialimmunesystenE|17].e^imatinnofdisrnbuIbDn『1叭indsrattef連arch卩？].Thing边ndLiiho卩no卩皿血IanewX1OEAbasedondecampositkiiiThismethoddecomposesaMOPintoanuinbEfofcellarDptimiza.tk>nsub・pitabiHiisdciiddiifn珂Uni辺凸釘euLcmi跑ufly|20|iInjdiliLiuuseveraleffaclwel^dniiquifhhaw*disc1%也1jdupu*Eitoobtain^nodi5»luiiDQ£.The匚urrentrese^rrhhasshnwnthatthediE^FDiCMimpruveHi虽]里1佃口血山馆心IPe>WIDE也新giiilic』il推d£tdiLItdp^IdprevtidLthel心滋of呂uudl古心1口Um沾unmLh号Iijveb^ikfbuikl[23211LAdyiidicTiicpupuladoii血已ddjubt^dduEui]ui]]DUhlybylIkonliiKfchaidLEeri^dLtirfpopulddoa]traderITanddensitydl^Dlbudoninformanon,has血蛭nfound[0bemoretfftciencjndeffoedveman<1c-onsQncpopuljcmn5122inteims时jv创dungprcmiMiircconverjsenccandunnecessarycompufjrionjicompledry|&,22].Morwvef,usingunc&nsrfaiLrKdEl【£ijtchivescouldd-voidHiereneatiiisand^hrinkin^estinured.Paretofronts|23|.Although-anumberofMO£^tuveaichieved嚣oodpertormancesinsomebenchnwrkproblemswiththesestrategiesjndtechnologies,therearestillseveidldisdd¥dnir3geswiththesealgorithm^.Onitheoneh生nd.manyMOEAsinfricareToobtaingoodsolutions,manyMOEAsU5€separatftechniquesforconvergenceanddiversity,dlrhoughthesetwoaspectsareeventuallyioreg.ratf!dintothefitnesse^'alujtionoftheindividkjalsinmastXfOE^s[2,5/G].In^dditiDiimanyparamFlefsintheMOE^sneedtnbe由dljustmdarccirdlingto[|佢prtiljlE?!]!>d4)iiunikikiuulE^dg't1Jiidtoperient^iFunxAiH卩I已dx鼻are口生客ddiidfuur驾imedmbea-djustedinDMOEA|計OnUmdiIhtIijchI,iiijii^MOEAijreliiiiE-cuiEiLmH"普.Thehighccmpucarlondemandofmete[:pubLigiiedMUEAs佬pirnallyduetoitw?fjcrchiliMUPlsusdtilly2hikfdcocmptiiaimnproblem杞.缶b也加鈕of【IkrhrcE-vaJucdre[ions1asfomparedtoSOP.AnwhcrCKplanauan1址占Lnrlictaath^itheMOEAresearchhisoftenneglectedtheissueafcomputarkna]c&mplecilyH].Fortuiutfly.maiiiyreafjrchershavebeguntopayattenriontorlirisproblem.DebetitproposedjtlstnondominMedsortalgarithmtoreducerheSEputMidrid』c&mploilyofrhenoDdomindt&dsortprocessfromCKMh'J)toOiMiV2)iinN5GA-II|2|.JensenhassystemkallyanalyzedthemmpLitjrionalcomplexityofmanycontemporaryMOEAs,drxlpne5fflntedsomeefficientalgorithmsfoerheiwndominare-dsortFnfprocess|4]Mo疋met,somedatasllnictuireshavebeenintroduced忖alL^vutetheditfi匚ultyQuad-t™ha^beenexamined血anCSJlJiftGwipLrVrE皿口值d；如」帥elitejrchivetoMrenrondomirMtedsoliutiofis|24J.Theirreducibledominatiflnigraph(IDGJw奄proposedtomanagepopulation|25].Domiiy(edindn-Dndominatfdtreeitmcnifeswereiirnrroducedtofacilitafeth?nomdomtnatedso市ngintheelkearchive[23J6|.ThesenewailgDritlim^andih佶stnucturesspredupthefitrwssdssigiiimenlproemstosomeextent.Hdwfvfj,ilii£rill,jiabletofurlherthisimportantge^ueanddesignsimplebutefficientfitnessa&signmentappm^匚bes.3.Evolutionary占堆。『Mlim也丸。ondomiiiatiu^tree3.1.Du闭机说叫£1怡帖J.].].StmctureQftfamirtdtingiFrcAsweknow,thefitnessassignmentisakeycomponentinMDEAs.whithhighlyimpictsthealgorithmspertormantf：andirisjhojctMtlym^ttwintermsofthtprocessingrime.MostIPdir€tobasedfitnessassignmentsr£<)unerhjteachsolutionshouldbecomfaredwithala唱吃numberofothersolutionsrwhichimposesm-ostMOEAawiththeccmpuftdrionalcomplex-iirie5boundedbyOfGM普)[4J.Pleasei>oterhart:(h：得〕factorme^nsthecomplexitygrwsveryta^rasthepopulationsizeintreas^5.However,inminysituati-onis.it占desiirablerousel^ngepopuldtiDHsiz^forMOEAs.fsperiallywhenfihenumberofonfllfcringcibjertivesislargeThus,thhdilemi™need?tobeadd「盛礎d.Through^j^lyzing&ame□(the卩npoldr$Ee們a&signmentprocesses.,wecanfindIherearemanyui^iieizes^arycarnprisnnsuilI[臥卩ilh足妙.Tlwdotinnjih:E*r^htoLNisjniuikjjiiildividujkcdi]be^LibUdlLZedwiLlidgjapti•曰KhiihlkI.^repie^enlhdi]Lildividujldiadeai.li^dgertpi'eseutithe『创dLiunbe[wse]][]ieadjdLSiilcihlhI^;.Forejcjcuple,Fi冷Iullui-tiJle£H】edmiiiiLJiHj!!reldtiLKk£Jinuik^HuQ【itid出withdgisph.Wenilu.i[ivE]^ubsa-uivethattheremight血somere>lundinEfdanonsinH*.l(b)_Roduclingthesefedundantrclanonsmaybeeffi£lenitstrategytoreducerhecompuractonjlcompJoatj1oftheArncssassignmem.BecauserhercJatio-nofParetodominiinccistrjnsLtivc[7]Pscwiierelations-can阮dodtictdtoiledontheexistingrelations.Tdlcingfig.lfb-lforexample；ifwtkncwN4卩arctodominatesNJ,andNJParetodomLnatesN2,th蚀wecandeduceM巾比中d^minartesN2wirhoutiny<lireLtcomparL50fli.Thus,,thecompf-isofibetweenM4andN2cjnbeavoided.Wedhonc<keanotherfactrharweonlyneedtoachieverheParetooptimalsetofrhepopuldtionineachgenetairion.alrtouglithosedomiinatedsDlwliQns3nestillusefulforth?e^'oliftitJiuryprocess.ThereasonisthatadecisionmdkeroftenmdkesdecisionsbasedontheoptimaL盟twirtmol:p呼imgmuchattejKL-ontoEheothersalutL-Dns.Alsoduetothisrpason,manyn?]irinnsamojigtbe^olulians(e.g.ptherridtL-onsNino>ngthedannin^tEddreoniKcessarytnIctidiAi,jcmIHmjs[h盛社r^latiunsC2t\be【ediifad.Iii佝赳也)uiTi]d色inFig.1(b]rlii£obvia口$[ha[N1diidN4£imMLuig(hePdrewoptinulsei.W<iCJibDlbstiiveLIliIN4dmi!L[id£ti!i；IM3diidNIducEiiiuLe^N2.Thu、,TeLdEi^]]b^EweenN2diidN3i]]jyiiG【beuflei£u因t-Du£acidilisuyiiulwurthwp^iidlin耳L】理luuipulingIleei-ueilti^rdirectly3mpannj?ordedu-clngit.Throughrueanalysisabov^,wecouldlindrwoprinciplescoreduce[heunnecessarycompunngdme:i]1avoidingthexedurulantffimparLg&ns；L£.,mlerniifi(hoserclatLonsbydeductLon)：[2\onlyprwscrvm^thenecessaryrciations(i.cSrignoringth&y?reJatiansthatarcnotvery时interests).Aswehiivtmentioned,differentmomrherelatbvi^时thesolutionsinSOPs,thoseinMOPs<ihthreeviluclJtonbesiinim^rizedbyatBecttrfunction:DeHiktioi)3.fuiMQonf1Fi^)__FiXi)Better；Z|.j一J=1科庵)二州爲)(2)I0niondDmimtedTh^lui]Cdu(]ihdllirw-vJuni(ueiUl-UclWiaillienbjiiulivevifluLurof5]doiiiiidte、thatof抵Benw僑旦;i=I;whei]Lineubjifclivi!uwlurufJLl£dtiniiiidletlbytlidtu■闵,Bfe■见刖用,i^}=-1;wlH?nLlK*y出用imctikiciiiiidt^d,EentrpE!，^i=0.AsweknbwPLlmbiiidr^佝1iRST)i£an昌伽cd诧(milfurhqi力曙hnovjIuEdreldLhi]^JicKJii^^idld]]]U[[ber£|27].IrkjEIST,jri心血bk?ftKub-Lns*LiuluL<jjnudt!wliuwvaluuh^iiiidillmEImiiiE^dfjulUiEtri^tL-CjkLiii也LqdnudtiwIh>紀valLHfhLhj爭可ChanilHiIf.WHtuikhidei*Llmrhree-vjilued!reUncmsinMOPtmay川血b也storedLnabinaiytreewithexcensmnLFollowingrJieLdejioftreesrrucrureproposed旳thejurliorsrtartyworkmRtf.ps],wedicslgnjsprawlb皿tuyirwforthisAKJL-UC<llllUl^d447：仁Huei<1[:gp血宴ftCaTyjbtmfiI艇4应purpose.AnexamplpthatrepresentstheneldtioiisdniangthenodesinFig.1isshewninFi^2.Inrhefigure,wherethefartitodptimMsct£(NlrN4|,thcmjyjorrelations川亡conserved!andmanyunlmponaiii：『型diim儈[e.書.，e诞TeLaiioiK启irnwgrhedbmiruiedrwd宦)areumfttedAsanwellbfnarytr<s,wenameitcfcmRra耳ngtree.[MiiiniRkmdDu『nfu汕i■嚳[阳e(DrtAddrfifrj^Ciryj[fhe祉jbid^ryOreedefinedbelow.tAdomiit-slirtfnrfiseitheranexternalnodeordininfenMlnodefonneoffidlinjpuiirolPmnmoM昭trees,,whicn占佗ciLted.ttieLEtmb-lwu1daid[he^ub-lr^if>ufItulikidp.2Eachnodeinthe血mil协ti昭tmhds(ourikkk:idLc=ountPleft-lintandright-link,wheretheid!tiddresisterswhichindividualrhenode佬pc•叫eni#[hec*untheldr@gi&G?r&the生曲oflceMftaib-tree(includingirsdf).rheleft-linkfieldlinkstoitsleftsul>treewl»serootnodeisdominatedlbytkutn-ode,indtherightllinkHiedlinksiaitsrLghisub-rreewhoserootnodeisDotido]]ii]iji^dbyilidi[lh1i>.ThedelinitLnnofatDrissimdaftochaiof話bst.DTand1STJhb^lldie他mms.iiii]ldirpiupBrliifs-.FQ『bailiDTHiidBST,anode'schildjstherootofitsaub-tree:conresponrdingly,thenoJcisrheparentofilschild.DTalsohassomediftcrcntfeamres.Anewterm芳Ltding£h2in'lsused.LnOF.The口tdingchjinof』DTisdBfineddsachainconsrhutedbyitsrootandEheroot'srijht^linknodes„SinceeachDrhatsonlyonerootnoderhesiblingchounofdiZTsomcninesissimplycalled【hesiblingchainofrheOTsroofnodeiothefollowing丈Bytracing-downuheright-linkfiled,entcjnobtainthesiblingthatin.丁;ikingFig,2血an&KamplerN1jndN4^onstLiuierheELblLngciinnofrueDTwho毎ttiuXi£N4.h怕佢纲即；H3-JtdN5jIsue£iilS;EiluE^j^blingdidnofrheDTwhoserootnodeisN3.Itshouldbenrotedthjtalthoughwithrhesumendinc!*theleftjndrightsub-treesofdinodeinaDTdrxlairracfiri-omiB5Thave-differenltmeiningsandthustheirpropertiesared.sodifferentwhichwillbefurtherdisoisLcdinSection3JJs工1.2.6阻[?11口初览皿剖i討if匪”曲miiMzRii富[F^eIfweconsidertlutthedomimtedrdMkmi5Mmparj&letothesnulLermanr^ljfionmaBSTannlrhenondoniimarecl佬utkmiscomparablFtothel0irg«e「thaiirelditioninaB5T.amdIbeinaDfisverysimila『h)aB5T.Thu^thetflnslruLtiQnofaDTissimilantothatofaliST.However,£tn<ewekn^wthjrthtrcJarionjmongEh^nudlifhindBSTDwo-valual,wheraasiha[ofjDTisdir^e-vjlu-ed,besidesthesimilarities,,theydohaveaimumberofdifterenrjspeots.UnlikeinBSTPanewnodetobeinsertedintodDFwil]beemreg£hoiceG„Whenttwnewnoded*dominaiedbytheroot,itwillbeinertedintolt>eHeftsub-treeof(beroot.ThisissimLldrtothesmallerthanrelddonindBST.Whenthenewnodeisnondominiitedbyrheroot,itwillbeinsertedintorherigfliEsub-[mnfGht*root.ThkissimilartoiheI百戛MEhdiirelatiomiinaBST.Whenrhenewrwdedomiriatesrheroot,rhemwnodeshoul-dnotonlyrepkeetheroutandlettherootinsertLnroitsleftsiib-ueerbucalsolonrimue[ocomparewlEh[heoiliernodesinitssiblingchainIftherearenodesdorniiluredbythenewnodlePthosedomiiut-ednodesshouldbedeletedfromrhesiblingchainandthenbeinsertedintotheleftsuthtrccofthetn?vvii心dkFig.3demonstratesrheprocessofcireatinjaDTCltif-completetreelgshowninFig;2).Theinputorderotthesenodesisfromft1toN5randrhetn強iring^wp盼厲showninFig.3(a：-(e)■Afrenhefivenodeshavebeeninserted,theDTwithfivenodesisshowninFig.^ej.ltlsobviousthattheDFisunbahneedbccAjscthecauntofN4:whLchi§3)l£thanthaiofNl:wtuchis2].T-obaileelhe匸直巴whhiiEIrftsub-freemovesalongthesiblingchainintheleftdirectionasshowninFig.UTl；Le.,N4withitsleftsub-treewitchthepositionwithINIwithitsleftsuto-treeinthiscw}.Alllbuughliwd£li)oiiduesnutth血郞f【hmrelaiEimih酒陆enudes(mlethatrhenodesinth?siblingchain^restillnondominaredroeachofterl,itbaljnc码rheDT「whichisnowrheamejsrhecompare[r?eshownLnFig.2Anaddiu^rulben^licolrhebdilidncingprocessisthattheoodlesintiiesjmesibllingchainwillbeaojtedbytheircountdescendingorderafterthfproctH.Withthispropertj1.deledngjlnodebecomesveryeasy.Thiswillbefuillwilluwishih电血怆险昭.占Igor汕】m(i.e.pAlgorithm2).Easedonthejbovccamples,weshowEhedDmi'idhngrwconsirucnonJlgonrhmsinAlgofithm].Cdfisei住丁f呢isrhemjmloopafcr«atingaDT.TherearethreeFuiKtiDflsinrh?algari.rhJTks.加din斤昶dind.flddu-iSibiiPigconsisto-frhenecesadryactionswhenanewnodeisinsertedintoaDTStialanceTreeperformsrheh』也ncingp『DCQ弼d^uiij^dabove.Mai«sp^ciftcjILy,ii辺t凸亦enodesinthesiblingcliarniotheircountdescendinjorderbymovingthfnodestotheleftorrightdirectionalongthesamesellingctuin.Etg.1.ILImtrafixindIEhtf匸rcQfi咤prucuu时th皆曲iminalm^InwinFig.Z丁血li*KruirntminlheDixlu*i££id,and.then^hl；nunilMjri£itscountIhf^cquuruzelk”ph±4fic.mC5ftlfT盧血呪帧OsmpLn'rEW(ZCW)Alforilhm1.Pwudocodeofdonsnarinf"叶constnuclionalgo-rithctis产1Cretin皐d湘币昭柏花穴匕pIrccimliltrwtolih-c^tiolcfreeqitir>nmpllacy,pTraonlyiLmil:暇[册册乩山吐ienmmmmdivadual).Mput:AflindSidiinlsinth^pnpiilaticiTiOuLpuL:Llk1/iir.uLUd/rn^f「eu*fLinkCwalndT恨e(FopfurtHchindiviiiljLiJi]^pNewiHide)iilIkpiipulnlionPAdkliiiTrtiefpTrte.pN^wnocte):殖turnplrec;莎__n«teispRi>x,wlienpbteunodeisdominaledbypRocc.*/AddinTreefl.inkpR<H)L,I.inkpNcwruidi；)-；卩R.Mt-3-couiii=pRi：it)i■疋+pNeu-nod^-^wunL,tffpRco^^Lett^liiik==NULL)pRLiUi-^hft-lhk-pNmiKfdk!;M就AJdLTiSibling(pRouLpRoiit-Mell-link.,pK^nftde)：尸pNcwodcbcoinpaTcdwithpCJiild.anod:in11ksiblingchainufpPurcnl'sIcftsiLb^nctwhenpNi^iKKfc話in^urtedinlopPireMMItlisub-lree.",AddlnSIblln£{LickpFarcMLinkpChildLinkpNcwnode)■；switch(Hf^'(pN^ftundc,pOiklHewsr0:"tKHniloffiihhledIfTpOii皿>ri卵-linkNULL]jrfhiid^riu.hl-link=pNcwmde;rl*Add^nSIhllngipPsrdni,pf'hild-^ri^tii-link^pNEwriodEg临牌I;山山rniii^tingpNemucxiecakes(hephrepChtld：AUEiriTn^ipNeuncilj,pCIhild};IWeachnod^耳附皿]山pN^nod^'ssiMimg^n■!Jf(^eHpNewaode.pNcdel--1}{血油epNodeItwnDiesiMin^ihain:1.^cLiinTres(pKvwr^od^pNodeI；Ualan.ccJrcefpPkreit,pbc^n-odk:,L);-liI'ydurhinalcdAddinTrte(p(?hLl4pNewrKide);BalanceTre<j(pParent.pChild.L);・*Sortdienodesinthesiblingch^in卅the洌mttleftaib-tre^intheirKMini:cksKndingci血r.I:〔hicoont时pMoviiKxfe(anodeinthesjkmgctidiinimfre自昶头itmovesalongtb.csiblingClinin.h>IhcIcHdircc-ticim,sjr^ls^IqtherighEdiT^cti™,垃BahnttFree：11\rk卩PjrcnL.LinkpM\ntnslc,inidiiuLLiQii)；if(direction一L)^liiltpMuvenndwlwuril>LcmpNodE!->c-oiinti|i|rien!pNixljeisiliepMi^EiniMfe'sklirodjeuhichisin山匕sajiicsiblingchain7dusuiiuhthepu^iiiuiLilpMcryeiiudendkiiLpNude.if(directiM=R)whiilcpMkwe口|_詁亡・rxMinL<iiiimpNkide--?LQLinly*iem.pNodeisthEpMtAenode's.riglunodewhictiisinch?samesiblingchai