《组合最优化问题.》由会员分享，可在线阅读，更多相关《组合最优化问题.（25页珍藏版）》请在金锄头文库上搜索。
1、参考书:, 现代优化计算方法 邢文训 谢金星, 非数值并行算法 第一册 模拟退火算法 康立山 谢云等,组合最优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，该问题可用数学模型描述为：,其中，f(x)为目标函数， g(x)为约束函数，x为决策变量， D表示有限个点组成的集合,1.1 组合最优化问题,一个组合最优化问题可用三参数(D , F , f )表示，其中D表示决策变量的定义域，F 表示可行解集合F x xD, g(x)0，F 中的任何一个元素称为该问题的可行解，f 表示目标函数满足,f (x)min f (x) xF 的可行解x 称为该问题的 最优解组合最优化的特点
2、是可行解集合为有限 点集,例1.1 o-1背包问题(knapsack problem),设有一个容积为b的背包，n个体积分别为ai (i1,2,n)，价值分别为ci (i1,2,n)的物品，如何以最大的价值装包？这个问题称为o-1背包问题用数学模型表示为：,其中xi 1表示装第i个物品，xi 0表示不装此时，D 0 , 1n，F为D中满足(1.2)的可行解集,例1.2 旅行商问题(TSP,traveling salesman problem),当 dij=dji ,i,j 时，称为对称距离TSP，否则称为非对称距离TSP对一般的TSP，它的一种数学模型描述为：,一个商人欲到n个城市推销商品，每
3、两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短,TSP可分为对称和非对称距离两大类问题,其中(1.8)中的决策变量 xij=1 表示商人行走的路线包含从城市i 到城市j 路径，xij=0 表示商人没有选择走这条路i j 的约束可以减少变量的个数，使得共有n(n1)个决策变量. (1.5)要求商人从城市i 出来一次，(1.6)要求商人走入城市 j只有一次.,(1.5)和(1.6)表示每个城市经过一次仅有(1.5)和(1.6)的约束无法避免回路的产生，(1.7)约束商人 在任何一个城市子集中不形成回路此时,D 0 , 1nn1,TSP问题解的另一种
4、表示法为循环排列,数学模型为：,(记 in1 i1 ),1.2 计算复杂性的概念,由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问题在实践中并不一定可解。由组合最优化问题的定义可知，每一个组合最优化问题都可以通过枚举的方法求得最优解。枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接受。,例如对非对称距离TSP问题，可以用另一个方法来表示它的可行解：用n个城市的一个排列表示商人按这个排列序推销并返回起点。若固定一个城市为起点，则需要n个枚举。以计算机秒可以完,成个城市所有枚举为单位，则枚举时城市数与计算时间的关系如表所示。,通过表可以看出，随着城市数的增多，计算时间
5、增加非常之快，当城市数增加到时，计算时间约.年，已无法接受。所以，我们必须对计算复杂性理论有所了解，这也是最优化的理论基础。只有了解所研究问题的复杂性，才能有针对性地设计算法，进而提高优化效率。主要简单介绍一下多项式时间算法和指数时间算法。,一个算法常常是针对一个问题来设计的，而若用计算机求解，则必须对问题中的参数赋予具体值问题中的参数赋予了具体值的例子称为问题的实例一个问题通过它的所有实例表现,衡量一个算法的好坏通常是用算法中的加，减，乘，除和比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来度量,我们对实例的二进制输入长度和算法的基本计算总次数是粗略估计的，一般是给予一
6、个上限一个求解实例 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 是多项式时
7、间算法；若存在 g(x) 为多项 式函数且 对该问题任意的一个实例 I，都有 成立则称 该算法为解决该问题的多项式时间 算法,当不存在多项式函数 g(x) 使成立时，称相应 的算法是指数时间算法,相比较而言，随着变量的增加，多项式函数增长的速度比指数函数增长的速度要慢得多，因此，我们更喜欢多项式函数 。例如，随着n的增加，nkk 的整数的增长速度远比an a 1为实 数增长的速度慢。,复杂性分析的一个研究方向是对算法进行评价。对于解决一个问题的算法，如何评估这个 算法的性能？复杂性分析是评价算法的一个指标。复杂性分析是通过从最坏实例的条件下，确定是否存在多项式函数 g(x)，即可以叙 述为：对
8、一个求解问题的算法，是否存在多项 式函数 g(x)和常数，使得对问题的任意一个实例I，都有成立。,复杂性分析的另一个研究方向是对组合优化 问题归类。,定义1.3,例1.4,1.3 邻域的概念,对于组合优化问题( D , F , f )，D上的一,个映射：N: SDN(S)2D 称为一个邻域映射，其中2D表示D的所有子集组成的集合， N(S)称为S 的邻域， SN(S)称为S 的一个邻居,例1.2已给出TSP的一种数学模型，由模型,Dxx0,1n(n1)，可以定义它的一种邻域为：,k为一个正整数这个邻域定义使得x 最多有k 个位置的值可以发生变化x 的邻居有,的 TSP问题，当 S =(1,2,
9、3,4)时，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1, 2,4,3).,例1.5 TSP问题解的另一种表示法为,定义它的邻域映射为2-opt，即S中的两个元素进行,定义1.4 若S*满足 f (S*) ( )f (S )，其中， S N(S*) F，则称S*为 f 在 F 上的局部最小(大)解若 f (S*) ( )f (S )， S F，则称S*为 f 在 F 上的全局最小(大)解,例1.6,对o-1背包问题，由模型,Dxx0,1n，可以定义它的一种邻域为：,这个邻域定义使得x 最多有2个位置的值可以发生变化x 的邻居
10、有,启发式算法是相对于最优算法提出的一个问题的最优算法求得该问题每个实例的最优解启发式算法可以这样定义：,一个基于直观或经验构造的算法，在可接受的花费（指计算时间，占用空间等）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计,1.4 启发式算法,因为一些组合最优化问题还没有找到求最优解的多项式时间算法，而这些组合最优化问题又有非常强的实际应用背景，人们才不得不尝试用一些并不一定可以求解到最优解的算法，在此称为启发式算法，来求解组合最优化问题。,例 背包问题的贪婪算法,step1 对物品以ci ai从大到小排列，不妨把 排列记成1,2, ,n，k1；,
11、k k 1 ；当k n 1 时，停止；否则重复step2,(x1, x2, , xn)为贪婪算法所得解单位体积价值比越大越先装包是贪婪算法的原则,这样的算法非常直观，非常容易操作,大规模计算分析,就是通过大量的实例计算,评价算法的计算效果.算法的计算效果分成两个方面:一方面是算法的计算复杂性,它的效果通过计算机的中央处理器(CPU)的计算时间表现;另一个方面是计算解 的性能,它通过计算停止时输出的解表现.,启发式算法的性能分析,对一个算法进行评价时,它的计算时间效果往往通过目前的计算机设备能否承受,用户能否接受现有的计算时间来衡量.对它的计算解进行评价时,一个简单的要求是用户是否满意.,1.5
12、 局部搜索算法,局部搜索算法可以简单的表示为：,假设算法用以解决如下组合优化问题：,其中，f (x)为目标函数，g(x)为约束函数，D定义域,局部搜索算法,Step1 选一个初始可行解x0；记录当前最优解,Step2 当P=时，或满足其他停止运算准则时,xbest:=x0，令P=N(xbest )；,输出计算结果，停止运算；否则，从N(xbest )中选一集合S ，得到S 中的最优解xnow；若 f (xnow)f (xbest)，则 xbest:= xnow， P:=N(xbest )；否则；P:= P S ；重复step2,Step1的初始可行解选择可以采用随机的方法，也可用一些经验的方法
13、或其他算法所得到的解Step2中的集合S 选取可以大到是N(xbest )本身，也可以小到只有一个元素，如用随机的方 法在N(xbest )中选一点,例2.1 5个城市（A,B,C,D,E）的对称TSP数据，对应的距离矩阵为,初始解为xbest（ABCDE）， f(xbest )=45.邻域映射定义为对换两个城市位置的2-opt选定A城市为起点，用全邻域搜索，即S:=N(xbest ),第二循环：N(xbest )=(ACBDE),(ABCDE) (ADBCE),(AEBDC),(ACDBE),(ACEDB), (ACBED), f(x)=43, 45, 44, 59,59,58,43. xb
14、est : = xnow=(ACBDE）,第一循环： N(xbest )=(ABCDE),(ACBDE) (ADCBE),(AECDB),(ABDCE),(ABEDC), (ABCED)，对应目标函数值为: f(x)=45,43, 45,60, 60,59,44. xbest : = xnow=(ACBDE）,此时，P=N(xbest ) S 为空集，于是所得解为(ACBDE），目标值为43局部搜索算法的优点是简单易行，容易理解，但其缺点是无法保证全局最优性因其只按下降规则转移状态,改变局部搜索算法中只按下降规则转移状态的一个方法是蒙特卡罗方法，主要变化是局部搜索算法的第二步为：,Step2 当满足停止运算准则时，停止运算；否则，从N(xbest )中随机选一点xnow；若 f (xnow) f (xbest)，则 xbest:=xnow；否则根据 f (xnow) f (xbest)以一定的概率接受xnow（ xbest:=xnow ）；返回step2,蒙特卡罗算法是以一定的概率接受一个较坏的状态，如可以均匀的概率,蒙特卡罗算法,从N(xbest )中选任意一点，以概率,接受xnow模拟退火算法就是采用这样的搜索方法,
