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

1、华北电力大学毕业设计摘 要 在最近二十年，作为一类新兴的优化技术，多目标进化算法吸引了极大关注，许多学者提出了不同的算法，多目标进化算法已经成为处理多目标工程设计和科学研究问题的重要方法。许多moea的方面被广泛地调研，然而一些问题仍然没有被很好地受到关注。例如，随着这类算法的快速发展，对算法之间性能进行比较变得越来越重要。本文分析总结了两种目前流行的所目标进化算法的基本原理，并通过算例来比较它们的性能。本文主要工作内容如下：1. 简要回顾了多目标进化算法的发展历史，按照算法原理与进化模式将算法分类。2. 简述多目标问题及进化算法的相关技术，详细分析了nsga-ii算法和mogls算法。3.

2、分别利用nsga-ii算法和mogls算法对算例进行求解，并用c指标对两种算法的结果进行评价，得出它们各自的优缺点。多目标问题仍向算法设计，呈现和执行提出挑战。不断变化的多目标问题很少被考虑到它的时变特性，对此有效的多目标进化算法很罕见，多目标进化算法的结合量计算和有区别的进化还始终停留在初级阶段。多目标进化算法的应用应该在未来不断地延续，moea的理论分析比它本身更复杂而且应该通过主要从事计算机和数学研究人员的努力工作来解决。关键词：多目标优化，进化算法，适应度计算，精英保留，局部搜索 abstractin the past two decades, as a new subject， mu

3、lti-objective evolutionary algorithm (moea) has attracted much attention, the numerous algorithms have been proposed and moea has become the important approach to deal with multi-objective optimization problem （mop） of engineering design and science research. many aspects of moea have been extensive

4、ly investigated, however, some problems are still not considered very well. for example,under the condition that many algorithms are brought up, the methods that compare the performance between the algorithms have become very prominent. the main principles of two popular algorithms were analyzed in

5、this paper. the main work of this paper can be sumrised as the following:1.a brief review of the history and current studies of moea was brought out.all common algorithms have been distributed into several sorts. 2 mop and the relational technique of moea was introduced concisely.then nsga-ii and mo

6、gls were expounded in detail.3 nsga-ii and mogls were used for solving the same multi-objective scheduling problem separately and their sesults was evaluated by c norm, through this ,the advantage and defect of these two algorithms have been emerged.moop still poses the challenges for algorithm desi

7、gn, visualization and implementation. the dynamic mop is seldom considered for its time-varying nature. the effective pmoea is very sparse and the moea combining quantum computing and differential evolution is still in the infancy period. the applications of moea should be extended continuously in t

8、he near future. the theory analysis of moea is more complicated than moea itself and should be considered through the hard works of researchers majoring in computers and mathematics et al.key words: multi-objective optimization,evolutionary algorithm,fitness calculating,elitism duplication,local sea

9、rch 目 录摘 要 .abstract.第1章 绪 论11.1究背景及意义11.2多目标进化算法的研究现状21.3本文研究内容4第2章 多目标进化算法62.1 多目标优化基本概念62.1.1多目标优化问题描述62.2多目标遗传算法设计的关键技术72.2.1适应值设计72.2.2维持群体多样性72.2.3精英保留策略92.3 nsga-和mogls算法12!异常的公式结尾2.3.2mogls142.4本章小结11附 录26致 谢33第3章 优化算例及分析303.1多目标遗传算法的性能评价20 3.3.1性能评价指标20 3.3.2测试函数及其设计253.2二级标题 353.3二级标题 403.

10、3.1三级标题40 3.3.2三级标题45第 4 章 总结304.1二级标题 304.2二级标题 354.3二级标题 404.3.1三级标题40 4.3.2三级标题45参考文献50附 录 51致 谢 52第1章 绪 论许多科学研究和工程实践中遇到的优化问题，通常需要综合考虑多方面因素，这就要求在解决问题时同时对多个目标进行优化，这样的问题被称为多目标优化问题(multi-objective optimization problem, mop)，它们有许多冲突的目标。有时目标之间是相辅相成、互相促进的，但更多的时候，目标之间是相互矛盾、此消彼长的。因此在绝大多数情况下，若想达到总目标的最优，就需

11、要对各个目标进行综合考虑、折中处理，所得到的解是一组基于pareto最优性概念的非劣解集1，所以如何进行综合与折中就成为解决问题的关键。1.1研究背景及意义生物在其延续生存的过程中，逐渐适应其生存环境，使得品种不断的到改良，这种生命现象叫做进化。进化算法(evolutionary algorithm, ea)是一种通过模拟生物进化规律来进行选择与变化的随机搜索算法，起源于20 世纪50 年代末，现有的代表性进化方法有遗传算法(genetic algorithm, ga)、进化规划(evolutionary programming, ep)和进化策略(evolutionstrategy, es)

