现代优化算法讲义

《现代优化算法讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、现代优化算法简介安徽师范大学数学计算机科学学院1.优化问题概述3.生物启发式优化2.经典计算方法最优化问题模型1.优化问题概述全局最优与局部最优实际生活中的优化问题组合优化问题优化模型组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：组合优化问题组合优化问题的三参数表示：经典的计算方法17世纪Newtown微积分1847年Cauchy最速下降法1947年Dantzig单纯形方法1939年

2、Kantorovich下料问题和运输问题问题求解传统运筹学面临新挑战现代问题的特点离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处

3、理数据的关键就在于这些算法，通常使用Matlab作为工具）3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）计算机上的常用算法：5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最

4、优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用）7、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）9、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）10、图象处理算法（

5、赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）启发式计算方法【定义1-1】启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例

6、的一个可行解，该可行解与最优解的偏离程度未必可事先估计。【定义1-2】启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。经典的启发式方法基本原理:根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。启发式算法_优点优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最

7、优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；可应用那些问题可应用那些问题NP问题………不存在多项式算法的问题,典型问题如背包问题,周游问题,选址问题等某些高阶多项式算法问题……….如对应算法时间复杂度超过4阶以上,此时利用普通算法在有效时间内可能不能得到结果那些问题不适合使用……..求解为精确解…….