典型优化问题的遗传算法求解—4组合优化问题.doc

典型问题 组合优化问题 (Combinatorial Optimization Problems) 东北大学 系统工程研究所 2014.09 什么是组合优化 ? 定义： min f (x) s.t. x S, S X ? ? S, X : ? 假设是一个求极小的问题，目标函数为 f(x), ? 问题的解 x 属于 S，而 S 包含于 X，X 是解空间，S 是可行解空间（可行区域） ? 所谓组合优化，是指在离散的、有限的数学结构上， 寻找一个(或一组)满足给定约束条件并使其目标函 数值达到最小的解。 典型优化问题的模型与算法-R03 2 组合优化问题的特点 min f (x) s.t. x S, S X ? ? S, X :拥有有限个或可数无限 个解的离散集合 ? 如果 S 是有限集合的话，从理论上来讲，只要遍历所 有的组合，就能找到最优解。 ? 然而，随着问题规模的增大，S 中解的个数会迅速增大，实 际上要想遍历所有的解，几乎是不可能的。 ? 一般来说，组合优化问题通常带有大量的局部极值点，往 往是不可微的、不连续的、多维的、有约束条件的、高度 非线性的NP完全(难)问题 ? 组合最优化无法利用导数信息 ? 精确地求解组合优化问题的全局最优解的“有效”算法一 般是不存在的。 典型优化问题的模型与算法-R03 3 组合优化的研究 ? 怎么才能把一些社会现象、活动等捕捉归纳 为组合优化问题？ ? 怎么才能够在尽可能短的时间内求解组合优 化问题？ ? 各种组合优化问题拥有什么性质？ ? 为了构造快速解法，什么样的性质是有用的？ 典型优化问题的模型与算法-R03 4 组合优化问题 ? 在日常生活中，特别是在工程设计中，有许多组合 优化问题。 ? 其中一个重要而广阔的应用领域就是如何有效地利 用不充足的资源以提高生产效益。典型问题有： ? 覆盖问题(set-covering problem) ? 装箱问题(bin-packing problem) ? 背包问题(knapsack problem) ? 指派问题(assignment problem) ? 旅行商问题(traveling salesman problem) ? 影片递送问题(film delivery problem) ? 最小生成树问题(minimum span tree problem) ? 作业调度问题(job-shop scheduling problem) 典型优化问题的模型与算法-R03 5 求解方法分类 ? 从求解方法的大的分类上，可以分为： ? 精确的求解方法 ? 可以得到问题的最优解，对小规模问题适用，当问 题的规模较大时，一般无法在有限的时间内获得问 题的最优解 ? 所以，对于组合优化问题，通常采用的是近似求解 方法。 ? 近似的求解方法，可以进一步划分为： ? 以确保解的精度为目标的方法 ? 以尽可能获得更好解为目标的方法，包括： ? 启发式(Heuristics) ? 亚启发式(Meta-Heuristics) 典型优化问题的模型与算法-R03 6 近似求解方法 ? 以确保解的精度为目标的方法 ? 能保证一定的精度，且成本较低，例如： ?程序所获得的目标函数值和最优解的目标函数值相 比，达到90%或99%以上，而且获得这样的解的成 本不超过获得最优解的成本的10%或20%，这样的 算法是可接受的。 ? 当然，从数学上准确地保证并不是一件简单的 事情 ? 这类近似方法的研究，会产生很多有趣的数学 特征，吸引了很多从事理论研究的学者，从事 这方面的工作。 典型优化问题的模型与算法-R03 7 近似求解方法 ? 以尽可能获得更好解为目标的方法 ? 这类方法侧重于实际应用，有很多方法都是从实用 的角度出发来考虑问题的。 ? 启发式(Heuristics)方法 ? 是基于直观或经验构造的方法。即使我们求解很多的应 用问题，也不会产生精度很差的解，偶尔，对于非常棘 手的问题也许会产生精度很差的解，但一般的场合下， 应该没有问题。 ? 亚启发式(Meta-Heuristics)方法 ? 近年来在启发式方法中，一种被称之为亚启发式的方法 ，得到了广泛的研究，发现了一些较好的求解方法 ? GA就是其中之一，另外还有 TS，SA，PSO等算法。 典型优化问题的模型与算法-R03 8 近似求解方法 ? 亚启发式(Meta-Heuristics) ? 从算法的角度来讲，是指不依赖于特定问题的启发 式算法。 ? 其算法的基本框架被设计成不论对什么样的问题都 具有通用性。 ? 一般情况下，亚启发式算法要比特定问题专用的启 发式算法的解的精度要差。 ? 所以，针对特定的问题，要精心设计特定的算法。 也有人把以邻域有哪些信誉好的足球投注网站为基础的组合优化方法统称为 亚启发式 典型优化问题的模型与算