组合优化问题ppt课件.ppt

《组合优化问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、典型问题组合优化问题(CombinatorialOptimizationProblems)什么是组合优化定义：minf(x)s.t.xS,SXS,X:拥有有限个或可数无限个解的离散集合假设是一个求极小的问题，目标函数为f(x),问题的解x属于S，而S包含于X，X是解空间，S是可行解空间（可行区域）所谓组合优化，是指在离散的、有限的数学结构上，寻找一个(或一组)满足给定约束条件并使其目标函数值达到最小的解。组合优化问题的特点minf(x)s.t.xS,SXS,X:拥有有限个或可数无限个解的离散集合如果S是有限集合的话

2、，从理论上来讲，只要遍历所有的组合，就能找到最优解。然而，随着问题规模的增大，S中解的个数会迅速增大，实际上要想遍历所有的解，几乎是不可能的。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全(难)问题组合最优化无法利用导数信息精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。组合优化的研究怎么才能把一些社会现象、活动等捕捉归纳为组合优化问题？怎么才能够在尽可能短的时间内求解组合优化问题？各种组合优化问题拥有什么性质？为了构造快速解法，什

3、么样的性质是有用的？求解方法分类从求解方法的大的分类上，可以分为：精确的求解方法可以得到问题的最优解，对小规模问题适用，当问题的规模较大时，一般无法在有限的时间内获得问题的最优解所以，对于组合优化问题，通常采用的是近似求解方法。近似的求解方法，可以进一步划分为：以确保解的精度为目标的方法以尽可能获得更好解为目标的方法，包括：启发式(Heuristics)亚启发式(Meta-Heuristics)近似求解方法以确保解的精度为目标的方法能保证一定的精度，且成本较低，例如：程序所获得的目标函数值和最优解的目标函数值

4、相比，达到90%或99%以上，而且获得这样的解的成本不超过获得最优解的成本的10%或20%，这样的算法是可接受的。当然，从数学上准确地保证并不是一件简单的事情这类近似方法的研究，会产生很多有趣的数学特征，吸引了很多从事理论研究的学者，从事这方面的工作。近似求解方法以尽可能获得更好解为目标的方法这类方法侧重于实际应用，有很多方法都是从实用的角度出发来考虑问题的。启发式(Heuristics)方法即使我们求解很多的应用问题，也不会产生精度很差的解，偶尔，对于非常棘手的问题也许会产生精度很差的解，但一般的场合下，应该没有问题。

5、亚启发式(Meta-Heuristics)方法近年来在启发式方法中，一种被称之为亚启发式的方法，得到了广泛的研究，发现了一些较好的求解方法GA就是其中之一，另外还有TS，SA，PSO等算法。近似求解方法亚启发式(Meta-Heuristics)从算法的角度来讲，是指不依赖于特定问题的启发式算法。其算法的基本框架被设计成不论对什么样的问题都具有通用性。一般情况下，亚启发式算法要比特定问题专用的启发式算法的解的精度要差。所以，针对特定的问题，要精心设计特定的算法。也有人把以邻域搜索为基础的组合优化方法统称为亚启发式贪婪

6、算法（greedymethod）采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。一种近似求解方法货箱装船、机器调度、最短路径、背包问题等方面都有应用贪婪算法例[最短路径]：给出一个有向网络，要求找一条从初始点s到达目的点d的最短路径。贪婪算法分步构造这条路径，每一步加入一个顶点。假设当前路径已到达点q，且顶点q并不是目的点d。加入下一个顶点所采用的贪婪准则为：选择离q最近且目前不在路径中

7、的顶点。qdS23243这种贪婪算法并不一定能获得最短路径。人工智能的方法神经网络遗传算法……由于要进行高度复杂的计算，所以计算效果比较好，当然也需要花费更长的计算时间。小结…同样的组合优化问题，采用不同的近似求解方法，所得到的解、以及解的精度是不一样的。同样一个算法，用于不同的问题，其性能与效率也不尽相同。某些算法，只要稍微做些改变，就有可能导致解的精度或搜索效率的大幅度提高。因此，对于什么样的问题，应该采用什么样的方法，怎样使用这种方法才更有效果，在这方面人们已经进行了很多的研究。典型问题旅行商问题(Trave

8、lingSalesmanProblem)旅行商问题TSP的历史很久最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。一般性描述：有一个推销员，要到n