现代优化算法简介.ppt

《现代优化算法简介.ppt》由会员分享，可在线阅读，更多相关《现代优化算法简介.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、AHNUAHNU现代优化算法简介 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望AHNUAHNUv最优化问题模型最优化问题模型优化问题概述v全局最优与局部最优全局最优与局部最优 v实际生活中的优化问题实际生活中的优化问题AHNUAHNU组组组组合合合合优优优优化化化化问题优问题优问题优问题优化模型化模型化模型化模型 组合优化（组合优化（组合优化（组合优化（combinatorial optimizationcombinatorial optimizationcom

2、binatorial optimizationcombinatorial optimization）:解决离散问题的优解决离散问题的优解决离散问题的优解决离散问题的优化问题化问题化问题化问题运筹学分支。通过数学方法的研究去寻找离散事件的运筹学分支。通过数学方法的研究去寻找离散事件的运筹学分支。通过数学方法的研究去寻找离散事件的运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、最优编排、分组、次序或筛选等，可以涉及信息技术、经济

3、管理、工业工程、交通运输和通信网络等许多方面。工业工程、交通运输和通信网络等许多方面。工业工程、交通运输和通信网络等许多方面。工业工程、交通运输和通信网络等许多方面。数学模型：数学模型：数学模型：数学模型：AHNUAHNU组组组组合合合合优优优优化化化化问题问题问题问题 组合优化问题的三参数表示：组合优化问题的三参数表示：组合优化问题的三参数表示：组合优化问题的三参数表示：AHNUAHNU经典的计算方法v17世纪世纪Newtown 微积分微积分v1847年年 Cauchy 最速下降法最速下降法v1947年年 Dantzig 单纯形方法单纯形方法v1939年年 Kantorovich下料问题和运

4、输问题下料问题和运输问题 问题求解问题求解AHNUAHNU传统运筹学面临新挑战传统运筹学面临新挑战传统运筹学面临新挑战传统运筹学面临新挑战现代问题的特点现代问题的特点现代问题的特点现代问题的特点 离散性问题离散性问题离散性问题离散性问题主要以组合优化（针对离散问题，定义见后）理论主要以组合优化（针对离散问题，定义见后）理论主要以组合优化（针对离散问题，定义见后）理论主要以组合优化（针对离散问题，定义见后）理论为基础为基础为基础为基础 不确定性问题不确定性问题不确定性问题不确定性问题随机性数学模型随机性数学模型随机性数学模型随机性数学模型 半结构或非结构化的问题半结构或非结构化的问题半结构或非结

5、构化的问题半结构或非结构化的问题计算机模拟、决计算机模拟、决计算机模拟、决计算机模拟、决 策支持系统策支持系统策支持系统策支持系统 大规模问题大规模问题大规模问题大规模问题并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论现代优化方法现代优化方法现代优化方法现代优化方法 追求满意追求满意追求满意追求满意近似解近似解近似解近似解 实用性强实用性强实用性强实用性强解决实际问题解决实际问题解决实际问题解决实际问题现代优化算法的评价方法现代优化算法的评价方法现代优化算法的评价方法现代优化算法的评价方法 算法复杂性算法复杂性算

6、法复杂性算法复杂性AHNUAHNU1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）正确性，是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用常使用Matlab作为工具）作为工具）3、线性规划、

7、整数规划、多元规划、二次规划等规划类问题（建、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用学规划算法来描述，通常使用Lindo、Lingo软件实现）软件实现）4、图论算法（这类算法可以分为很多种，包括最短路、网络流、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）真准备）计算机上的常用算法：计算机上的常用算法：AHNUAHN

8、U5、动态规划、回溯搜索、分治算法、分支定界等计算机、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用）实现比较困难，需慎重使用）7、数值分析算法（如果在比

9、赛中采用高级语言进行编程、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行矩阵运算、函数积分等算法就需要额外编写库函数进行调用）调用）8、一些连续离散化方法（很多问题都是实际来的，数据、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）非常重要的）AHNUA