12、等几种方法2。进化算法非常适用于于求解高度复杂的非线性问题，并且由于这类算法具有通用性，因而被广泛地应用于单个目标的复杂系统优化问题。然而，人们在求解现实世界许多优化问题时，通常不追求单一目标的最优性，这就要求在解决问题时同时对多个目标进行优化和权衡，有时目标之间是相辅相成、互相促进的，但更多的时候，目标之间是相互矛盾、此消彼长的，这样的问题被称为多目标优化问题(multi-objective optimization problem, mop)，大多数工程和科学问题是多目标最优问题。多目标优化问题的各目标之间通过决策变量相互制约,对其中一个目标优化必须以其它目标作为代价,而且各目标的单位又往

13、往不一致,因此很难客观地评价多目标问题解的优劣性。例如,在设计一座桥梁时,我们一方面希望建设桥梁的费用最小,另一方面希望桥梁具有最大的安全性。与单目标优化问题的本质区别在于,多目标优化问题的解不是唯一的,而是存在一个最优解集合,集合中元素称为pareto 最优或非劣最优(non-dominance) 。求解它们需要用不同于单目标优化的数学工具,甚至最优的含义也发生了变化。由于它们有许多冲突的目标，因此若想达到总目标的最优，就需要对各个目标进行综合考虑、折中处理，所以如何进行综合与折中就成为解决问题的关键。多目标进化算法(multi-objective evolutionary algorith

14、m, moea)就是一类可以有效解决这种问题的优化技术3。它的主要思想是将进化算法的概念引入到多目标优化领域，对多目标优化问题同样采用进化操作方式，但算法由单目标优化问题求取一个最优解，转变为多目标优化问题中求取一个最优解集，该解集称为pareto最优解集。最优解集中的每个解，理论上都是“最优解”，而在实际应用中，可以根据决策需要选择其中一个解作为最终决策方案，实现最优化的目的。多目标进化算法是一门新兴的学科，理论与算法并不完善，尚处于发展阶段。然而，它对工程项目具有重要的实践意义，因此在过去的十多年间涌现出许多新的改进算法，人们不断地寻找是否存在优化效果更好的多目标进化算法。而对算法性能进行

15、比较和评价就成为一个重要的核心问题，引起了诸多学者的研究兴趣。1.2多目标进化算法的研究现状优化问题一直是倍受人们关注的问题，自1950 年以来,运筹学研究人员已经建立了许多方法解决mop。在专业文献中,有许多数学规划技巧解决mop ,如多目标加权法、分层序列法、约束法、目标规划法等。遗传算法自出现以来在许多领域得到了广泛的应用，在解决简单的单目标优化问题方面取得了很好的成果，但面对复杂的多目标优化问题，传统的遗传算法就显得力不从心。例如在现代能源系统生产过程参数的优化4设计中经常会遇到多目标函数的优化问题，使用经典的多目标优化方法通常把多个目标函数整合成单目标，将问题转变为单目标优化问题，然

16、后采用单目标的优化技术求解。但这些方法存在：只能得到一个解；多个目标函数之间量纲不同难以统一；加权值的分配带有较强的主观性；加权的目标函数之间通过决策变量相互制约，最终优化目标仅为各目标之和，各目标的优化进度不可操作等缺点。这是因为传统数学规划方法存在一些缺陷,例如有些方法对pareto 前沿比较敏感,当pareto 前沿是凹的或者不连续时,这些方法失效;有些方法要求目标函数和约束条件可微;有些方法每次运行只产生一个解,求多个解时需要运行多次,效率较低。进化多目标优化始于1967年，此后众多的研究人员通过对遗传算法进行改造，相继提出了多种用于解决多目标优化问题的遗传算法，如基于向量评估的遗传算

17、法(vega) 5，小组决胜遗传算法(npga) 6，非支配排序遗传算法(nsga)及其改进算法nsga-ii7等. 其中nsga的改进算法nsga-ii是带有精英策略的非支配排序遗传算法，改进了先前算法的不足之处，提高了算法的运算速度和鲁棒性，并保证了非劣最优解的均匀分布。自scharfer提出vega起，多目标进化算法的发展经历了由基于单目标子群体优化的算法到基于pareto最优性指导的分级策略与适应值共享策略算法的发展历程。按照算法原理与进化模式划分，现有多目标进化算法可分如下四大类：第一类算法是早期基于单目标群体优化的moga。这类算法通过加权或划分子群体进化等方法将mop转化为不同的

18、sop，然后借助现有单目标遗传算法对转化后的sop进行求解，最后对进化获得的解进行分析，筛选出非劣解集。由于这类算法的设计思想是基于单目标遗传算法的进化策略，因此它的优点是算法容易实现；其不足是，基于单目标子群体优化的算法很难搜索到严格意义上的非劣解集，往往仅能得到非劣解集中的部分极值点。代表算法有vega、wbga、dm等。ishibuchi、murata等人1996年提出的mogls是在随机权策略的wbga中引入局部搜索的改进算法，其本质属于这类算法8。第二类算法是基于goldberg提出的适应值分级和共享策略的多目标遗传算法。这类算法在适应值设计中鼓励非劣解等级优先个体和同一等级内较为稀

