NSGA—II的改进算法研究本科毕业设计.doc

《NSGA—II的改进算法研究本科毕业设计.doc》由会员分享，可在线阅读，更多相关《NSGA—II的改进算法研究本科毕业设计.doc（87页珍藏版）》请在三一办公上搜索。

1、本科毕业设计（论文）NSGAII的改进算法研究2013年6月 本科毕业设计（论文）NSGAII的改进算法研究学 院： 专 业： 自动化 学生姓名： 学 号： 指导教师： 答辩日期： 2013年6月 学院：电气工程学院 系级教学单位：自动化系 学号091203011076学生姓名专 业班 级过控09-2题目题目名称NSGA-的改进算法研究题目性质1.理工类：工程设计 （ ）；工程技术实验研究型（ ）；理论研究型（ ）；计算机软件型（ ）；综合型（ ）。2.文管类（ ）；3.外语类（ ）；4.艺术类（ ）。题目类型1.毕业设计（ ） 2.论文（ ）题目来源科研课题（ ） 生产实际（ ）自选题目（

2、） 主要内容1 学习多目标优化求解算法；2掌握NSGA-算法的原理，对其缺陷进行改进；3 利用遗传算法完成多目标优化求解。基本要求1 按电气工程学院本科生学位论文撰写规范的要求完成设计说明书一份。2 说明书及插图一律打印，要求条理清晰、文笔流畅、图形及文字符号符合国家现行标准。3查阅文献，翻译与课题有关的外文资料。参考资料1史峰,王辉,胡斐,等.MATLAB智能算法30个案例分析(第1版).北京航空航天大学出版社,2011.72王宇平.进化计算的理论和方法.科学出版社.2011,4周 次14周58周911周1215周1617周应完成的内容查阅并消化理解资料完成主要内容项目1完成主要内容项目2、

3、3完成主要内容项目4整理论文思路和仿真结果，总结结论并撰写论文，准备答辩；指导教师： 职称： 2012年12月6日系级教学单位审批： 年 月 日摘要在实际工程中领域中，不可避免地存在着与材料性质、几何特性、边界条件、测量偏差等有关的误差或不确定性，这些误差或不确定性使得目标函数或者约束函数也具有不确定性，所以传统的优化方法已经不能适用。为此，本文将针对多目标区间数优化展开系统的研究，力求通过改进多目标确定数优化问题来解决多目标区间数优化问题。首先，对于区间数多目标优化问题，本文给出了一种利用区间数学来把不确定多目标优化转化为确定性多目标优化的数学模型。具体来讲就是利用区间序关系，将不确定的目标

4、函数转化成为确定性的目标函数；利用区间可能度将不确定的约束函数转化成为确定性的约束函数；最后，利用线性加权法和罚函数分别处理目标函数和约束函数，将带约束的不确定多目标优化问题转化成为无约束的确定性多目标优化问题。其次，在多目标确定数优化问题中，不可能存在一个使每个目标都达到最优的解，所以多目标优化问题的解往往是一个非劣解的集合Pareto解集。在存在多个Pateto解集的情况下，如果没有更多的说明，很难决定哪个解更重要，因此，找到尽可能多的Pateto最优解至关重要。本文采用的带精英策略的快速非支配排序遗传算法(NSGS-II)是一种多目标遗传算法，该算法求得的Pareto最优解分布均匀，收敛

5、性和鲁棒性好，对多目标优化问题具有良好的优化效果。最后，本论文给出利用MATLAB仿真程序求解区间数多目标优化问题的最终结果，并利用二个区间数多目标函数来调试程序中的关键参数（如约束可能度水平，多目标权系数，正则化因子等），根据参数在不同取值下的仿真结果，分析并说明参数设置对最后优化结果的影响。关键词多目标区间数优化；NSGA-II；Pareto解集；区间序关系；区间可能度AbstractIn the actual project, there is inevitably material properties, geometry, boundary conditions, initial c

6、onditions, measurement error and other related errors or uncertainty, these errors or uncertainties on the objective or constraints function also has uncertainty. Therefore, the conventional optimization methods have not apply for that. This article will focus on multi-objective interval number opti

7、mization and carry out a systematic study, and solve multi-objective interval number optimization problem by improving multi-objective exact number optimization problem.Firstly, in terms of multi-objective interval number optimization problem, this paper presents a mathematical model where take adva

8、ntage of interval mathematics to transfer uncertain multi-objective optimization into certain multi-objective optimization. Specifically, transfer the uncertain objective function into the certain objective function by using interval order relation, and transfer the uncertain constraint functions in

9、to certain constraint functions by using interval possible degree. At the end of the method, taking advantage of the linear weighting method and penalty functions handle the objective and constraint functions. The constrained multi-objective optimization problem of uncertainty are transformed into u