10、HNU9、网格算法和穷举法（网格算法和穷举法都是暴力搜索、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）好使用一些高级语言作为编程工具）10、图象处理算法（赛题中有一类问题与图形有关，即、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用

11、如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）进行处理）AHNUAHNU背背背背 景景景景传统实际问题的特点传统实际问题的特点传统实际问题的特点传统实际问题的特点 连续性问题连续性问题连续性问题连续性问题主要以微积分为基础，且问题规模较小主要以微积分为基础，且问题规模较小主要以微积分为基础，且问题规模较小主要以微积分为基础，且问题规模较小传统的优化方法传统的优化方法传统的优化方法传统的优化方法 追求准确追求准确追求准确追求准确精确解精确解精确解精确解 理论的完美理论的完美理论的完美理论的完美结果漂亮结果漂亮结果漂亮结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规

12、划、整数规划等；主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。排队论、库存论、对策论、决策论等。排队论、库存论、对策论、决策论等。排队论、库存论、对策论、决策论等。传统的评价方法传统的评价方法传统的评价方法传统的评价方法 算法收敛性（从极限角度考虑）算法收敛性（从极限角度考虑）算法收敛性（从极限角度考虑）算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）收敛速度（线性、超线性、二次收敛等）收敛速度（线性、超线

13、性、二次收敛等）收敛速度（线性、超线性、二次收敛等）AHNUAHNU启发式计算方法【定义【定义1-11-1】启发式算法是一种基于直观或经验构造的算启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。偏离程度未必可事先估计。【定义【定义1-21-2】启发式算法是一种技术，该技术使得能在可启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所接受的

14、计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。解与最优解的近似程度。经典的启发式方法基本原理经典的启发式方法基本原理:根据问题的部分已知信息来启发式根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较息来指导下一步的

15、动作并修正以前的步骤，从而获得在整体上较好的解决方案。好的解决方案。AHNUAHNU启发式算法启发式算法启发式算法启发式算法_ _ _ _优点优点优点优点 优点：优点：（1 1 1 1）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；（2 2 2 2）对有些难题，计算时间可接受；）对有些难题，计算时间可接受；）对有些难题，计算时间可接受；）对有些难题，计算时间可接受；（3 3 3 3）可用于某些最优化算法（如分支定界算）可用于某些最优化算法（如分支定界算）可用于某些最优化算法（如分支定界算）可用于某些最优化算

16、法（如分支定界算 法）之中的估界；法）之中的估界；法）之中的估界；法）之中的估界；（4 4 4 4）直观易行；）直观易行；）直观易行；）直观易行；（5 5 5 5）速度较快；）速度较快；）速度较快；）速度较快；（6 6 6 6）程序简单，易修改。）程序简单，易修改。）程序简单，易修改。）程序简单，易修改。AHNUAHNU启发式算法启发式算法_ _不足不足不足：不足：（1 1 1 1）不能保证求得全局最优解；）不能保证求得全局最优解；）不能保证求得全局最优解；）不能保证求得全局最优解；（2 2 2 2）解的精度不稳定，有时好有时坏；）解的精度不稳定，有时好有时坏；）解的精度不稳定，有时好有时坏；

17、）解的精度不稳定，有时好有时坏；（3 3 3 3）算法设计与问题、设计者经验、技术）算法设计与问题、设计者经验、技术）算法设计与问题、设计者经验、技术）算法设计与问题、设计者经验、技术 有关，缺乏规有关，缺乏规有关，缺乏规有关，缺乏规律性；律性；律性；律性；（4 4 4 4）不同算法之间难以比较。）不同算法之间难以比较。）不同算法之间难以比较。）不同算法之间难以比较。AHNUAHNU可可应应用那些用那些问题问题可应用那些问题可应用那些问题可应用那些问题可应用那些问题NPNPNPNP问题问题问题问题不存在多项式算法的问题不存在多项式算法的问题不存在多项式算法的问题不存在多项式算法的问题,典型问题