19、疏个体以较大概率出现在后代群体中。由于这类算法是基于pareto概念的moga，因此，它的优点是可以通过单次优化获得一组靠近真实非劣解前沿的非劣解集；但由于算法未考虑进化过程中精英个体的保留，因此解的收敛速度及收敛性能不够稳健。代表算法有moga、nsga和npga等。第三类算法是由第二类算法发展起来的精英保留策略moga。这类算法通过在进化过程中引入外部伴随群体对群体中的精英个体加以保留，同时采用更加成熟的适应值设计策略，使算法不仅在收敛速度上有所提高，而且在优化性能上也有所改善。这类算法的不足之处是，算法进化模式单一、局部搜索性能欠佳，之所以存在这些不足，主要是因为这类算法大多由第二类算法

20、改进得到，因此进化模式不可能完全摆脱先前的算法框架，并且遗传算法的进化原理决定了它不可能具有性能较高的局部搜索能力。代表算法有npga-ii、nsga-ii、paes和spea等9。第四类算法是采用其他搜索算法策略改进的moea。这类算法由于采用的进化策略是基于模拟退火搜索、禁忌搜索、粒子群优化、小生境策略等不以传统遗传算法进化结构为主导的优化策略，因此在早期的多目标进化算法研究中并未受到广泛重视，只是在近年随着多目标遗传算法局部搜索性能欠佳的不足逐渐呈现，以及其他进化策略单目标进化算法的迅速发展才开始活跃起来。这类算法由于群体规模适中，因此算法复杂性相对较低，而且由于算法局部搜索性能优越，因

21、此常常可以与现有的moga结合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遗传算法那样既能保证全局寻优、又能维持群体多样性，因此，在算法设计时往往设置了许多控制参数对算法性能进行调整，这又导致在求解问题时常常需要借助大量试验计算分析确定进化参数，因此算法性能不够稳健。代表算法有mose、mopso等10。除了上述四类算法外，一些学者在演化策略中引入偏好分级或适应值分享机制获取满意解。但由于这些方法不能通过几次运行获得稳定的非劣解集，且算法复杂性较高，因此这类研究不是多目标进化算法研究的主流方向。而考虑偏好关系对遗传进化的影响，大多是用模糊集方法进行偏好信息的处理，而进一步利用偏好对

22、进化进行指导或通过进化引导偏好的交互式多目标进化算法还仅仅处于概念研究阶段，距算法实现尚有较大差距。多目标遗传算法的研究一直是这类算法研究的主流方向：尽管遗传算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他进化策略或启发式局部搜索算法好的局部搜索性能，因此，以进化算法为算法主体，结合遗传算法全局搜索和一般启发式进化策略局部搜索的优势，获得高性能的多目标优化算法，成为多目标进化算法研究的潜在发展方向。1.3本文研究内容 多目标进化算法如果按决策方式划分，则可以分为三类11：前决策（先验式）、后决策（后验式）和交互式决策，这是按照用户的人工决策信息作用于算法的时间先后划分的。其

23、中，后决策是最常用的技术，即算法终止时提供给用户一组最优解。目前绝大多数多目标进化算法是排序选择法和后决策技术类型的。spea/spea2 (zitzler & thiele 2001)和nsga/nsga-ii (srinivas & deb 2002)两类算法目前的应用更广泛，也更具有代表性。由于本文需要对多目标进化算法的结构进行深入的分析，所以需要在此选择一个代表性的算法，通过该算法的简介，来描述一下多目标进化算法的一些基本概念和工作原理。本文将以nsga-ii算法和mogls（multi-objective genetic lcal search）算法为例，通过算例和指定的函数指标来分

24、析比较它们各自性能的优缺点。nsga-ii算法首先随机产生一个初始种群，对种群通过采用轮盘赌的方式选择、交叉和变异操作获得新的种群，将种群中的个体构造其pareto 边界集，并根据个体间的聚集距离，建立偏序关系，最终从偏序关系中选择原始种群规模大小的个体，组成新的种群，完成了一次进化操作。由此可见，对于多目标进化算法而言，构造pareto 边界集和计算个体间的聚集距离是新的概念，也是绝大多数多目标进化算法共有的流程，这为之后提取算法公共流程方式的讨论提供了基本的依据。mogls是ishibuchi和murata两位学者提出的。最初的mogls是在遗传进化过程中，每代遗传操作生成新个体后，对现有

