本科毕业设计-多目标进化算法及应用预计

华北电力大学毕业设计摘要在最近二十年，作为一类新兴的优化技术，多目标进化算法吸引了极大关注，许多学者提出了不同的算法，多目标进化算法已经成为处理多目标工程设计和科学研究问题的重要方法。许多MOEA的方面被广泛地调研，然而一些问题仍然没有被很好地受到关注。例如，随着这类算法的快速发展，对算法之间性能进行比较变得越来越重要。本文分析总结了两种目前流行的所目标进化算法的基本原理，并通过算例来比较它们的性能。本文主要工作内容如下1简要回顾了多目标进化算法的发展历史，按照算法原理与进化模式将算法分类。2简述多目标问题及进化算法的相关技术，详细分析了NSGAII算法和MOGLS算法。3分别利用NSGAII算法和MOGLS算法对算例进行求解，并用C指标对两种算法的结果进行评价，得出它们各自的优缺点。多目标问题仍向算法设计，呈现和执行提出挑战。不断变化的多目标问题很少被考虑到它的时变特性，对此有效的多目标进化算法很罕见，多目标进化算法的结合量计算和有区别的进化还始终停留在初级阶段。多目标进化算法的应用应该在未来不断地延续，MOEA的理论分析比它本身更复杂而且应该通过主要从事计算机和数学研究人员的努力工作来解决。关键词多目标优化，进化算法，适应度计算，精英保留，局部搜索ABSTRACTINTHEPASTTWODECADES,ASANEWSUBJECT，MULTIOBJECTIVEEVOLUTIONARYALGORITHMMOEAHASATTRACTEDMUCHATTENTION,THENUMEROUSALGORITHMSHAVEBEENPROPOSEDANDMOEAHASBECOMETHEIMPORTANTAPPROACHTODEALWITHMULTIOBJECTIVEOPTIMIZATIONPROBLEM（MOP）OFENGINEERINGDESIGNANDSCIENCERESEARCHMANYASPECTSOFMOEAHAVEBEENEXTENSIVELYINVESTIGATED,HOWEVER,SOMEPROBLEMSARESTILLNOTCONSIDEREDVERYWELLFOREXAMPLE,UNDERTHECONDITIONTHATMANYALGORITHMSAREBROUGHTUP,THEMETHODSTHATCOMPARETHEPERFORMANCEBETWEENTHEALGORITHMSHAVEBECOMEVERYPROMINENTTHEMAINPRINCIPLESOFTWOPOPULARALGORITHMSWEREANALYZEDINTHISPAPERTHEMAINWORKOFTHISPAPERCANBESUMRISEDASTHEFOLLOWING1ABRIEFREVIEWOFTHEHISTORYANDCURRENTSTUDIESOFMOEAWASBROUGHTOUTALLCOMMONALGORITHMSHAVEBEENDISTRIBUTEDINTOSEVERALSORTS2MOPANDTHERELATIONALTECHNIQUEOFMOEAWASINTRODUCEDCONCISELYTHENNSGAIIANDMOGLSWEREEXPOUNDEDINDETAIL3NSGAIIANDMOGLSWEREUSEDFORSOLVINGTHESAMEMULTIOBJECTIVESCHEDULINGPROBLEMSEPARATELYANDTHEIRSESULTSWASEVALUATEDBYCNORM,THROUGHTHIS,THEADVANTAGEANDDEFECTOFTHESETWOALGORITHMSHAVEBEENEMERGEDMOOPSTILLPOSESTHECHALLENGESFORALGORITHMDESIGN,VISUALIZATIONANDIMPLEMENTATIONTHEDYNAMICMOPISSELDOMCONSIDEREDFORITSTIMEVARYINGNATURETHEEFFECTIVEPMOEAISVERYSPARSEANDTHEMOEACOMBININGQUANTUMCOMPUTINGANDDIFFERENTIALEVOLUTIONISSTILLINTHEINFANCYPERIODTHEAPPLICATIONSOFMOEASHOULDBEEXTENDEDCONTINUOUSLYINTHENEARFUTURETHETHEORYANALYSISOFMOEAISMORECOMPLICATEDTHANMOEAITSELFANDSHOULDBECONSIDEREDTHROUGHTHEHARDWORKSOFRESEARCHERSMAJORINGINCOMPUTERSANDMATHEMATICSETALKEYWORDSMULTIOBJECTIVEOPTIMIZATION,EVOLUTIONARYALGORITHM,FITNESSCALCULATING,ELITISMDUPLICATION,LOCALSEARCH目录摘要ABSTRACT第1章绪论111究背景及意义112多目标进化算法的研究现状213本文研究内容4第2章多目标进化算法621多目标优化基本概念6211多目标优化问题描述622多目标遗传算法设计的关键技术7221适应值设计7222维持群体多样性7223精英保留策略923NSGA和MOGLS算法12异常的公式结尾232MOGLS1424本章小结11附录26致谢33第3章优化算例及分析3031多目标遗传算法的性能评价20331性能评价指标20332测试函数及其设计2532二级标题3533二级标题40331三级标题40332三级标题45第4章总结3041二级标题3042二级标题3543二级标题40431三级标题40432三级标题45参考文献50附录51致谢52第1章绪论许多科学研究和工程实践中遇到的优化问题，通常需要综合考虑多方面因素，这就要求在解决问题时同时对多个目标进行优化，这样的问题被称为多目标优化问题MULTIOBJECTIVEOPTIMIZATIONPROBLEM,MOP，它们有许多冲突的目标。有时目标之间是相辅相成、互相促进的，但更多的时候，目标之间是相互矛盾、此消彼长的。因此在绝大多数情况下，若想达到总目标的最优，就需要对各个目标进行综合考虑、折中处理，所得到的解是一组基于PARETO最优性概念的非劣解集1，所以如何进行综合与折中就成为解决问题的关键。11研究背景及意义生物在其延续生存的过程中，逐渐适应其生存环境，使得品种不断的到改良，这种生命现象叫做进化。进化算法EVOLUTIONARYALGORITHM,EA是一种通过模拟生物进化规律来进行选择与变化的随机搜索算法，起源于20世纪50年代末，现有的代表性进化方法有遗传算法GENETICALGORITHM,GA、进化规划EVOLUTIONARYPROGRAMMING,EP和进化策略EVOLUTIONSTRATEGY,ES等几种方法2。进化算法非常适用于于求解高度复杂的非线性问题，并且由于这类算法具有通用性，因而被广泛地应用于单个目标的复杂系统优化问题。然而，人们在求解现实世界许多优化问题时，通常不追求单一目标的最优性，这就要求在解决问题时同时对多个目标进行优化和权衡，有时目标之间是相辅相成、互相促进的，但更多的时候，目标之间是相互矛盾、此消彼长的，这样的问题被称为多目标优化问题MULTIOBJECTIVEOPTIMIZATIONPROBLEM,MOP，大多数工程和科学问题是多目标最优问题。多目标优化问题的各目标之间通过决策变量相互制约,对其中一个目标优化必须以其它目标作为代价,而且各目标的单位又往往不一致,因此很难客观地评价多目标问题解的优劣性。例如,在设计一座桥梁时,我们一方面希望建设桥梁的费用最小,另一方面希望桥梁具有最大的安全性。与单目标优化问题的本质区别在于,多目标优化问题的解不是唯一的,而是存在一个最优解集合,集合中元素称为PARETO最优或非劣最优NONDOMINANCE。求解它们需要用不同于单目标优化的数学工具,甚至最优的含义也发生了变化。由于它们有许多冲突的目标，因此若想达到总目标的最优，就需要对各个目标进行综合考虑、折中处理，所以如何进行综合与折中就成为解决问题的关键。多目标进化算法MULTIOBJECTIVEEVOLUTIONARYALGORITHM,MOEA就是一类可以有效解决这种问题的优化技术3。它的主要思想是将进化算法的概念引入到多目标优化领域，对多目标优化问题同样采用进化操作方式，但算法由单目标优化问题求取一个最优解，转变为多目标优化问题中求取一个最优解集，该解集称为PARETO最优解集。最优解集中的每个解，理论上都是“最优解”，而在实际应用中，可以根据决策需要选择其中一个解作为最终决策方案，实现最优化的目的。多目标进化算法是一门新兴的学科，理论与算法并不完善，尚处于发展阶段。然而，它对工程项目具有重要的实践意义，因此在过去的十多年间涌现出许多新的改进算法，人们不断地寻找是否存在优化效果更好的多目标进化算法。而对算法性能进行比较和评价就成为一个重要的核心问题，引起了诸多学者的研究兴趣。12多目标进化算法的研究现状优化问题一直是倍受人们关注的问题，自1950年以来,运筹学研究人员已经建立了许多方法解决MOP。在专业文献中,有许多数学规划技巧解决MOP,如多目标加权法、分层序列法、约束法、目标规划法等。遗传算法自出现以来在许多领域得到了广泛的应用，在解决简单的单目标优化问题方面取得了很好的成果，但面对复杂的多目标优化问题，传统的遗传算法就显得力不从心。例如在现代能源系统生产过程参数的优化4设计中经常会遇到多目标函数的优化问题，使用经典的多目标优化方法通常把多个目标函数整合成单目标，将问题转变为单目标优化问题，然后采用单目标的优化技术求解。但这些方法存在只能得到一个解；多个目标函数之间量纲不同难以统一；加权值的分配带有较强的主观性；加权的目标函数之间通过决策变量相互制约，最终优化目标仅为各目标之和，各目标的优化进度不可操作等缺点。这是因为传统数学规划方法存在一些缺陷,例如有些方法对PARETO前沿比较敏感,当PARETO前沿是凹的或者不连续时,这些方法失效有些方法要求目标函数和约束条件可微有些方法每次运行只产生一个解,求多个解时需要运行多次,效率较低。进化多目标优化始于1967年，此后众多的研究人员通过对遗传算法进行改造，相继提出了多种用于解决多目标优化问题的遗传算法，如基于向量评估的遗传算法VEGA5，小组决胜遗传算法NPGA6，非支配排序遗传算法NSGA及其改进算法NSGAII7等其中NSGA的改进算法NSGAII是带有精英策略的非支配排序遗传算法，改进了先前算法的不足之处，提高了算法的运算速度和鲁棒性，并保证了非劣最优解的均匀分布。自SCHARFER提出VEGA起，多目标进化算法的发展经历了由基于单目标子群体优化的算法到基于PARETO最优性指导的分级策略与适应值共享策略算法的发展历程。按照算法原理与进化模式划分，现有多目标进化算法可分如下四大类第一类算法是早期基于单目标群体优化的MOGA。这类算法通过加权或划分子群体进化等方法将MOP转化为不同的SOP，然后借助现有单目标遗传算法对转化后的SOP进行求解，最后对进化获得的解进行分析，筛选出非劣解集。由于这类算法的设计思想是基于单目标遗传算法的进化策略，因此它的优点是算法容易实现；其不足是，基于单目标子群体优化的算法很难搜索到严格意义上的非劣解集，往往仅能得到非劣解集中的部分极值点。代表算法有VEGA、WBGA、DM等。ISHIBUCHI、MURATA等人1996年提出的MOGLS是在随机权策略的WBGA中引入局部搜索的改进算法，其本质属于这类算法8。第二类算法是基于GOLDBERG提出的适应值分级和共享策略的多目标遗传算法。这类算法在适应值设计中鼓励非劣解等级优先个体和同一等级内较为稀疏个体以较大概率出现在后代群体中。由于这类算法是基于PARETO概念的MOGA，因此，它的优点是可以通过单次优化获得一组靠近真实非劣解前沿的非劣解集；但由于算法未考虑进化过程中精英个体的保留，因此解的收敛速度及收敛性能不够稳健。代表算法有MOGA、NSGA和NPGA等。第三类算法是由第二类算法发展起来的精英保留策略MOGA。这类算法通过在进化过程中引入外部伴随群体对群体中的精英个体加以保留，同时采用更加成熟的适应值设计策略，使算法不仅在收敛速度上有所提高，而且在优化性能上也有所改善。这类算法的不足之处是，算法进化模式单一、局部搜索性能欠佳，之所以存在这些不足，主要是因为这类算法大多由第二类算法改进得到，因此进化模式不可能完全摆脱先前的算法框架，并且遗传算法的进化原理决定了它不可能具有性能较高的局部搜索能力。代表算法有NPGAII、NSGAII、PAES和SPEA等9。第四类算法是采用其他搜索算法策略改进的MOEA。这类算法由于采用的进化策略是基于模拟退火搜索、禁忌搜索、粒子群优化、小生境策略等不以传统遗传算法进化结构为主导的优化策略，因此在早期的多目标进化算法研究中并未受到广泛重视，只是在近年随着多目标遗传算法局部搜索性能欠佳的不足逐渐呈现，以及其他进化策略单目标进化算法的迅速发展才开始活跃起来。这类算法由于群体规模适中，因此算法复杂性相对较低，而且由于算法局部搜索性能优越，因此常常可以与现有的MOGA结合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遗传算法那样既能保证全局寻优、又能维持群体多样性，因此，在算法设计时往往设置了许多控制参数对算法性能进行调整，这又导致在求解问题时常常需要借助大量试验计算分析确定进化参数，因此算法性能不够稳健。代表算法有MOSE、MOPSO等10。除了上述四类算法外，一些学者在演化策略中引入偏好分级或适应值分享机制获取满意解。但由于这些方法不能通过几次运行获得稳定的非劣解集，且算法复杂性较高，因此这类研究不是多目标进化算法研究的主流方向。而考虑偏好关系对遗传进化的影响，大多是用模糊集方法进行偏好信息的处理，而进一步利用偏好对进化进行指导或通过进化引导偏好的交互式多目标进化算法还仅仅处于概念研究阶段，距算法实现尚有较大差距。多目标遗传算法的研究一直是这类算法研究的主流方向尽管遗传算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他进化策略或启发式局部搜索算法好的局部搜索性能，因此，以进化算法为算法主体，结合遗传算法全局搜索和一般启发式进化策略局部搜索的优势，获得高性能的多目标优化算法，成为多目标进化算法研究的潜在发展方向。13本文研究内容多目标进化算法如果按决策方式划分，则可以分为三类11前决策（先验式）、后决策（后验式）和交互式决策，这是按照用户的人工决策信息作用于算法的时间先后划分的。其中，后决策是最常用的技术，即算法终止时提供给用户一组最优解。目前绝大多数多目标进化算法是排序选择法和后决策技术类型的。SPEA/SPEA2ZITZLER（2）至少存在一个子目标,使P比好。即1,23,LR,使11FPFQ其中R为子目标的数量。此时称为非支配的NONDOMINATED,Q为被支配的DOMINATED。表示为PQ,其中“”是支配关系。定义2PARETO非支配集。设有解集P,若中的个体Q不被任何其它个体支配,则Q是P中的非支配个体由中的所有非支配个体构成的子集称为P的非支配集_NDSET。即_Q|PP,NDSET且使最优性的含义为X是PARETO最优解，表示在整个解空间中，不存在这样的解某一个目标比X小的同时，保持其余1K个目标值不大于X的目标值。因此，满足这种最优性的“最优解”往往不是单个解，而是一组满足上式最优性条件的非劣解集合，包含非劣解的集合称作非劣解集（PARETOSOLUTIONSSET）或非受控解集NONDOMINATEDSOLUTIONSSET；非劣解对应的目标值在目标空间中称为非劣点；最优解集在优化目标空间构成的分布称作非劣解前沿。在决策和优化问题中，最优性取决于如何比较和排序候选解，及决策者的偏好结构。从决策者的立场来看，一般认为每对候选解具有以下比较关系1一方明显优于另一方；2两者相互非劣；3两者不具有可比性。由此才可以对每对解之间的优劣比较进行细致的区分13。22多目标遗传算法设计的关键技术221适应值设计MOP问题包含多个待优化的子目标，通常EAS用于多目标优化时必须考虑两个关键问题1为了保证朝PARETO最优集的方向搜索，如何实施适应度赋值和选择。2为了避免未成熟收敛和获得均匀分布且范围最广的非劣解，如何保持群体的多样性。在已有研究中，多目标遗传算法的适应值设计FITNESSASSIGNMENT主要有基于加权策略、基于目标设计策略和基于非劣解等级优先策略三种设计策略141基于加权策略的适应值设计，即基于聚合策略的方法，是通过加权策略将多个目标转化为单个目标后进行优化。这种适应值设计的遗传算法通常需要在算法进化过程中系统地对函数中的参数的权重值进行调整，以便得到一组非劣解集。在进化的每一代中参数呈现有规律的变化，但在该代操作过程中保持不变，常见的进化加权法，个体的评估使用确定的加权组合，所有个体都有一个适应度值，保证了搜索方向朝最优解迈进。2基于目标设计策略的算法，即基于准则的策略，每当个体选中后进行复制时根据不同的目标来决定是否被复制至配对池。此方法通过在不同进化代之间更换优化目标每次优化一个目标，使算法群体每次运行得到一个非劣解，从而通过多次运行找到优化问题的非劣解集。目前，常用的方法是在选择阶段根据概率来确定各子目标的排序，该概率值由用户确定或随机产生。这种策略存在的问题是进化结果容易偏向某些极端边界解，并且对PARETO最优前端的非凸部敏感。3基于非劣解等级优先概念的适应值分配策略由GOLDBERG最先提出，后人大多在此基础上进行改进，如将群体划分为几个有序的子群体。这类算法的适应值设计主要有等级优先、深度优先和基于优先数三种等级优先策略算法在计算适应值时主要考虑个体在群体中“优于”其他个体的数目或考虑优于该个体的其他个体数目之和，以此确定给个体的适应度值；而深度优先策略算法在分配个体适应值时主要以个体所在的非劣解等级及等级内的疏密程度有关；基于优先数的适应值分配算法在计算个体适应值时，考虑了个体所优先于或劣于群体中其他个体的数目。一般来说直接统计优胜个体数目的操作方式简单，在原理上一目了然。单目标优化中的目标函数常与适应度函数相同，但MOP问题中的适应度赋值和选择必须考虑几个子目标，MOEAS必须根据个体间的PARETO优胜关系和其他信息为个体确定适应度值，这种适应度值和每个目标函数的具体大小没有直接关系。另外，与单目标优化不同的是，在个体保持不变的条件下，同一个体在这一代和下一代的适应值可能不相等。PARETO优胜关系是决定个体适应度函数值的重要依据，很多MOEAS根据个体间的这种关系，将个体的适应度函数值分成两个层次，即劣解和非劣解，后者的适应度值总是优于前者。当个体间没有PARETO优胜关系时，其他形式的个体信息被用于确定适应度函数值，其中个体密度值是利用最多的信息，并采用不同的方法估计个体密度值。基于PARETO优胜关系的选择方法已经被广大研究者采纳，现已有多种基于PARETO的适应度赋值方案，其中基于种群个体级别排序的适应度赋值方法是较常见的一种方法。多目标问题与单目标问题不同，它的优劣性与支配关系并非定义目标向量之间的那种整体有序关系，只是给出部分有序关系，因而种群的级别排序不具有唯一性。假设第T代种群中的个体UX，UX在第T代种群个体排序中的位置为,URANKXT，基于个体排序的适应度赋值步骤描述如下1基于,URANKXT的数值将种群中所有个体进行级别排序。2利用线性或非线性的插值方法在最低序号与最高序号之间进行插值。3具有相同序号的个体进行适应度共享算子操作，即通过除以相同序号的个体数目得到新的适应度值，另外，也可以给不同序号的个体分配固定不变的适应度值。222维持群体多样性因为EAS是并行地处理一组解，通过杂交和变异来搜索空间以寻找可能的最优区域，通过选择来搜索具有较高适应度的个体。传统的进化算法在PARETO最优集上执行多目标搜寻，希望找出尽可能均匀分布的解集，因而个体的多样性减少的很快，经常收敛至单个解而丢失多个其他非劣解。在进化过程中某些具有较高适应度个体的大量复制造成高选择压力，使得个别具有更高适应度的个体得不到遗传的机会，甚至导致整个群体出现同解的现象15。如果单纯从群体多样性出发，群体规模应该越大越好，但群体规模太大会带来若干弊病一是从计算效率来看，群体越大，导致其适应度评估次数增加，引起计算量的增加，从而影响算法效能；二是群体中个体生存下来的选择概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，大多数个体被淘汰，严重影响交叉操作。因此群体规模只能维持在一定数量上，它并不能成为解决进化算法多样性的途径。进化算法由于其进化算子固有的随机误差，因而基于有限群体实施进化时会出现收敛至某一个解。因为多目标优化的目的是得到一组在整个PARETO曲面上尽可能均匀分布的一组解，因此必须在进化过程中采取措施避免进化结果收敛至单个解。为使算法优化得到一组尽可能分布均匀的非劣解集而非此集合中的非劣解极值点，大多数MOEAS在当代群体中维持多样性是在选择过程中结合了密度信息，即个体在其邻域范围内所占的密度越高被选择复制的机会越小。现有多目标遗传算法可根据统计概率密度估计的方法加以分类为如下三种策略来维持群体多样性1基于核函数的评价策略基于核函数的评价策略主要通过计算以个体为“核”、群体中其他个体距离“核”的核函数之和，通过优先保留核函数值较大的个体即较稀疏的解个体达到维持群体多样性的目的。具体应用时首先根据内核函数K来定义一个点的邻域范围，内核函数采用至另一点的距离作为参数。每一个个体计算至其他个体I的距离ID，通过内核函数K的映射后求和计算出ID值，该累加值代表了个体的密度估计。2基于邻域解数目的评价策略基于邻域解数目的评价策略是以评价解为核心、包含一定数量邻域解的邻域半径为指标，优先保留邻域半径较大的个体即较稀疏的解个体。该策略主要考虑给定点至第K个最近邻居的距离，以便估计出其在邻域内的密度。3分区统计数目策略分区统计数目策略是将目标空间划分成一定比例的区域，通过统计个体所在区域中邻域解数目来确定个体被保留的概率邻域解数目越大，被保留概率越小。该方法采用一个网格来定义空间上的邻居关系，个体的密度只要通过简单地统计同一网格内的个体数目即可，这种网络可以是固定的，也可以根据当前群体进行自适应调整。多目标进化算法与单目标进化算法类似，为了提高群体多样性，在算法过程中尽量采用小生境（NICHE）共享技术，使得在一个群体内可以形成在多目标问题TUREPF上分布均匀的非劣最优解集KNOWPF。具有相同PARETO级别序号的解个体在实施共享适应度值后，还必须按解的目标向量之间的空间距离进行小生境规模调整。当两个解的目标向量之间的空间距离小于某一预定值SHARE时，相应解的小生境规模就必须进行调整。此外，还有同时基于决策向量空间与目标向量空间的混合共享技术，共享问题的关键是如何确定共享参数SHARE，SHARE的选择将会影响算法的性能，而适应度共享效果则共同取决于SR和种群大小16。223精英保留策略遗传算法是基于随机进化选择的算法，因此，为改善遗传算法的收敛性能，现有多目标遗传算法大都引入了精英保留策略。现有算法中精英策略的实现方式主要有两种其一是采用新旧群体合并，通过确定性的选择方法在混合群体中选择后代，而不是采用变化之后的配对池来替换旧群体，增大了精英个体在后代群体中出现的概率，以此改善算法收敛性。另一种实现方式是采用独立于进化群体的伴随群体，即使用带有所谓的档案（ARCHIVE）的方式，保留与更新算法进化过程中搜索到的非劣解集来维护当代群体中的满意群体，使其能够复制到下一代，伴随群体仅作为一个外部存储集，独立于进化过程的优化操作17。由于内存资源的限制，以上两种最优个体保留策略必须确定哪些个体作为最优个体加以保留。通常采用优胜准则来确定最优个体。如果使用伴随群体的方式，则伴随群体中包括当前的近似PARETO集，即伴随群体中受控的个体被移去。但是使用优胜关系比较的方法有时也存在问题，如对某些连续型问题所对应的PARETO集可能包含无穷多个解，因此需要补充其他的信息知识来减小所存储的个体数目。这些信息包括密度信息，个体进入伴随群体所需时间。MOEAS的最优个体大多利用优胜关系和密度两者的组合来进行挑选，最优个体保存在每代的伴随群体中。更新的算法研究表明，如果同时采用这两种精英策略，可以进一步提高算法的搜索性能与收敛效果。23遗传算法的一般流程HOLLAND教授提出的遗传算法，现在一般称为简单遗传算法或基本遗传算法18，其基本流程如下图开始种群初始化计算适应度是否满足优化准则交叉变异选择输出结果算法结束YESNO图21遗传算法基本流程1参数编码遗传算法一般不直接处理问题空间的参数，因此在算法开始进行之前，首先要选择合适的编码方式对待优化的参数进行编码。通常采用二进制编码，将参数转换成为0和1组成的数字串。2产生初始种群随机地产生一个由N个个体组成的种群，该种群代表一些可能解的集合。遗传算法的任务是种群出发，模拟生物进化的过程进行优胜劣汰，最后得出满足优化要求的种群和个体。3设计适应度函数把问题的目标函数转换成合适的适应度函数，并根据适应度函数计算种群中的每个个体的适应度，为种群进化的选择提供依据。4优化准则也可称作终止条件，是用来判断算法是否可以终止的标准。可以设定进化的最大代数，当进化到最大代数时，算法终止运行。也可以设定期望的适应度函数值，只有当种群中存在个体能达到期望值时，算法才可以结束。通常情况下，这两种方法同时作为优化准则使用。5选择复制操作按一定概率从群体中选择个体，作为双亲用于繁殖后代，产生新的个体。在此操作中，适应于生存环境的优良个体将有更多的机会繁殖后代，这使得优良特性能够遗传到下一代。6交叉操作随机地选择用于繁殖的每一对个体的同一基因位，将其染色体在此基因位断开并相互交换。7变异操作以一定的概率从群体中选择若干个个体。对于选中的个体，随机选择某一位进行取反操作。对产生的新一代群体重新进行评价、选择、杂交和变异。一代一代循环往复，使种群中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度满足优化准则或最优个体的适应度和平均适应度不再提高，则迭代过程收敛，算法结束。遗传算法的选择和交叉算子赋予了它强有力的搜索能力，变异算子则使算法能搜索到问题解空间的每一个点，以确保算法能达到全局最优。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化计算的实际应用问题，一般可以按照上述步骤来构造求解该问题的遗传算法。由上述步骤可以看出，构造遗传算法时需要考虑的两个主要问题是可行解的编码方法和遗传算子的设计，这也是设计遗传算法的两个关键步骤。24算法性能评价241多目标进化算法性能评价的研究现状多目标遗传算法的性能评价与传统优化算法及单目标遗传算法的性能评价有所不同，传统算法的优化性能可以通过梯度下降速度进行评价，并且可以通过严格的数学证明分析其收敛性能；单目标遗传算法可以采用基于模式定理或基于马尔可夫随机过程理论的证明分析其收敛性，尽管这类证明研究还很初步。然而在对多目标进化算法的性能进行评价时，一般需要考虑到三个较为重要的因素19算法的效率、算法的效果，以及算法的鲁棒性。算法的效率是指算法自身的时间复杂度和空间复杂度，也即算法运算时间的长短和资源消耗的多少；算法的效果是指算法求得的解集的质量，也即算法的收敛效果和解集的分布性效果；算法的鲁棒性是指算法的应用范围和稳定性，也即是否对多种问题都有很好的求解能力、是否求解问题时总是相对稳定的。而从现阶段的研究来看，人们更关注的是，算法结果是否为高质量的结果，而对于另外两个因素相对要求并不高，而且对于算法的效率来说，涉及到的是经典的算法复杂度理论，已经有很完善的泛化体系对其进行评价了，无需在多目标进化算法领域对其再进行专门的研究。所以现阶段的性能评价方法主要集中于对算法的效果的衡量。242多目标进化算法的性能评价方法多目标进化算法的性能评价方法有很多，大体上可以分为两类20，一类是评价算法的收敛性效果的，一类是评价解集的分布性效果的。下面分别对二者加以介绍。1算法收敛性评价所谓的收敛性，实际上是指算法的真实结果集与理论上的最优结果集之间的趋近度，即理论上的PARETO边界和真正得到的PARETO边界之间的差距。收敛性的评价方法有很多种，如错误率、解集间覆盖率、世代距离、最大出错率等等。以解集间覆盖率为例，该覆盖率又称为S指标ZITZLER,200021，用来计算一个解集中被另一个解集中的个体支配的个体所占的比率。如式31所示。PAORAAPS,|,31对于收敛性的评价指标而言，可以通过指标值反映出算法间优化效果的差异，但只局限于最优解集中更优解的数量，对于其空间上的特性不做相关考虑。2解集分布性评价在更多的算法应用领域中，解集的空间分布特性是十分重要的，决策一般希望能够在目标空间中找到一组均匀的解集，以便做出不同的决策，如果解过于集中，则周围的很多解事实上并没有太大的意义，也不利于产生新个体，从而影响了种群的进化效果。分布性的评价方法也有很多，如空间评价方法、基于个体信息的评价方法、网格分布度评价方法等等。以空间评价方法为例，该方法又被称为DELTA指标SCHOTT,199522，用来计算解的分布信息的，如式32所示。NIID1232其中，,21,MIN21JIXFFXFFDJJII对于分布性的评价指标而言，只关注结果集的分布特性，用以检测算法是否被阻在一个很小的范围之内进行搜索，而导致无法实现全局的最优搜索的现象。由于收敛性评价与分布性评价的应用方向不同，因而在比较算法的时候，多会综合两种评价后，对算法的性能得出适当的结论。243现有性能评价体系的特点分析现有的性能评价体系可以分为两种形式221理论证明理论证明即是对算法的复杂度、收敛性等进行求解和比较，即通过理论的分析得出正确的结论。但是由于多目标进化算法是一门新兴的学科，多目标进化计算的理论基础尚未成熟，算法收敛性的理论证明对有限时间内的收敛性分析较少，而时间无穷大的收敛性并没有工程实际的应用价值。因此从理论上来证明算法的优劣并不常用，也较难实现正确的评估。2实验比较分析实验比较分析是指通过对优化算例的结果和结果的各种指标进行比较，验证新算法与已存在的算法之间的性能差别。这种基于解决实际算例进行评价的方法具有一定的局限性，很难得出某种算法一定比另外一种更优的结论，其结论的说服力也不够。但是，由于这种方法可以简单直观的反映出算法的一些特性，所以在分析算法性能领域的应用十分广泛。因此，现有的性能评价体系从使用范围上讲，是基于实验比较分析来实现的。25本章小结本章首先介绍了多目标进化算法的基本概念和原理。然后着重介绍了多目标进化算法的关键技术，现代多目标进化算法正是在这些方面存在差异，也是判断算法之间性能优劣的出发点。第三部分给出了多目标进化算法的一般流程，这是所有算法的原型，不同算法都是在此基础上做出改动，了解此框架是学习其他算法的基础。最后简单介绍了算法的性能评价体系，为几种算法比较的方案提供依据，得出基于实验的方法是可行的，本文将在第三章利用这一思想来试验NSGA和MOGLS两种算法的优劣。第三章优化算例及分析31NSGA和MOGLS算法311带精英策略的非支配排序的遗传算法（NSGA）在NSGA中,同一个小生境内的个体适应度共享,从而降低该小生境内个体的竞争力,防止种群在收敛过程中陷入局部最优,实现种群多样性。首先,对种群内个体按非劣性排序,为获得的PARETO最优解赋予相同的适应度其次,根据GOLDBERG和DEB等23提出的共享方法,按式23和式24计算出每一个PARETO最优解的小生境数,将该个体原适应度除以小生境数,就得到它的共享适应度。这样,处于同一个PARETO前沿的非劣解,由于各自的小生境数不同,最后的共享适应度也不同。21,0,IJIJSHARESHAREDFDIJOTRWISSHD23其中,IJ表示个体I与个体I的距离,SHARE是同一小生境中个体间的最大允许距离,IJSHD表示距离为IJD时的共享函数值。其中,IIJJPOPMSHD24表示个体I的小生境数。虽然非支配排序遗传算法（NSGA）在许多问题上得到了应用，但仍存在一些问题，如计算复杂度较高，需要指定共享半径SHARE，易丢失已经得到的满意解。NSGA针对以上的缺陷通过以下三个方面进行了改进1提出了快速非支配排序法，在选择运算之前，根据个体的非劣解水平对种群分级。首先将当前的所有的非劣解个体划为同一等级，令其等级为1；然后将这些个体从种群中移出，在剩余个体中寻找出新的非劣解，再令其等级为2；重复上述过程，直至种群中所有个体都被设定相应的等级。具体方法与NSGA的快速非支配排序方法不同，NSGA对于每个个体I都设有以下两个参数IN和IS，IN为在种群中支配个体的解个体的数量，IS为被个体I所支配的解个体的集合。首先，找到种群中所有0IN的个体，将它们存入当前集合1F，然后对于当前集合的每个个体J，考察它所支配的个体集J,将集合中的每个个体K的KN减去1，即支配个体K的解个体数减1，如果10KN则将个体存入另一个集H。最后，将1F作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序RANKI，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有个体都被分级。如此操作降低了算法的计算复杂度。由原来的3OMN降到2N，其中，M为目标函数个数，N为种群大小。2提出了拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使准PARETO域中的个体能扩展到整个域，并均匀分布，保持了种群的多样性。拥挤度的概念拥挤度DI是指在种群中的给定点I的周围个体的密度，计算上要考虑个体I周围包含本身但不包含其他个体的最小正方形，如下图，个体I的聚集距离是1122TAN11DISCEFFFFPPIPIPIPI。为了计算每个个体的聚集距离，需要对群体按每个子目标函数值进行排序，在本算法中，若群体规模为N，最极端情况下，对R个子目标分别进行排序的时间复杂度为LOGOR。从图中可以看出DI值较小时，该个体周围就比较拥挤，那么这几个个体的适应度就要降低，使得分布比较分散的解能保留下的几率加大。拥挤度比较算子为了维持种群的多样性，需要一个比较拥挤度的算子以确保算法能够收敛到一个均匀分布的PARETO面上。由于经过了排序和拥挤度计算，群体中每个个体I都得到了两个属性非支配序RANKI和拥挤度DI，则定义偏序关系（N）当满足条件RANKRANKIJ，或满足RANKJ且DJ时，定义NIJ。即如果两个个体的非支配排序不同，取排序号较小的个体；如果两个个体在同一级，取周围较不拥挤的个体。3引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。NSGA算法的主流程首先随即初始化一个父代种群0P，并将所有个体按非支配关系排序，且指定一个适应度值。然后采用选择、交叉、变异算子产生下一代种群0Q，大小也为N，完成第一代进化。在产生新种群TQ后，将T与其父代种群TP合并组成TR，此时种群大小为2。然后TR进行非支配排序，产生一系列非支配集12,F并计算拥挤度，通常选择前1IJJF个个体组成1，满足1IJJN且1IJJN。在上图中，由于子代和父代个体都包含在TR中，则经过非支配排序以后的非支配集1F中包含的个体是TR中最好的，所以先将1F放入新的父代种群1TP中。如果的大小小于N，则继续向1TP中填充2，直到添加到3F时种群大小超出N，对3中的个体进行拥挤度排序3,NSORT，取前1TN个个体。使1TP个体数量达到。然后通过遗传算子产生新的子代种群TQ。当排序产生的非支配集的个体数目足够填充1TP时，就不必再继续对剩下的部分排序了。非支配解的多样性由拥挤度比较算子保证，不需要额外的共享参数。算法流程图进化开始种群初始化保留使用轮盘赌的方法选择交叉变异进化代数GEN大于最大代数终止产生混合种群RT对RT进行非支配排序，产生非支配集FI计算适应度通过精英选择策略控制I的大小将混合种群的级别和适应度赋给初始种群计算适应度保留GEN1NOYES图31NSGA的算法流程312MOGLS在MOGLS中，局部搜索过程应用于通过遗传操作所获得每一个解。这种算法应用在适应度评价功能上应用一种计算权值和的方式，即当一对父代种群被选择通过交叉变异去获得新解时使用这个功能。局部搜索过程应用于新解而最大限度地发挥它的适应度的效率24。这个算法的一大典型特性是无论何时选择一组父代种群都要指定权值效率。每个解通过不同的权值矢量执行。另一个特点是在局部搜索的过程中不需要计算当前种群的所有邻域解，只有少部分邻域解被检验避免在这个算法中消耗过多的所有可行解的计算时间。多目标遗传局部搜索算法试图寻找多目标最有问题所有的非支配解，如果在一个多目标问题中一个解不被其他解支配，它叫做非劣解，一个多目标问题有许多非劣解。杂交算法的目的不是确定一个单一的最终解，而是试图寻找这个多目标问题所有符合约束条件的最优解。当我们应用GA算法解决多目标问题时，需要评价每个解的适应度，我们通过计算N个目标权值和的方式定义一个解X的适应度函数12NFXFFXFX2512,N是这个目标的权值，它们符合以下条件（1）0,IFOR1,I。（2）12N26如果我们使用连续的权值，通过GA局部搜索的方向是已经固定的。连续权值策略和一个目标的选择方式都不能为寻找所有的多目标问题的非劣解高效的服务，这是因为各种搜索方向需要寻找多种非劣解。为了实现各个方向搜索，而提出这种算法。这个权值被定义为1IINRANDOMRRADOM1,2,IN27其中，IRANDO是随机值。无论何时选择一组父代种群我们都这样定义权值。在此算法中局部搜索应用每个由父代种群向子代种群进化的过程中，新种群的适应度通过被用于选择父代种群的权值而定义，这样，对每个解的局部搜索的方向就由应用于它的父代解选择的权值定义了。这种方法下，每个解都有自己的搜索方向。另一个值得注意的是，如何决定介于局部搜索和进化操作的可行计算时间。按照惯例的局部搜索，只有等在检验所有相邻解后没找到比当前解更好的解时，搜索才结束。本算法不会花相当长的时间，还有代数通过遗传操作更新能够反复声明很多次。总之，我们能通过局部搜索调整计算时间。从用于通过交叉操作的后代群体的当前群体中选择一组父代解，1、2，N已经通过上面的式子确定，在当前种群中每个解X的适应度已经作为个目标权值之和而得到。解X选择概率PX已经通过使用线性缩放的轮盘赌方法得到MINIXFFPX28MINF是当前群体最坏解的适应度。局部搜索的步骤（1）指定一个初始解X；（2）检验初始解的相邻解Y；（3）如果Y比好，那么用代替X；（4）如果X得所有相邻解都已经被检验了，结束这个过程，否则返回（1）；在（4）中可以看出，对一个初始解通过局部搜索检验的解的总数要远大于相邻解的总数25。精英保留策略本算法保留了两组解当前解和试验的非劣解。局部搜索后，当前种群已被进化的种群替换，接着试验的非劣解被新的当前种群所更新，即如果当前种群的一个解不受其他解和试验的非劣解集支配，那么将此解添加进这个试验集合，在试验集合中被这个解支配的其他解就被剔除。在试验集合中，一小部分解被任意地选择作为局部搜索的最初解，这是因为如果一个非劣解没有父代解，随机权值分配给那个非劣解去执行局部搜索，随机选择的非劣解可能被认为是精英解，因为它们被添入没有进过遗传操作的当前种群。MOGLS的步骤（1）初始化，随机产生一个初始种群PON是这个种群解的个数。（2）评价适应值对当前种群中每个解在N个目标方向计算适应度值，更新临时非劣解集。（3）选择重复以下过程去选择父代解的POSLITEN通过27在适应度函数1中计算随机的权值，1、2，N。通过（28）确定的选择概率，从当前种群中选择一组父代解。（4）交叉和变异从父代解中选择的POSLITE对，分别应用交叉过程，从每个父代解的对中产生新解，然后对新解使用变异操作。（5）精英保留策略从试验非劣解集中随机选择ELITN解，接着将这个选中的ELITN解加入到在4中POSLITEN解中，它的功能是为了创建PON解的一个种群。（6）局部搜索在当前种群对所有PO解应用改进的局部搜索过程，对每个解的局部搜索方向已经由父代解被选择的适应度函数中的权值确定。当前种群被局部搜索改进的ELITN解置换。（7）终止测试如果一个提前确定的停止条件被满足，结束算法，否则，返回第二步。如果多目标优化问题有凹的PRAETO前端，使用带有连续权值的计算权值之和的方法将不能得到整个PRAETO前端。但MOGLS能处理带有凹的PRAETO前端的多目标进化问题。具体流程见下图进化开始种群初始化非劣解整理选择交叉变异进化代数GEN大于最大代数终止计算适应度产生混合种群RT对RT中的解赋权值，并利用权值分级计算适应度通过精英选择策略剔除劣解局部搜索非劣解整理保留保留GEN1NOYES32性能评价指标现有研究中，对新的多目标遗传算法进行性能评价时，普遍采用两种方法一种是构造一系列可以独立评价算法性能的指标用于考察算法搜索到的非劣解集的优劣；另一种是选取一种迄今为止性能优越的验证算法与新算法在相同进化条件下对测试算例进行优化，比较搜索到的非劣解集。在采用验证算法比较时，C指标使用最为普遍26。指标由ZITZLER提出，其定义为设,ABX是两种算法优化所得的非劣解集，指标是一种值域定义在0,1上、用来刻画,之间偏序能性的指标|,|BBAABA。若C，则说明对于集中的任一个非劣解个体，集中总存在“优于”DOMINACE它的解个体；,0CAB，说明对于B集中任一个解个体，集中都不存在“优于”它的解个体。33算例分析331算例描述为了对新提出的多目标进化算法性能进行评价，或对多种不同的多目标进化算法进行性能比较，研究者们常常需要借助不同性状的标准测试函数对算法性能进行考察。已有的测试函数的设计原则主要有（1）优化问题为非凸情形下的优化性能测试；（2）优化问题目标空间不连续情形下的优化性能测试；（3）多变量优化问题的优化性能测试。针对这些测试原