18、如背包问题典型问题如背包问题典型问题如背包问题典型问题如背包问题,周游问题周游问题周游问题周游问题,选址问选址问选址问选址问题等题等题等题等某些高阶多项式算法问题某些高阶多项式算法问题某些高阶多项式算法问题某些高阶多项式算法问题.如对应算法时间复杂度超过如对应算法时间复杂度超过如对应算法时间复杂度超过如对应算法时间复杂度超过4 4 4 4阶以上阶以上阶以上阶以上,此时利用普通算法在有效时此时利用普通算法在有效时此时利用普通算法在有效时此时利用普通算法在有效时间内可能不能得到结果间内可能不能得到结果间内可能不能得到结果间内可能不能得到结果那些问题不适合使用那些问题不适合使用那些问题不适合使用那些

19、问题不适合使用.求解为精确解求解为精确解求解为精确解求解为精确解.不是优化模型问题不是优化模型问题不是优化模型问题不是优化模型问题.有低阶多项式算法有低阶多项式算法有低阶多项式算法有低阶多项式算法AHNUAHNU当前进化算法新进展当前进化算法新进展多目标优化多目标优化多目标优化多目标优化动态环境下优化动态环境下优化动态环境下优化动态环境下优化大规模超大规模优化大规模超大规模优化大规模超大规模优化大规模超大规模优化不确定环境下优化不确定环境下优化不确定环境下优化不确定环境下优化.AHNUAHNU生物启发式优化方法生物启发式优化方法v遗传算法遗传算法v神经网络神经网络v模糊逻辑模糊逻辑v。生物启发

20、式计算是指以生物界的各种自然现象或过程生物启发式计算是指以生物界的各种自然现象或过程为灵感，而提出的一系列启发式智能计算方法。为灵感，而提出的一系列启发式智能计算方法。AHNUAHNU遗传算法进化过程进化过程优化过程优化过程生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过”“优胜劣汰”及遗传变异来达到进化（优化）目的的。AHNUAHNU遗传算法生物的进化机制生物的进化机制u自然选择自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来u杂交杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体

21、u突变突变 随机改变父代的染色体基因结构，产生新染色体AHNUAHNU神经计算树突树突 突触突触 轴突轴突 细胞体细胞体人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。AHNUAHNU神经计算人工神经网络（人工神经网络（Artificial Neural Networks,ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。INxT？I1I2I3SAHNUAHNU模糊

22、逻辑 是是是是 A A1 1集结器去模糊化y规则规则1 1 y y 是是是是 B B1 1 y y 是是是是 B B2 2 y y 是是是是 B Br r 是是是是 A A2 2 是是是是 A Ar r规则规则2规则规则r模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（MembershipFunctions,MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论。AHNUAHNU其它生物启发式计算技术v进化规

23、划算法进化规划算法v进化编程进化编程v人工免疫系统人工免疫系统vDNA计算计算v膜计算等膜计算等AHNUAHNU群体智能（群体智能（Swarm Intelligence）生物学家研究表明：在这些群居生物中虽然每个个体生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。用下，却表现出异常复杂而有序的群体行为。AHNUAHNUACAHNUAHNU轨迹更新:Visibility:ij=

24、1/dij蚂蚁算法蚂蚁算法表示轨迹的相对重要性表示能见度的相对重要性轨迹的持久性表示第K只蚂蚁在本次循环中留在路径ij上的信息量AHNUAHNU生物社会学家生物社会学家E.O.Wilson指出：指出：“至少从理论上，在搜索食至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。来的优势是决定性的，远大于对食物的竞争带来的劣势。”鱼群觅食模型AHNUAHNU避免碰撞避免碰撞速度速度匹配匹配 中心中心聚集聚集鸟群的飞行行为AHNUAHNU鸟群觅食模型FoodGlobal Best SolutionPast Best SolutionAHNUAHNU谢谢谢谢大家大家Q/A