《现代优化算法简介.pptx》由会员分享，可在线阅读，更多相关《现代优化算法简介.pptx（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、v最优化问题模型优化问题概述v全局最优与局部最优v实际生活中的优化问题第1页/共29页组合优化问题优化模型 组合优化（combinatorial optimization）:解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：第2页/共29页组合优化问题 组合优化问题的三参数表示：第3页/共29页经典的计算方法v17世纪Newtown微积分v1847年Cauchy最速下降法v1947年Dantzig单纯形方法v1939年Kantorovich下料问题和运输问题问题求解第4
2、页/共29页传统运筹学面临新挑战现代问题的特点离散性问题主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题随机性数学模型半结构或非结构化的问题计算机模拟、决策支持系统大规模问题并行计算、大型分解理论、近似理论现代优化方法追求满意近似解实用性强解决实际问题现代优化算法的评价方法算法复杂性第5页/共29页1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）3
3、、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现）4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备）计算机上的常用算法：第6页/共29页5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困
4、难，需慎重使用）7、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）第7页/共29页9、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不
5、乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）第8页/共29页背景传统实际问题的特点连续性问题主要以微积分为基础，且问题规模较小传统的优化方法追求准确精确解理论的完美结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）第9页/共29页启发式计算方法【定义1-1】启发式算法是一种基于直观或经验构造的算法，在可接受的耗费（指计算时间、占用空间等）下给出待解决优化问题每一实例的一个可行解，该可行解与最优解的偏离程度未必可事先估计。
6、【定义1-2】启发式算法是一种技术，该技术使得能在可接受的计算费用内去寻找尽可能好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法描述所得解与最优解的近似程度。经典的启发式方法基本原理:根据问题的部分已知信息来启发式地探索该问题的解决方案，在探索解决方案的过程中将发现的有关信息记录下来，不断积累和分析，并根据越来越丰富的已知信息来指导下一步的动作并修正以前的步骤，从而获得在整体上较好的解决方案。第10页/共29页启发式算法_优点 优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行
7、；（5）速度较快；（6）程序简单，易修改。第11页/共29页启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。第12页/共29页可应用那些问题可应用那些问题NP问题不存在多项式算法的问题,典型问题如背包问题,周游问题,选址问题等某些高阶多项式算法问题.如对应算法时间复杂度超过4阶以上,此时利用普通算法在有效时间内可能不能得到结果那些问题不适合使用.求解为精确解.不是优化模型问题.有低阶多项式算法第13页/共29页当前进化算法新进展多目标优化动态环境下优化大规模超大规模优化不
8、确定环境下优化.第14页/共29页生物启发式优化方法v遗传算法v神经网络v模糊逻辑v。生物启发式计算是指以生物界的各种自然现象或过程为灵感，而提出的一系列启发式智能计算方法。第15页/共29页遗传算法进化过程优化过程生物进化过程是一个自然，并行，稳健的优化过程，这一优化过程的目的在于使生命体达到适应环境的最佳结构与效果，而生物种群通过”“优胜劣汰”及遗传变异来达到进化（优化）目的的。第16页/共29页遗传算法生物的进化机制u自然选择 适应环境的个体具有更高的生存能力，同时染色体特征被保留下来u杂交 随机组合来自父代的染色体上的遗传物质，产生不同于它们父代的染色体u突变 随机改变父代的染色体基因
9、结构，产生新染色体第17页/共29页神经计算树突 突触 轴突 细胞体人工神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。第18页/共29页神经计算人工神经网络（ArtificialNeuralNetworks,ANN），一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络具有自学习和自适应的能力。INxT？I1I2I3S第19页/共29页模糊逻辑是是 A A1 1集结器去模糊化y规则1 y y 是是 B B
10、1 1 y y 是是 B B2 2 y y 是是 B Br r是是 A A2 2是是 A Ar r规则2规则r模糊推理系统是建立在模糊集合理论、模糊if-then规则和模糊推理等概念基础上的先进的计算框架。模糊推理系统的基本结构由三个重要部件组成：一个规则库，包含一系列模糊规则；一个数据库，定义模糊规则中用到的隶属度函数（MembershipFunctions,MF）；以及一个推理机制，按照规则和所给事实执行推理过程求得合理的输出或结论。第20页/共29页其它生物启发式计算技术v进化规划算法v进化编程v人工免疫系统vDNA计算v膜计算等第21页/共29页群体智能（Swarm Intellige
11、nce）生物学家研究表明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。第22页/共29页AC第23页/共29页轨迹更新:Visibility:ij=1/dij蚂蚁算法表示轨迹的相对重要性表示能见度的相对重要性轨迹的持久性表示第K只蚂蚁在本次循环中留在路径ij上的信息量第24页/共29页生物社会学家E.O.Wilson指出：“至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。”鱼群觅食模型第25页/共29页避免碰撞速度匹配 中心聚集鸟群的飞行行为第26页/共29页鸟群觅食模型FoodGlobal Best SolutionPast Best Solution第27页/共29页谢谢大家Q/A第28页/共29页感谢您的观看！第29页/共29页