[硕士论文精品]应用于多目标优化问题的非支配排序差分进化算法

武汉科技大学硕士学位论文第1页摘要现实世界的很多问题都是多目标优化问题。在多目标问题中，各目标之间通常不是独立存在的，往往互相冲突，因而，不存在单一解向量使得所有目标最优，这使得多目标问题难于优化。进化算法启发于自然界的生物进化过程。它的潜在并行性及自组织自适应自学习的智能特性对于求解多目标问题具有巨大潜力。近年来多目标优化与决策问题已成为进化计算的一个重要的研究方向。本文首先对国内外进化多目标领域的研究现状和研究方法进行了系统的归纳和总结，接着分析了当前的一些有代表性的进化多目标算法各自的优点和不足之处，并据此提出了一种应用于多目标优化的非支配排序差分进化算法。该算法继承了NSGAII的快速非支配排序和种群多样性保持策略，同时使用简单但高效的差分方式取代NSGAII中的模拟二进制交叉和多项式变异的方式产生子代个体。最后，为进一步提高算法性能，在差分方式中融入了直接的收敛信息和扩散信息，收敛信息有助于提高算法的收敛速度，而扩散信息则利于算法所得解的分布通过MATLAB对所提出算法以及NSGA进行了数值仿真实验。实验结果表明融入直接信息的非支配排序差分进化算法所得非劣解集的收敛和分布特性均优于NSGA。关键词多目标问题；进化算法；多目标进化优化差分进化第1I页武汉科技大学硕士学位论文ABSTRACTMULTIOBJECTIVEOPTIMIZATIONPROBLEMHASAWIDERANGEOFAPPLICATIONSINTHEREALWORLDITOFTENINVOLVESINCOMMENSURABLEANDCOMPETINGOBJECTIVESSOTHEREWASNOTSINGLESOLUTIONVECTORTHATMADEALLTHEOBJECTIVESOPTIMALASNRESULT,ITW器DIFFICULTFOROPTIMIZINGTHEMULTIOBJECTIVEPROBLEMEVOLUTIONARYALGORITHMSWEREINSPIREDFROMTHEIDEASFROMRLARLRALEVOLUTIONARYPROCESSESDUETOITSINTRINSICPARALLELISM，SELFORGANIZING，ADAPTATIONANDSELFLEARNINGINTELLIGENTPROPERTIES,EVOLUTIONARYALGORITHMSHAVELARGEPOTENTIALTOSOLVEMULTIPLEOBJECTIVESOPTIMALSOLUTIONSTHEMULTIPLEOBJECTIVESOPTIMIZATIONANDDECISIONMAKINGHASBECOMEANIMPORTANTRESEARCHAREAOFEVOLUTIONARYALGORITHMSINRECENTYEARSFIRSTLY,THERESEARCHSTATUSANDMETHODSOFEVOLUTIONARYMULTIOBJECTIVEOPTIMIZATIONWERESYSTEMATICALLYELABORATEDANDSUMMARIZEDTHEN,SOMESTATEOFARTMULTIOBJECTIVEEVOLUTIONARYALGORITHMSWEREANALYZEDFORTHEIRADVANTAGESANDDRAWBACKS,BASEDOILWHIELLTHENONDOMINATEDSORTINGDIFFERENTIALEVOLUTIONALGORITHMWASPROPOSEDFORTHEMULTIOBJECTIVEOPTIMIZATIONTHEPROPOSEDALGORITHMINHERITEDTHEFASTNONDOMINATEDSORTINGAPPROACHANDTHEDIVERSITYPRESERVATIONMETHODOFNSGAIIATTHESAMETIMEITMADE哪OFTHESIMPLEBUTEFFICIENTDIFFERENTIALWAYFOROBTAININGTHEOFFSPRINGINSTEADOFTHESIMULATEDBINARYCROSSOVERANDPOLYNOMIALMUTATIONFORTHEFURTHERIMPROVEMENTOFTHEPERFORMANCEOFTHEPROPOSEDALGORITHM，THEDIRECTCONVERGENCEANDSPREADINFORMATIONWASINCORPORATEDINTHEDIFFERENTIALMETHODTHECONVERGENCEINFORMATIONHELPTOTHEIMPROVEMENTOFTHECONVERGENCESPEEDOFTHEALGORITHMTHESPREADINFORMATIONWASUSEDTOOPTIMIZETHEDISTRIBUTIONOFTHESOLUTIONSFROMTHEALGORITHMMATLABWASUSEDFORTHENUMERICALSIMULATIONTHEEXPERIMENTALRESULTSDEMONSTRATEDTHESOLUTIONOBTAINEDBYTHENONDOMINATEDSORTINGDIFFERENTIALEVOLUTIONALGORITHMHADBETTERCONVERGENCEANDDISTRIBUTIONPROPERTIESTHANNSGAIIKEYWORDSMULTIOBJECTIVEOPTIMIZATIONPROBLEM；EVOLUTIONARYALGORITHMS；EVOLUTIONARYMULTIOBJECTIVEOPTIMIZATION；DIFFERENTIALEVOLUTION武汉科技大学硕士学位论文第1页第一章绪论11选题的背景和意义优化问题是一个古老的问题，同时也是一个困难的问题，它吸引了不少学者的目光，经典的方法很好地解决了部分优化问题，但是有些问题比如多目标优化问题FMULTIOBJEETIVEOPTIMIZATIONPROBLEM，MOP却没有高效实用的解决方法。然而现实世界中的多数优化问题都涉及多个目标的优化，而且这些目标通常不是独立存在的，它们往往是耦合在一起且处于相互竞争状态，每个目标有不同的意义和量纲，它们的竞争和复杂性使得对其优化变得十分困难。在现实生活中，人类改造自然的方案规划与设计过程总体上反映了“最大化效益，最小化成本”这一基本优化原则，在合作对策问题中如何求解最优策略以获得共赢目标，在竞争对策问题中如何使碍自己的利益实现最大，对方的受益最，J、，以及控制工程中的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题等实际上都是多目标的优化问题，因此多目标优化问题在现实世界中随处可见，所以对多目标优化问题的研究成为一个引人注目的研究领域，具有一定的现实意义。传统的应用于MOP优化的数学规划技术【L捌存在一些局限性11数学规划技术对非劣前沿的形状和连续性较敏感，当非劣前沿是凹或者离散时，这些数学规划技术便会失效。21数学规划技术要求目标函数和约束条件可微。3数学规划技术对初值敏感，同时，每次实验结果仅可得单一的非支配解，因此，为获取MOP的非劣最优解集，需从不同初始点开始并多次运行数学规划技术，这大大减缓了MOP的优化效率。因此，有必要研究求解的高效多目标优化的算法及理论。近年来，越来越多研究者倾向于使用进化算法【34LEVOLUTIONARYALGORITHMS，EAS进行多目标优化。使用EAS进行多目标优化具有不少优势11EAS可同时对一组解进行并行操作，在EAS的一次实验中可获得MOP非劣最优解集中的多个解甚至所有解。21EAS对非劣前沿的形状和连续性没有要求，可处理非连续非凸的非劣前沿。3EAS不需要任何目标函数和约束条件的梯度信息。起初使用EAS进行多目标优化时，多采用权值法将多目标问题转化为单目标优化问题，然后采用单目标EAS求解其最优值。由于不符合多目标优化问题本身的特点，该方法在求解多目标优化问题时表现的相当脆弱。法国经济学家PARETO在经济学领域最早提出TPARETO解集的概念PJ。PARETO解集的概念十分符合多目标优化问题本身的特点，在多目标优化方法研究中具有里程碑的意义。近些年来发展起来的多目标优化方法，绝大部分都是基于PARETO概念的多目标演化算法。例如，多目标遗传算法【6IMULTIPLEOBJECTIVEGENETICALGORITHM，MOGA非支配排序遗传算第2页武汉科技大学硕士学位论文法【71NONDOMINATEDSORTINGGENETICALGORITHM，NSGA，小生境非劣遗传算法SLNICHEDPARETOGENETICALGORITHM，NPGA，多目标粒子群优化算法【9“1IMULTIPLEOBJECTIVEPARTICLESWARMOPTIMIZATION,MOPSO和非劣蚁群优化PARETOANTCOLONYOPTIMIZATION，PACO等。性能优越的多目标优化方法，应该能够得到比较理想的非劣解集，具体包括以下几个方面1获得的非劣解集与真实非劣解集的距离应尽可能的小。2获得的非劣解集应均匀分布。3获得的非劣解集应有较好的扩展性，即非劣解集的端点应尽量接近单目标极值。但是，目前己有的算法还不能好的满足这些要求。为此，开发能够有效求解多目标优化问题的优化方法一直是该领域的重要研究课题之一12多目标优化方法的发展和研究现状多目标优化问题在现实世界中的普遍存在性以及求解的困难性，促使人们付出了很多精力来寻求解决的方法。早在1772年，FRANKLIN1就提出了多目标问题矛盾如何协调的问题。1896年PARETO首次从数学角度提出了多目标最优决策问题，并引入PARETO最优解的概念151，与此同时，KUHN141等人给出了向量极值问题有效解的必要条件。至此，多目标优化逐渐受到人们的关注。从20世纪50年代末到90年代初，CHAMES、ZADEH、GEOFFRION和STEUCR等人先后做出了卓有成效的工作，出现TIN权和法、目标规划法和E约束法等基于权重的多目标优化方法，期间多目标优化方法和理论的研究引人注目。近十年来，随着进化算法技术和群智能SWARMINTELLIGENCE方法的兴起以及在科研和实践中的广泛应用，多目标优化技术的发展更为迅猛，应用这些技术和方法求解多目标优化成为当前一个热门的研究领域。由于这些方法具有高度的并行机制，可以对多个目标同时进行优化，因此多目标优化问题的求解方法也开始由目标组合方式逐步向基于PARETO的向量优化方法发展，期间出现了一批优秀的多目标优化方法。然而到目前为止，多目标优化仍处于不断探索之中，且有许多未解决的问题。121传统的多目标优化方法传统的处理多目标优化问题的方法是基于权重的方法，在多目标优化方法发展的初期得到了广泛的使用，其特点是通过各种方式将多目标优化问题转换为单目标优化问题，然后用单目标优化方法来求解。1211加权和方法WEIGHTEDSUMMETHOD该方法是由ZADEHT”I录QGEOFFRIONLL6】提出的，该方法使用不同的权重系数将所有的目标函数聚合成为个新的目标函数，也就是通过加权和的方式将多目标优化问题转换为以下形式的单目标优化问题进行求解IMINIMIZE叶，Z11武汉科技大学硕士学位论文第3页其中，权系数，O，用来表示各个目标的相对重要性，在通常情况下有HL通过J选取不同的权重组合，可以获得不同的PARETO最优解。这是最为简单有效的一种求解多目标优化问题的经典方法，而且对于PARETO最优前端为凸的多目标优化问题，这种方法保证可以获得PARETO最优解。但是其缺点也是明显的，权重的选取与各个目标的相对重要程度相关，如果对于被求解问题没有足够的先验知识，就很难找到能让决策者满意的PARETO最优解。此外，当搜索空间非凸时，很难在PARETO最优前端的非凸部分上取得解。1212目标规划法GOALPROGRAMMING目标规划法11刀是FLJCHARNES等人为求解单目标线性规划问题而提出的一种方法。在该方法中，决策者必须根据待求解问题的情况给出每个目标所期望获得的目标值，这些值将作为附加的约束条件加入到原问题中。这样原问题就转化为求目标函数值到规定目标值之间绝对偏差最小的问题，即IMINIMIZE一乃I“I12其中，Z为决策者设定的期望第I个目标达到的目标值。如果设定的目标值在可行域内，使用这种方法肯定可以得至LJPARETO最优解，而且求解效率较高它的主要缺点是需要决策者事先给定各目标函数的目标值，而且还需要对搜索空间的形状很了解。该方法对于目标函数为线性的优化问题较为有效，但对于求解非线性优化问题效率不高。1213F约束法CONSTRAINTMETHODF约束法【18J是FLJHAIMES等人于197T年提出的，其原理是先对多个目标中最重要的一个进行优化，其它目标作为约束条件考虑，模型如下MINIMIZEO13SUBJECTTODS毛，1SIGK，岛作为上界可在优化过程中取不同的值，以便发现多个PARETO最优解。通过这种方式将多目标优化问题转化为单目标优化问题，然后通过普通的数学规划方法或模拟退火法等进行求解，BRAIN等曾将S约束法和遗传算法结合起来求解多目标优化问题【I。该方法比较简单，易于实施。但是求得的解在很大程度上依赖于毛的取值。无论日如何取值，一般都会或多或少的缩小可行区域的范围。1214字典排序法LEXICOGRAPHIEORDERING在字典排序法I圳中，决策者首先根据先验知识按照各个目标的重要程度对且标进行排序，然后从最重要的目标开始优化，向下递推，直至求出整个问题的最优解。这种方法简单易用，但是各目标函数的重要程度不容易理清。在实际工程应用中，字典排序法很少被单独使用，它通常和一些其它的优化方法如第4页武汉科技大学硕士学位论文目标规划法、遗传算法等结合起来对多目标问题进行优化。1215博弈论法GAMETHEORY在博弈论法中，每个目标函数都可以被看作是一个游戏的参与者，他们能够分析相互间存在的冲突，并且能相互协商，最终得到一个对各方有利的解。该方法来自经济学，后进入工程优化领域。其优点是计算效率高，但只能得到一个非支配解。L216最小最大法FMINMAXAPPMACH最小最大法起源于博弈论法，是为求解有冲突的目标函数而设计的。该方法的线性模型由JUTLER和SOLICH211提出，后由OSYCZLA和RAO进一步发展，这种方法是通过最小化各个目标函数值与预设目标值之间的最大偏移量来寻求问题的最优解从以上描述可以看出，这些传统的多目标优化算法只是提供了一些不同的途径，将多目标优化问题转化为单目标优化问题，然后采用较为成熟的单目标优化方法来进行求解。这些传统的方法简单高效，而且能够保证收敛到PA陀TO最优解集，因此得到了广泛的使用。然而，它们在求解多目标优化问题时也存在着一些困难1在大多数情况下，采用这些方法求解通常只能得到一个PA陀T0最优解，而且该解的获得与转化过程中参数的设定有着很大的关系。为了获取更多的PARETO最优解，就得通过多次调整参数、多次运行单目标优化方法来进行寻优，由于各次优化过程相互独立，往往得到的结果很不一致，令决策者很难有效地决策，而且还要花费巨额的时间开销。2所有的这些算法都需要根据问题的先验知识来选取合适的参数，不同的参数设置会导致产生不同的PARETO最优解。这就要求决策者事先要对问题有足够深的认识，能够合适地选取参数，而这往往是一个很艰难的过程。3一些算法对PARET0最优前端的形状很敏感，比如加权和方法，在处理PARCTO最优前端为非凸的问题时，无论参数如何调整，都无法在非凸区域找到PATO最优解。122多目标进化算法进化算法借鉴生物演化的思想和机理解决实际问题。目前，进化算法己在自动控制、经济预测、机器学习和工程优化等领域得到了成功的应用，且在众多领域掀起了进化计算的研究热潮。现实世界中的很多优化问题都涉及多个目标的优化，多目标优化问题与单目标优化问题不同，单目标优化问题的最优解往往只有一个或少数几个，而多目标优化题的最优解往往很多，甚至是无穷多个，而进化算法是以种群进化为基础的，其进化的结果是一群解，利用它可在一次运行中求出问题的多个解甚至全部解，因此，进化算法模型比较适合于多目标优化问题的求解，同时，进化算法因其具有的隐并行性、智能性及表现的自适应性和自组织性等特点，加之其又适应于大规模的并行计算，可以同时搜索到问题解空间中的多个区域。因此，进化算法为多目标优化问题的解决提供了新的思路和新的契机。另外，由于多目标问题的广泛存在性和其求解的困难性。该问题一直是富有挑战性武汉科技大学硕士学位论文第5页和吸引力的问题。从90年代开始流行的进化算法为求解多目标优化问题提供了有力的理论工具，近年来，进化计算界相继提出了多种不同的多目标进化算法MULTIOBJECTIVEEVOLUTIONARYALGORITHMS，MOEAS，它们的提出引起了众多研究机构的重视，这一方向已成为学术界研究的热点，这一方面近几年来取得的引人瞩目的成就与其应用于实际工程中的巨大价值已使得IEEE学会的进化计算杂志专门出版了多目标进化计算理论与技术的专辑。纵观MOEAS的研究成果，大部分研究还是集中在算法的设计上，对算法的性能、收敛性分析等理论性的研究则很少，偶有一些理论成果，但仅仅局限在对算法的参数、状态等研究之上，且内容和深度都较浅，因此理论研究大大滞后于MOEAS在工程中的应用。对MOEAS的研究主要集中在两个方面其一，如何避免未成熟收敛，即保持非劣解向PARETO界面移动；其二，使获得的PARETO最优解非劣解均匀分布且范围最广，即保持解的多样性早在1967年，ROSENBERG在其博士学位论文中就曾提到可用遗传算法求解多目标优化问题田】。但直到1985年，SCHAFE研究多目标优化问题时，在扩展SGASIMPLEGENETIC姆RITTUA时提出了向量形式的适应度计算方法，称为向量评价遗传算UVCCTOREVALUATMIGENETICALGORITHM,VEGA，至此开刨了用遗传算法求解多目标优化问题的先河，之后许多学者致力于这方面的研究。1989年，GOLDBERG2SL提出采用非支配排序NONDOMINATEDSORTING方法和小生境技术设计有效的求解多目标优化问题的进化算法。之后几年，在GOLDBERG思想的影响下出现了一系列有效的多目标进化算法。进化算法应用于多目标优化领域始于20世纪80年代中期，但真正引起进化计算界足够重视的是1990年后，特别是FONSOEA和FLEMING的关于多目标进化算法的第一份综述性文献【26】的出现，将多目标进化算法的研究带入了一个新的研究阶段，但该综述并未详细介绍每种算法的详细操作过程，且在1985年到1995年之间，有关多目标进化算法方面的文章的数目相对很少。然而自1995年之后，该方面文章的数目呈指数增长，而且出现了一系列的多目标进化算法的综述文献，特别是COELLO的多目标优化网站【2刀的建立，及COELLO28捌，DEB30L等人出版的多目标进化算法方面的专著为从事该方面研究工作的人员提供了大量多目标进化算法方面的最新研究动态及大量资料迄今为止，多目标进化算法方面的文章数目己超过2600篇，这些文章涉及到工业、农业等各个国民经济领域。基于PARETO概念求解多目标进化算法的思想是由GOLDBERG首次提出的，进一步地，根据算法提出的时间又可分为两个阶段第一阶段的算法以使用适应度共享、小生境技术及PARETO为主要特点，这一时期的典型算法有FONSECA和FLEMING于1993年提出的多目标遗传算法161，同年，SRINIVAS和DEB提出的非支配排序遗传算法I7】及HORN等提出的小生境非劣遗传算法，GOLDBERG的思想在这些算法中都得到了很好的体现。MOGA算法对群体中每个个体的排序数是基于PARETO最优概念的当前群体中优于该个体解的其它个体数，并采用一种基于排序数的适应度赋值方法，同时采用自适应的小生境技术与受限杂交技术来提高种群多样性，进而达第6页武汉科技大学硕士学位论文到防止种群的过早收敛。MOGA的主要优点是算法执行相对简单且效率高，缺点是算法易受小生境半径大小的影响。值得一提的是，FONSECA和FLEMING从理论上解决TD,生境大小的计算问题。NSGA算法是基于对多目标解群体逐层分类的方法。每代选种配对之前先按个体的非劣性进行排序，并引进基于决策向量空间的共享函数法。该算法的优点是优化目标可以是任意多个，且所求得的非劣解是均匀的，此外算法还允许存在多个同等的非劣解。缺点是算法效率较低，算法中未采用最优保留策略。此外，算法中的共享参数需要根据经验预先确定。NPGA算法采用基于PARETO最优概念的联赛选择机制，与基于两个个体之间的直接比较方案不同的是，NPGA算法还额外的从种群中选取一定数目的一般取10其它个体参与非劣最优解的比较。因为该算法的非劣最优解选择是基于种群的部分而不是全体，因此，其优点是能很快找到一些好的非劣最优解，并能维持一个较长时期的种群更新期。缺点是除了要设置共享参数外，还要选择一个适当的联赛规模，因而限制了算法的实际应用效果。但是要保证算法收敛于真正的PARETO最优集，则多目标进化算法需要强有力的最优保留机制。因此，在此之后的算法主要集中在如何在算法中引入强有力的最优保留机制，这又标志着多目标进化算法进入了另一个新的阶段。在多目标进化算法中，最优保留通常指使用外部群体或第二群体保存在算法进行过程中迄今为止找到的PARETO最优解。然而，在使用外部群体时需要解决以下问题1外部群体与当前进化群体也称主群体，MAINPOPULATION之间如何发生作用与联系；2当外部群体中的个体数目大于群体预设规模时，哪些个体将被删除；3除了PARETO最优解的概念之外，是否还需要使用别的准则来确定哪些个体将进入外部群体。此外，最优保留机制还可以通过引入其它选择方式来实现。这一阶段的具有代表性的算法有ZITZLER和THIELE提出的强度值非劣进化算法T3QSTRENGTHPARETOEVOLUTIONARYALGORITHM,SPEA，及ZITZLER等提出的改进的SPEA21321，KNOWLES等提出的非劣存档进化策略P3LPARETOARCHIVEDEVOLUTIONSTRATEGY，PAES，COME等提出的非劣选择多目标算法P“PARETOENVELOPEBASEDSELECTIONALGORITHMFORMULTIOBJECTIVEOPTIMIZATION,PESA及COELL0135,361等人提出的微遗传算法。其中，SPEA是一种典型的外部辅助选择法，该方法继承了以往所有多目标进化算法的优点。此外，SPEA使用了两个群体，即外部群体和进化群体，将搜索群体和PARETO最优解分开保存，外部群体EXTERNALSET用于记录到目前为止进化过程中所搜索至LJPARETO最优解，另一个是当前进化群体，且外部群体与进化群体一起参与整个进化过程的操作为维持群体的多样性，算法中使用了一种新的基于PARETO方法的小生境技术，算法的优点在于不需要设置共享参数。SPEA2又进一步的对SPEA作了相应的改进，它与SPEA的主要差别在于1SPEA2使用了一种新的适应度赋值方法；2它使用邻域密度估计技术以引导搜索过程的有效性；3对外部群体中采用了一种新的删除方法以利于边界个体的保存。KNOWLES与COME提出了一种类似于11ES的进化策略的多目标进化算法PAES，该算法中只采用一个父本与一个子代个体，且使用一个用来保存业已发现的非劣解的档案ARCHIVE。PESA使用了两个群体一个是内部群体，其规模较小；另一个是外部群体，规模较大一些。此外，该算法还使用类似于PAES的方法维持群体的多样性。COELLO等人武汉科技大学硕士学位论文第7页提出的微遗传算法采用小规模的进化群体及重新初始化的过程。此外还有一些基于决策者预期目标的目标向量法，如目标规划法，最小最大法等，这些方法优点是计算效率高，缺点是个优化指标的预期目标难以确定，且对非凸搜索空问不适用。随着一些优秀算法的出现，多目标进化算法也越来越广泛的应用于实际问题的求解之中。遗憾的是，多目标进化算法在理论方面的研究速度进展缓慢且相对于算法的研究要滞后得多在这方面RUDOLPH和AGAPIE07J等迸行了大量的理论工作，但他们却未考虑以下两方面的问题一方面，收敛的算法不能保证算法所求解集具有良好的扩展性；另一方面，当算法收敛于真正的PARETO最优集时未给出算法的时间复杂度。13多目标优化方法的研究热点目前，国内外许多学者都致力于多目标优化的研究。关于目前多目标优化方法的研究主要集中在以下几个方面1高效多目标优化算法的研究为了得到性能优越的多目标优化方法，一些学者提出了新的思路。例如，2003年“等人提出TPPOAPREDATORPRCYGENETICALGORITHM算法该算法采用基于超立方体的方法，模拟自然界食肉动物与食草动物间的关系进行演化计算。该方法的显著特点是可以动态的改变种群结构，同时对个体的评价规则可以不止一个每个捕食者代表的规则可以不同1，而小生境则通过超立方体网格自动实现。不过，寻求高效多目标优化方法的研究还是更多地集中于对己有算法的改进方面。例如，在原有非支配排序遗传算法NSGA的基础上，DEB等人发展了NSGAII网。2交互式多目标优化方法的研究多目标优化问题的优化结果为一非劣解集。要得到众多的非劣解不可避免的需要较大的计算开支。在交互式多目标优化方法中，决策人不断的根据优化结果提炼偏好信息，然后在偏好信息的指导下进行优化，交互式多目标优化方法只搜索决策人关心的区域，因而不仅容易得到决策人满意的优化结果，而且计算开支比较小。决策人的偏好一般用目标期望值、优先次序、效用函数和模糊逻辑等方式表示，但是在实际中要用明确的公式表达决策人的偏好是一件很困难的事情。目前，常用的交互式多目标优化方法有逐步进行法STEM、多目标问题的序贯解法SEMOP、GEOFFRION法和代理价值权衡法SWT等。3多目标优化方法收敛性的研究目前，多目标优化算法缺乏收敛理论。RUDOLPHT39】等于1998年对两目标组成的简单多目标优化问题的演化算法的收敛性行为进行了分析，以集合间的距离定义解的收敛性，说明具有比例步长均匀变异算子的11演化策略能以概率L收敛到问题的非劣最优域。但是，RUDOLPH的分析过程比较复杂，而且中间过程不太清晰，似有疑问，且这种收敛倾向在一般多目标优化问题的推广上具有局限性。4多目标优化方法的并行实现为了提高多目标优化方法的优化效率，可以将优化算法在高性能计算机上执行。并第8页武汉科技大学硕士学位论文行计算程序设计时，需要优先考虑的并行任务是目标以及约束的计算以及适应度的评估。5近似技术在多目标优化方法中的应用采用近似技术来建立目标以及约束的近似模型，基于近似模型进行优化设计，避免了大量耗时的高精度分析计算过程，使多目标优化方法的寻优效率得到提高。研究中，如何建立比较精确的近似模型是采用近似技术进行优化设计的关键和难点。6测试函数的设计为了对己有和新提出的多目标优化方法进行评估及比较，必须设计些能反应实际多目标优化问题基本特征的标准测试函数集。WHITLEY提出了一些测试函数的设计准则，包括A1测试问题必须是简单搜索策略所不易解决的。B1测试函数中应包括非线性藕合以及非对称问题。C1测试问题的规模应是可伸缩的。M一些测试问题的评估代价应具有可伸缩性。E测试问题应有规范的表达形式。7非劣解集质量的评价目前，已经发展了多种技术用来评价非劣解集的质量。例如，绝对评估方法、统计分布方法和非劣最优解区域占有率方法等。14本课题的研究任务和拟解决的关键问题141本课题的研究任务11对已存在的各种非支配排序方式的时间复杂度和优化效果进行比较2对各种已存在的种群多样性保持方式的算法复杂度和优化效果进行比较。31分别使用差分方式和遗传交叉变异方式生成各种不同类型问题的子代个体，以取得两种方式对不同问题的性能优劣比较结果。41在差分中融入各种引导信息以期望获得更优的算法性能。51熟悉已有多目标测试函数的特征，以选择合适的函数对算法的性能进行综合测试。6对已有的MOEAS算法性能比较方式进行分析，以选择合适的方式对算法获得的解的收敛和分布状况进行客观评价。142拟解决的关键问题1如何设计合适的差分模型，以使得该差分模型生成子代的性能优于交叉和变异方式生成的子代。21如何在差分算法中融入有利于提高算法搜索效率和改进效果的直接信息。1S本文的组织本文各章内容组织如下武汉科技大学硕士学位论文第9页第一章、阐述了本文的研究背景和意义，对当前国内外的研究现状做了简单概述，并对本文的研究内容和解决的关键问题做了说明。第二章、概括介绍了进化计算的发展，组成和应用。第三章、对当前已有的一部分进化多目标算法进行了介绍。第四章、提出了非支配排序差分进化算法，并对其中的差分模型进行了实验性研究。第五章、在非支配排序差分进化算法的差分模型中融入了各种有助于提高算法性能的直接信息，并比较了融入不同直接信息的算法的优劣。第六章、总结本文的主要工作，并给出了进化多目标领域的一些未来的研究课题。本课题先后得到以下专项研究基金的共同资助，特此致谢国家自然科学基金低雷诺数气动特性与微机电系统控制的多学科优化设计研究项目号50675161；教育部重点研究项目多学科优化设计在微小智能服务机器人中的应用研究项目号205098；湖北省国际科技合作重点研究项目基于网络化智能体架构的微小型光机电系统项目号2006CA025；第10页武汉科技大学硕士学位论文第二章进化计算21从生物进化到进化计算按照达尔文的进化论，地球上每一个物种从诞生开始就进入漫长的进化历程。生物种群从低级、简单的类型逐渐发展成高级、复杂的类型。各种生物要生存下去就必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代个体具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直到消亡。达尔文把这一过程叫做“自然选择，适者生存”。生物学家对自然界生物的进化机理进行了系统的研究，在如此短暂时间里，生物由最简单的单细胞动物，发展到现在的纷繁复杂、种类繁多的高级生物，充分证明了自然界的“自然选择，适者生存”的思想的实际意义。与之相关的关于生物进化的研究结论，已得到了广泛的接受和应用。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每一个细胞中，并以基因的形式排列在染色体上，每一基因有特殊的位置并控制生物的某些特性。不同基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。现代遗传学则对基因的本质、功能、结构、突变和调控进行了深入的探讨，开辟了遗传工程研究的新领域。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。遗传物质是细胞核中染色体的有效基因，其中包含了大量的遗传信息。染色体上携带着关于生物性状的物质元素，生物体表现出来的外在特征是对其染色体构成的一种体现。生物的进化本质体现在染色体的改变和改进上，生物体的自身形态的变化是染色体结果变化的表现形式。基因组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物种的稳定性，而基因的杂交的变异使生物的进化成为可能。生物的遗传是通过父代向子代传递基因来实现的，而这种遗传信息的改变决定了生物体的变异。生物进化过程的发生需要四个基本条件1存在由多个生物个体组成的种群。2生物个体之间存在差异，或群体具有多样性。3生物能够自我繁殖。4不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。生物群体的进化机制可分为三种基本形式1自然选择武汉科技大学硕士学位论文第1I页自然选择控制生物群体行为的发展方向，能够适应环境变化的生物个体具有更高的生存能力，使缛它们在种群中的数量不断增加，同时该生物个体具有的染色体性状特征在自然选择中得以保留。2杂交通过杂交随机组合来自父代染色体上的遗传物质，产生不同于它们的父代的染色体。生物进化过程不需要记忆，它所产生的能很好适应自然环境的信息都包含在当前生物所携带的染色体的基因库中，并可以很好地由子代个体继承下来。3突变变异随机改变父代个体的染色体上的基因结构，产生具有新染色体的子代个体。变异是一种不可逆过程，具有突发性，间断性和不可预测性，对于保证群体的多样性具有不可替代的作用。另外，生物进化是一个开放的过程，自然界对进化中的生物群体提供及时的反馈信息，或称为外界对生物的评价。评价反映了生物的生存价值和机会。在基于相同环境下的生存竞争中，生存价值低的个体被淘汰了，生存下来的个体则具有较高的生存价值。由此形成了生物进化的外部动力机制。大多数高级生物体是以自然选择和有性生殖这两种基本过程实现进化发展的。自然选择决定了生物群体中哪些个体能够存活并繁殖。有性生殖保证了生物体后代基因中的杂交和重组，从而使得群体的进化比其它方式更加快速而有效自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体也就是不断完善和发展。可见，生物进化本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是GA等一类模拟自然进化的计算方法的思想源泉。以生物进化过程为基础，计算科学者提出了各种模拟形式的计算方法。尽管到目前为止，进化计算EVOLUTIONARYALGORITHMS，EAS的发展不过20余年，但其思想可以追溯到20世纪50年代。一般认为EAS包括三个组成部分1由美国密歇根大学HOLLAND教授提出的遗传算法GENETICALGORITHM，GA。2由美国科学家FOGEL等人提出的进化规划EVOLUTIONARYPROGRAMMING，EP。3由德国科学家RECHENBERG和SCHWEFEL提出的进化策略EVOLUTIONSTRATEGIES，ES。它们使用不同的进化控制模式模拟了生物进化过程。从而形成了三种具有普遍影响的模拟进化的优化计算方法。EAS是一种基于自然选择和遗传变异等生物进化机制的全局概率搜索算法。与基于导数的解析方法和其它启发式搜索方法如爬山法、模拟退火方法等一样，EAS在形式也是一种迭代方法。它从选定的初始解出发，通过不断迭代逐步改进当前解，直至最后搜索到最优解或满意解。在EAS中，迭代计算过程通过采用模拟生物体的进化机制，从一组解出发，采用类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生第12页武汉科技大学硕士学位论文成具有更好性能指标的下一代解的群体。优化问题采用EAS计算求解的一般过程包括以下步骤11随机给定一组初始解。21评价当前这组解的性能。3根据2的评价结果，从当前解中选择一定数量的解作为基因操作的对象。4对所选择的解进行基因操作，得到一组新的解。5返回到2，对该组新的解进行评价。6若当前解满足要求或进化过程达到一定的代数，计算结束，否则转到3继续进行。EAS是一种随机优化搜索方法，在初始解生成以及选择、交叉和变异等遗传操作过程中，均采用随机处理方法。与其它搜索技术如梯度搜索技术、随机搜索技术、启发式搜索技术和枚举技术等相比，EAS具有以下特点1EAS的搜索过程是从一群初始点开始搜索，而不是从单一初始点开始搜索，这种机制意昧着搜索过程可以有效地跳出局部极值点。特别是当采用有效的保证种群多样性的措施时，EAS可以很好地将局部搜索和全局搜索协调起来，既可以完成极值点邻域内解的求精，也可以在整个问题空间实施探索，得到问题全局最优解的概率大大提高。2EAS在搜索过程中使用的是基于目标函数值的评价信息，而不是传统方法主要采用的目标函数的导数信息或待求解问题领域内的知识。EAS的这一特点使其成为具有良好普适性和可规模化的优化方法。3EAS具有显著的隐式并行性。EAS虽然在每一代只对有限解个体进行操作，但处理的信息量为群体规模的高次方。41EAS在形式上简单明了，不仅便于与其它方法相结合，而且非常适合于大规模并行计算机运算，因此，可以有效地用于解决复杂的适应性系统的模拟和优化问题。51EAS具有很强的鲁棒性，即在存在噪声的情况下，对同一问题的进化算法的多次求解中得到的结果是相似的。EAS的鲁棒性在大量的实例中得到了充分的验证。22进化计算分类介绍221遗传算法GA【牡42】是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是EAS的一种最重要形式。GA与传统的数学模型截然不同，它以那些难以找到传统数学模型的难题找出了一个解决方法。同时，EAS和GA借鉴了生物科学中的某些知识，从而体现了人工智能这一交叉学科的特点。自从HOLLAND于1975年在他的著作“ADAPTATIONINNATURALANDARTIFICIALSYSTEM”中首次提出GA以来，经过30年的研究，现在已发展到了一个比较成熟的阶段，并在实际中得到了很好的应用。GA是一种基于空间搜索的算法，它通过自然选择、遗传和变异等操作以及达尔文的适者生存理论，模拟自然进化过程来寻找所求问题的答案。因此，GA的求解过程也武汉科技大学硕士学位论文第13页可看做是最优化过程需要指出的是GA并不能保证所得到的是最佳答案，但通过一定的方法，可以将误差控制在允许的范围内。GA具有以下特点1GA是对参数集合的编码和非针对参数本身进行进化2GA是从问题解的编码组开始而非从单个解开始搜索。3GA利用目标函数适应值这一信息而非利用导数或其它辅助信息来指导搜索。4GA利用选择、交叉和变异等算子而不是利用确定性规则进行随机操作。GA利用简单的编码技术和繁殖技术来表现复杂的现象，从而解决非常困难的问题。它不受搜索空间的限制性假设条件的约束，不必要求诸如连续性、导数存在和单峰等假设，能从离散的、多极值的、含有噪音的高维问题中以很大的概率找到全局最优解。图21是GA的运算流程图。图2,1GA的运算流程222进化策略。ESL4习是一类模仿自然进化原理以求解参数优化问题的算法。最简单的ES可描述如下1问题被定义为寻求与函数的极值相关联的实数疗维矢量，FXR“哼R。2从每个可能的范围内随机选择父矢量的初始种群，初始试探的分布具有典型的一致性。3父矢量工，F1,2，P通过加入一个零均方差的高斯随机变量以及预先选择X的标准偏差来产生子代矢量X。第14页武汉科技大学硕士学位论文4通过对误差FX，F1,2，P排序以选择和决定保持哪些矢量。那些拥有最小矢量误差的P矢量成为下一代的新的父代。5产生新的试验数据以及选择最小误差矢量的过程将继续到找到符合条件的答案或者所有的计算已经全部完成。ES和GA具有很强的相似性，它们都是一类模仿自然进化原理的算法。同时，两者也存在区别，其中最基本的区别是它们的研究领域不同。ES是一种数值优化方法，它采用的是一个具有自适应步长DR和倾角目的特定爬山法。直到最近，ES才被应用到离散型优化问题。而GA从广义上说是一种自适应搜索技术，它决定如何分配在高于平均规划的情况下呈指数增长的试验数据。GA已经应用于很多领域，参数优化只是它的应用领域之一。除了在研究和应用领域存在一些区别以外，ES和GA还存在以下区别1ES采用浮点编码方式，GA除了采用浮点编码方式外，还可以采用二进制编码方式。2ES和GA的选择过程不同。3ES和GA的复制参数不同，GA的复制参数在进化过程中保持恒定，而ES需时时改变它们。223进化规划EP是由FOGELL44在1962提出的一种模仿人类智能的方法。他们为有限状态机的演化而提出进化规划来预测问题。这些状态机的状态变换表是通过对应的离散有界集上进行均匀随机变异来修改的。EP根据正确的预测的符号数来度量适应值。通过变异，为父代种群中的每一个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。EP的提出也是受自然界中生物进化机制的启发。不论是仿生如神经网络还是启发式编程如专家系统都试图模仿人的行为，但FOGEL认为人类不过是自然进化过程的加工品，千百年来进化过程使生物智能不断增加，因此，模拟进化过程比单纯的模拟某些特定人例如专家1解决问题更加有效。在此基础上，他提出了与启发式编程相对照的进化编程。EP的过程可以理解为从所有可能的计算机程序形成的空间中，搜索具有高适应度的计算机程序个体。在EP中，可能有几百或者几千计算机程序参与遗传进化。EP设计强调种群行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。EP最初由一个随机产生的计算机程序种群开始，这些计算机程序由合适于问题空间领域的函数所组成，这样的函数可以是标准的算术运算函数、标准的编程操作、逻辑函数或由领域指定的函数。种群中每个计算机程序个体是用适应度来评价，该适应值与特定的问题领域有关。EP可以繁殖出新的计算机程序以解决问题，它分三个步骤1产生初始种群，它由关于问题计算机程序的函数随机组合而成。2迭代完成下述子步骤，直到满足选种标准为止A执行种群中的每个程序，根据武汉科技大学硕士学位论文第15页其解决问题的能力，给它指定一个适应值。B应用变异等操作创造新的计算机程序种群。基于适应值，根据概率从种群中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体把现有的计算机程序复制到新的种群中。通过遗传随机重组两个现有程序，创造新的计算机程序个体3在后代中适应值最高的计算机程序个体被指定为进化编程的结果。EP的基本过程如图22所示。图Z2EP的基本过程23本章小结本章对EAS的起源、发展和特征做了简单介绍，并分类讨论了进化计算的三个分支；GA、ES和EP的搜索实现过程和以及它们相互之问的异同。GA、ES和EP都是模拟生物界自然进化过程而建立的鲁棒性计算算法。但它们之间存在较大的差异其一、编码方式不同，GA使用二进制编码或者浮点编码，ES使用浮点编码，EP则使用有限状态机表示个体；其二、选择机制不同，标准GA和EP都强调随机选择机制的重要性，而在ES的角度看，选择是完全确定的；其三、交叉ES和EP都把变异作为主要的搜索算子，而在标准遗传算法中，变异只处于次要位置。第16页武汉科技大学硕士学位论文第三章进化多目标优化算法31进化多目标算法简介近年来，使用EAS进行多目标优化已经成为一个十分热点的研究领域。COELLO在他的网站上列举了有关该领域的截止于2006年11月的2600多篇文献。在2007年举行的进化计算领域全球规模最大的科学年会G