组合最优化问题.ppt

* 参考书: １．《 现代优化计算方法 》— 邢文训　谢金星 ２．《 非数值并行算法　第一册 　— 模拟退火算法》 　　　　　　— 康立山　谢云等 　组合最优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，该问题可用数学模型描述为： 其中，f(x)为目标函数， g(x)为约束函数，x为决策变量， D表示有限个点组成的集合． 1.1　组合最优化问题 　一个组合最优化问题可用三参数(D , F , f )表示，其中D表示决策变量的定义域，F 表示可行解集合F ??x ? x?D, g(x)?0?，F 中的任何一个元素称为该问题的可行解，f 表示目标函数．满足 f (x?)?min? f (x)? x?F ?的可行解x? 称为该问题的 最优解．组合最优化的特点是可行解集合为有限 点集． 例1.1　o-1背包问题(knapsack problem) 　设有一个容积为b的背包，n个体积分别为ai (i?1,2,?,n)，价值分别为ci (i?1,2,?,n)的物品，如何以最大的价值装包？这个问题称为o-1背包问题．用数学模型表示为： 其中xi ? 1表示装第i个物品，xi ? 0表示不装．此时，D ??0 , 1?n，F为D中满足(1.2)的可行解集． 例1.2　旅行商问题(TSP,traveling salesman problem) 当 dij=dji ,?i,j 时，称为对称距离TSP，否则称为非对称距离TSP．对一般的TSP，它的一种数学模型描述为： 　一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短． 　TSP可分为对称和非对称距离两大类问题． 其中(1.8)中的决策变量 xij=1 表示商人行走的路线包含从城市i 到城市j 路径，xij=0 表示商人没有选择走这条路．i? j 的约束可以减少变量的个数，使得共有n?(n?1)个决策变量. (1.5)要求商人从城市i 出来一次，(1.6)要求商人走入城市 j只有一次.　　　　　　　 (1.5)和(1.6)表示每个城市经过一次．仅有(1.5)和(1.6)的约束无法避免回路的产生，(1.7)约束商人 在任何一个城市子集中不形成回路．此时　　　　　　　　 D ??0 , 1?n??n?1?． TSP问题解的另一种表示法为循环排列 数学模型为： (记 in?1 ? i1 ) 1.2 计算复杂性的概念 　由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问题在实践中并不一定可解。由组合最优化问题的定义可知，每一个组合最优化问题都可以通过枚举的方法求得最优解。枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接受。 　例如对非对称距离TSP问题，可以用另一个方法来表示它的可行解：用n个城市的一个排列表示商人按这个排列序推销并返回起点。若固定一个城市为起点，则需要?n????个枚举。以计算机?秒可以完 成??个城市所有枚举为单位，则枚举时城市数与计算时间的关系如表所示。 　通过表可以看出，随着城市数的增多，计算时间增加非常之快，当城市数增加到??时，计算时间约??.?年，已无法接受。所以，我们必须对计算复杂性理论有所了解，这也是最优化的理论基础。只有了解所研究问题的复杂性，才能有针对性地设计算法，进而提高优化效率。主要简单介绍一下多项式时间算法和指数时间算法。 　一个算法常常是针对一个问题来设计的，而若用计算机求解，则必须对问题中的参数赋予具体值．问题中的参数赋予了具体值的例子称为问题的实例．一个问题通过它的所有实例表现． 　衡量一个算法的好坏通常是用算法中的加，减，乘，除和比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来度量． 　我们对实例的二进制输入长度和算法的基本计算总次数是粗略估计的，一般是给予一个上限．一个求解实例 I 的算法的基本计算总次数 C( I )同实例I 的计算机二进制输入长度d( I ) 的关系常用符号C( I ) ? f (d( I )) ? O(g(d( I )))表示，它的含义是：求解实例 I 的算法的基本计算总次数 C( I ) 是实例输入长度d( I ) 的一个函数，这个函数被另一个函数g(x) 控制，即存在一个函数g(x) 和一个正常数?，使得C( I ) ? ? g(d( I ))　???．其中g(x)的函数特性决定了基本计算总次数 的性能． 　定义1.1　假设问题和解决该问题的一个算法已　　经给定，若给定该问题的一个实例 I，存在多项式　　函数 g(x)，使得???成立，我们称该算法对实例 I 　　是多项式时间算法；若存在 g(x) 为多项 式函数且　　对该问题任意的一个实例 I，都有???