NSGAII的改进算法研究.docx
- 文档编号:15756531
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:81
- 大小:1.02MB
NSGAII的改进算法研究.docx
《NSGAII的改进算法研究.docx》由会员分享,可在线阅读,更多相关《NSGAII的改进算法研究.docx(81页珍藏版)》请在冰点文库上搜索。
NSGAII的改进算法研究
本科毕业设计(论文)
NSGA—II的改进算法研究
2013年6月
号
0912********
学生姓拿
专业班级
过控09-2
题目
题目名称
NSGA-II的改进算法研究
题目性质
1•理工类:
工程设计():
工程技术实验研究型():
理论研究型(7):
计算机软件型():
综合型()。
2•文管类():
3•外语类():
4•艺术类()o
题目类型
1•毕业设计(V)2•论文()
题目来源
科研课题()生产实际()自选题目(7)
主要内容
1学习多目标优化求解算法:
2掌握NSGA-II算法的原理,对其缺陷进行改进;3利用遗传算法完成多目标优化求解。
基本要求
1.按电气工程学院本科生学位论文撰写规范的要求完成设汁说明书一份。
2.说明书及插图一律打印,要求条理淸晰、文笔流畅、图形及文字符号符合国家现行标准。
3・査阅文献,翻译与课题有关的外文资料。
一参考资料
1.史峰,王辉,胡斐,等.MATLAB智能算法30个案例分析(第1版)•北京航空航天大学岀版社7011.7
2.王宇平•进化计算的理论和方法•科学出版社.2011,4
周次
1—4周
5—8周
9—11周
12—15周
16—17周
应完成的内容
査阅并消化理解资料
完成主要内容项目1
完成主要内容项目2、3
完成主要内容项目4
整理论文思路和仿真结果,总结结论并撰写论文,准备答辩:
指导教师:
职称:
2012年12月6日
系级教学单位审批:
年月日
学院:
电气工程学院
系级教学单位:
自动化系
摘要
摘要
在实际工程中领域中,不可避免地存在着与材料性质、儿何特性、边界条件、测量偏差等有关的误差或不确定性,这些误差或不确定性使得口标函数或者约束函数也具有不确定性,所以传统的优化方法已经不能适用。
为此,本文将针对多H标区间数优化展开系统的研究,力求通过改进多U标确定数优化问题来解决多目标区间数优化问题。
首先,对于区间数多目标优化问题,本文给出了一种利用区间数学来把不确定多LI标优化转化为确定性多LI标优化的数学模型。
具体来讲就是利用区间疗;关系,将不确定的□标函数转化成为确定性的□标函数;利用区间可能度将不确定的约束函数转化成为确定性的约束函数:
最后,利用线性加权法和罚函数分别处理LI标函数和约束函数,将带约束的不确定多LI标优化问题转化成为无约束的确定性多目标优化问题。
其次,在多目标确定数优化问题中,不可能存在一个使每个目标都达到最优的解,所以多LI标优化问题的解往往是一个非劣解的集合——Pareto解集。
在存在多个Pateto解集的情况下,如果没有更多的说明,很难决定哪个解更重要,因此,找到尽可能多的Pateto最优解至关重要。
本文采用的带精英策略的快速非支配排序遗传算法(NSGS-II)是一种多LI标遗传算法,该算法求得的Pareto最优解分布均匀,收敛性和鲁棒性好,对多LI标优化问题具有良好的优化效果。
最后,本论文给出利用MATLAB仿真程序求解区间数多目标优化问题的最终结果,并利用二个区间数多U标函数来调试程序中的关键参数(如约束可能度水平,多口标权系数,正则化因子等),根据参数在不同取值下的仿真结果,分析并说明参数设置对最后优化结果的影响。
关键词多LI标区间数优化:
NSGA-II;Pareto解集;区间序关系;区间可能度
燕山大学本科生毕业设汁(论文)
Abstract
Intheactualproject,thereisinevitablymaterialproperties,geometry,boundaryconditions,initialconditions,measurementerrorandotherrelatederrorsoruncertainty,theseerrorsoruncertaintiesontheobjectiveorconstraintsfunctionalsohasuncertainty.Therefore,theconventionaloptimizationmethodshavenotapplyforthat.Thisarticlewillfocusonmulti-objectiveintervalnumberoptimizationandcarryoutasystematicstudy,andsolvemulti-objectiveintervalnumberoptimizationproblembyimprovingmulti-objectiveexactnumberoptimizationproblem.
Firstly,intermsofmulti-objectiveintervalnumberoptimizationproblem,thispaperpresentsamathematicalmodelwheretakeadvantageofintervalmathematicstotransferuncertainmulti-objectiveoptimizationintocertainmulti-objectiveoptimization.Specifically,transfertheuncertainobjectivefunctionintothecertainobjectivefunctionbyusingintervalorderrelation,andtransfertheuncertainconstraintfunctionsintocertainconstraintfunctionsbyusingintei-valpossibledegree.Attheendofthemethod,takingadvantageofthelinearweightingmethodandpenaltyfunctionshandletheobjectiveandconstraintfunctions.Theconstrainedmulti-objectiveoptimizationproblemofuncertaintyaretransformedintounconstrainedmulti-objectiveoptimizationproblemofcertainty.Thus,theconventionaloptimizationmethodcanbeused・
Secondly,inmulti-objectiveexactnumberoptimizationproblem,itisimpossibletomakeeachgoalhasanoptimalsolution,sothesolutionsofmulti-objectiveoptimizationisoftenasetofnon-dominatedsolutions—Paretoset.BecauseofthepresenceofmultipleParetosolutionset,andthereisifnomorefurtherexplanation,itisdifficulttodecidewhichsolutionismoreimportant.Thus,findingthePatetooptimalsolutionasmuchaspossibleiscrucial.AfastElitist
II
Abstract
Non-dominatedSortingGeneticAlgorithm(NSGS-II)inthispaperisamulti-objectivegeneticalgorithm,whichobtaintheParetooptimalwithgooddistribution,convergenceandrobustnessandhasagoodoptimizationresultsformulti-objectiveoptimizationproblem.
Finally,thepaperpresentsthefinalresultofmulti-objectiveintervalnumberoptimizationthroughtheMATLABsimulationprogram.Andusingmulti-objectiveintervalnumberfunctionsdebugthekeyparameters.(suchasconstraintspossibledegreelevel,multi-objectiveweights,regularizationfactor,etc.)・Accordingtothedifferentvaluesabouttheparametersinthesimulationresults,analyzeandexplainoptimalparametersettingsthathowtoimpcetonthefinalresults.
Keywordsmulti-objectiveintervalnumberoptimization,NSGA-II,Paretoset,intervalorderrelation,intervalpossibledegree
III
燕山大学本科生毕业设汁(论文)
IV
摘要I
AbstractII
第1章绪论1
1」多目标区间数优化研究的目的和意义1
1.2多日标区间数优化国内外研究现状及分析2
1.3多目标区间数优化发展趋势和存在问题3
1.4本文的研究目标和主要研究内容3
第2章多目标区间数优化的数学转换模型5
2」多目标优化的基本概念5
2.1.1多目标优化的数学描述5
2.1.2多目标优化的目标占优和Pareto占优7
2.1.3多目标优化问题的解7
2.2区间数介绍8
2.3不确定性区间结构分析10
2.4区间可能度和不确定约束的转换10
2.4.1改进的区间可能度方法11
2.4.2基于区间可能度的不确定约束的转换16
2.5区间序关系转换模型17
2.5.1区间序关系17
2.5.2不确定目标函数的转换19
2.5.3转换后的确定性优化问题20
2.6本章小结21
第3章NSGA-II算法22
3.1NSGA-II算法的简介22
3.2快速非支配排序法23
3.3拥挤度25
3.4精英策略26
3.5NSGA-II算法的拥挤度距离公式改进27
3.6NSGA-II算法流程30
3.7本章小结30
第4章仿真结果和相关参数分析32
4」测试函数和仿真结果32
4.2相关参数的分析33
4.2.1约束可能度水平入的影响33
4.2.2多目标权系数卩的选取34
4.2.3正则化因子①和屮的选取35
4.2.4交叉.参数mu与变异参数mum的影响36
4.3本章小结37
结论39
参考文献40
致谢42
附录143
附录251
附录356
附录463
附录570
VI
第1章绪论
第1章绪论
1.1多目标区间数优化研究的目的和意义
优化是一种用于在多种决策当中选出最好决策的方法,它被广泛地应用在工业、农业、交通、国防等许多领域,对于合理利用资源、提高系统性能、降低能源消耗以及经济效益的增长均有非常显著的作用⑷。
一般来说,对实际工程领域中问题的分析和优化设计通常基于确定性的系统参数和优化模型,并且借助传统的确定性优化方法匕:
来进行求解。
然而,在大多数实际工程中,不可避免地存在着与材料性质、温度变化、工程边界、噪音影响、测量偏差等有关的误差或不确定性,这些误差或不确定性虽然在大多数情况下都比较小,但耦合在一起可能使整个工程系统产生较大的误差或偏差。
在实际的工程系统中,山于系统经常工作在不同环境下,使得系统的参数也经常发生变化,不能维持在一个恒定的值上;参数在一定的区域内变化,使得参数无法精确测定等。
事实上,在绝大多数实际工程中,都或多或少地存在着一些不确定因素,只是山于对这些工程系统从数学角度上处理困难,所以在很多情况下不得不做出简化,将多日标转化为单口标以及将不确定性转化为确定性⑸。
从辩证法的角度来看,确定性是相对的,而不确定性却是绝对的。
对于不确定性系统的优化问题,经典的优化理论和方法无法完成,必须通过不确定性优化(uncertainoptimization)jlt行建模和求解,在求解的过程中必须充分考虑参数的不确定性对系统的影响,并对不确定变量解耦后建立新的优化模型。
不确定优化理论是传统的确定性优化理论的发展与延伸,利用不确定性优化方法进行优化设计时,无需做出很多假设和简化,可以建立更为真实客观的优化模型,从而获得更可靠、更贴近实际的设计方案。
不确定性优化理论的发展和应用,给社会带来了巨大的效益。
以实际工业生产为例,企业可以借助不确定性优化技术来提高产品安全性和可靠性,以满足生产安全规范,减少对环境破坏以及不必要的能耗,从而能够更好地适应复杂多变的市场,为企业创造出更为可观的经济、社会效益。
为此,不确定性优化理论方法的研究具有非常重要的现实意义。
燕山大学本科生毕业设计(论文)
1.2多目标区间数优化国内外研究现状及分析
山于不确定性问题的普遍存在,并且表现形式多种多样,如随机性、模糊性等,经典的优化理论和方法对于这些不确定性的优化问题已不再适用,处理起来往往会遇到很大的困难和不便。
为此,用以专门处理不确定性优化问题的理论应运而生。
这些理论的产生,为解决实际工程中不确定性优化问题的研究提供了理论基础。
目前,人们研究的多目标优化问题大部分针对确定性问题,而在实际的工程领域中往往存在材料、测量、载荷等多方面的不确定性。
对于不确定优化问题的处理,总体来说,其主要思路是一般是先通过数学转换模型将不确定性优化问题转换为确定性优化问题,继而利用传统的确定性多LI标优化方法进行求解。
对于不确定性优化问题的研究,具体来说,LI询国内外主要有三种方法来处理多U标区间数优化:
即随机规划方法、模糊规划方法和区间数优化方法。
随机规划方法⑷和模糊规划方法⑻是两类比较传统的不确定性优化方法。
在这两种方法中,分别是基于概率统讣理论畫和模糊统讣理论用来进行转换的。
其中,采用随机规划方法的不确定优化问题,其不确定参数是随机变量,并且需要知道该随机变量满足的分布。
许多专家学者对这种方法进行了深入的探讨和研究。
如在1984年,Stancu-Minasian在他编著的《随机多口标规划》一书中,对随机规划的方法进行了详细深入的说明,给出了一些随机多LI标规划问题的求解方法。
Teghem等人提出了一种线性随机多U标规划(MOSLP)的求解方法,这种方法被人们称为Strange方法,其特点是将随机多L1标规划问题转化为确定性多LI标规划的问题,然后再采用交互规划法来求得原问题的解;对于采用模糊规划方法的不确定优化问题,其不确定参数为模糊数,并且事先需要知道该模糊数的隶属函数。
这种方法把模糊概念与多LI标优化问题进行有机结合,来描述决策者对解的满意程度,进而求出最终的解。
如Amelia和Marinao提出的GeneralProcedure方法,这种方法针对一个已经完全达到要求的LI标,并且此时的模糊有效解有可能不是最优非劣解的情况,通过此方法仍然能够找到模糊有效的最优非劣解集。
但是,在实际工程系统中,以上这两种方法都需要大量的信息来构造随机变量的分布或模糊隶属度函数,这对于实际的优化问题来说有一定的困
第1章绪论
难。
第三种方法叫做区间数优化方法,在区间数优化中,往往是基于区间序关系園或者最大最小后悔准则叫而本文主要研究的不确定多LI标优化问题,主要是基于区间序关系将参数不确定的LI标函数转化为参数确定的LI标函数;通过区间可能度的方法,将参数不确定的不等式约束转换为参数确定的不等式约束。
最后利用罚函数法叫将具有约束的多口标函数转化为参数确定的无约束多LI标罚函数。
每个U标函数的罚函数表示是山该口标函数的中值和半宽以及约束函数的罚函数组成的,最终得到的是基于区间不确定参数的Pareto解集。
1.3多目标区间数优化发展趋势和存在问题
近五十多年来,不确定性优化的理论和方法已经得到广泛的研究,并吸引越来越的关注,U前已被应用于诸多实际工程领域,如:
生产过程、存储系统、网络优化、车辆调度、系统可靠性、设备选址、结构优化等。
这些课题的研究和发展,一方面反映了不确定性优化在实际应用中的作用,对实际工程的优化确实行之有效。
另一方面也给出了许多不确定性优化的研究背景和应用前景,并为其后续的研究和发展提供不竭的动力和源泉。
但是,就口前看来多目标区间数优化所研究的问题缺乏一般性,在为数不多的关于非线性区间数优化问题的研究中,还没有总结出针对一般非线性区间数优化问题的数学转换模型,这一定程度上阻碍了区间数优化的研究进展。
1.4本文的研究目标和主要研究内容
综上所述,在H前的区间数优化研究方面,特别是在非线性区间数优化的研究方面,还存在着一些难点和技术问题。
为此,本文将针对其中的一些问题展开深入的研究。
本文的整个研究内容和研究思路将按三个方面展开:
首先,从区间序规划的理论层面上找出一种能处理一般非线性区间数优化的数学转换模型;其次,基于数学转换模型,将不确定性优化问题转化为确定性优化问题,继而利用带精英策略的非支配排序遗传算法(NSGA-II),对多LI标优化问题进行优化和求解;最后,本文将利用区间数多LI标函数来测试算法的有效性,以及对算法中的重要算子进行研究,通过对比各个不同
燕山大学本科生毕业设汁(论文)
参数下的最终仿真结果,分析并说明参数的取值对最终优化结果的影响。
第2章多目标区间数优化的数学转换模型
第2章多目标区间数优化的数学转换模型
2.1多目标优化的基本概念
多U标优化是在现实各个领域中都普遍存在的问题,每个L1标不可能都同时达到最优,必须各有权重。
但是,究竟要怎样分配这样的权重,这已经成为人们研究的热点问题。
同时,根据生物进化论发展起来的遗传算法,也得到了人们的关注。
将这两者结合起来,能够利用遗传算法的全局搜索能力,避免传统的多LI标优化方法在寻优过程中陷入局部最优解,可以使解个体保持多样性。
所以,基于遗传算法的多LI标寻优策略已经被应用于各个领域中。
2.1.1多目标优化的数学描述
—般来讲,多LI标优化问题是山多个LI标函数与有关的一些等式以及不
等式约束组成,从数学角度可以做如下描述叫
min
£(“宀,…宀)
min
max
力+1(“,厂,…,心)(21)
max
s.t.
九(州,勺,…,兀)^(.(x)>O,z=1,2,hj(x)=0J=1,2,…,g
式中,函数/应),(山1,2,-,加)称为目标函数;g,⑴和何(x)称为约束函数;X=(X“2,…,xj是"维的设计变量。
X=品eR”,幻⑴20,叫(x)=O,i=1,2,…,p,j=1,2,…,q}称为(2-1)的可行域。
在这个多口标优化问题中有>2)个目标函数(r个极小化口标函数,加-厂个极大化目标函数)和p+q(p,q>0)个约束函数(其中有"个不等式约束和q个等式约束)。
如果上述多口标优化问题式(2-1)的LI标函数全部是极小化标函数,约束函数全都是不等式约束,则可以得到一个标准多U标优化模型:
燕山大学本科生毕业设计(论文)
minF(a)=[/,(Qf2(Q…,九(x)f(2-2)
sJ.g1(A)<0,z=l,2,-,/?
设计•变量兀=(“,2,…,兀A是一组确定的向量,对应”维欧氏设计变量空间R”上的一点,而相应的目标函数/(X)则对应一个加维的欧氏目标函数空间尺”的一点。
也就是说,口标函数/(X)对应的是由n维设计变量空间R"到m维目标函数空间R”的一个映射叫
f:
RJR”'
由此可知,设计变量、目标函数以及约束函数是构成多忖标优化问题的三要素。
设计变量册山2「"”是在实际工程设计中可以人为指定控制的,并且能对工程系统的属性、性能产生影响的一组向量,不同取值的设计变量便意味着对应不同的工程系统设计方案,一组设计变量通常可以用向量X=(坷…,兀)丁表示,并把它称之为优化问题的一个解。
H标函数可以看作是评价设计系统性能指标的数学表达式,在实际工程设计中,设讣者(决策者)希望能同时使这些性能指标达到最优化。
所有的U标函数J\(以f2(Q…J,”(X)构成了多口标优化问题(2-2)的U标函数向量吩)。
约束给出了设计变量需要满足的限制条件,用含有等式和不等式的约束函数来表示。
满足所有约束函数(约束条件)的一组设计变量可以称之为一个可行解,优化问题中所有的可行解构成了整个优化问题的可行域。
根据目标函数、约束函数以及设计变量的特点,多目标优化问题可以分成以下儿种类型叫
如果在多tl标优化问题中,所有的LI标函数和约束函数都是线性的,则称此类优化问题为线性多口标优化问题;如果至少有一个U标函数或约束函数是非线性的,则称此类优化问题为非线性多LI标优化问题;如果系统模型中设讣变量是连续的,则此类优化问题是连续多U标优化问题;反之,就称之为离散问题。
由于在实际工程应用中,我们遇到的问题大多都是非线性的。
然而,非线性优化问题的解决难度要远远大于线性优化问题。
另外,在大多数的工程
第2章多目标区间数优化的数学转换模型
设计问题中,设计变量通常是连续的,所以多LI标优化主要的研究方向就是怎样解决连续非线性多目标的优化问题。
2.1.2多目标优化的目标占优和Pareto占优
在多LI标优化算法的搜索中,普遍使用了占优(dominate)的概念。
在这里将给出占优的概念以及相关术语的定义他。
定义2.1(向量序)设人=[。
1,。
2,…,。
』'〃=[勺'“2,…,勺J是加维欧氏空间中的两个向量。
1)若q=处=1,2,…,〃?
),则称向量A等于向量B,记作A二B。
2)若①<吐=1,2,■•-,/»),则称向量A小于等于向量B,记作A竺。
3)若©5加=1,2,…,加),并且至少有一个是严格不等式,则称向量A小于向量B,即向量A优于向量B,记作A 4)若q=1,2,…,加),则称向量A严格小于向量B,记作AvB。 定义2・2(绝对最优解、非劣解)S为多目标优化的可行域,/(X)为 多目标优化的向量目标函数。 若/(x”kf(x),vxwS,则称x-是多目标优化的绝对最优解
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NSGAII 改进 算法 研究