10、nconstrained multi-objective optimization problem of certainty. Thus, the conventional optimization method can be used.Secondly, in multi-objective exact number optimization problem, it is impossible to make each goal has an optimal solution, so the solutions of multi-objective optimization is often

11、 a set of non-dominated solutions- Pareto set. Because of the presence of multiple Pareto solution set, and there is if no more further explanation, it is difficult to decide which solution is more important. Thus, finding the Pateto optimal solution as much as possible is crucial. A fast Elitist No

12、n-dominated Sorting Genetic Algorithm (NSGS-II) in this paper is a multi-objective genetic algorithm, which obtain the Pareto optimal with good distribution, convergence and robustness and has a good optimization results for multi-objective optimization problem.Finally, the paper presents the final

13、result of multi-objective interval number optimization through the MATLAB simulation program. And using multi-objective interval number functions debug the key parameters.(such as constraints possible degree level, multi-objective weights, regularization factor, etc.) .According to the different val

14、ues about the parameters in the simulation results, analyze and explain optimal parameter settings that how to impcet on the final results.Keywords multi-objective interval number optimization, NSGA-II, Pareto set, interval order relation, interval possible degree目 录摘要IAbstractII第1章 绪论11.1多目标区间数优化研究

15、的目的和意义11.2 多目标区间数优化国内外研究现状及分析21.3 多目标区间数优化发展趋势和存在问题31.4 本文的研究目标和主要研究内容3第2章 多目标区间数优化的数学转换模型52.1 多目标优化的基本概念52.1.1 多目标优化的数学描述52.1.2 多目标优化的目标占优和Pareto占优72.1.3 多目标优化问题的解72.2区间数介绍82.3 不确定性区间结构分析102.4 区间可能度和不确定约束的转换102.4.1 改进的区间可能度方法112.4.2 基于区间可能度的不确定约束的转换162.5 区间序关系转换模型172.5.1 区间序关系172.5.2 不确定目标函数的转换192.

16、5.3 转换后的确定性优化问题202.6 本章小结21第3章 NSGA-II算法223.1 NSGA-II算法的简介223.2 快速非支配排序法233.3 拥挤度253.4精英策略263.5 NSGA-II算法的拥挤度距离公式改进273.6 NSGA-II算法流程303.7 本章小结30第4章 仿真结果和相关参数分析324.1 测试函数和仿真结果324.2 相关参数的分析334.2.1约束可能度水平的影响334.2.2 多目标权系数的选取344.2.3 正则化因子和的选取354.2.4 交叉参数mu与变异参数mum的影响364.3 本章小结37结论39参考文献40致谢42附录143附录251附

17、录356附录463附录570第1章 绪论1.1多目标区间数优化研究的目的和意义优化是一种用于在多种决策当中选出最好决策的方法，它被广泛地应用在工业、农业、交通、国防等许多领域，对于合理利用资源、提高系统性能、降低能源消耗以及经济效益的增长均有非常显著的作用1。一般来说，对实际工程领域中问题的分析和优化设计通常基于确定性的系统参数和优化模型，并且借助传统的确定性优化方法2来进行求解。然而，在大多数实际工程中，不可避免地存在着与材料性质、温度变化、工程边界、噪音影响、测量偏差等有关的误差或不确定性，这些误差或不确定性虽然在大多数情况下都比较小，但耦合在一起可能使整个工程系统产生较大的误差或偏差。在

18、实际的工程系统中，由于系统经常工作在不同环境下，使得系统的参数也经常发生变化，不能维持在一个恒定的值上；参数在一定的区域内变化，使得参数无法精确测定等。事实上，在绝大多数实际工程中，都或多或少地存在着一些不确定因素，只是由于对这些工程系统从数学角度上处理困难，所以在很多情况下不得不做出简化，将多目标转化为单目标以及将不确定性转化为确定性3。从辩证法的角度来看，确定性是相对的，而不确定性却是绝对的。对于不确定性系统的优化问题，经典的优化理论和方法无法完成，必须通过不确定性优化(uncertain optimization)进行建模和求解，在求解的过程中必须充分考虑参数的不确定性对系统的影响，并对

19、不确定变量解耦后建立新的优化模型。不确定优化理论是传统的确定性优化理论的发展与延伸，利用不确定性优化方法进行优化设计时，无需做出很多假设和简化，可以建立更为真实客观的优化模型，从而获得更可靠、更贴近实际的设计方案。不确定性优化理论的发展和应用，给社会带来了巨大的效益。以实际工业生产为例，企业可以借助不确定性优化技术来提高产品安全性和可靠性，以满足生产安全规范，减少对环境破坏以及不必要的能耗，从而能够更好地适应复杂多变的市场，为企业创造出更为可观的经济、社会效益。为此，不确定性优化理论方法的研究具有非常重要的现实意义。1.2 多目标区间数优化国内外研究现状及分析由于不确定性问题的普遍存在，并且表