25、群体中的所有个体进行局部搜索；后来ishibuchi等人对局部搜索的步长选取、邻域搜索效率做了进一步研究后，将局部搜索过程仅应用于当前群体中的优秀，显著提高了算法效率，改进后的算法可获得与spea、nsga-ii相当的优化性能。mogls的优点是通过随机权将mop转化为sop，算法容易实现，并且恰当控制mogls中邻域搜索个体的选取及步长可以在减少计算复杂度的同时获得良好的计算结果；算法的不足之处是，算法的构造是基于mop转化为sop的思想，因此在不明确多个目标偏好情况下，采用随机权的方法往往不能保证所得非劣解集分布的均匀性。第2章 多目标进化算法2.1 多目标优化基本概念2.1.1多目标优化

26、问题描述 多目标问题( mop) 的一般描述为: 给定决策向量 , 它满足下列约束: ( 2-1) ( 2-2)设有r 个优化目标, 且这r 个优化目标是相互冲突的, 优化目标可表示为: 寻求, 使在满足约束( 2-1) 和( 2-2) 的同时达到最小。2.1.2最优性对于多目标优化问题, 由于其待优化的各个子目标一般是相互冲突的, 因此需要定义解个体间的优劣关系, 以便对候选解进行评价与取舍。本文采用广泛使用的pareto 最优性12定义。定义1 ( 个体的pareto 支配关系) 。设和是进化群体中的任意两个不同的个体,称支配(dominate) ,则必须满足下列二个条件:( 1) 对所有

27、的子目标, 不比 差, 即 ( k=1, 2, r) ; （2） 至少存在一个子目标,使比好。即, 使其中r 为子目标的数量。此时称 为非支配的( non- dominated), 为被支配的( dominated) 。表示为, 其中“”是支配关系。定义2( pareto 非支配集)。设有解集,若中的个体不被任何其它个体支配, 则是 中的非支配个体; 由 中的所有非支配个体构成的子集称为 的非支配集。即: 最优性的含义为：是pareto最优解，表示在整个解空间中，不存在这样的解：某一个目标比小的同时，保持其余个目标值不大于x的目标值。因此，满足这种最优性的“最优解”往往不是单个解，而是一组满足

28、上式最优性条件的非劣解集合，包含非劣解的集合称作非劣解集（pareto solutions set）或非受控解集(nondominated solutions set)；非劣解对应的目标值在目标空间中称为非劣点；最优解集在优化目标空间构成的分布称作非劣解前沿。在决策和优化问题中，最优性取决于如何比较和排序候选解，及决策者的偏好结构。从决策者的立场来看，一般认为每对候选解具有以下比较关系：(1)一方明显优于另一方；(2)两者相互非劣；(3)两者不具有可比性。由此才可以对每对解之间的优劣比较进行细致的区分13。2.2多目标遗传算法设计的关键技术2.2.1适应值设计mop问题包含多个待优化的子目标，

29、通常eas用于多目标优化时必须考虑两个关键问题：(1)为了保证朝pareto最优集的方向搜索，如何实施适应度赋值和选择。(2)为了避免未成熟收敛和获得均匀分布且范围最广的非劣解，如何保持群体的多样性。在已有研究中，多目标遗传算法的适应值设计(fitness assignment)主要有基于加权策略、基于目标设计策略和基于非劣解等级优先策略三种设计策略14：(1)基于加权策略的适应值设计，即基于聚合策略的方法，是通过加权策略将多个目标转化为单个目标后进行优化。这种适应值设计的遗传算法通常需要在算法进化过程中系统地对函数中的参数的权重值进行调整，以便得到一组非劣解集。在进化的每一代中参数呈现有规律

30、的变化，但在该代操作过程中保持不变，常见的进化加权法，个体的评估使用确定的加权组合，所有个体都有一个适应度值，保证了搜索方向朝最优解迈进。(2)基于目标设计策略的算法，即基于准则的策略，每当个体选中后进行复制时根据不同的目标来决定是否被复制至配对池。此方法通过在不同进化代之间更换优化目标每次优化一个目标，使算法群体每次运行得到一个非劣解，从而通过多次运行找到优化问题的非劣解集。目前，常用的方法是在选择阶段根据概率来确定各子目标的排序，该概率值由用户确定或随机产生。这种策略存在的问题是进化结果容易偏向某些极端边界解，并且对pareto最优前端的非凸部敏感。(3)基于非劣解等级优先概念的适应值分配

31、策略由goldberg最先提出，后人大多在此基础上进行改进，如将群体划分为几个有序的子群体。这类算法的适应值设计主要有等级优先、深度优先和基于优先数三种：等级优先策略算法在计算适应值时主要考虑个体在群体中“优于”其他个体的数目或考虑优于该个体的其他个体数目之和，以此确定给个体的适应度值；而深度优先策略算法在分配个体适应值时主要以个体所在的非劣解等级及等级内的疏密程度有关；基于优先数的适应值分配算法在计算个体适应值时，考虑了个体所优先于或劣于群体中其他个体的数目。一般来说直接统计优胜个体数目的操作方式简单，在原理上一目了然。单目标优化中的目标函数常与适应度函数相同，但mop问题中的适应度赋值和选

