最优化问题和遗传算法学习教案.pptx

会计学1最优化问题最优化问题(wnt)和遗传算法和遗传算法第一页，共84页。n nMATLABMATLAB优化工具箱（优化工具箱（Optimization ToolboxOptimization Toolbox）中包含）中包含有一系列优化算法和模块，可以用于求解线性规划和有一系列优化算法和模块，可以用于求解线性规划和二次规划、函数的最大和最小值、非线性规划、多目二次规划、函数的最大和最小值、非线性规划、多目标优化、非线性最小二乘逼近和曲线拟合、非线性系标优化、非线性最小二乘逼近和曲线拟合、非线性系统方程和复杂结构的大规模优化问题。统方程和复杂结构的大规模优化问题。n n遗传算法（遗传算法（Genetic AlgorithmGenetic Algorithm）是模拟生物自然进）是模拟生物自然进化过程的进化算法中一个重要的领域，它已经被广泛化过程的进化算法中一个重要的领域，它已经被广泛地应用于自动控制、机器学习、模式识别、图形处理、地应用于自动控制、机器学习、模式识别、图形处理、人工神经网络、优化调度、经济人工神经网络、优化调度、经济(jngj)(jngj)预测、通讯预测、通讯网络和函数优化等各个领域，它作为一种新的全局优网络和函数优化等各个领域，它作为一种新的全局优化搜索算法，在求解复杂的工程优化问题中取得良好化搜索算法，在求解复杂的工程优化问题中取得良好的效果。利用的效果。利用MATLABMATLAB系统中的遗传算法工具箱（系统中的遗传算法工具箱（GA GA ToolboxToolbox）可以实现遗传算法许多基本运算。）可以实现遗传算法许多基本运算。第1页/共84页第二页，共84页。9.1 MATLAB9.1 MATLAB9.1 MATLAB9.1 MATLAB优化工具箱的应用优化工具箱的应用优化工具箱的应用优化工具箱的应用(yngyng)(yngyng)(yngyng)(yngyng)n n常用的优化功能常用的优化功能(gngnng)(gngnng)函数有函数有n n求解线性规划问题的函数求解线性规划问题的函数linproglinprogn n求解二次规划问题的函数求解二次规划问题的函数quadprogquadprogn n求解无约束非线性规划问题的函数求解无约束非线性规划问题的函数fminbndfminbnd、fminuncfminunc和和fminsearchfminsearchn n求解约束非线性规划问题的函数求解约束非线性规划问题的函数fminconfminconn n求解多目标优化问题的函数求解多目标优化问题的函数fgoalattainfgoalattain和和fminimaxfminimaxn n使用使用MATLABMATLAB优化工具箱函数处理优化设计问题的优化工具箱函数处理优化设计问题的分析和计算的一般步骤是：分析和计算的一般步骤是：n n1 1、针对具体工程问题建立优化设计的数学模型、针对具体工程问题建立优化设计的数学模型（其中，不等式约束条件表示成的形式）；（其中，不等式约束条件表示成的形式）；第2页/共84页第三页，共84页。n n2 2、分析数学模型中的目标函数，并建立相应的、分析数学模型中的目标函数，并建立相应的目标函数文件（包括目标函数文件（包括(boku)(boku)计算目标函数必需计算目标函数必需的输入参数，描述目标函数表达式等内容），以的输入参数，描述目标函数表达式等内容），以自定目标函数文件名将它存储在工作间自定目标函数文件名将它存储在工作间MATLABWORKMATLABWORK中；中；n n3 3、分析数学模型中的非线性约束条件，并建立、分析数学模型中的非线性约束条件，并建立相应的非线性约束函数文件（包括相应的非线性约束函数文件（包括(boku)(boku)计算计算约束函数必需的输入参数，描述约束函数表达式约束函数必需的输入参数，描述约束函数表达式等内容），以自定的约束函数文件名将它存储在等内容），以自定的约束函数文件名将它存储在工作间工作间MATLABWORKMATLABWORK中；中；n n4 4、分析优化设计的数学模型，选择适用的优化、分析优化设计的数学模型，选择适用的优化工具函数，并建立调用优化工具函数的命令文件工具函数，并建立调用优化工具函数的命令文件（内容包括（内容包括(boku)(boku)输入初始点，建立设计变量输入初始点，建立设计变量的线性约束和边界约束的矩阵和向量，使用优化的线性约束和边界约束的矩阵和向量，使用优化工具函数调用目标函数文件和约束函数文件的语工具函数调用目标函数文件和约束函数文件的语句，以及运算结果输出等内容），将优化工具函句，以及运算结果输出等内容），将优化工具函数作为数作为“黑箱黑箱”调用，以自定的命令文件名将调用，以自定的命令文件名将它存储在工作间它存储在工作间MATLABWORKMATLABWORK中。中。第3页/共84页第四页，共84页。n n将优化设计的命令文件复制到将优化设计的命令文件复制到MATLABMATLAB命令窗口的运算提命令窗口的运算提示符示符“”“”后面运行。后面运行。n n如果编制的目标函数文件、约束函数文件和命令文件存如果编制的目标函数文件、约束函数文件和命令文件存在错误在错误(cuw)(cuw)，MATLABMATLAB就会给出错误就会给出错误(cuw)(cuw)的类型和的类型和在在M M文件中的位置，方便用户对错误文件中的位置，方便用户对错误(cuw)(cuw)进行定位和进行定位和检查。检查。n n如果如果M M文件没有错误文件没有错误(cuw)(cuw)（包括逻辑错误（包括逻辑错误(cuw)(cuw)和语和语法错误法错误(cuw)(cuw)），命令窗口就会显示出运算信息，获得），命令窗口就会显示出运算信息，获得与所有条件都相容的优化结果。与所有条件都相容的优化结果。第4页/共84页第五页，共84页。n n9.1.1 9.1.1 9.1.1 9.1.1 线性规划问题线性规划问题线性规划问题线性规划问题n n线性规划（线性规划（线性规划（线性规划（Linear ProgrammingLinear ProgrammingLinear ProgrammingLinear Programming）是数学规划）是数学规划）是数学规划）是数学规划中最简单和基本的问题，它主要用来解决在有中最简单和基本的问题，它主要用来解决在有中最简单和基本的问题，它主要用来解决在有中最简单和基本的问题，它主要用来解决在有限的资源条件下完成最多的任务，或是限的资源条件下完成最多的任务，或是限的资源条件下完成最多的任务，或是限的资源条件下完成最多的任务，或是(hu(hu(hu(hu sh)sh)sh)sh)确定如何统筹任务完成以使用最少的资源。确定如何统筹任务完成以使用最少的资源。确定如何统筹任务完成以使用最少的资源。确定如何统筹任务完成以使用最少的资源。n n线性规划的数学模型包括决策变量线性规划的数学模型包括决策变量线性规划的数学模型包括决策变量线性规划的数学模型包括决策变量X X X X、约束条、约束条、约束条、约束条件和目标函数三个要素，它的决策变量是非负件和目标函数三个要素，它的决策变量是非负件和目标函数三个要素，它的决策变量是非负件和目标函数三个要素，它的决策变量是非负的，而且约束函数和目标函数都是线性函数。的，而且约束函数和目标函数都是线性函数。的，而且约束函数和目标函数都是线性函数。的，而且约束函数和目标函数都是线性函数。n n线性规划的数学模型表示为线性规划的数学模型表示为线性规划的数学模型表示为线性规划的数学模型表示为第5页/共84页第六页，共84页。n n用于求解线性规划的用于求解线性规划的MATLABMATLAB函数是函数是linproglinprog，其调，其调用格式为：用格式为：n nxopt,fopt=linprog(f,A,b,Aeq,beq,lb,ub,x0,xopt,fopt=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)options)n n其中，输入其中，输入(shr)(shr)参数有：参数有：n n f f是目标函数各维变量的系数向量；是目标函数各维变量的系数向量；n n A A和和b b是不等式约束函数的系数矩阵和常数向量；是不等式约束函数的系数矩阵和常数向量；n n Aeq Aeq和和beqbeq是等式约束函数系数矩阵和常数向量；是等式约束函数系数矩阵和常数向量；n n lb lb和和ubub分别是设计变量的下限和上限；分别是设计变量的下限和上限；n n x0 x0是初始点；是初始点；n n options options是设置优化选项参数（参考表是设置优化选项参数（参考表9-19-1）。）。n n输出参数有：输出参数有：n n xopt xopt和和foptfopt是返回目标函数最优解及其函数值。是返回目标函数最优解及其函数值。第6页/共84页第七页，共84页。第7页/共84页第八页，共84页。第8页/共84页第九页，共84页。n n例例例例9-1 9-1 9-1 9-1 求解求解求解求解n n线性规划问题线性规划问题线性规划问题线性规划问题n n编制求解线性规划问题的编制求解线性规划问题的编制求解线性规划问题的编制求解线性规划问题的M M M M文件文件文件文件(wnjin)(wnjin)(wnjin)(wnjin)：n n%求解线性规划问题求解线性规划问题求解线性规划问题求解线性规划问题n nf=-2,-1,3,-5;%f=-2,-1,3,-5;%f=-2,-1,3,-5;%f=-2,-1,3,-5;%各维变量的系数向量各维变量的系数向量各维变量的系数向量各维变量的系数向量n nA=1,2,4,-1;2,3,-1,1;1,0,1,1;%A=1,2,4,-1;2,3,-1,1;1,0,1,1;%A=1,2,4,-1;2,3,-1,1;1,0,1,1;%A=1,2,4,-1;2,3,-1,1;1,0,1,1;%系数矩阵系数矩阵系数矩阵系数矩阵n nb=6,12,4;%b=6,12,4;%b=6,12,4;%b=6,12,4;%不等式约束函数的常数向量不等式约束函数的常数向量不等式约束函数的常数向量不等式约束函数的常数向量n nlb=0,0,0,0;%lb=0,0,0,0;%lb=0,0,0,0;%lb=0,0,0,0;%设计变量的下限设计变量的下限设计变量的下限设计变量的下限n nxopt,fopt=linprog(f,A,b,lb)xopt,fopt=linprog(f,A,b,lb)xopt,fopt=linprog(f,A,b,lb)xopt,fopt=linprog(f,A,b,lb)第9页/共84页第十页，共84页。n n由于线性规划问题中没有等式由于线性规划问题中没有等式(dngsh)(dngsh)约束，所以相应约束，所以相应的系数矩阵的系数矩阵AeqAeq和常数向量和常数向量beqbeq用空矩阵符号用空矩阵符号“”“”表示。表示。程序运行结果：程序运行结果：n nOptimization terminated successfully.Optimization terminated successfully.n nxopt=0.0000 xopt=0.0000n n 2.6667 2.6667n n 0.0000 0.0000n n 4.0000 4.0000n nfopt=-22.6667fopt=-22.6667n n可见，约束最优解位于两个边界约束可见，约束最优解位于两个边界约束n n 和和 的交集上。的交集上。第10页/共84页第十一页，共84页。n n9.1.2 9.1.2 9.1.2 9.1.2 二次规划问题二次规划问题二次规划问题二次规划问题n n二次规划问题（二次规划问题（二次规划问题（二次规划问题（Quadratic ProgrammingQuadratic ProgrammingQuadratic ProgrammingQuadratic Programming）是）是）是）是最简单的非线性规划问题，其目标函数是二次最简单的非线性规划问题，其目标函数是二次最简单的非线性规划问题，其目标函数是二次最简单的非线性规划问题，其目标函数是二次函数，而约束函数是线性函数。由于二次规划函数，而约束函数是线性函数。由于二次规划函数，而约束函数是线性函数。由于二次规划函数，而约束函数是线性函数。由于二次规划问题的求解比较成熟，有时可以将一些求解比问题的求解比较成熟，有时可以将一些求解比问题的求解比较成熟，有时可以将一些求解比问题的求解比较成熟，有时可以将一些求解比较困难较困难较困难较困难(kn nn)(kn nn)(kn nn)(kn nn)的一般非线性约束规划问题的一般非线性约束规划问题的一般非线性约束规划问题的一般非线性约束规划问题转化为较易处理的序列二次规划子问题求解。转化为较易处理的序列二次规划子问题求解。转化为较易处理的序列二次规划子问题求解。转化为较易处理的序列二次规划子问题求解。n n用于求解二次规划问题的函数是用于求解二次规划问题的函数是用于求解二次规划问题的函数是用于求解二次规划问题的函数是 quadprog quadprog quadprog quadprogn n二次规划的二次规划的二次规划的二次规划的n n 数学模型为数学模型为数学模型为数学模型为 第11页/共84页第十二页，共84页。n n使用格式为使用格式为n n xopt,fopt=xopt,fopt=n n quadprog(H,C,A,b,Aeq,beq,lb,ub,x0,options)quadprog(H,C,A,b,Aeq,beq,lb,ub,x0,options)n n其中，输入参数有：其中，输入参数有：n n H H是目标函数的海色矩阵；是目标函数的海色矩阵；n n C C是目标函数设计变量一次项的系数向量；是目标函数设计变量一次项的系数向量；n n A A和和b b是不等式约束函数的系数矩阵和常数向量；是不等式约束函数的系数矩阵和常数向量；n n Aeq Aeq和和beqbeq是等式约束函数的系数矩阵和常数向量是等式约束函数的系数矩阵和常数向量n n lb lb和和ubub分别是设计变量的下限和上限；分别是设计变量的下限和上限；n n x0 x0是初始点；是初始点；n n options options是设置是设置(shzh)(shzh)优化选项参数（参考表优化选项参数（参考表9-19-1）。）。n n输出参数有：输出参数有：n nxoptxopt和和foptfopt返回目标函数的最优解及其函数值。返回目标函数的最优解及其函数值。第12页/共84页第十三页，共84页。n n例例例例9-2 9-2 9-2 9-2 求解约束优化问题求解约束优化问题求解约束优化问题求解约束优化问题n n将目标将目标将目标将目标(mbio)(mbio)(mbio)(mbio)函数写成二次函数的形式函数写成二次函数的形式函数写成二次函数的形式函数写成二次函数的形式n n其中：其中：其中：其中：第13页/共84页第十四页，共84页。n n线性不等式约束函数的系数矩阵和常数线性不等式约束函数的系数矩阵和常数(chngsh)(chngsh)向量向量为为n n线性等式约束函数的系数矩阵和常数线性等式约束函数的系数矩阵和常数(chngsh)(chngsh)向量为向量为n n编制求解二次规划的编制求解二次规划的M M文件文件n n%求解二次规划问题求解二次规划问题n nH=2,-2,0;-2,3,0;0,0,2;%H=2,-2,0;-2,3,0;0,0,2;%函数的海色矩阵函数的海色矩阵n nC=0,0,1;%C=0,0,1;%各维变量的系数向量各维变量的系数向量n nA=1,3,2;%A=1,3,2;%不等式约束函数的系数矩阵不等式约束函数的系数矩阵n nb=6;%b=6;%不等式约束函数的常数不等式约束函数的常数(chngsh)(chngsh)向量向量n nAeq=2,-1,1;%Aeq=2,-1,1;%等式约束函数的系数矩阵等式约束函数的系数矩阵n nbeq=4;%beq=4;%等式约束函数的常数等式约束函数的常数(chngsh)(chngsh)向量向量n nlb=zeros(3,1);%lb=zeros(3,1);%设计变量的下限设计变量的下限第14页/共84页第十五页，共84页。n nxopt,fopt=quadprog(H,C,A,b,Aeq,beq,lb)xopt,fopt=quadprog(H,C,A,b,Aeq,beq,lb)%调用线性规划函数调用线性规划函数n n%最优点的约束函数值最优点的约束函数值n ng=A*xopt-b%g=A*xopt-b%不等式约束不等式约束n nh=Aeq*xopt-beq%h=Aeq*xopt-beq%等式约束等式约束n nM M文件运行文件运行(ynxng)(ynxng)结果：结果：n nOptimization terminated successfully.Optimization terminated successfully.n nxopt=2.4783xopt=2.4783n n 1.0870 1.0870n n 0.1304 0.1304n nfopt=2.6739fopt=2.6739n ng=8.8818e-016g=8.8818e-016n nh=-4.4409e-016h=-4.4409e-016n n可见，二次规划的约束最优解位于不等式约束和等可见，二次规划的约束最优解位于不等式约束和等式约束的交集。式约束的交集。第15页/共84页第十六页，共84页。n n9.1.3 9.1.3 9.1.3 9.1.3 无约束非线性规划问题无约束非线性规划问题无约束非线性规划问题无约束非线性规划问题n n1 1 1 1、函数、函数、函数、函数fminbndfminbndfminbndfminbnd应用应用应用应用n n函数函数函数函数fminbndfminbndfminbndfminbnd只能求解单变量的无约束非线只能求解单变量的无约束非线只能求解单变量的无约束非线只能求解单变量的无约束非线性规划问题，而且要求目标函数为连续函性规划问题，而且要求目标函数为连续函性规划问题，而且要求目标函数为连续函性规划问题，而且要求目标函数为连续函数。调用格式数。调用格式数。调用格式数。调用格式n n xopt,fopt,exitflag,output=xopt,fopt,exitflag,output=xopt,fopt,exitflag,output=xopt,fopt,exitflag,output=fminbnd(fun,x1,x2,options)fminbnd(fun,x1,x2,options)fminbnd(fun,x1,x2,options)fminbnd(fun,x1,x2,options)n n其中，输入参数有：其中，输入参数有：其中，输入参数有：其中，输入参数有：n n fun fun fun fun是目标函数；是目标函数；是目标函数；是目标函数；n n x1,x2 x1,x2 x1,x2 x1,x2是迭代搜索区间，即变量的边界是迭代搜索区间，即变量的边界是迭代搜索区间，即变量的边界是迭代搜索区间，即变量的边界约束，即约束，即约束，即约束，即x1xx2x1xx2x1xx2x1xx2；n n options options options options是设置优化选项参数（见表是设置优化选项参数（见表是设置优化选项参数（见表是设置优化选项参数（见表9-19-19-19-1）。）。）。）。例如例如例如例如(lr)options(1)(lr)options(1)(lr)options(1)(lr)options(1)为负值时，则显示为负值时，则显示为负值时，则显示为负值时，则显示中间过程，默认值是中间过程，默认值是中间过程，默认值是中间过程，默认值是options(1)=0options(1)=0options(1)=0options(1)=0；options(2)options(2)options(2)options(2)为最优解为最优解为最优解为最优解xoptxoptxoptxopt的误差范围，默的误差范围，默的误差范围，默的误差范围，默认值是认值是认值是认值是1e-41e-41e-41e-4；等等。；等等。；等等。；等等。第16页/共84页第十七页，共84页。n n输出参数有：输出参数有：n n Xopt Xopt为返回的满足为返回的满足funfun取得最小值的取得最小值的x x的值；的值；n n fopt fopt为目标函数最小值；为目标函数最小值；n n exitflag exitflag表示退出条件：表示退出条件：exitflag0exitflag0表示计算收表示计算收敛，敛，exitflag=0exitflag=0表示超过了最大的迭代次数，表示超过了最大的迭代次数，exitflag 0exitflag 0exitflag0表表示计算收敛，示计算收敛，exitflag=0exitflag=0表示超过了最大的迭代次表示超过了最大的迭代次数，数，exitflag 0exitflag 9|y2-4|x(3)9|y2-4|x(3)=0)&(g2=0)if(g1=0)&(g2=0)n n y=-f;%y=-f;%满足约束条件时满足约束条件时n nelseelsen n y=-(f+p);%y=-(f+p);%不满足约束条件时不满足约束条件时n nendend第79页/共84页第八十页，共84页。n n 2 2、调用遗传优化算法函数，初始种群个体数目取、调用遗传优化算法函数，初始种群个体数目取2020，其他默认缺省参数（进化繁殖其他默认缺省参数（进化繁殖100100代）代）n n%生成初始种群，个体数目取生成初始种群，个体数目取2020n nbounds=ones(2,1)*-1 3;%bounds=ones(2,1)*-1 3;%变量上变量上下限下限n nstartPop=initializega(20,bounds,minf_4,);startPop=initializega(20,bounds,minf_4,);n n%遗传优化算法搜索遗传优化算法搜索(su su)(su su)n nxf,endPop,beestSols,trace=ga(bounds,minf_4);xf,endPop,beestSols,trace=ga(bounds,minf_4);n nbeestSolsbeestSolsn nxfxfn nM M文件运行结果文件运行结果:n nbeestSols=%beestSols=%略去输出数据略去输出数据第80页/共84页第八十一页，共84页。n nxf=xf=n n 2.0310 0.8229 -0.0323 2.0310 0.8229 -0.0323n n运算结果表明，繁殖到第运算结果表明，繁殖到第6262代时获得最优解：代时获得最优解：n n将最优解代入两个约束条件中进行将最优解代入两个约束条件中进行(jnxng)(jnxng)检检验：验：n n%计算最优点不等式约束函数值计算最优点不等式约束函数值n ng1y=xf(1)-2*xf(2)+1 g1y=xf(1)-2*xf(2)+1 n ng2y=0.25*xf(1)2-3*xf(2)2+1g2y=0.25*xf(1)2-3*xf(2)2+1n nM M文件运行结果：文件运行结果：n ng1y=g1y=n n 1.3859 1.3859n ng2y=g2y=n n 4.2997e-007 4.2997e-007第81页/共84页第八十二页，共84页。n n3 3、描述遗传算法搜索过程、描述遗传算法搜索过程n n%绘制遗传优化算法过程图形绘制遗传优化算法过程图形(txng)(txng)n nplot(trace(:,1),trace(:,2),b:);plot(trace(:,1),trace(:,2),b:);n nhold on;hold on;n nplot(trace(:,1),trace(:,3),r);plot(trace(:,1),trace(:,3),r);n ngrid;grid;n nxlabel(bf Generation);ylabel(bf xlabel(bf Generation);ylabel(bf Fitness);Fitness);n ntitle(bf title(bf 二维约束非线性遗传算法的各代最好解二维约束非线性遗传算法的各代最好解与平均值与平均值););n nlegend(legend(虚线：各代种群平均值虚线：各代种群平均值,实线：各代最优实线：各代最优解解)M)M文件运行结果如图文件运行结果如图9-99-9所示，图中实线表示各所示，图中实线表示各代最优解，虚线表示各代种群平均值。代最优解，虚线表示各代种群平均值。第82页/共84页第八十三页，共84页。第83页/共84页第八十四页，共84页。