20、现形式多种多样，如随机性、模糊性等，经典的优化理论和方法对于这些不确定性的优化问题已不再适用，处理起来往往会遇到很大的困难和不便。为此，用以专门处理不确定性优化问题的理论应运而生。这些理论的产生，为解决实际工程中不确定性优化问题的研究提供了理论基础。目前，人们研究的多目标优化问题大部分针对确定性问题，而在实际的工程领域中往往存在材料、测量、载荷等多方面的不确定性。对于不确定优化问题的处理，总体来说，其主要思路是一般是先通过数学转换模型将不确定性优化问题转换为确定性优化问题，继而利用传统的确定性多目标优化方法进行求解。对于不确定性优化问题的研究，具体来说，目前国内外主要有三种方法来处理多目标区间

21、数优化：即随机规划方法、模糊规划方法和区间数优化方法。随机规划方法4和模糊规划方法5是两类比较传统的不确定性优化方法。在这两种方法中，分别是基于概率统计理论4和模糊统计理论5来进行转换的。其中，采用随机规划方法的不确定优化问题，其不确定参数是随机变量，并且需要知道该随机变量满足的分布。许多专家学者对这种方法进行了深入的探讨和研究。如在1984年，Stancu-Minasian在他编著的随机多目标规划一书中，对随机规划的方法进行了详细深入的说明，给出了一些随机多目标规划问题的求解方法。Teghem等人提出了一种线性随机多目标规划(MOSLP)的求解方法，这种方法被人们称为Strange方法，其特

22、点是将随机多目标规划问题转化为确定性多目标规划的问题，然后再采用交互规划法来求得原问题的解；对于采用模糊规划方法的不确定优化问题，其不确定参数为模糊数，并且事先需要知道该模糊数的隶属函数。这种方法把模糊概念与多目标优化问题进行有机结合，来描述决策者对解的满意程度，进而求出最终的解。如Amelia和Marinao提出的General Procedure方法，这种方法针对一个已经完全达到要求的目标，并且此时的模糊有效解有可能不是最优非劣解的情况，通过此方法仍然能够找到模糊有效的最优非劣解集。但是，在实际工程系统中，以上这两种方法都需要大量的信息来构造随机变量的分布或模糊隶属度函数，这对于实际的优化

23、问题来说有一定的困难。第三种方法叫做区间数优化方法，在区间数优化中，往往是基于区间序关系6或者最大最小后悔准则7。而本文主要研究的不确定多目标优化问题，主要是基于区间序关系将参数不确定的目标函数转化为参数确定的目标函数；通过区间可能度的方法，将参数不确定的不等式约束转换为参数确定的不等式约束。最后利用罚函数法3，将具有约束的多目标函数转化为参数确定的无约束多目标罚函数。每个目标函数的罚函数表示是由该目标函数的中值和半宽以及约束函数的罚函数组成的，最终得到的是基于区间不确定参数的Pareto解集。1.3 多目标区间数优化发展趋势和存在问题近五十多年来，不确定性优化的理论和方法已经得到广泛的研究，

24、并吸引越来越的关注，目前已被应用于诸多实际工程领域，如：生产过程、存储系统、网络优化、车辆调度、系统可靠性、设备选址、结构优化等。这些课题的研究和发展，一方面反映了不确定性优化在实际应用中的作用，对实际工程的优化确实行之有效。另一方面也给出了许多不确定性优化的研究背景和应用前景，并为其后续的研究和发展提供不竭的动力和源泉。但是，就目前看来多目标区间数优化所研究的问题缺乏一般性，在为数不多的关于非线性区间数优化问题的研究中，还没有总结出针对一般非线性区间数优化问题的数学转换模型，这一定程度上阻碍了区间数优化的研究进展。1.4 本文的研究目标和主要研究内容综上所述，在目前的区间数优化研究方面，特别

25、是在非线性区间数优化的研究方面，还存在着一些难点和技术问题。为此，本文将针对其中的一些问题展开深入的研究。本文的整个研究内容和研究思路将按三个方面展开：首先，从区间序规划的理论层面上找出一种能处理一般非线性区间数优化的数学转换模型；其次，基于数学转换模型，将不确定性优化问题转化为确定性优化问题，继而利用带精英策略的非支配排序遗传算法(NSGA-II)，对多目标优化问题进行优化和求解；最后，本文将利用区间数多目标函数来测试算法的有效性，以及对算法中的重要算子进行研究，通过对比各个不同参数下的最终仿真结果，分析并说明参数的取值对最终优化结果的影响。第2章 多目标区间数优化的数学转换模型2.1 多目