32、择必须考虑几个子目标，moeas必须根据个体间的pareto优胜关系和其他信息为个体确定适应度值，这种适应度值和每个目标函数的具体大小没有直接关系。另外，与单目标优化不同的是，在个体保持不变的条件下，同一个体在这一代和下一代的适应值可能不相等。pareto优胜关系是决定个体适应度函数值的重要依据，很多moeas根据个体间的这种关系，将个体的适应度函数值分成两个层次，即劣解和非劣解，后者的适应度值总是优于前者。当个体间没有pareto优胜关系时，其他形式的个体信息被用于确定适应度函数值，其中个体密度值是利用最多的信息，并采用不同的方法估计个体密度值。基于pareto优胜关系的选择方法已经被广大研

33、究者采纳，现已有多种基于pareto的适应度赋值方案，其中基于种群个体级别排序的适应度赋值方法是较常见的一种方法。多目标问题与单目标问题不同，它的优劣性与支配关系并非定义目标向量之间的那种整体有序关系，只是给出部分有序关系，因而种群的级别排序不具有唯一性。假设第代种群中的个体，在第代种群个体排序中的位置为，基于个体排序的适应度赋值步骤描述如下：(1)基于的数值将种群中所有个体进行级别排序。(2)利用线性或非线性的插值方法在最低序号与最高序号之间进行插值。(3)具有相同序号的个体进行适应度共享算子操作，即通过除以相同序号的个体数目得到新的适应度值，另外，也可以给不同序号的个体分配固定不变的适应度

34、值。2.2.2维持群体多样性因为eas是并行地处理一组解，通过杂交和变异来搜索空间以寻找可能的最优区域，通过选择来搜索具有较高适应度的个体。传统的进化算法在pareto最优集上执行多目标搜寻，希望找出尽可能均匀分布的解集，因而个体的多样性减少的很快，经常收敛至单个解而丢失多个其他非劣解。在进化过程中某些具有较高适应度个体的大量复制造成高选择压力，使得个别具有更高适应度的个体得不到遗传的机会，甚至导致整个群体出现同解的现象15。如果单纯从群体多样性出发，群体规模应该越大越好，但群体规模太大会带来若干弊病：一是从计算效率来看，群体越大，导致其适应度评估次数增加，引起计算量的增加，从而影响算法效能；

35、二是群体中个体生存下来的选择概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，大多数个体被淘汰，严重影响交叉操作。因此群体规模只能维持在一定数量上，它并不能成为解决进化算法多样性的途径。进化算法由于其进化算子固有的随机误差，因而基于有限群体实施进化时会出现收敛至某一个解。因为多目标优化的目的是得到一组在整个pareto曲面上尽可能均匀分布的一组解，因此必须在进化过程中采取措施避免进化结果收敛至单个解。为使算法优化得到一组尽可能分布均匀的非劣解集而非此集合中的非劣解极值点，大多数moeas在当代群体中维持多样性是在选择过程中结合了密度信息，即个体在其

36、邻域范围内所占的密度越高被选择复制的机会越小。现有多目标遗传算法可根据统计概率密度估计的方法加以分类为如下三种策略来维持群体多样性：(1)基于核函数的评价策略：基于核函数的评价策略主要通过计算以个体为“核”、群体中其他个体距离“核”的核函数之和，通过优先保留核函数值较大的个体即较稀疏的解个体达到维持群体多样性的目的。具体应用时首先根据内核函数来定义一个点的邻域范围，内核函数采用至另一点的距离作为参数。每一个个体计算至其他个体的距离，通过内核函数的映射后求和计算出值，该累加值代表了个体的密度估计。(2)基于邻域解数目的评价策略：基于邻域解数目的评价策略是以评价解为核心、包含一定数量邻域解的邻域半

37、径为指标，优先保留邻域半径较大的个体即较稀疏的解个体。该策略主要考虑给定点至第个最近邻居的距离，以便估计出其在邻域内的密度。(3)分区统计数目策略：分区统计数目策略是将目标空间划分成一定比例的区域，通过统计个体所在区域中邻域解数目来确定个体被保留的概率邻域解数目越大，被保留概率越小。该方法采用一个网格来定义空间上的邻居关系，个体的密度只要通过简单地统计同一网格内的个体数目即可，这种网络可以是固定的，也可以根据当前群体进行自适应调整。多目标进化算法与单目标进化算法类似，为了提高群体多样性，在算法过程中尽量采用小生境（niche）共享技术，使得在一个群体内可以形成在多目标问题上分布均匀的非劣最优解

