最优化模型与算法课件.ppt

最优化模型与算法,2,内容概要,优化模型简介优化模型分类优化算法及其分类 Matlab优化工具箱现代智能优化算法,3,优化模型简介概念、基本形式,什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化理论就是研究如何在状态空间中寻找到全局最优点。一般的优化具有下面形式：min f(x1,x2,xn)s.t.g(x)0，xD其中x1,x2,xn（即问题的可行域，代表问题参数的选择范围），即minf(X)，其中X（矢量形式）。f(x)是决策问题的数学模型，也是决策问题的目标函数，g(x)0是决策问题的约束条件，X是决策问题的决策变量，D是决策问题的定义域（可行域）。问题归结为求极值。极值点非常多，需要找到全局最小点。注：求问题的最大和最小是同一个问题，算法完全一样。分布模型的参数估计问题是典型的优化问题，最大似然估计模型是典型的优化模型。,4,优化模型分类,1.根据是否存在约束条件 有约束模型，无约束模型 注：有约束问题通常采用转换方法将有约束模型转换为无约束模型再求解。2.根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标规划等 注：最常见的优化模型为非线性规划模型。3.根据决策变量的连续性 连续性优化模型，离散性优化模型（典型的组合优化问题，最短路）注：两类模型在求解方法上有较大不同，本次讲解针对前一种。,5,优化算法及其分类,什么是优化算法？专门用于求解优化模型的方法叫做优化算法，优化算法与优化模型有本质区别。优化算法可分为两大类 1 梯度类算法 牛顿法、二分法、共轭梯度法、梯度下降法、单纯形法等，该类算法也称为局部优化算法，明显缺陷是局部优化。Matlab优化工具箱多用该类算法。2 非梯度类算法（1）遍历搜索法，在组合优化中称为穷举法，计算量大，适用于小规模计算求解。（2）随机搜索法，包括遗传算法、模拟退火算法、群类算法、禁忌搜索法等，又称为现代优化算法，是一类全局最优算法，求解的准确性与时间长度、迭代次数直接相关。,常用的优化功能函数求解线性规划问题的主要函数是linprog。求解二次规划问题的主要函数是quadprog。求解无约束非线性规划问题的主要函数是fminbnd、fminunc和fminsearch。求解约束非线性规划问题的函数是 fmincon。多目标优化问题的MATLAB函数有fgoalattain和fminimax。,MATLAB优化工具箱,优化求解一般步骤,建立目标函数文件,针对具体工程问题建立优化设计的数学模型,不等式约束条件表示成g(X)0的形式,建立调用优化工具函数的M文件或命令文件,建立约束函数文件,运行优化工具函数的M文件或命令文件求解,min f(x1,x2,xn)s.t.g(x)0,无约束非线性规划问题的MATLAB函数,fminbnd,要求目标函数为连续函数,只求解单变量问题,fminunc,可求解单变量和多变量问题,适用于简单优化问题,可求解复杂优化问题,fminsearch,xopt,fopt,exitflag=fminsearch(fun,x0,options),无约束多元函数最小值函数fminsearch调用格式,设置优化选项参数,初始点,目标函数,返回最优设计变量,返回目标函数值,返回算法的终止指示变量值,例 求y=2x13+4x1x23-10 x1x2+x22 的最小值点.解：X=fminsearch(2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2,0,0)结果为:X=1.0016 0.8335或在MATLAB编辑器中建立函数文件.function f=myfun(x)f=2*x(1)3+4*x(1)*x(2)3-10*x(1)*x(2)+x(2)2;保存为myfun.m，在命令窗口键入 X=fminsearch(myfun,0,0)或 X=fminsearch(myfun,0,0)结果为：X=1.0016 0.8335,有约束的多元函数最小值数学模型形式：min f（X）s.t.AXb（线性不等式约束）AeqX=beq（线性等式约束）C(X)0（非线性不等式约束条件）Ceq(X)=0（非线性等式约束）Lb X Ub（边界约束条件）其中：x、b、beq、lb、ub是向量，A、Aeq为矩阵，C(x)、Ceq(x)是返回向量的函数，f(x)为目标函数，f(x)、C(x)、Ceq(x)可以是非线性函数.,函数 fmincon格式 x=fmincon(fun,x0,A,b)x=fmincon(fun,x0,A,b,Aeq,beq)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x,fval=fmincon()x,fval,exitflag=fmincon()x,fval,exitflag,output=fmincon()x,fval,exitflag,output,lambda=fmincon()x,fval,exitflag,output,lambda,grad=fmincon()x,fval,exitflag,output,lambda,grad,hessian=fmincon(),参数说明：fun为目标函数，它可用前面的方法定义；nonlcon的作用是通过接受的向量x来计算非线性不等约束和非线性等式约束分别在x处的估计C和Ceq，通过指定函数名或函数名句柄来使用，如：x=fmincon(myfun,x0,A,b,Aeq,beq,lb,ub,mycon)，先建立非线性约束函数，并保存为mycon.m：function C,Ceq=mycon(x)C=%计算x处的非线性不等约束的函数值.Ceq=%计算x处的非线性等式约束的函数值.lambda是Lagrange乘子，它体现哪一个约束有效.output输出优化信息；grad表示目标函数在x处的梯度；hessian表示目标函数在x处的Hessian值.,控制参数options,控制参数options,【例】,求解约束非线性规划：,解:首先建立一个m文件myfun.mfunction y=myfun(x)y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2);存储为myfun.m,首先将问题转化为matlab要求的格式;即求出fun,A,b,Aeq,Beq,X0,Lb,Ub,然后建立一个 m文件 confun.mfunction c,cep=confun(x)c=;%c为非线性不等式cep=exp(x(1)+x(2)2-3;%cep为非线性等式然后存储为confun.m,最后在命令窗口中输入：A=;b=;Aeq=;beq=;Lb=;Ub=;x,f=fmincon(myfun,1;1,confun),题目中有非线性约束条件，所以建立非线性约束m-文件。,x=0.8852 0.7592f=6.2043e-016,优化过程演示,为了进一步了解优化模型的求解算法，给出具体实例的优化过程演示。例：以共轭梯度优化算法优化某函数进行演示,并说明计算时间复杂度。,18,现代优化算法 遗传算法 模拟退火算法 禁忌搜索算法 蚁群算法 粒子群算法 差分进化算法,特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；都属于随机搜索算法，具有全局优化能力；具有普适性，可解决实际应用问题。,注：群类算法还有鱼群算法、蜂群算法、鸟群算法等。,现代优化算法,20,现代优化算法,全局性优化理论的一般性描述两种搜索方式：单点法和多点法。单点法是一种串行方式，即从一个初始状态（单个个体）出发，按照某种方式转移状态进行全局优化，这种方式通常要消耗较多机时；多点法是一种并行方式，即从可行域的多个初始状态（多个个体）同时进行搜索寻找全局最优解，但是空间开销大。根据各态历经假设，理论上二者可以具有相同的搜索效果。事实上，单CPU情况下的单点法和多点法并没有本质性的区别。,模拟退火算法及模型,算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。,物理退火过程,算法的目的 解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。,什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,物理退火过程,模拟退火算法及模型,Metropolis准则以概率接受新状态,物理退火过程,固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。若在温度T，当前状态i 新状态j若EjEi，则接受 j 为当前状态；否则，以概率 p=exp-(Ej-Ei)/kBT 接受j 为当前状态。即：p大于0,1)区间的随机数，则仍接受状态 j 为当前状态；否则保留状态 i 为当前状态。,模拟退火算法及模型,Metropolis准则以概率接受新状态 p=exp-(Ej-Ei)/kBT,物理退火过程,在低温下，只接受与当前状态能量差较小的新状态。,在高温下，可接受与当前状态能量差较大的新状态；,组合优化与物理退火的相似性,相似性比较,SA算法描述,27,遗传算法,Darwin 的物种进化的主要思想是自然选择(Natural selection)。生物通过竞争来进化，以适应环境。生物通过遗传(Heredity)、变异(Mutation)等过程实现进化。遗传和变异的物质基础是染色体(Chromosome)。染色体又是由DNA 和蛋白质组成的。基因中保留着遗传物质。通过基因的复制(production)、交叉(crossover)和变异(mutation)实现生物的性状的变异和遗传。标准遗传算法的基本框架是由Holland于20世纪60年代提出的，它使用二进制编码，采用赌轮选择和随机配对，关键是编码。这是一类模拟生物进化过程的全局性优化算法，其搜索效率取决于搜索策略或状态转移策略、编码策略、运行参数的合理配置等方面。对于具有下面数学结构的研究对象min（或max）f(x)，s.t.g(x)0，xD 遗传算法可以具有较好的搜索效果。,28,遗传算法,基本思路：第一步：建立研究对象的数学结构模型，确定目标函数类型（即求目标函数的最大值还是最小值?）。第二步：确定表示可行解的染色体编码方法，即确定个体基因型X及遗传算法的搜索空间。第三步：确定解码方法，即确定由个体基因型X到相应表现型的对应关系或转换关系。,29,遗传算法,基本思路：第四步：设计遗传算子，包括选择算子、交叉算子、变异算子等的具体操作方法。第五步：确定个体适应度的量化评价方法，即制定由目标函数 f(x)到个体适应度的转换规则。第六步：确定遗传算法的有关运行参数。包括编码串长度l（对于二进制编码）、交叉概率Pc、变异概率Pm、种群规模M、终止代数T等运行参数的设置。第七步：设计遗传算法程序，其中使用了最优保留策略。,30,遗传算法,为了提高其搜索效率，可以在三个方面提出改进措施：1)采用更好的搜索策略。主要包括：精英策略（elitist strategy）；构造与模拟退火算法、局部搜索算法如最速下降法等相结合的混和遗传算法（hybrid genetic algorithm）；通过改造模式定理和引入半序关系将所有模式构成一个半序格，从而将人工智能理论中的状态空间搜索算法如A算法与遗传算法相结合而提出的统计遗传算法（statistical genetic algorithm）；基于家族优生学原理构成两两结合的家族竞争机制，通过引入正交设计法构造出“正交交配”算子，从而在每个家庭内部形成局部竞争环境的进化算法；利用小生境技术、聚类分析或狭义遗传算法而提出的分区域搜索遗传算法等。,31,遗传算法,2)采用更加合理的编码策略。如采用十进制编码，多维实数编码，或根据模式定理将二进制编码的低阶、高平均适应度的长定义距模式转换为短定义距模式等。3)合理配置运行参数。遗传算法的求解效率在很大程度上取决于编码串长度l（对于二进制编码）、种群规模M、交叉概率Pc、变异概率Pm、终止代数T、适应度函数f(M)等运行参数的设置，当然与具体的选择算子也有很大关系，这在搜索策略中已经有一定体现。除了种群规模和终止代数之外，人们对于染色体编码、交叉和变异概率、适应度函数等进行了深入广泛的讨论，此处不再详细说明。,全局优化,(Rastrigins Function),全局最小点(0,0),优化算法解方程,威布尔分布统计量方程假设=1000;=1.15.则=951.7015；2=6.8841e+005.将与视为待求解变量，转化为最优化问题，则最优化模型为：,谢谢大家！,