最优化算法与MATLAB的.pptx

机动 目录 上页 下页 返回 结束 最优化算法与MATLAB的Global Optimization Toolbox 1，你参加建模竞赛（培训）的目的是什么？2，Matlab（c语言等计算机语言和lingo等其他软件）对于建模有什么作用大小如何？Matlab还有什么其他的作用？最优化算法理论上了解Global Optimization Toolbox 实际上解决问题机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 最优化算法最优化算法 许多生产计划与管理问题都可以归纳为最优化问题,最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等.近几年来的全国大学生数学建模竞赛中，几乎每次都有一道题要用到此方法.机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 线性规划主要方法：单纯形方法计算机软件：Lingo非线性规划主要方法：一维搜索算法一维搜索算法（二分法，黄金分割法等）（二分法，黄金分割法等）最速下降法最速下降法 (所谓最速下降方向仅反映所谓最速下降方向仅反映f f(x x)在在x x点点的局部性质的局部性质.最速下降法适用于寻优过程的前期最速下降法适用于寻优过程的前期迭代迭代,当接近极值点时当接近极值点时,宜选用其它收敛快的算法宜选用其它收敛快的算法)牛顿法、阻尼牛顿法、拟牛顿法牛顿法、阻尼牛顿法、拟牛顿法.多目标规划 (1)两个以上的目标函数；(2)若干个约束条件。最优解如何确定？不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求非劣解（又称非支配解或帕累托解pareto）。机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 全局最优化工具箱可以解决多种多样的极大值或者极小值问题：1，全局搜索（global search)2，模式搜索法(Pattern search method 线性，非线性，有界约束）3,遗传算法(genetic algorithm 线性，非线性，有界约束，多目标）4，模拟退火算法(simulated annealing method）5，多初始点法(MultiStart)这里多种多样-连续，离散，随机，含参数的。遗传算法和模式搜索法可以根据自己的需要来设定一些变量的值。Algorithmic customization.全局最优化工具箱有时候只能求解出局部最优解，不能确认是否为全局最优解，因此还需要在原有的基础上写出你自己的程序，或者将其与其他工具组合在一起。机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 Rastrigin 函数4个方法：1，fminunc（多初始点法）2，模式搜索法(patten search)3，遗传算法(ga)4，全局搜索（global search)机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 1，fminunc（多初始点法）rf2=(x)rastriginsfcn(x/10);%objectivex0=20,30;%start point away from the minimumxf ff flf of=fminunc(rf2,x0)初始点改变为10,10;结果如何？思考一下原因机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 2，模式搜索法(patten search)rf2=(x)rastriginsfcn(x/10);%objectivex0=20,30;%start point away from the minimumxp fp flp op=patternsearch(rf2,x0)初始点改变为10,10;结果如何？思考一下原因机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 3，遗传算法(ga)rf2=(x)rastriginsfcn(x/10);%objectivex0=20,30;%start point away from the minimuminitpop=10*randn(20,2)+repmat(10 30,20,1);opts=gaoptimset(InitialPopulation,initpop);xga fga flga oga=ga(rf2,2,opts)1,initpop=10*randn(20,2)+repmat(10 30,20,1)是 利用指定的均值向量mean vector和协方差矩阵covariance matrix计算2变量正态分布。2,x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 4，全局搜索（global search)rf2=(x)rastriginsfcn(x/10);%objectivex0=20,30;%start point away from the minimumproblem=createOptimProblem(fmincon,objective,rf2,.x0,x0);gs=GlobalSearch;xg fg flg og=run(gs,problem)机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 说明：1，fminunc可以很快的找到初始点所在盆地（basin）的局部极值点，但是不会跳出。2，patternsearch计算的函数值要好于fminunc。可以经过多个盆地，从而找到多个局部极值点，进而找到较好的点。3，ga计算的函数值要好于patternsearch。ga具有随机性，所以每次运行的结果都是不同的。可以经过多个盆地，从而找到多个局部极值点，进而找到较好的点。机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 4，global search计算的函数值要好于patternsearch。也是搜索多个盆地，到达相对好的点。利用多个初始点，搜索各自所在盆地中的极值点。在这个例子中可以找到全局最优点。5，simulannealbnd 有时候（偶尔）会接受不好的点来取代当前的点，为的是跳出这个盆地，到达另外的盆地。机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 光滑问题如果是求全局最优解的话那么怎么选取？方法：GlobalSearch,MultiStart,patternsearch,ga,simulannealbnd1,GlobalSearch；2,第二尝试MultiStart；包括的语句：fmincon,fminunc,lsqcurvefit,or lsqnonlin3,patternsearch不如前面两个有效，因为它没有用到梯度.但是比其他的要好;4,ga处理各类约束比simulannealbnd有效;5,simulannealbnd仅处理无约束或者边界约束.机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 总结：1，GlobalSearch 快速收敛到局部最优点 (1)有确定性的迭代 (2)基于梯度的方法2，MultiStart 快速收敛到局部最优点 基于梯度的方法3，patternsearch 可以收敛，但是速度要比上面两个基于梯度的方法慢 (1)有确定性的迭代 (2)不基于梯度的方法 (3)需要我们能提供初始点机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束 4，ga 没有证明收敛性 (1)迭代随机性 (2)不基于梯度的方法5，simulannealbnd 在缓慢冷却方案下对于有界问题缓慢收敛到全局最优点 (1)迭代随机性 (2)不基于梯度的方法 (3)需要我们能提供初始点(4)仅仅是有界问题以上的方法在记性比较的时候要注意的几个方面：收敛性 迭代方式 梯度模拟退火法模拟退火法求解无约束或者边界约束的优化问题。“模拟退火”算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。退火与冶金学上的退火相似，而与冶金学的淬火有很大区别，前者是温度缓慢下降，后者是温度迅速下降。在每一步迭代，新点会随机生成，新点与原来点的距离，搜索长度，都是基于概率分布的.算法接受所有降低目标函数的新点，但是也会有一定的可能性接受增加目标函数的新点。这样有更大可能找到全局最优解。机动 目录 上页 下页 返回 结束 机动 目录 上页 下页 返回 结束