38、集。具有相同pareto级别序号的解个体在实施共享适应度值后，还必须按解的目标向量之间的空间距离进行小生境规模调整。当两个解的目标向量之间的空间距离小于某一预定值时，相应解的小生境规模就必须进行调整。此外，还有同时基于决策向量空间与目标向量空间的混合共享技术，共享问题的关键是如何确定共享参数，的选择将会影响算法的性能，而适应度共享效果则共同取决于和种群大小16。2.2.3精英保留策略遗传算法是基于随机进化选择的算法，因此，为改善遗传算法的收敛性能，现有多目标遗传算法大都引入了精英保留策略。现有算法中精英策略的实现方式主要有两种：其一是采用新旧群体合并，通过确定性的选择方法在混合群体中选择后代，

39、而不是采用变化之后的配对池来替换旧群体，增大了精英个体在后代群体中出现的概率，以此改善算法收敛性。另一种实现方式是采用独立于进化群体的伴随群体，即使用带有所谓的档案（archive）的方式，保留与更新算法进化过程中搜索到的非劣解集来维护当代群体中的满意群体，使其能够复制到下一代，伴随群体仅作为一个外部存储集，独立于进化过程的优化操作17。由于内存资源的限制，以上两种最优个体保留策略必须确定哪些个体作为最优个体加以保留。通常采用优胜准则来确定最优个体。如果使用伴随群体的方式，则伴随群体中包括当前的近似pareto集，即伴随群体中受控的个体被移去。但是使用优胜关系比较的方法有时也存在问题，如对某些

40、连续型问题所对应的pareto集可能包含无穷多个解，因此需要补充其他的信息知识来减小所存储的个体数目。这些信息包括密度信息，个体进入伴随群体所需时间。moeas的最优个体大多利用优胜关系和密度两者的组合来进行挑选，最优个体保存在每代的伴随群体中。更新的算法研究表明，如果同时采用这两种精英策略，可以进一步提高算法的搜索性能与收敛效果。2.3遗传算法的一般流程holland教授提出的遗传算法，现在一般称为简单遗传算法或基本遗传算法18，其基本流程如下图：图2-1遗传算法基本流程 (1)参数编码：遗传算法一般不直接处理问题空间的参数，因此在算法开始进行之前，首先要选择合适的编码方式对待优化的参数进行

41、编码。通常采用二进制编码，将参数转换成为和组成的数字串。 (2) 产生初始种群：随机地产生一个由个个体组成的种群，该种群代表一些可能解的集合。遗传算法的任务是种群出发，模拟生物进化的过程进行优胜劣汰，最后得出满足优化要求的种群和个体。 (3) 设计适应度函数：把问题的目标函数转换成合适的适应度函数，并根据适应度函数计算种群中的每个个体的适应度，为种群进化的选择提供依据。 (4) 优化准则：也可称作终止条件，是用来判断算法是否可以终止的标准。可以设定进化的最大代数，当进化到最大代数时，算法终止运行。也可以设定期望的适应度函数值，只有当种群中存在个体能达到期望值时，算法才可以结束。通常情况下，这两

42、种方法同时作为优化准则使用。(5) 选择(复制)操作:按一定概率从群体中选择个体，作为双亲用于繁殖后代，产生新的个体。在此操作中，适应于生存环境的优良个体将有更多的机会繁殖后代，这使得优良特性能够遗传到下一代。(6) 交叉操作:随机地选择用于繁殖的每一对个体的同一基因位，将其染色体在此基因位断开并相互交换。(7) 变异操作:以一定的概率从群体中选择若干个个体。对于选中的个体，随机选择某一位进行取反操作。对产生的新一代群体重新进行评价、选择、杂交和变异。一代一代循环往复，使种群中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度满足优化准则或最优个体的适应度和平均适应度不再提高，则迭代过

43、程收敛，算法结束。遗传算法的选择和交叉算子赋予了它强有力的搜索能力，变异算子则使算法能搜索到问题解空间的每一个点，以确保算法能达到全局最优。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化计算的实际应用问题，一般可以按照上述步骤来构造求解该问题的遗传算法。由上述步骤可以看出，构造遗传算法时需要考虑的两个主要问题是可行解的编码方法和遗传算子的设计，这也是设计遗传算法的两个关键步骤。2.4算法性能评价2.4.1多目标进化算法性能评价的研究现状多目标遗传算法的性能评价与传统优化算法及单目标遗传算法的性能评价有所不同，传统算法的优化性能可以通过梯度下降速

44、度进行评价，并且可以通过严格的数学证明分析其收敛性能；单目标遗传算法可以采用基于模式定理或基于马尔可夫随机过程理论的证明分析其收敛性，尽管这类证明研究还很初步。然而在对多目标进化算法的性能进行评价时，一般需要考虑到三个较为重要的因素19：算法的效率、算法的效果，以及算法的鲁棒性。算法的效率是指算法自身的时间复杂度和空间复杂度，也即算法运算时间的长短和资源消耗的多少；算法的效果是指算法求得的解集的质量，也即算法的收敛效果和解集的分布性效果；算法的鲁棒性是指算法的应用范围和稳定性，也即是否对多种问题都有很好的求解能力、是否求解问题时总是相对稳定的。而从现阶段的研究来看，人们更关注的是，算法结果是否

