最优化问题和遗传算法PPT课件

1、 MATLAB优化工具箱（Optimization Toolbox）中包含有一系列优化算法和模块，可以用于求解线性规划和二次规划、函数的最大和最小值、非线性规划、多目标优化、非线性最小二乘逼近和曲线拟合、非线性系统方程和复杂结构的大规模优化问题。 遗传算法（Genetic Algorithm）是模拟生物自然进化过程的进化算法中一个重要的领域，它已经被广泛地应用于自动控制、机器学习、模式识别、图形处理、人工神经网络、优化调度、经济预测、通讯网络和函数优化等各个领域，它作为一种新的全局优化搜索算法，在求解复杂的工程优化问题中取得良好的效果。利用MATLAB系统中的遗传算法工具箱（GA Toolbo

2、x）可以实现遗传算法许多基本运算。第1页/共84页9.1 MATLAB9.1 MATLAB优化工具箱的应用优化工具箱的应用 常用的优化功能函数有 求解线性规划问题的函数linprog 求解二次规划问题的函数quadprog 求解无约束非线性规划问题的函数fminbnd、fminunc和fminsearch 求解约束非线性规划问题的函数fmincon 求解多目标优化问题的函数fgoalattain和fminimax 使用MATLAB优化工具箱函数处理优化设计问题的分析和计算的一般步骤是： 1、针对具体工程问题建立优化设计的数学模型（其中，不等式约束条件表示成的形式）；第2页/共84页 2、分析数

3、学模型中的目标函数，并建立相应的目标函数文件（包括计算目标函数必需的输入参数，描述目标函数表达式等内容），以自定目标函数文件名将它存储在工作间MATLABWORK中； 3、分析数学模型中的非线性约束条件，并建立相应的非线性约束函数文件（包括计算约束函数必需的输入参数，描述约束函数表达式等内容），以自定的约束函数文件名将它存储在工作间MATLABWORK中； 4、分析优化设计的数学模型，选择适用的优化工具函数，并建立调用优化工具函数的命令文件（内容包括输入初始点，建立设计变量的线性约束和边界约束的矩阵和向量，使用优化工具函数调用目标函数文件和约束函数文件的语句，以及运算结果输出等内容），将优化工

4、具函数作为 “黑箱”调用，以自定的命令文件名将它存储在工作间MATLABWORK中。第3页/共84页 将优化设计的命令文件复制到MATLAB命令窗口的运算提示符“”后面运行。 如果编制的目标函数文件、约束函数文件和命令文件存在错误，MATLAB就会给出错误的类型和在M文件中的位置，方便用户对错误进行定位和检查。 如果M文件没有错误（包括逻辑错误和语法错误），命令窗口就会显示出运算信息，获得与所有条件都相容的优化结果。第4页/共84页 9.1.1 9.1.1 线性规划问题线性规划问题 线性规划（Linear Programming）是数学规划中最简单和基本的问题，它主要用来解决在有限的资源条件下

5、完成最多的任务，或是确定如何统筹任务完成以使用最少的资源。 线性规划的数学模型包括决策变量X、约束条件和目标函数三个要素，它的决策变量是非负的，而且约束函数和目标函数都是线性函数。 线性规划的数学模型表示为min. .Tf XstAXbAeqXbeqlbXub第5页/共84页 用于求解线性规划的MATLAB函数是linprog，其调用格式为： xopt,fopt=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 其中，输入参数有： f是目标函数各维变量的系数向量； A和b是不等式约束函数的系数矩阵和常数向量； Aeq和beq是等式约束函数系数矩阵和常数向量； lb

6、和ub分别是设计变量的下限和上限； x0是初始点； options是设置优化选项参数（参考表9-1）。 输出参数有： xopt和fopt是返回目标函数最优解及其函数值。第6页/共84页第7页/共84页第8页/共84页 例例9-1 9-1 求解线性规划问题 编制求解线性规划问题的M文件： % 求解线性规划问题 f=-2,-1,3,-5; % 各维变量的系数向量 A=1,2,4,-1;2,3,-1,1;1,0,1,1; % 系数矩阵 b=6,12,4; % 不等式约束函数的常数向量 lb=0,0,0,0; % 设计变量的下限 xopt,fopt=linprog(f,A,b,lb) 12341234

7、12341341234min235. .24623124,0fXxxxxstxxxxxxxxxxxx xx x 第9页/共84页 由于线性规划问题中没有等式约束，所以相应的系数矩阵Aeq和常数向量beq用空矩阵符号“”表示。程序运行结果： Optimization terminated successfully. xopt = 0.0000 2.6667 0.0000 4.0000 fopt = -22.6667 可见，约束最优解位于两个边界约束 和 的交集上。01x03x第10页/共84页 9.1.2 9.1.2 二次规划问题二次规划问题 二次规划问题（Quadratic Programmi

