（计算机软件与理论专业论文）设备定位问题局部搜索算法的分析与实现.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： ：找：遵l 日 期：土副i z 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：她导师签名料日 期：卫删 山东大学硕士学位论文 摘要 n p h a r d 问题是输入规模的多项式时间内无法计算最优解的一类优化问题， 其近似算法设计一直是计算机理论工作的重要内容，相应问题近似方案的设计更 是其中的难点。f a c i l i t yl o c a t i o np r o b l e m 是一个经典的问题，根据不同的限 制条件可以派生出不同的问题，比如u n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ， c a p a c i t a r e df a c i l i t yl o c a t i o np r o b l e m ，k l e v e lu n c a p a c i t a t e df a c i l i t y l o c a t i o np r o b l e m ，k - m e d i a np r o b l e m 等，这些问题都已经证明是n p h a r d 问 题，到目前为止人们已经提出了局部搜索，p r i m a ld u a l ，l p r o u n d i n g ，贪心算 法等近似方案来解决这些问题。局部搜索算法由于其思想简单，在实际应用当中 较为广泛。 本文讨论u f l p 的局部搜索近似算法及其在实际计算中表现出的新性质。 v i j a ya r y a 等的分析方法得到该问题局部搜索算法的近似性能比为3 。本文首先 对局部搜索算法求解多服务中心设置问题的实际近似性能比给出一个针对性分 析结果，然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。 然后编程实现该算法，对局部搜索求解算法的求解时间和求解质量进行了探讨， 主要讨论局部搜索算法中初始解的产生方法，设备价值与服务价值大小对算法求 解性能的影响，最后研究了局部搜索算法的改进方法。实验表明：约有9 9 以上 的实例可直接利用局部搜索算法求得最优解；贪心算法产生初始解的局部搜索算 法求解时间明显短于随机算法产生初始解的方法，但两者求解质量相当；设备价 值和服务价值数值范围越大，局部搜索算法越容易求得最优解。约1 0 的实例可 通过改进局部搜索算法进一步改进解质量。 k r a r u p 与p r u z a n 19 8 3 年证明u n c a p a c i t a t e df a c i l i t y l o c a t i o n p r o b l e m ( u f l p ) 是n p h a r d ，o u h a 与k h u l l e r l 2 1 19 9 7 年证明u f l p 是 m a x 趴俨一h a r d ，并进一步证明该问题不存在近似性能比p 0 和问题厅的任意实例i ，算法爿( s ) 可求出实例，的可 行解，其解值为a ( e ) u ，使得 爿( ) 卅 ( 1 + e ) o p t ( i ) 山东大学硕士学位论文 若7 t 为最大优化问题，则 o p t ( i ) 0 ，一( 占) 是关于问题石实例输入规模的多项式时间算法，则 称爿( 占) 为多项式时间近似方案。 2 3 算法简介 下面简单介绍一下后面要用到的一些算法。 2 3 1 局部搜索算法( l o c a ls e a r c h ) 局部搜索算法是在六，七十年代求解组合优化问题时发展起来的，它的思想 非常简单，就是常说的爬山法。下面是局部搜索算法的一般性描述： p r o c e d u r e l o c a l s e a r c h i n p u t ：一个优化问题实例 o u t p u t ：实例的一个解 b e g i n w h i l e ( t r u e ) x = i n i t i l i z i n gs o l u t i o n ； w h i l e ( 在x 的邻域中存在解x ，并且使得f 伍) f ( x ) ) x 2 x ： i f ( f ( x ) 满足要求) r e t u m ( x ) ； ) ) e n d 在邻域中的搜索方式。常用的搜索方式有贪，i , , 策略( g r e e d ym e m o d ) 和最速 下降策略，贪心策略是指只要遇到比当前可行解好的点就向前走，而最速下降策 山东大学硕士学位论文 略是走到邻域中找到下降幅度最大的点。在后面编程的实现中采用的是最速下降 的策略。 2 3 2 贪心算法 贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以 尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法 停止。 该算法存在问题： l ，不能保证求得的最后解是最佳的； 2 ，不能用来求最大或最小解问题； 3 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发： w h i l e 能朝给定总目标前进一步d o 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 在文章的后面将利用贪心算法得到局部搜索算法的一个初始解，并将这个由 贪心算法产生的初始解与随机产生的初始解进行数据对比。 2 3 3 组合的生成算法 下面来简单的介绍一个从”个数中取出r 个组合，其中r n 。由于组合不同 于排列，与这r 个数的排列顺序无关，所以可以有如下假定 6 】： 1 ) 若，个元素组合用i 表示，可以假定 c l c l ( c 3 4 即c r s 栉，o ，腔一1 ，c ，兰挖，+ 1 或表示为e ”一，+ f ，i = 1 ，2 ，r 2 ) 当存在巳 t - - y + 时，其中下标的最大者设为j ，即 j = m a x jj c ， ”一，+ ，贝0 作o i c ，+ l 山东大学硕士学位论文 c i + | 一c 声i ，c i + 2 一c i 一i ， 有了上面的假设和分析以后 算法描述如下： 初始令c l c ?c ，= 1 2 r 可以得到组合的生成算法。 w h i l e ( c i c 2 c r ( n - h 1 ) ( n r 十2 ) 埘) ( 求满足不等式c i n r + f 的最大的下标i 即 i = m a x j l c j n r + y ) ； 令c i - - - c ，+ l 从i + 1 位开始修改：q 卜q 一1 ，产f + 1 ，i + 2 ，r ) 该算法在后面的编程实现中对全局最优解的寻找中用到。 2 4f a c i l i t yl o c a t i o np r o b l e m f a c i l i t y l o c a t i o np r o b l e m ( f l p ) 就是给定一组客户和设备，设备用来服务客 户，目标是找到一个设备子集来服务客户，使得总的成本最小。下面用两个图来 说明这个问题。 口 选出服务于客户的设备前的图 山东大学硕士学位论文 一上 选出服务于客户的设备后的图 上面的两个图中正方形表示客户，圆形表示设备，一个有七个客户三个设 备。设备是用来服务客户的，从三个设备中选出了两个来服务客户，其中一个服 务四个客户，一个服务三个客户，还有一个没有被选中。 根据限制条件的不同，f a c i l i t yl o c a t i o np r o b l e m 可以演化出不同的问题， 比如：u n c a p a c i t a t e df a c i l i t y l o c a t i o n p r o b l e m c a p a c i t a t e df a c i l i t y l o c a t i o n p r o b l e m ，k - l e v e lu n c a p a c i t a t e df a c i l i t yp r o b l e m ，k - m e d i a n 等问题。下面来简单的 介绍一下这几个问题。 2 4 1u n c a p a c i t a t e d f a c i l i t yl o c a t i o np r o b l e m 有设备集合f = e ，e ，e ，) 和客户集合c = c l ，c 2 ，c n ，设备表示 准备打开的服务中心，打开一个设备e ，需要成本，客户of 0由设备为其提 供服务，一个客户只需一个设备服务即可。客户和设备又分别视为空间中的点， 因此取y = ，u c = v - ，v 2 ，v 。) ，且叶到v ，的距离记为勺。若旷c ，c ， v ，= 巧f ，则勺表示客户c ，被设备f 服务的代价。若选定设备子集s c _ f 为所 有客户服务，则总服务成本为：c o s t ( s ) = 。，+ ，e c 勺( 叫，其中b ) 表 示服务于c ，的设备。欲求个设备集合s f ，打开s 中的设备为所有客户提供 服务，使总的成本最小。若距离满足c p = c ，且。f + 。一，其中v j ，v ，v f u c ， 则称该问题为公制空间的多服务中心设置问题( m e t r i cu r i c a d a c i t a t e d 山东大学硕士学位论文 f a c i l i t y l o c a t i o np r o b l e m ) ，简称u f l p a u f l p 在计算机网络服务器配置；通信站点选择；物流中心确定等实践中 均有重要应用价值。k r a r u p 与p r u z a n 1 1 1 9 8 3 年证明u f l p 是n p - h a r d ，g u h a 与 k h u l l e r t 2 1 1 9 9 7 年证明u f l p 是m a x - s n p h a r d ，并进一步证明该问题不存在近似 性能比p 1 4 6 3 的近似算法，除非| p d t i m e ( n 。“8 ”8 ”) 。人们利用 l p r o u n d i n g ，p r i m a l - d u a l ，局部搜索等技术分别设计了该问题的多种近似求解算 法m 】。目前具有最小近似性能比的求解算法是由m o h a m m a dm a h d i a n 、y i n y u y e 、 j i a w e i z h a n g 3 l 给出的p = 1 5 2 近似算法。我们所知主要的u f l p 求解算法研究结 果见表l ，表中的h = ”r + 甩。 表1u f l p 的近似算法 近似比采用的算法时问复杂度 o ( h an o )g r e e d ya l g o r i t h m o ( n ) 3 1 6l p r o u n d i n g 2 1 4l p r o u n d i n g + g r e e d ya u g m e n t a t i o n 1 7 3 6l p r o u n d i n g 5 + l o c a ls e a r c w o ( n 6 1 。g ( 形) ) 3 i 由c a ls e a r c h 1 8 5 3 p r i m a l - d u a lm e t h o d + g r e e d y a u g m e n t a t i o n o ( n 3 ) 1 7 2 8l p r o u n d i n g + p r i m a l - d u a lm e t h o d + g r e e d ya u g m e n t a t i o n 1 8 6 l g r e e d ya l g o r i t h m 1 6 1 g r e e d ya l g o r i t h m o ( n 3 ) 1 5 8 2l pr o u n d i n g 1 5 2 g r e e d ya l g o r i t h m + g r e e d ya u g m e n t a t i o n o ( n3 ) 山东大学硕士学位论文 2 4 2c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ( c f l p ) 指的是给定一组设备集合和客 户集合，客户由设备为其提供服务，一个客户只需一个设备服务即可。开设每一 个设备需要一个设备成本，设备服务客户也需要服务成本，与u f l p 不同的是每 一个设备只能服务有限的客户。目标是找到一个设备子集来服务客户使得总的服 务成本和客户成本最小，而且选中的设备不能超过其能服务的客户的上限。 下面还是来形式化的描述一下c f l p ，有设备集合f = e ，e ，c ，) 和客 户集合c = 喝，c 2 ，c 0 ) ，打开一个设备c f ，需要开设成本0 ，客户和设 备又分别视为空间中的点，服务成本用客户和设备之间的距离c 。来表示其中 i ，f u c 。对于每一个f f 都有一个容量m ，也就是说该设备只能为至多坼个 客户服务。目标是找到一个设备子集s f 来服务客户集合c ，使得总的开设成 本和服务成本最小，并且选中的设备不能超过其能服务的客户的上限。同样对于 任意的f ，j ，k f u c ， c = c i g c + c 肚c i k 。 c f l p 是n p h a r d 问题，也存在着各种多项式近似算法。s h m o y s ，t a r d o s a r a d a l 8 1 对于该问题给出了5 6 9 的近似算法。c h d a k 和s h m o y s 【9 对于该问题的一 个特例运用l pr o u n d i n g 给出了一个近似性能比是3 的近似算法，该特例假定每 一个设备的容量都是一样的，也就是对于每一个设备f f 都有“= 7 , 。对于一般 的c f l p 问题，j a i n 和v a z i m i 1 0 l 将该问题归约成u f l p , 并且运用p r i m a l d u a l 算法 得到了4 的近似性能比。a r y a t i 等运用局部搜索算法得到了3 7 3 2 的近似性能比。 j a i n ，m a h d i a n 和s a b e r i i “l 得n t3 的近似算法，这个结果后来被提高到了2 8 9 。 m o h a m m a dm a h d i a n ，y i n y uy e ，j i a w e i z h a n g 1 2 于2 0 0 3 年通过将c f l p 转化到 u f l p 得到了2 的近似算法。 山东大学硕士学位论文 2 4 3k - l e v e l u n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m k - l e v e lu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ( k - l f l p ) n 样是给定一组 设备集合和一组客户集合，每一个客户必须被一组有顺序的设备服务，设备的顺 序已经事先定义好了。每一个设备都有一个开设成本，设备服务客户也需要服务 成本，目标还和前面的一样，找到一个顺序设备子集来服务客户，使得总的成本 最小。 下面的这个例图中的矩形表示要被服务的客户，圆形表示设备，这些设备是 分层的，黑色的圆形表示被选出来服务客户的设备，箭头的方向表明了这些设备 的服务顺序。 客户 设备 k l e v e lu o c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m 的一个模型 下面来形式化的描述一下k l e v e lu n c a p a c i t a t e d f a c i l i t yl o c a t i o np r o b l e m 。 有客户集合c 和k 层的设备集合曩，最，e 。 定义p = 最e e f = u ：。f 山东大学硕士学位论文 每一个c 的客户必须被一个k 层的开路p = ( i ，f 2 ，) 尸来服务。开 设每一个f ( 1 r k ) 的设备需要设备成本工。如果客户j c 被一条开路 p = ( ，i ：，k ) p 来服务，那么需要服务成本，并且m c 。+ ：c “，其 中c ，是f 和，之间的距离( f ，j c u f ) 。目标是找到一个设备的集合，使得每 一个客户都被一条开路所服务并且使得总的成本最小。即选择墨c f ， f = 1 ，2 ，七使得萎，。艇曼。r + e 。e 。s z , , 最小。同样对于任意的j ，2 ，u c c v 2c ) i 且c u + c m 2 c t k 。 k l f l p 问题同样也是n p h a r d 问题。a a r d a l ，c h u d a ka n ds h m o y s 1 那运用 l pr o u n d i n g 技术第一次给出了一个3 的近似性能比。对于k l f l p 问题研究最 多的就是当k 等于1 和2 的情况。当k = i 的时候就是上面介绍的u f l p ，在此 不再重复介绍。下面来简单介绍一个k = 2 的情况。 2 - l f l p 是研究比较多的k l f l p 问题，原因是2 l 孔p 问题在两层结构的 供应链中应用较多。对于1 - l f l p 问题的最低下界1 4 6 3 同样可以运用到2 - l f l p 中，并且目前还没有发现更低的下界。d b s h m o y s 。e t a r d o s ，a n dk i a a r d a l 1 4 ) 将解答l - l f l p 问题的算法运用到2 - l f l p 中，并且取得了3 1 6 的近似性能比。 后来a a r d a l ，c h u d a ka n ds h m o y s 13 】运用l pr o u n d i n g 算法对于k 2 的k l f l p 得 到了3 的近似性能比，当然这其中也包括k = 2 的情况。j i a w 西z h a n g 1 5 】于2 0 0 3 年1 0 月份运用类贪心算法( q u a s i g r e e d ya l g o r i t h m ) 对于公制空间的2 l f l p 得 到了1 7 7 的近似性能比，对于非公制空间的2 - l f l p 问题文章给出了d ( 埘h ) ) 近似算法，在这篇文章中还对于3 - l f l p 和4 - l f l p 也分别给出了2 5 1 和2 8 l 的 近似性能比。 2 4 4k - m e d i a np r o b l e m k - m e d i a n 问题是给定一组设备和客户，设备用来服务客户，与前面几个问 题不同的是开设设备不需要成本。k 是一个给定的常数，目标是找到一个设备子 山东大学硕士学位论文 集来服务整个客户，使得总的成本也就是服务成本最小，但是这个设备子集中设 备的数目不能超过k 。 下面来形式化的描述下k m e d i a n 问题。有设备集合f = 何，e ，e ， 和客户集合c = c ，c 2 ，c ) ，客户由设备为其提供服务，一个客户只需一个。 设备服务即可e 取v = f u c = 叶，v 2 ， + n i ，且垮到h 的距离记为咯。若 旷c j c ，v 产f f ，则勺表示客户c j 被设备f 服务的代价。另外有一个输入 常数k ，0 ，n s ( 只) = c 3 ) 。 由于全局最优解里面只有一个设备，所以对于ce s ，将略( e ) 划分成如 下两部分： 墨= n s , ( f y q n s ( f o ) = c 1 ，q - l 墨 2 吃= 虬( c ) n 虬( ) = c 3 ) ，i 吃l = 1 对于性质1 1 ，由于i 囊i _ c o s t g s ) 一o ，( 力一s ，( ，) ( 3 ) x 证：将所有好点得到的不等式( 1 ) 和所有坏点得到的不等式( 2 ) 相加， 可以得到不等式( 3 1 。 定理3 1 ：给定u f l p 实例，为u f l p 实例的某个最优解，s 为该实例的一 个局部最优解，c o s t ( s ) 表示设备集合s 的总的成本，c o s t ( s ) 表示设备集合s 的总的成本，x 如前定义，则有： ( a ) 如果c o s t ，( s ) 一一o ， xx ( b ) 如果c 。s “s ) _ z 。o ，r ( j ) - - 莩n 。且；。，专c 。s ( s ) ， 则 磐2 + 土。 c o sr 岱12 ” 证： ( a ) 如果c o s t ，( s ) 一o 砌) 一0 ，则由( 3 ) 可以得到 xx c o s t ，( s ) 蔓c o s t ，( s + ) + c o s 气( s ) 综合上式以及由引理3 1 ( a ) 可以得到 c 。s ，( s ) + c o s t , ( s ) 2 ( c 。s 。( s ) + c o s c ( s + ) ) ，故可以得到器2 。 山东大学硕士学位论文 ( b ) 若c 。s ( 回一莩。州，一事。， 。且莓，广专c 。s ( s ) 。 因为c o s t , ( s ) - s 删) o ，所以由( 3 ) 可以得到 c 。s t f ( s ) c 。s t ( s ) + ( 1 + 争c 。s ( 趵 综合上式和引理3 1a ) 中的服务成本的不等式可以得到吾蠹鬟务s 2 + 专 在定理3 1 中，c x 表示被局部最优解s 服务的客户集合与被s 扑获的设 备服务的客户集合的交表示除此剩下的客户集合。c o s t , ( s ) 一o r ( ) 一( 力 xx = k ( n 一( 力表示c 一石中的客户在局部最优解s 中的服务成本与z 中的 c xx 客户在全局最优解中的s 服务成本的差。定理的条件无法验证，但是下面的编 程实验结果表明，在很多情况下该定理中的条件总是满足。 山东大学硕士学位论文 第四章局部搜索算法的实现与求解实验 本章通过实验研究初始解对最终局部搜索结果的影响。初始设备集合s 采 用两种方法产生：( 1 ) 一种是随机算法产生；( 2 ) 另一种是采用简单的贪心算法产 生。实验结果表明，后一种方法获得可行解的总体计算时间快于前一种方法总体 计算时间。在进行的3 6 次实验中，只有3 次用随机算法所用的时间比用贪心算 法所用的时间少，而且这3 次中两者相差不大。另外，这两种方法求得解的质量 几乎没有差别。若局部搜索修改s 的操作为“增加、删除、交换一个设备”，对 用 2 0 的3 0 0 0 多个实例的实际运算结果显示：方法( 1 ) 有9 9 8 9 的实例可直接得 到最优解，方法( 2 ) 有9 9 7 8 的实例可直接获得最优解。其中，方法( 1 ) 求解得到 三个最坏实例的近似性能比为：1 1 5 ，1 1 ，1 1 。方法( 2 ) 得到三个最坏实例的近似 性能比为：1 1 2 5 ，l ，0 9 ，1 ，0 2 9 。v i j a y m y a 等给出上述算法近似性能比的理论值 为3 。实验结果显示，先利用贪心算法获得初始解，再利用局部搜索得到最终 可行解的方法是求解u f l p 速度快的一种实用计算方法。 4 1 实例生成 对- t c 。是对称的并且满足三角不等式这两个条件，用字符串的海明距离 来实现。具体做法是：随机产生_ 和以个只包含a ，b 的字符串作为设备字符串 和客户字符串，计算这些字符串之间的海明距离作为设备客户点之间的距离。很 容易证明这样产生的距离是对称的并且满足三角不等式。 4 2 初始解产生与全局最优解的求解 解s 。 ( a ) 随机算法 随机算法就是从设备集合，中随机生成一个设备集合作为局部搜索的初始 具体实现是：随机产生一个小于设备数量的整数 ”r ，然后再从这”，个 山东大学硕士学位论文 设备中随机的选出n 个作为初始解。 ( b ) 简单的贪心算法 简单的贪心算法的具体的实现是：将设备成本，按照从小到大的顺序排 列。让f c o s t ，和c c o s t , 分别表示前i 个设备的设备成本和服务成本。从i 一直计 算到”，找出其中的f c o s t , + c c o s t , 最小的设备集合作为初始解s 。 全局最优解的求法采用的是穷举法，即采用组合的生成算法一一列举所有 组合，然后算出每一种组合的总的成本，找出其中的最小值0 1 。时间复杂度是 o ( n 0 2 i o 目前我们所具备的试验环境，当旧立o ，可在适当时间内求得u f l p 最优 解。当实例规模再增大时，因求解时间太长，无法进行最优解求解试验。 4 3 实验数据 编程环境 硬件环境：联想开天4 6 0 0 ，c p u 为p 4 一1 9 g ，内存为2 5 6 md d r ，硬盘为6 0 g 。 软件环境：w i n 2 0 0 0 + v c 6 0 4 3 1 初始解对局部最优解的影响 ( 1 ) 求解质量 在这部分采用的设备数量和客户数量都比较小，所以可以求得全局最优解。 将局部最优解与全局最优解比较可知道局部最优解的优化程度。 在实验中，几乎每次得到的局部最优解值和全局最优解值都是相等的，为 了对贪心算法和随机算法产生的初始解对局部搜索解的最终影响进行比较，这里 采用另外的一种方法来进行比较，具体的做法是：先随机产生一个实例，求得局 部最优解和全局最优解，如果两者相等，则重新产生，如此反复，直到找到第一 次局部最优解和全局最优解不相等的实例，记录产生的总的实例次数。总的次数 越大说明该局部搜索算法越好。随机算法和贪心算法分别作为初始解的实验数据 山东大学硕士学位论文 见表2 和表3 表2 随机算法作为初始解( m - 位次) f 设祷幻。 第幸e第二轮第里轮第2 嘞第i 粥黼第博e并耵啦第九轮黼 平均 【5 * 5 1 62 蝤3 8 45 1 03 3 7 3 4 0 4 1 51 5 38 7 4 4 5 8吼2 1 0 1 0 3 8 21 5 1 3凹8 6 1卵4 4 1瞄 4 23 2 78 9 45 0 5 1 5 1 5 5 63 。21 5 01 4 8 1 1 1 79 4 3 8 2 21 丝l 2 0 * 2 0 71 63 91 91 885 8昕5孤9 表3 贪心算法作为初始解( 单位次) 设备客户第一轮第二轮第三轮第四轮 第五轮第六轮 第七轮第八轮第力轮第十轮平均 5 芍1 1 1 31 8 8 26 1 2搠 7 9 71 0 7 89 4 62 9 田1 3 4 51 6 8 41 5 2 0 1 0 幸1 01 3 8 31 3 8 l2 9 0 61 2 2 81 5 29 6 41 1 1 61 5 8 5 8 4 61 5 4 1 1 3 1 n 2 1 5 1 5 7 95 3 53 26 23 3 5鹄2 8 79 2 4 6 9 5 8 32 5 2 2 0 嘲 5 8 3 3 1 653 91 03 73 42 56 23 1 _ 9 将上面两个表得到的数据的平均值进行比较，可以得到下面的图表。 上面两表中，0 c 。2 0 ，0 sfs 2 0 ，其中5 * 5 等分别表示5 个设备和5 个客 户。对于5 * 5 ，1 0 + 1 0 ，1 5 1 5 ，2 0 * 2 0 用随机算法和贪心算法作为初始解分别进 行了1 0 轮实验，然后求平均值。对于设备数量和客户数量是5 * 5 ，1 0 1 0 ，1 5 1 5 ， 2 0 * 2 0 用随机算法作为初始解分别有9 9 7 3 2 ，9 9 8 0 1 ，9 9 1 8 1 ，9 6 2 8 2 可以求 到全局最优解，用贪心算法作为初始解分别有 9 9 9 3 1 ，9 9 ，9 2 4 ，9 9 6 0 9 ，9 6 8 3 5 可以求到全局最优解。从实验数据不难看出， 对于同样数量的设备和客户贪心算法的次数总是大于随机算法的次数，上面数据 说明，用贪心算法产生的初始解的局部搜索求解算法要优于用随机算法产生的初 始解的求解算法。上面的求解试验只是针对设备客户数较小的u f l p 实例进行 的，当实例规模增大时，受试验环境限制，无法进行十分确切的计算实验。 山东大学硕士学位论文 下面给出一个近似性能比是1 3 3 3 的实例，见下图l ： 图l 近似性能比是1 3 3 3 的实例 三个设备的设备成本分别是1 、1 和2 ，服务成本见图中的标注，设备和客 p 2 _ r 目j 的距离是对称的并且满足三角不等式。很容易计算全局最优解是 e ，e ) ， 总的成本是3 ， e ) 是其中的一个局部最优解，总的成本是4 。本例中允许的操 作是增加、删除和交换一个设备。 下面迸一步利用规模较小的u f l p 实例验证定理3 1 中的条件是否满足。若 局部搜索已经求得最优解，则定理3 。l ( a ) ( b ) 两结论的条件必然满足。所以利用 局部最优解和全局最优解不相等的实例验证定理2 1 条件，我们在此只验证结论 ( a ) 的条件。在约i 0 0 0 个局部最优解和全局最优解不相等的实例中，利用程序验 证条件，有7 5 的实例满足定理3 1 中c o s t ，( s ) 一0 州) 一( ) 0 的条件。 ( 2 ) 计算速度 在下面的这些实例中，取o 勺 2 0 0 ，0 s z 2 0 0 ，其中勺表示设备墨服务 于q 的服务成本。z 表示第f 个设备f 的设备成本。 对于初始解的产生，分别采用随机算法和贪心算法产生。实验的数据见 表4 。表中的1 0 0 + 5 0 0 等表示1 0 0 个设备，5 0 0 个客户。每一次随机算法和贪心 算法都是对相同的实例进行计算。 山东大学硕士学位论文 表中的“局部最优解”指的是用随机算法和用贪心算法求得的局部最优解 s 的总的成本c o s t ( s ) ，“运行时间”是指用随机算法和用贪心算法产生的初始 解的整个局部搜索算法运行的时间，单位是秒。 在进行的3 6 次实验中，只有3 次随机算法比贪心算法所用的时间短，而 且只有一次随机算法求得的局部最优解好于贪心算法，其余两种都是相等的。从 上面的数据对比不难看出用贪心算法比用随机算法产生的初始解求解速度要稍 快，质量上两者相差不大。 表4 初始解为随机算法和贪心算法的总的运行时间( 时间单位是秒) 翊亍日排* 物局鲰黜迳f 剥f 目鼢 局部最日懈运砷 局郎爱口懈 赍山僦n责d随帆负心随帆赍厶随机贪0随帆负b随帆 1 0 0 * 5 0 0l98 5 9 9 8笈渤23 58 6 1 3 8 78 。3 田42 58 2 7 驷渤 l o f f 1 0 0 045 51 6 3 0 6 21 6 3 0 6 23 2 8 1 6 4 3 1 91 6 4 3 1 91 04 71 7 0 8 0 81 7 1 0 f f 1 5 0 09 3 1 2 02 5 1 葛l2 5 1 3 8 l 2 49 72 4 娥 2 4 7 0 8 24 5 7 3捌聊 2 船新 1 0 伊。02 71 3 73 3 1 6 6 53 3 1 6 6 5国1 0 73 2 3 3 6 63 2 3 3 6 6 2 l1 1 8 3 3 0 8 5 63 3 0 8 5 6 1 5 0 * 5 0 01 51 2 58 0 1 8 s印1 8 5 1 l 1 1 58 6 4 1 28 6 4 1 251 9 28 1 6 8 18 l 鹋l 1 5 0 * 1 0 0 。 3 2 2 5 21 6 3 2 9 81 6 3 2 9 b 3 4 1 71 6 7 6 7 41 6 7 6 7 41 44 01 6 8 2 7 61 6 8 2 7 6 1 5 0 * 1 5 0 04 5 4 6 箱0 6 5 72 5 0 嘟 1 9 4 7 6别3 9 3 12 4 3 9 3 l2 24 5翻剁 1 5 0 * 2 0 0 08 46 0 93 3 3 2 9 83 3 3 2 孵拼8 2 8 茁0 0 。13 2 8 0 0 l1 田3 4 23 3 4 9 6 l麓雠1 2 0 铲5 0 01 8弘剖3 2 28 4 3 2 23 51 1 58 4 2 8 68 4 2 8 61 54 7 38 5 7 4 l8 5 7 4 l a 0 0 1 0 0 0 8 6 鹄1 6 2 1 8 41 6 2 1 8 i 6 9 西陵嚣姐翦 1 2 19 鹃1 6 5 6 0 51 6 5 6 0 5 2 0 泸1 5 0 01 5 6 1 0 8 0 2 4 9 6 2 92 4 9 6 2 94 11 7 陆2 5 哪2 5 附丌 1 4 64 3 32 剖 2 。+ 2 0 。5 8 57 鹋3 2 蝴5篮4 3 7 5l o l2 5 6 b3 嬲 3 苍6 8 31 1 4l l 筠 3 3 田7 23 簧脱 4 3 2 设备价值s h i l l 务价值的大小以及比值对于解的影响 同样采用3 3 1 中的方法，即求得第一次局部最优和全局最优不相等的次数。 ( 1 ) 设备价值和服务价值的大小对于解的影响 在本次实验中0 吒k ，0 ，蔓k ，设备和客户的数量固定为2 0 。不同的 k 的值对于解的影响见下面的表5 。 表5 设备价值和服务价值的大小对于解的影响( 单位次) 卜第吨第二抡第弓沦觥第醋凳娥黜射抛第燧剿 平均 1 0 3 3 04 1 2砑2 5 31 0 4 9 1 5 8 9弱94 刀9 4 6 1 8 5 3 6 5 0 3 3 51 7 91 1 图 1 7 9 6 g 。 2 7 1 92 研 2 1 1l 猫1 躺l 盈也7 1 0 。1 5 2 6 l 唧4 0 2 4 6 6 0 6 。凹姗 2 0 l o 1 3 3 d1 2 盯1 踊2 2 5 1 3 1 5 0 1 1 0 鹚l a 6 22 4 5 l3 3 8 4 6 1 5 3硒l2 1 0 2 3 6 6 62 2 3 l2 5 “姗2 2 。01 1 2 1 22 4 5 9础 7 0 7 07 7 2 4 4 2 8 27 2 3 羽砣3 6 唾02 1 9 24 9 1 6 4 2 5 。1 彻1 0 1 3 98 7 0 7 1 5 7 94 锄 8 5 蛹1 1 0 1 7 1 0 5 17 8 6 31 8 9 65 6 7 9 8 山东大学硕士学位论文 为了更直观的看到不同k 值对于解的影响，将1 0 轮数据得到的平均值作图 表表示如下： 对于不同的k 值，每次都进行l o 轮实验然后求得平均值，从上面的数据可 以看出，随着k 的增大，次数也增大，也就是局部最优解和全局最优解越来越容 易相等。这一实验同时表明，当设备价值与服务价值同时增大时，利用局部搜索 算法求不到最优解的实例越来越稀疏，或求解难度越来越小。 ( 2 ) 设备价值和服务价值的比值对于解的影响 再讨论设备价值和服务价值的比值对于解的影响，设备数量和客户数量还是 固定到2 0 ，服务成本的取值范围是0 c 。女，其中七= 2 0 0 。设备成本分别取 0 ，s 0 i k ，o i k ，0 2 k ，o 9 k z i k ，具体的数据见表6 。 表6设备价值和服务价值的比值对于解的影响( 单位次) 心第轮篱= 轮第罩轮第四轮第五轮第内轮第七轮甓，性第九轮第十轮平均