最优化算法与MATLAB的Global Optimization Toolbox.ppt

机动目录上页下页返回结束 最优化算法与MATLAB的GlobalOptimizationToolbox 1 你参加建模竞赛 培训 的目的是什么 2 Matlab c语言等计算机语言和lingo等其他软件 对于建模有什么作用大小如何 Matlab还有什么其他的作用 最优化算法 理论上了解GlobalOptimizationToolbox实际上解决问题 机动目录上页下页返回结束 机动目录上页下页返回结束 最优化算法许多生产计划与管理问题都可以归纳为最优化问题 最优化模型是数学建模中应用最广泛的模型之一 其内容包括线性规划 整数线性规划 非线性规划 动态规划 变分法 最优控制等 近几年来的全国大学生数学建模竞赛中 几乎每次都有一道题要用到此方法 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 线性规划主要方法 单纯形方法计算机软件 Lingo非线性规划主要方法 一维搜索算法 二分法 黄金分割法等 最速下降法 所谓最速下降方向仅反映f x 在x点的局部性质 最速下降法适用于寻优过程的前期迭代 当接近极值点时 宜选用其它收敛快的算法 牛顿法 阻尼牛顿法 拟牛顿法 多目标规划 1 两个以上的目标函数 2 若干个约束条件 最优解如何确定 不会存在使所有目标函数同时达到最大或最小值的最优解 于是我们只能寻求非劣解 又称非支配解或帕累托解pareto 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 全局最优化工具箱可以解决多种多样的极大值或者极小值问题 1 全局搜索 globalsearch 2 模式搜索法 Patternsearchmethod线性 非线性 有界约束 3 遗传算法 geneticalgorithm线性 非线性 有界约束 多目标 4 模拟退火算法 simulatedannealingmethod 5 多初始点法 MultiStart 这里多种多样 连续 离散 随机 含参数的 遗传算法和模式搜索法可以根据自己的需要来设定一些变量的值 Algorithmiccustomization 全局最优化工具箱有时候只能求解出局部最优解 不能确认是否为全局最优解 因此还需要在原有的基础上写出你自己的程序 或者将其与其他工具组合在一起 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 Rastrigin函数4个方法 1 fminunc 多初始点法 2 模式搜索法 pattensearch 3 遗传算法 ga 4 全局搜索 globalsearch 机动目录上页下页返回结束 机动目录上页下页返回结束 1 fminunc 多初始点法 rf2 x rastriginsfcn x 10 objectivex0 20 30 startpointawayfromtheminimum xfffflfof fminunc rf2 x0 初始点改变为 10 10 结果如何 思考一下原因 机动目录上页下页返回结束 机动目录上页下页返回结束 2 模式搜索法 pattensearch rf2 x rastriginsfcn x 10 objectivex0 20 30 startpointawayfromtheminimum xpfpflpop patternsearch rf2 x0 初始点改变为 10 10 结果如何 思考一下原因 机动目录上页下页返回结束 机动目录上页下页返回结束 3 遗传算法 ga rf2 x rastriginsfcn x 10 objectivex0 20 30 startpointawayfromtheminimuminitpop 10 randn 20 2 repmat 1030 20 1 opts gaoptimset InitialPopulation initpop xgafgaflgaoga ga rf2 2 opts 1 initpop 10 randn 20 2 repmat 1030 20 1 是利用指定的均值向量meanvector和协方差矩阵covariancematrix计算2变量正态分布 2 x ga fitnessfcn nvars A b Aeq beq LB UB nonlcon options 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 机动目录上页下页返回结束 4 全局搜索 globalsearch rf2 x rastriginsfcn x 10 objectivex0 20 30 startpointawayfromtheminimumproblem createOptimProblem fmincon objective rf2 x0 x0 gs GlobalSearch xgfgflgog run gs problem 机动目录上页下页返回结束 机动目录上页下页返回结束 说明 1 fminunc可以很快的找到初始点所在盆地 basin 的局部极值点 但是不会跳出 2 patternsearch计算的函数值要好于fminunc 可以经过多个盆地 从而找到多个局部极值点 进而找到较好的点 3 ga计算的函数值要好于patternsearch ga具有随机性 所以每次运行的结果都是不同的 可以经过多个盆地 从而找到多个局部极值点 进而找到较好的点 机动目录上页下页返回结束 机动目录上页下页返回结束 4 globalsearch计算的函数值要好于patternsearch 也是搜索多个盆地 到达相对好的点 利用多个初始点 搜索各自所在盆地中的极值点 在这个例子中可以找到全局最优点 5 simulannealbnd有时候 偶尔 会接受不好的点来取代当前的点 为的是跳出这个盆地 到达另外的盆地 机动目录上页下页返回结束 机动目录上页下页返回结束 光滑问题如果是求全局最优解的话那么怎么选取 方法 GlobalSearch MultiStart patternsearch ga simulannealbnd1 GlobalSearch 2 第二尝试MultiStart 包括的语句 fmincon fminunc lsqcurvefit orlsqnonlin3 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 仅仅是有界问题以上的方法在记性比较的时候要注意的几个方面 收敛性迭代方式梯度 模拟退火法 模拟退火法求解无约束或者边界约束的优化问题 模拟退火 算法是源于对热力学中退火过程的模拟 在某一给定初温下 通过缓慢下降温度参数 使算法能够在多项式时间内给出一个近似最优解 退火与