搜索
2012/6/261Iih培训教程（10）多目标优化Isight培训教程（10）多目标优化北京树优信息技术有限公司多目标优化算法发展•思路1：归一化方法，将多目标转为单目标：缺点：主观性，无法得到完整的权衡解•思路2：求解Pareto解集方法：–1985年,VEGA (Vector Evaluated Genetic Algorithm)•由J.D.Schaffer开发了第一个多目标遗传算法VEGA ，它基于对单目标优化算法的简单扩展。–1993年，MOGA （Multi –Objective Genetic Algorithm）•由C.M.Fonsecaand P.J. Fleming 开发了基于Pareto Optimality优化条件的多目标遗传算法(MOGA)–1994年，NSGA (Non-dominated Sorting Genetic Algorithm)•由N. Srinivasand K. Deb 开发NSGA ，改进了早期MOGA 算法在某些问题上收敛性–1999年，SPEA (Strength Pareto Evolutionarily Algorithm) •由E.Zitzlerand L.Thiele把单目标遗传算法中的精英性（Elitism）引入到多目标遗传算法中，开发了SPEA–2001年，SPEA 2 改进型•由Zitzler对SPEA进行了改进北京树优信息技术有限公司–2001年，NCGA •基于SPEA 2 方法，并在杂交算子和选择方法上做了改进–2001年，NSGA II •由K. Deb and S. Agrawal在在NSGA算法上改进得到NSGA II，并借鉴了SPEA 2方法，效果于SPEA 2类似–2005年，HMGE (Hybrid Multi-Gradient Explorer)混合多目标梯度优化算法•由Dr. Vladimir Sevastyanov开发，基于多目标梯度方法和动态响应面技术，结合了遗传算法的全局性，同时又保留了梯度算法的有效性，通常10~20次迭代即可获得一个Pareto解，且能处理大规模变量问题。2012/6/262多目标优化问题举例实际问题目标要求发动机设计油耗低总重量轻刚度高寿命长发动机设计油耗低、总重量轻，刚度高、寿命长。股票投资决策最小化投资和风险，最大化投资回报。生产计划在满足获得最大利润的前提下，满足加班时间最小，产品产量最大。飞行器设计最大化燃油效率和有效载荷，最小化总重量。北京树优信息技术有限公司轿车天窗设计最小化驾驶员处噪音，最大化通气量。多目标优化问题的数学表达北京树优信息技术有限公司多目标优化解•解决多目标优化问题的最终目的只能是在各个目标之间进行协调权衡和折衷处理使各子目标均尽可能达到最优行协调权衡和折衷处理，使各子目标均尽可能达到最优。因此需要重新定义有关多目标优化最优解的相关概念北京树优信息技术有限公司“Pareto解”的概念•完全最优解()()X∀∈*≦xfxfx•Pareto最优解()()X∃∈*xfxfx解的任何一个目标函数的值在不使北京树优信息技术有限公司Δ2f−Δ解的任何个目标函数的值在不使其他目标函数值恶化的条件下已不可能进一步改进2012/6/264Pareto解•Pareto解：也叫非劣解，非支配解。•在多目标优化问题中，我们所要找的并不是所有子目标的最优解，而是所谓的Pareto解。解•由于目标函数间的矛盾性质，一般说来使每个目标函数同时达到各自最优值的解是不存在的。多目标最优问题的解为Pareto最优解的条件是解的任何一个目标函数的值在不使其他目标函数值恶化的条件下已不可能进一步改进。•很显然的，Pareto最优解不止一个，事实上在一般多目标优化问题中，Pareto最优解常是连续的而且有无限多个，这就构成了Pareto前沿的概念。•多目标优化问题的最终解是从所有pareto最优解中挑一个最优折衷解。北京树优信息技术有限公司解•二目标优化问题，图显示了Pareto最优解集与Pareto前沿：•Minimize:f1（x）=x2-2xMiiif2（）•Minimize:f2（x）=-x•Subjectto:0=x=2北京树优信息技术有限公司多目标优化算法•主要算法线性加权法归化–线性加权法——归一化–多目标遗传算法——NCGA–多目标遗传算法——NSGAII北京树优信息技术有限公司归一化方法计算机制：确定方向•根据权重进行归一化的意思就是在目标空间里，导入根据权重决定的一个方向。的情况表示如下：iw()12,,,pfffK()12,,...,p=w2p=的情况表示如下：scalar化（权重法）1()()()01,2,..()01,2,...piiiwjkMinimizewfSSubjecttogjhk=⎧⎪⎪⎪=⎨⎪⎪==⎪⎩∑≦xxx北京树优信息技术有限公司左图为的情况，箭头是这个权重的导入方向。在箭头的垂直方向上画有若干细的实线，这些细实线上的值是一定的。也就是说细实线是被归一化了的目标函数的等值面（线）()0.5,0.5=w1122wfwf+2012/6/266归一化方法计算机制：Pareto解的计算（续）•进一步思考的话，我们可以得知，如果变化根据导入的等值面（线）的倾斜度，就可以在图中Pareto前沿上显示出全部的Pareto解。这与变化权重相对应wiw对应。北京树优信息技术有限公司多目标遗传算法（MOGA）•多目标遗传算法（Multi-ObjectiveGeneticAlgorithm，以下记为MOGA），不需要归一化可以直接处理多目标最优化问题。北京树优信息技术有限公司多目标遗传算法（MOGA）北京树优信息技术有限公司图10-8根据解的优劣关系施压进化图10-9最大限度覆盖Pareto前沿NSGA-II方法•NSGA-II，作为1994年发布的NSGA(Non-DominatedSortingGeneticAlgorithm)的改良版，由K.Deb，S.Agrawal等在2000年提出。•非劣个体通常都被存档•父代探索种群是从archive中根据拥挤度进行淘汰选择•交叉、变异运算北京树优信息技术有限公司•非支配排序•拥挤距离排序•新的非劣个体存档•生成新的父代探索种群2012/6/268NCGA算法•NCGA方法是由最早的GA（GeneticAlgorithm）算法发展而来，它视各目标同等重要通过排序后分组进行交叉的方法实现“相邻繁殖”的各目标同等重要，通过排序后分组进行交叉的方法实现相邻繁殖的机制，从而使接近于Pareto前沿的解进行交叉繁殖的概率增大，加速了计算收敛过程。北京树优信息技术有限公司混合多目标梯度优化算法zHMGE新一代的多目标优化算法:z探索过程中80%到95%的点都是Pareto解每生成个Pareto解大约需要进行35次模型评估z每生成一个Pareto解大约需要进行3-5次模型评估z能处理大规模的优化问题（设计变量超过5000个)，维数无关z全局Pareto求解能力（不连通、凹问题）z当优化问题的规模很小的时候：运算次数大约比GA算法少2-5倍，但会生成更多数量的Pareto解z当优化设计变量个数40，运算次数大约比GA算法少10-35倍；z当优化问题规模较大的时候：运算次数大约比GA算法少50-200倍；北京树优信息技术有限公司算法特点•传统优化算法（NSGA,NCGA,AMGA）的问题：–计算效率低–精度低–用户可控性差HMGE特点TypicalGeneticAlgorithm北京树优信息技术有限公司•HMGE特点–计算效率高–精度高–全局求解能力–用户交互自定义求解路径MGPHMGE(HybridMulti-GradientExplorer)Algorithms•HybridMulti-GradientEl(HMGE)lihfGenetic Explorer(HMGE)algorithmofglobalmulti-objective:–EfficiencyinfindingtheglobalParetofrontier–Highconvergencetypicalforgradient-basedmethodsAlgorithm FrameworkRandom MutationGradient Mutation北京树优信息技术有限公司–Scalability:Equalefficiencyoptimizingmodelswithdozens,hundreds,andeventhousandsofdesignvariablesDynamically Dimensioned Response SurfaceDDRSM–Superfast Gradient Estimationthe first Response Surface Method that is not limited by the dimension of optimization task. 2012/6/2610PointX0isaninput多目标优化梯度探索：寻找多个优化目标同时改进的方向MGE:Multi-GradientExplorationx2x1G1X0A1B1newgradient-basedtechniquewhichdeterminesadirectionofsimultaneousimprovementforallobjectivefunctionsForcriteriaj=1,...,mGjonthepointX0Xg},...,{1jnjjxgxgXg=TheintersectionpointofGjandunitcircumference:⎭⎬⎫⎩⎨⎧∂∂−∂∂−=njjjxFxFG,...,1pparameterG1L1x1x2L2X0G2A2B2北京树优信息技术有限公司*CreaterayR*MediumpointG*:{}nggG,...,*1=2)(min)(max,..1,..1jimjjimjixgxgg==+=TheimprovementdirectionrayR*istheoutputparameter多目标优化梯度方向EvolutionaryPartofHMGEAlgorithm北京树优信息技术有限公司