8、ng）是最简单的非线性规划问题，其目标函数是二次函数，而约束函数是线性函数。由于二次规划问题的求解比较成熟，有时可以将一些求解比较困难的一般非线性约束规划问题转化为较易处理的序列二次规划子问题求解。 用于求解二次规划问题的函数是 quadprog 二次规划的 数学模型为 1min2. .TTfXX HXC XstAXbAeqXbeqlbXub第11页/共84页 使用格式为 xopt,fopt= quadprog (H,C,A,b,Aeq,beq,lb,ub,x0,options) 其中，输入参数有： H是目标函数的海色矩阵； C是目标函数设计变量一次项的系数向量； A和b是不等式约束函数的系数

9、矩阵和常数向量； Aeq和beq是等式约束函数的系数矩阵和常数向量 lb和ub分别是设计变量的下限和上限； x0是初始点； options是设置优化选项参数（参考表9-1）。 输出参数有： xopt和fopt返回目标函数的最优解及其函数值。第12页/共84页 例例9-2 9-2 求解约束优化问题 将目标函数写成二次函数的形式 其中：222123123123123123222. .32624,0fXxxxx xxstg Xxxxh Xxxxx x x12TTfXX HXC X123xXxx220240002H 001C 第13页/共84页 线性不等式约束函数的系数矩阵和常数向量为 线性等式约束函

10、数的系数矩阵和常数向量为 编制求解二次规划的M文件 % 求解二次规划问题 H=2,-2,0;-2,3,0;0,0,2; % 函数的海色矩阵 C=0,0,1; % 各维变量的系数向量 A=1,3,2; % 不等式约束函数的系数矩阵 b=6; % 不等式约束函数的常数向量 Aeq=2,-1,1; % 等式约束函数的系数矩阵 beq=4; % 等式约束函数的常数向量 lb=zeros(3,1); % 设计变量的下限1,3,2A 6b 2, 1,1Aeq 4beq 第14页/共84页 xopt,fopt=quadprog(H,C,A,b,Aeq,beq,lb) % 调用线性规划函数 % 最优点的约束函

11、数值 g=A*xopt-b % 不等式约束 h=Aeq*xopt-beq % 等式约束 M文件运行结果： Optimization terminated successfully. xopt = 2.4783 1.0870 0.1304 fopt = 2.6739 g = 8.8818e-016 h = -4.4409e-016 可见，二次规划的约束最优解位于不等式约束和等式约束的交集。第15页/共84页 9.1.3 9.1.3 无约束非线性规划问题无约束非线性规划问题 1、函数fminbnd应用 函数fminbnd只能求解单变量的无约束非线性规划问题，而且要求目标函数为连续函数。调用格式 x

12、opt,fopt,exitflag,output= fminbnd(fun,x1,x2,options) 其中，输入参数有： fun是目标函数； x1,x2是迭代搜索区间，即变量的边界约束，即x1xx2； options是设置优化选项参数（见表9-1）。例如options(1)为负值时，则显示中间过程，默认值是options(1)=0；options(2)为最优解xopt的误差范围，默认值是1e-4；等等。第16页/共84页 输出参数有： Xopt为返回的满足fun取得最小值的x的值； fopt为目标函数最小值； exitflag表示退出条件：exitflag0表示计算收敛，exitflag=

13、0表示超过了最大的迭代次数，exitflag 0表示计算收敛，exitflag=0表示超过了最大的迭代次数，exitflag 9 | y2-4 | x(3)=0) & (g2=0) y=-f; % 满足约束条件时 else y=-(f+p); % 不满足约束条件时 end第79页/共84页 2、调用遗传优化算法函数，初始种群个体数目取20，其他默认缺省参数（进化繁殖100代） % 生成初始种群，个体数目取20 bounds=ones(2,1)*-1 3; % 变量上下限 startPop=initializega(20,bounds,minf_4,); % 遗传优化算法搜索 xf,en

14、dPop,beestSols,trace=ga(bounds,minf_4); beestSols xf M文件运行结果: beestSols = % 略去输出数据第80页/共84页 xf = 2.0310 0.8229 -0.0323 运算结果表明，繁殖到第62代时获得最优解： 将最优解代入两个约束条件中进行检验： % 计算最优点不等式约束函数值 g1y=xf(1)-2*xf(2)+1 g2y=0.25*xf(1)2-3*xf(2)2+1 M文件运行结果： g1y = 1.3859 g2y = 4.2997e-007第81页/共84页 3、描述遗传算法搜索过程 % 绘制遗传优化算法过程图形 plot(trace(:,1),trace(:,2),b:);