组合优化问题――东大公开课

典型问题典型问题组合优化问题组合优化问题(CombinatorialOptimizationProblems)p东北大学系统工程研究所2011.09什么是组合优化什么是组合优化定义：)(minf个解的离散集合拥有有限个或可数无限,..)(minXSXSSxtsxf假设是个求极小的问题目标函数为个解的离散集合拥有有限个或可数无限:,XS假设是一个求极小的问题，目标函数为f(x),问题的解x属于S，而S包含于X，X是解空间，S是可行解空间（可行区域）所谓组合优化是指在离散的有限的数学结构上所谓组合优化，是指在离散的、有限的数学结构上，寻找一个(或一组)满足给定约束条件并使其目标函典型优化问题的模型与算法-R032数值达到昀小的解。组合优化问题的特点组合优化问题的特点,..)(minXSSxtsxf如有集合的论上来讲遍所个解的离散集合拥有有限个或可数无限:,XS如果S是有限集合的话，从理论上来讲，只要遍历所有的组合，就能找到昀优解。然而，随着问题规模的增大，S中解的个数会迅速增大，实际上要想遍历所有的解，几乎是不可能的。般来说组合优化问题通常带有大量的局部极值点往一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全(难)问题非线性的NP完全(难)问题组合昀优化无法利用导数信息精确地求解组合优化问题的全局昀优解的“有效”算法一典型优化问题的模型与算法-R033精确地求解组合优化问题的全局昀优解的有效算法般是不存在的。组合优化的研究组合优化的研究怎么才能把一些社会现象、活动等捕捉归纳为组合优化问题？为组合优化问题？怎么才能够在尽可能短的时间内求解组合优怎么才能够在尽可能短的时间内求解组合优化问题？各种组合优化问题拥有什么性质？为了构造快速解法，什么样的性质是有用的？典型优化问题的模型与算法-R034组合优化问题组合优化问题在日常生活中，特别是在工程设计中，有许多组合优化问题。优化问题其中一个重要而广阔的应用领域就是如何有效地利用不充足的资源以提高生产效益。典型问题有：用不充的资源提高产效典问题有覆盖问题(set-coveringproblem)装箱问题(bin-packingproblem)(pgp)背包问题(knapsackproblem)指派问题(assignmentproblem)旅行商问题(travelingsalesmanproblem)影片递送问题(filmdeliveryproblem)昀小生成树问题(minimumspantreeproblem)作业调度问题(job-shopschedulingproblem)典型优化问题的模型与算法-R035求解方法分类求解方法分类从求解方法的大的分类上，可以分为：精确的求解方法精确的求解方法可以得到问题的昀优解，对小规模问题适用，当问题的规模较大时般无法在有限的时间内获得问题的规模较大时，一般无法在有限的时间内获得问题的昀优解所以对于组合优化问题通常采用的是近似求解所以，对于组合优化问题，通常采用的是近似求解方法。似的求法步划近似的求解方法，可以进一步划分为：以确保解的精度为目标的方法以尽可能获得更好解为目标的方法，包括：启发式(Heuristics)亚启发式(Meta-Heuristics)典型优化问题的模型与算法-R036近似求解方法近似求解方法以确保解的精度为目标的方法能保证定的精度且成本较低例如能保证一定的精度，且成本较低，例如：程序所获得的目标函数值和昀优解的目标函数值相比，达到90%或99%以上，而且获得这样的解的成本不超过获得昀优解的成本的10%或20%，这样的算法是可接受的。当然，从数学上准确地保证并不是一件简单的当然，从数学准确地保证并不是件简单的事情这类近似方法的研究会产生很多有趣的数学这类近似方法的研究，会产生很多有趣的数学特征，吸引了很多从事理论研究的学者，从事这方面的工作。典型优化问题的模型与算法-R037近似求解方法近似求解方法以尽可能获得更好解为目标的方法这类方法侧重于实际应用有很多方法都是从实用这类方法侧重于实际应用，有很多方法都是从实用的角度出发来考虑问题的。启发式方法启发式(Heuristics)方法即使我们求解很多的应用问题，也不会产生精度很差的解，偶尔，对于非常棘手的问题也许会产生精度很差的解，但一般的场合下，应该没有问题。亚启发式(Meta-Heuristics)方法近年来在启发式方法中，一种被称之为亚启发式的方法，得到了广泛的研究，发现了一些较好的求解方法GA就是其中之一，另外还有TS，SA，PSO等算法。典型优化问题的模型与算法-R038近似求解方法近似求解方法亚启发式(Meta-Heuristics)从算法的角度来讲，是指不依赖于特定问题的启发从算法的角度来讲，是指不依赖于特定问题的启发式算法。其算法的基本框架被设计成不论对什么样的问题都其算法的基本框架被设计成不论对什么样的问题都具有通用性。一般情况下，亚启发式算法要比特定问题专用的启般情况下，亚启发式算法要比特定问题专用的启发式算法的解的精度要差。所以，针对特定的问题，要精心设计特定的算法。也有人把以邻域搜索为基础的组合优化方法统称为亚启发式典型优化问题的模型与算法-R039亚启发式组合优化问题的求解方法组合优化问题的求解方法求解方法有很多，以下列举几种典型的方法：完全枚举法完全枚举法准完全枚举法降序排列法降序排列法贪婪法随机法随机法松弛法分割法从概念上来讲，这里所列的一些方法，有些是具有涵盖关系，比如说分割法分支定界法邻域搜索法具有涵盖关系，比如说降序排列法，也应该属于贪婪法的一种。邻域搜索法多起点邻域搜索法人工智能法典型优化问题的模型与算法-R0310完全枚举法完全枚举法枚举所有的组合，从中选择昀好的组合的方法这是一种昀简单的方法，可以找到问题的昀优解也是一种精确的解法但随着问题规模的扩大，会导致组合爆炸，使得完全枚举变得不可能例如：考虑把材料分配给n个零件的问题。我们可以按顺序给零件分配材料块材料无法满足要求的话就分配序给零件分配材料，一块材料无法满足要求的话，就分配下一块材料。这样我们可以得到一种分配结果。总的分配结果数，也就是零件的组合数，等于n个零件的总的分配结果数，也就是零件的组合数，等于n个零件的排列，n的阶乘。材料零件典型优化问题的模型与算法-R0311准完全枚举法准完全枚举法通过分组，使组合数降低，使完全枚举成为可能的一种方法正如在完全枚举法中所举例的那样，随着零件数量的增加，全部枚举零件的组合非常困难。然而如果按零件的尺寸形状的特征进行分组的话组的组合然而如果按零件的尺寸、形状的特征进行分组的话，组的组合就会减少，其结果导致有可能采用枚举的方法进行求解。尤其是，当把多个零件组合成一个零件进行处理时，零件的数合的数算等都会著减量、组合的数量、计算时间等都会显著减少。未必是问题的昀优解零件分组典型优化问题的模型与算法-R0312降序排列法降序排列法把零件按尺寸大小顺序排列，并分配材料，以此结果作为昀优组合的方法以此结果作为昀优组合的方法。想法很单纯，材料分配率也不坏。因为只进想法很单纯，材料分配率也不坏。因为只进行一次分配，所以几乎不花费计算时间。昀简单的方法之一，未必能得到昀优解典型优化问题的模型与算法-R0313贪婪算法（贪婪算法（greedymethodgreedymethod））采用逐步构造昀优解的方法。在每个阶段，都作出个看上去昀优的决策（在定的标都作出一个看上去昀优的决策（在一定的标准下）。决策一旦作出，就不可再更改。准下）。决策旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedycriterion）。一种近似求解方法种近似求解方法货箱装船、机器调度、昀短路径、背包问题等方面都有应用典型优化问题的模型与算法-R0314贪婪算法贪婪算法例[找零钱]：一个小孩买了价值少于1美元的糖，并将1美元交给售货员。售货员希望用数目昀少的硬币找给小孩。货员希望用数目昀少的硬币找给小孩。假设硬币数目不限，面值为25、10、5、及1美分。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下币时所采用的贪婪准则如下：每次都选择面值尽可能大的硬币，使找完的零钱数额尽量增大昀终的零钱数额等于要找的零钱数额假设需要找给小孩67美分假设需要找给小孩67美分，67美分零钱25*250美分+1060美分+565美分+1*267美分贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目昀少（至少是接近昀少的数目）。可以证明采用25*2=50美分+10=60美分+5=65美分+1*2=67美分典型优化问题的模型与算法-R0315上述贪婪算法找零钱时所用的硬币数目的确昀少。贪婪算法贪婪算法例[昀短路径]：给出一个有向网络，要求找一条从初始点s到达目的点d的昀短路径。贪婪算法分步构造这条路径，每一步加入一个顶点。假设当前路径已到达点且顶点并不是目的点假设当前路径已到达点q，且顶点q并不是目的点d。加入下一个顶点所采用的贪婪准则为：选择离q昀近且目前不在路径中的顶点选择离q昀近且目前不在路径中的顶点。qd3Sq2324这种贪婪算法并不定能获得昀短路径S3典型优化问题的模型与算法-R0316这种贪婪算法并不一定能获得昀短路径。邻域搜索法邻域搜索法也称为：局部搜索法、逐次改善法亚启发式的昀基本的方法首先找到问题的一个解，为了改善解的目标函数值，对解做一些变更，如果通过解的变更使目标值改善的话，就继续循环，否则终止搜索、输出解。典型优化问题的模型与算法-R0321局部搜索未必能得到问题的昀优解，有可能陷入局部昀优。多起点邻域搜索法多起点邻域搜索法基本想法：起点不同所获得的解也不同进行多次搜索起点不同，所获得的解也不同，进行多次搜索的话，可以从中找到更好的解。想法简单，据报道是非常有效的。典型优化问题的模型与算法-R0324人工智能的方法人工智能的方法神经网络遗传算法遗传算法……由于要进行高度复杂的计算，所以计算效果比较好当然也需要花费更长的计算时间比较好，当然也需要花费更长的计算时间。典型优化问题的模型与算法-R0325小结小结……同样的组合优化问题，采用不同的近似求解方法所得到的解以及解的精度是不一样的法，所得到的解、以及解的精度是不样的。同样一个算法，用于不同的问题，其性能与效率也不尽相同率也不尽相同。某些算法，只要稍微做些改变，就有可能导致解的精度或搜索效率的大幅度提高。因此，对于什么样的问题，应该采用什么样的法怎样使这种法才有效在这方法，怎样使用这种方法才更有效果，在这方面人们已经进行了很多的研究。面人们进行了很多的研究典型优化问题的模型与算法-R0326典型问题典型问题背包问题背包问题(KnapsackProblem)p典型优化问题的模型与算法-R0327背包问题背包问题所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现箱子里有很多大小与价值各不相同的物品，但小偷只有一个容积有限的背包来装东西，问题是小偷究竟要选择什么样的物品组合问题是小偷究竟要选择什么样的物品组合，才能使偷走的物品总价值昀大才能使偷走的物品总价值昀大。典型优化问题的模型与算法-R0328背包问题背包问题假设我们要从多种物品(一般称为项目)中选择几件物品，装满背包。件物品，装满背包。若有n个不同的项目，对于项目j其重量为wj;价值为pW是背包承受的昀大重量值为pj，W是背包承受的昀大重量。背包问题就是要在不超过背包承重量的前提下，使装入背包的价值昀大使装入背包的价值昀大。典型优化问题的模型与算法-R0329模型描述模型描述背包问题的数学描述：典型优化问题的模型与算法-R0330……背包问题吸引了许多理论和实