45、为高质量的结果，而对于另外两个因素相对要求并不高，而且对于算法的效率来说，涉及到的是经典的算法复杂度理论，已经有很完善的泛化体系对其进行评价了，无需在多目标进化算法领域对其再进行专门的研究。所以现阶段的性能评价方法主要集中于对算法的效果的衡量。2.4.2多目标进化算法的性能评价方法多目标进化算法的性能评价方法有很多，大体上可以分为两类20，一类是评价算法的收敛性效果的，一类是评价解集的分布性效果的。下面分别对二者加以介绍。1. 算法收敛性评价所谓的收敛性，实际上是指算法的真实结果集与理论上的最优结果集之间的趋近度，即理论上的pareto边界和真正得到的pareto边界之间的差距。收敛性的评价方

46、法有很多种，如错误率、解集间覆盖率、世代距离、最大出错率等等。以解集间覆盖率为例，该覆盖率又称为s指标(zitzler, 2000) 21，用来计算一个解集中被另一个解集中的个体支配的个体所占的比率。如式(3-1)所示。(3-1)对于收敛性的评价指标而言，可以通过指标值反映出算法间优化效果的差异，但只局限于最优解集中更优解的数量，对于其空间上的特性不做相关考虑。2. 解集分布性评价在更多的算法应用领域中，解集的空间分布特性是十分重要的，决策一般希望能够在目标空间中找到一组均匀的解集，以便做出不同的决策，如果解过于集中，则周围的很多解事实上并没有太大的意义，也不利于产生新个体，从而影响了种群的进

47、化效果。分布性的评价方法也有很多，如空间评价方法、基于个体信息的评价方法、网格分布度评价方法等等。以空间评价方法为例，该方法又被称为delta指标(schott, 1995) 22，用来计算解的分布信息的，如式(3-2)所示。 (3-2) 其中，对于分布性的评价指标而言，只关注结果集的分布特性，用以检测算法是否被阻在一个很小的范围之内进行搜索，而导致无法实现全局的最优搜索的现象。由于收敛性评价与分布性评价的应用方向不同，因而在比较算法的时候，多会综合两种评价后，对算法的性能得出适当的结论。2.4.3现有性能评价体系的特点分析现有的性能评价体系可以分为两种形式22：1. 理论证明理论证明即是对算

48、法的复杂度、收敛性等进行求解和比较，即通过理论的分析得出正确的结论。但是由于多目标进化算法是一门新兴的学科，多目标进化计算的理论基础尚未成熟，算法收敛性的理论证明对有限时间内的收敛性分析较少，而时间无穷大的收敛性并没有工程实际的应用价值。因此从理论上来证明算法的优劣并不常用，也较难实现正确的评估。2. 实验比较分析实验比较分析是指通过对优化算例的结果和结果的各种指标进行比较，验证新算法与已存在的算法之间的性能差别。这种基于解决实际算例进行评价的方法具有一定的局限性，很难得出某种算法一定比另外一种更优的结论，其结论的说服力也不够。但是，由于这种方法可以简单直观的反映出算法的一些特性，所以在分析算

49、法性能领域的应用十分广泛。因此，现有的性能评价体系从使用范围上讲，是基于实验比较分析来实现的。2.5本章小结 本章首先介绍了多目标进化算法的基本概念和原理。然后着重介绍了多目标进化算法的关键技术，现代多目标进化算法正是在这些方面存在差异，也是判断算法之间性能优劣的出发点。第三部分给出了多目标进化算法的一般流程，这是所有算法的原型，不同算法都是在此基础上做出改动，了解此框架是学习其他算法的基础。最后简单介绍了算法的性能评价体系，为几种算法比较的方案提供依据，得出基于实验的方法是可行的，本文将在第三章利用这一思想来试验nsga-和mogls两种算法的优劣。第三章 优化算例及分析3.1 nsga-和

50、mogls算法3.1.1带精英策略的非支配排序的遗传算法（nsga-）在nsga 中, 同一个小生境内的个体适应度共享, 从而降低该小生境内个体的竞争力, 防止种群在收敛过程中陷入局部最优, 实现种群多样性。首先, 对种群内个体按非劣性排序, 为获得的pareto 最优解赋予相同的适应度; 其次, 根据goldberg和deb等23提出的共享方法, 按式(2-3) 和式( 2-4) 计算出每一个pareto 最优解的小生境数, 将该个体原适应度除以小生境数,就得到它的共享适应度。这样, 处于同一个pareto 前沿的非劣解, 由于各自的小生境数不同, 最后的共享适应度也不同。 (2-3)其中,

