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

典型问题 组合优化问题 (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)