26、标优化的基本概念多目标优化是在现实各个领域中都普遍存在的问题，每个目标不可能都同时达到最优，必须各有权重。但是，究竟要怎样分配这样的权重，这已经成为人们研究的热点问题。同时，根据生物进化论发展起来的遗传算法，也得到了人们的关注。将这两者结合起来，能够利用遗传算法的全局搜索能力，避免传统的多目标优化方法在寻优过程中陷入局部最优解，可以使解个体保持多样性。所以，基于遗传算法的多目标寻优策略已经被应用于各个领域中。2.1.1 多目标优化的数学描述一般来讲，多目标优化问题是由多个目标函数与有关的一些等式以及不等式约束组成，从数学角度可以做如下描述8： （2-1）式中，函数称为目标函数；和称为约束函数；

27、是维的设计变量。称为(2-1)的可行域。在这个多目标优化问题中有个目标函数(个极小化目标函数，个极大化目标函数)和个约束函数(其中有个不等式约束和个等式约束)。如果上述多目标优化问题式(2-1)的目标函数全部是极小化目标函数，约束函数全都是不等式约束，则可以得到一个标准多目标优化模型： （2-2）设计变量是一组确定的向量，对应维欧氏设计变量空间上的一点，而相应的目标函数则对应一个维的欧氏目标函数空间的一点。也就是说，目标函数对应的是由n维设计变量空间到m维目标函数空间的一个映射3：f：由此可知，设计变量、目标函数以及约束函数是构成多目标优化问题的三要素。设计变量是在实际工程设计中可以人为指定控

28、制的，并且能对工程系统的属性、性能产生影响的一组向量，不同取值的设计变量便意味着对应不同的工程系统设计方案，一组设计变量通常可以用向量表示，并把它称之为优化问题的一个解。 目标函数可以看作是评价设计系统性能指标的数学表达式，在实际工程设计中，设计者（决策者）希望能同时使这些性能指标达到最优化。所有的目标函数构成了多目标优化问题(2-2)的目标函数向量。约束给出了设计变量需要满足的限制条件，用含有等式和不等式的约束函数来表示。满足所有约束函数（约束条件）的一组设计变量可以称之为一个可行解，优化问题中所有的可行解构成了整个优化问题的可行域。根据目标函数、约束函数以及设计变量的特点，多目标优化问题可

29、以分成以下几种类型9：如果在多目标优化问题中，所有的目标函数和约束函数都是线性的，则称此类优化问题为线性多目标优化问题；如果至少有一个目标函数或约束函数是非线性的，则称此类优化问题为非线性多目标优化问题；如果系统模型中设计变量是连续的，则此类优化问题是连续多目标优化问题；反之，就称之为离散问题。由于在实际工程应用中，我们遇到的问题大多都是非线性的。然而，非线性优化问题的解决难度要远远大于线性优化问题。另外，在大多数的工程设计问题中，设计变量通常是连续的，所以多目标优化主要的研究方向就是怎样解决连续非线性多目标的优化问题。2.1.2 多目标优化的目标占优和Pareto占优在多目标优化算法的搜索中

30、，普遍使用了占优(dominate)的概念。在这里将给出占优的概念以及相关术语的定义10。定义2.1（向量序） 设是维欧氏空间中的两个向量。1)若，则称向量A等于向量B，记作A=B。2)若，则称向量A小于等于向量B，记作 。3)若，并且至少有一个是严格不等式，则称向量A小于向量B，即向量A优于向量B，记作AB。4)若，则称向量A严格小于向量B，记作Al。此外，和的具体形式是区间还是实数应该根据以上不确定约束的转换过程而定，另外也跟的形式有关。2.5 区间序关系转换模型2.5.1 区间序关系区间序关系用于定性地判断一区间是否优于或者劣于另一区间，通常在区间数优化问题中用于处理带有不确定参数的目标

31、函数。对于任一的设计变量，由于有不确定参数的存在，使得目标函数可能的取值是一区间而非确定的实数值。由于在区间数优化问题中，需要比较在不同的设计变量下目标函数取值区间的优劣，进而评价相应设计变量的优劣，以寻找到最优的设计变量。对于最大化和最小化的优化问题，同一区间序关系可以具有不同的表述形式，因为在这两种问题中它们的评价指标并不相同，例如在最大化问题中目标函数的函数值大的决策变量为优，而在最小化问题中刚好相反，目标函数的函数值小的决策变量为优。文献16总结了目前常用的几种区间序关系，对于最大化和最小化优化问题它们具有如下形式16：1) 区间序关系：该序关系表达了决策者对区间上、下边界的偏好。，并且仅当， （最大化优化问题），并且仅当， （2-28），并且仅当， （最小化优化问题），并且仅当， （2-29）2）区间序关系：该序关系表达了决策者对区间中点和半径的偏好。，并且仅当， （最大化优化问题），并且仅当， （2-30），并且仅当， （最小化优化问题），并且仅当， （2-31）3）区间序关系：该序关系表