51、 表示个体 与个体 的距离, 是同一小生境中个体间的最大允许距离, 表示距离为时的共享函数值。其中, ( 2-4) 表示个体i 的小生境数。虽然非支配排序遗传算法（nsga）在许多问题上得到了应用，但仍存在一些问题，如计算复杂度较高，需要指定共享半径，易丢失已经得到的满意解。nsga-针对以上的缺陷通过以下三个方面进行了改进：(1)提出了快速非支配排序法，在选择运算之前，根据个体的非劣解水平对种群分级。首先将当前的所有的非劣解个体划为同一等级，令其等级为；然后将这些个体从种群中移出，在剩余个体中寻找出新的非劣解，再令其等级为；重复上述过程，直至种群中所有个体都被设定相应的等级。具体方法与nsg

52、a的快速非支配排序方法不同，nsga-对于每个个体都设有以下两个参数和，为在种群中支配个体的解个体的数量，为被个体所支配的解个体的集合。首先，找到种群中所有的个体，将它们存入当前集合，然后对于当前集合的每个个体，考察它所支配的个体集,将集合中的每个个体的减去1，即支配个体的解个体数减1，如果则将个体存入另一个集。最后，将作为第一级非支配个体集合，并赋予该集合内个体一个相同的非支配序，然后继续对作上述分级操作并赋予相应的非支配序，直到所有个体都被分级。如此操作降低了算法的计算复杂度。由原来的降到，其中，为目标函数个数，为种群大小。(2)提出了拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度

53、共享策略，并在快速排序后的同级比较中作为胜出标准，使准pareto域中的个体能扩展到整个域，并均匀分布，保持了种群的多样性。拥挤度的概念：拥挤度是指在种群中的给定点的周围个体的密度，计算上要考虑个体周围包含本身但不包含其他个体的最小正方形，如下图，个体的聚集距离是。为了计算每个个体的聚集距离，需要对群体按每个子目标函数值进行排序，在本算法中，若群体规模为，最极端情况下，对个子目标分别进行排序的时间复杂度为。从图中可以看出值较小时，该个体周围就比较拥挤，那么这几个个体的适应度就要降低，使得分布比较分散的解能保留下的几率加大。拥挤度比较算子：为了维持种群的多样性，需要一个比较拥挤度的算子以确保算法

54、能够收敛到一个均匀分布的pareto面上。由于经过了排序和拥挤度计算，群体中每个个体都得到了两个属性：非支配序和拥挤度，则定义偏序关系（）：当满足条件，或满足且时，定义。即如果两个个体的非支配排序不同，取排序号较小的个体；如果两个个体在同一级，取周围较不拥挤的个体。(3)引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。nsga-算法的主流程：首先随即初始化一个父代种群，并将所有个体按非支配关系排序，且指定一个适应度值。然后采用选择、交叉、变异算子

55、产生下一代种群，大小也为，完成第一代进化。在产生新种群后，将与其父代种群合并组成，此时种群大小为。然后进行非支配排序，产生一系列非支配集并计算拥挤度，通常选择前个个体组成，满足且。在上图中，由于子代和父代个体都包含在中，则经过非支配排序以后的非支配集中包含的个体是中最好的，所以先将放入新的父代种群中。如果的大小小于，则继续向中填充，直到添加到时种群大小超出，对中的个体进行拥挤度排序，取前个个体。使个体数量达到。然后通过遗传算子产生新的子代种群。当排序产生的非支配集的个体数目足够填充时，就不必再继续对剩下的部分排序了。非支配解的多样性由拥挤度比较算子保证，不需要额外的共享参数。算法流程图：图3-

56、1 nsga-的算法流程3.1.2mogls在mogls中，局部搜索过程应用于通过遗传操作所获得每一个解。这种算法应用在适应度评价功能上应用一种计算权值和的方式，即当一对父代种群被选择通过交叉变异去获得新解时使用这个功能。局部搜索过程应用于新解而最大限度地发挥它的适应度的效率24。这个算法的一大典型特性是无论何时选择一组父代种群都要指定权值效率。每个解通过不同的权值矢量执行。另一个特点是在局部搜索的过程中不需要计算当前种群的所有邻域解，只有少部分邻域解被检验避免在这个算法中消耗过多的所有可行解的计算时间。多目标遗传局部搜索算法试图寻找多目标最有问题所有的非支配解，如果在一个多目标问题中一个解不被其他解支配，它叫做非劣解，一个多目标问题有许多非劣解。杂交算法的目的不是确定一个单一的最终解，而是试图寻找这个多目标问题所有符合约束条件的最优解。当我们应用ga算法解决多目标问题时，需要评价每个解的适应度，我们通过计算个目标权值和的方式定义一个解的适