下载此文档

组合优化问题.ppt


文档分类:IT计算机 | 页数:约24页 举报非法文档有奖
1/24
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/24 下载此文档
文档列表 文档介绍
典型问题组合优化问题(Combinatorial Optimization Problems) 1 ????什么是组合优化定义: min f (x). x?S, S?XS,X :拥有有限个或可数无限个解的离散集合假设是一个求极小的问题,目标函数为 f(x) , 问题的解 x属于 S,而 S包含于 X,X是解空间,S 是可行解空间(可行区域) 所谓组合优化,是指在离散的、有限的数学结构上, 寻找一个(或一组)满足给定约束条件并使其目标函数值达到最小的解。 2 ?组合优化问题的特点 min f (x). x?S, S?XS,X :拥有有限个或可数无限个解的离散集合如果 S是有限集合的话,从理论上来讲, 只要遍历所有的组合,就能找到最优解。?然而,随着问题规模的增大, S中解的个数会迅速增大, 实际上要想遍历所有的解,几乎是不可能的。???一般来说,组合优化问题通常带有大量的局部极值点,往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的 NP 完全(难)问题组合最优化无法利用导数信息精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。 3 ????组合优化的研究怎么才能把一些社会现象、活动等捕捉归纳为组合优化问题? 怎么才能够在尽可能短的时间内求解组合优化问题? 各种组合优化问题拥有什么性质? 为了构造快速解法,什么样的性质是有用的? 4 ??求解方法分类从求解方法的大的分类上,可以分为: 精确的求解方法?可以得到问题的最优解,对小规模问题适用,当问?题的规模较大时,一般无法在有限的时间内获得问题的最优解?所以,对于组合优化问题,通常采用的是近似求解方法。近似的求解方法,可以进一步划分为: ?以确保解的精度为目标的方法?以尽可能获得更好解为目标的方法,包括: ?启发式(Heuristics) ?亚启发式(Meta-Heuristics) 5 ?近似求解方法以确保解的精度为目标的方法?能保证一定的精度,且成本较低,例如: ?程序所获得的目标函数值和最优解的目标函数值相比,达到 90% 或99% 以上,而且获得这样的解的成本不超过获得最优解的成本的 10% 或20% ,这样的算法是可接受的。?当然,从数学上准确地保证并不是一件简单的事情?这类近似方法的研究,会产生很多有趣的数学特征,吸引了很多从事理论研究的学者,从事这方面的工作。 6 ?近似求解方法以尽可能获得更好解为目标的方法?这类方法侧重于实际应用,有很多方法都是从实用的角度出发来考虑问题的。?启发式(Heuristics) 方法?即使我们求解很多的应用问题,也不会产生精度很差的解,偶尔,对于非常棘手的问题也许会产生精度很差的解,但一般的场合下,应该没有问题。?亚启发式(Meta-Heuristics) 方法?近年来在启发式方法中,一种被称之为亚启发式的方法,得到了广泛的研究,发现了一些较好的求解方法? GA 就是其中之一,另外还有 TS , SA , PSO 等算法。 7 ?近似求解方法亚启发式(Meta-Heuristics) ????从算法的角度来讲,是指不依赖于特定问题的启发式算法。其算法的基本框架被设计成不论对什么样的问题都具有通用性。一般情况下,亚启发式算法要比特定问题专用的启发式算法的解的精度要差。所以,针对特定的问题,要精心设计特定的算法。也有人把以邻域搜索为基础的组合优化方法统称为亚启发式 8 ?贪婪算法( greedy method ) 采用逐步构造最优解的方法。在每个阶段, 都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就不可再更改。?作出贪婪决策的依据称为贪婪准则( greedy criterion )。?一种近似求解方法?货箱装船、机器调度、最短路径、背包问题等方面都有应用 9 ?贪婪算法例[最短路径]: ????给出一个有向网络,要求找一条从初始点 s到达目的点d的最短路径。贪婪算法分步构造这条路径,每一步加入一个顶点。假设当前路径已到达点 q,且顶点 q并不是目的点 d。加入下一个顶点所采用的贪婪准则为: ?选择离 q 最近且目前不在路径中的顶点。 q dS 2 3243?这种贪婪算法并不一定能获得最短路径。 10

组合优化问题 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数24
  • 收藏数0 收藏
  • 顶次数0
  • 上传人ranfand
  • 文件大小735 KB
  • 时间2017-03-22