现代优化算法简介.ppt

《现代优化算法简介.ppt》由会员分享，可在线阅读，更多相关《现代优化算法简介.ppt（29页珍藏版）》请在三一办公上搜索。

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

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

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

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

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

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

7、改。,启发式算法_不足,不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术 有关，缺乏规律性；（4）不同算法之间难以比较。,可应用那些问题,可应用那些问题NP问题不存在多项式算法的问题,典型问题如背包问题,周游问题,选址问题等某些高阶多项式算法问题.如对应算法时间复杂度超过4阶以上,此时利用普通算法在有效时间内可能不能得到结果那些问题不适合使用.求解为精确解.不是优化模型问题.有低阶多项式算法,当前进化算法新进展,多目标优化动态环境下优化大规模超大规模优化不确定环境下优化.,生物启发式优化方法,遗传算法神经网络模糊逻辑。,生物启发式计

8、算是指以生物界的各种自然现象或过程为灵感，而提出的一系列启发式智能计算方法。,遗传算法,进化过程,优化过程,生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过”“优胜劣汰”及遗传变异来达到进化（优化）目的的。,遗传算法,生物的进化机制,自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体突变 随机改变父代的染色体基因结构，产生新染色体,神经计算,人工神经网络是由 具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真

9、实世界物体所作出的交互反应。,神经计算,人工神经网络（Artificial Neural Networks,ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。,模糊逻辑,是 A1,集结器,去模糊化,y,规则1,y 是 B1,y 是 B2,y 是 Br,是 A2,是 Ar,规则2,规则r,模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含

10、一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（Membership Functions,MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论。,其它生物启发式计算技术,进化规划算法进化编程人工免疫系统DNA计算膜计算等,群体智能（Swarm Intelligence）,生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。,A,C,轨迹更新:,Visibility:,ij=1/dij,蚂蚁算法,表示轨迹的相对重要性,表示能见度的相对重要性,轨迹的持久性,表示第K只蚂蚁在本次循环中留在路径ij上的信息量,生物社会学家E.O.Wilson指出：“至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。”,鱼群觅食模型,避免碰撞速度匹配 中心聚集,鸟群的飞行行为,鸟群觅食模型,Food,Global Best Solution,Past Best Solution,谢谢大家,Q/A,