（计算机应用技术专业论文）局部搜索算法的改进及其应用.pdf

上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名： 一 日期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 上海大学硕士学位论文 摘要 避二卜年慕，焉聱搜索算法在各令矮域戆蔽羯 骜广泛，黪裂是锋对一些 比较复杂的优化问题。局部搜索算法的主要优点在于它燎一种比较通用的优化 簿法，以跷鞍方便适应翔予翼体的诺纯阔遂。藕且蜀鄢攘索算法翡运行对阉 和优化程度可以由用户通过参数来控制，因此用户可以根据自己的要求沫定制 适合自己的局部搜索算法。根据局部搜索算法的上述特点，允许了一些非算法 专家的用户比较方便地利用各种局部搜索算法钵对自融地特定问题在霹行的 时间内求得合理的优化解。 瞧怒传绞戆弱部搜索算法墩存在罄一些骧鬣缺隆，爨主要豹裁是传统装弱 部搜索算法在优化过程中容易陷入局部鼹优。尽管一些周部搜索算法采用了一 蓬籍臻豹策硌糸避免陷入蜀部簸饶，毽怒当滔爨溪模，笺杂度琵较大静清况下 这些算法还是会不可避免地陷入局部最优。易于陷入局部最优这一缺点使得传 统的焉都援索算法一般缀难实观商效静优化。 本文正是针对传统髑部搜索冀法的缺点，创新地将多邻域搜索的思想加入 传统的尉部搜索簿法中，即在算法的搜索过程中按照一定策略，在多个不同的 邻域结技内进行不颤黪甥换，这襻不仅可以避免在一令邻域结构内易于骧入局 部最优的情况，而且还w 极大地提高局部搜索算法在解空间内的搜索能力。我 镅将这琴申瑟熬竭罄接索耱法稼为基于多邻城懿弱罄援素冀法( m n b l s ) ，壤搭 多邻域搜索和传统局部搜索算法结合方式的不同，基于多邻域的局部搜索算法 可馥努两两大爽：内嵌式多邻城羯部援索算法和混合式多邻域蠲部援豢算法。 内嵌式多邻域局部搜索算法又可分为：单路内嵌式多邻域局部搜索算法和多路 内嵌式多邻域髑部搜索算法；潜台式多邻域局部搜索算法也可辫细分为：非交 换型混合多邻域局部搜索算法和交换型混合多邻域局部搜索算法。 为了测试基于多邻域的局部搜索算法的优化性能，我们引入时间表问题作 为我翻艴测试霹象。蓄受我们跨餐穗传绞弱蕈邻壤禺部攘索篓法，跑鲡聪由法、 模拟退火算法、禁忌搜索算法应用于时间表问题；接着将上述各种基于雾邻域 豹裁部接索算法应嗣予辩闯表秘题，试验结莱表翻基于多邻域静局部疆索算法 的优化性能远近优于传统的单邻域局部搜索算法；最后分析了产生优化性能差 上海大学硕士学位论文 异的原因以及各种基于多邻域的局部搜索算法的并行方案。 在本文的惹艏，我们系统地介绍了繁予多邻域酶局部援索算法中需簧继续 研究的些内容，这些内容既涉及理论方面也涉及应用方面。 本文的主要贡献有以下四点： 1 1 总结了糖类是郝搜索算法鲍饯缺点，讨论了各秘局部搜索算法的统一 框架和并行化问题。 2 ) 将多搜索穰域熬愚怒妻鬟入蜀聱羧素算法，提窭了霉耪不圈结秘的墓于 多邻域的局部搜索算法。 3 ) 将瑟穆不同结构的蓥予多邻蠛的局部搜索算法畿稻子嚣孝润表瀚题，并 形成了一个可以实用的时间表软件。 4 1 提出基于多邻域的局部搜索算法未来的研究方向。 关键字：基于多邻域的局部搜索算法，并行算法，混台算法，时间表问题， 羼罄接褰舞法 2 上海大学硕士学位论文 a b s t r a c t l o c a ls e a r c ha l g o r i t h m sb e c a m ev e r yp o p u l a ri nt h el a s tt w od e c a d e sa n da r e v e r yo f t e nu s e dt o t a c k l e c o m p l e xp r o b l e m sa r i s i n gf r o mp r a c t i c e t h e i rm a i n a d v a n t a g ei st h a tt h e ya r eg e n e r a lp u r p o s em e t h o d sw h i c h c a nb er e l a t i v e l ye a s i l y a d a p t e d t oac o n c r e t eo p t i m i z a t i o np r o b l e m f u r t h e r m o r e ，t h e i r r u n n i n gt i m ec a n b e v a r i e db yt h eu s e ra n d ，t h u s ，t h er u n n i n gt i m em a yb ea d a p t e dt ot h ec o n c r e t e c i r c u m s t a n c e si nw h i c ht h em e t h o di sa p p l i e d t h i sa l l o w se v e nn o n - e x p e l st o a d a p tl o c a ls e a r c h t og e ts o l u t i o n so fr e a s o n a b l eq u a l i t yi nr e a s o n a b l et i m e ， b u tt h em a i nd r a w b a c ko f t h e s et r a d i t i o n a ll o c a ls e a r c ha l g o r i t h m si st h a t 也e y h a r d l ye s c a p e t h el o c a lm i n i m u m s o l u t i o n s a l t h o u g h c e r t a i nl o c a ls e a r c h a l g o r i t h m se m p l o ys o m es p e c i f i cm e c h a n i s m sf o re s c a p i n gt h e m ( 1 i k es i m u l a t e d a n n e a l i n ga l g o r i t l m ao rt a b us e a r c ha l g o r i t h m ) ，t h er e s u l t so fs o m ee x p e r i m e n t s i n d i c a t et h a tt h e s es p e c i f i cm e c h a n i s m sa r en o tv e r ye f f e c t i v ew h e np r o b l e m sa r e v e r yc o m p l e x no r d e rt oo v e r c o m et h ed r a w b a c k ，w ec o m b i n et h et r a d i t i o n a l o c a is e a r c h a l g o r i t h m sw i 嫩m u l t i p l es e a r c hn e i g h b o r h o o d s w ec a l l t h e i m p r o v e dl o o m s e a r c h a l g o r i t h m sm u l t i p l en e i g h b o r h o o d s b a s e dl o c a ls e a r c h a l g o r l t h m s ( m n b l s f o r s h o r 0 。w e a l s od i s c u s sh m v m u l t i p l e s e a r c h n e i g h b o r h o o d sc a nc o m b i n ew i t hl o c a ls e a r c ha l g o r i t h m se f f e c t i v e l y a n dw e c l a s s i f yt h em n b l s i n t of o u rs u b c l a s s e sb yt h ec o m b i n a t i o n sw a yo fm u l t i p l e s e a r c hn e i g h b o r h o o d sa n dt r a d i t i o n a ll o c a ls e a r c h a l g o r i t h m s i no r d e rt od e m o n s t r a t et h eo p t i m i z a t i o np e r f o r m a n c eo fm n b l s ，w e a p p l y m n b l st ot i m e t a b l ep r o b l e mw h i c hi sa t y p i c a l n p h a r dc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m w ed e s i g na n di m p l e m e n ta l lf o u rk i n d so fm n b l s f o rt h e t i m e t a b l e p r o b l e m 。b y t h e e x p e r i m e n t s r e s u l t s ，w e f i n d t h em n b l s s o p t i m i z a t i o np e r f o r m a n c ei sv e r ys a t i s f i e dc o m p a r e dt o o t h e ra l g o r i t h m s a n d m n b l si s s p e c i a le f f e c t i v e i n f i n d i n gt h eo p t i m a ls o l u t i o nf r o ma l le n o r m o u s s e a r c hs p a c e a tl a s tw ed i s c u s st h ed i f f e r e n c e so ft h ef o u rk i n d so fm n b l s b y t h e 1 上海大学硕士学位论文 e x p e r i m e n t sr e s u l t s a t l a s t ，w e i n d i c a t e st h ed i r e c t i o n sf o rf u r t h e r r e s e a r c h ，i n c l u d i n g t h e c o m b i n a t i o nb e t w e e nm n b l sa n dg e n e t i c a l g o r i t h m ，a d d i n g t h e p e r t u r b a t i o n o p e r a t i o ni n t ot h em n b l s a n ds o m et h e o r yr e s e a r c h sd i r e c t i o n so f m n b l s t h em a i nc o n t r i b u t i o n so f t h et h e s i sa r e ： 1 ) s u m m a r i z i n gt h et r a d i t i o n a l l o c a ls e a r c ha l g o r i t h m sd r a w b a c k sa n d d i s c u s s i n gt h ef u n d a m e n t a lf r a m ea n ds o m ep a r a l l e l i z a t i o nm e t h o d so f l o c a ls e a r c h a l g o r i t h m s 2 ) p r e s e n t i n g an o v e li m p r o v e dl o c a ls e a r c ha l g o r i t h m s ：m n b l s 3 ) a p p l y i n g m n b l st ot h et i m e t a b l ep r o b l e m s u c c e s s f u l l y 4 ) i n d i c a t i n g f o u rd i r e c t i o n sf o rt h ef u r t h e rr e s e a r c ho fm n b l s k e yw o r d s ：m u l t i p l en e i g h b o r h o o d sb a s e dl o c a ls e a r c ha l g o r i t h m s ，p a r a l e l l a l g o r i t h m ，c o m p o s i t ea l g o r i t h m ，t i m e t a b l ep r o b l e m ，l o c a ls e a r c ha l g o r i t h m s 4 上海大学硕士学位论文 第l 章绪论 人类在认识大自然，改造大自然的过程中，遭遇到了棘手的n p h a r d 问题， 人们在解决这类问题时显得那么苍白无力。近似算法的出现使这一糟糕的情况 得到了改观，d o r i th o c h b a u m 在他的文章“a p p r o x i m a t i o na l g o r i t h m sf o r n p h a r dp r o b l e m s ” 1 中是这样描述近似算法的：对于n p h a r d 问题，没有 一个确定性算法可以在多项式时间内给出最优解，而近似算法可以在有限时间 内，给出问题的一个近似最优解。 本文研究的内容正是一类近似算法一一局部搜索算法( l o c a ls e a r c h a l g o r i t h m s ) 。局部搜索算法的框架是这样的：从一个初始解出发，利用邻域 函数持续的在当前解的邻域中搜寻一个解来取代当前解，然后重复上述过程直 至满足算法的停止条件。迄今为止，很多种有效的局部搜索算法被提出，比如 模拟退火算法，禁忌搜索算法等，这些算法的全局收敛性都已经被证明了，但 是全局收敛的条件十分苛刻，甚至是不可能的，尽管如此局部搜索算法依然可 以在多项式时间内找到问题的近似解。自从局部搜索算法的概念被提出后，各 种局部搜索算法就不断的被提出，应用也很广泛： 最早的一种局部搜索算法是k o p tr o u t i n e ，被l i n 提出并用来解决旅 行商问题( t r a v e l i n gs a l e s p e r s o np r o b l e m ) 2 3 1 9 8 3 ，一个里程碑式的局部搜索算法一模拟退火算法被 k i r k p a t r i c k ，g e l a t t 和v e c c h i 提出 4 ，模拟退火算法的出发点是基 于物理中固体物质的退火过程于一般组合优化问题之间的相似性，模 拟退火算法和以往的局部搜索算法相比最大的特点就是它允许概率的 接受恶化解。模拟退火算法最早被k i r k p a t r i c k 应用于电路设计中的 优化问题，随后更多的研究者将模拟退火算法应用于其它的问题。关 于模拟退火算法最近的应用，可以参见 5 1 9 8 6 ，g l o v e r 首先提出了禁忌搜索算法 6 7 ，并将禁忌搜索算法应 用于组合优化。生产调度，机器学习，电路设计等邻域。禁忌搜索算 法通过引入一个灵活的储存结构和相应的禁忌准则来避免迂回搜索， 并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有 上海大学硕士学位论文 效搜索以最终实现全局优化。 虽然上述的这些局部搜索算法取得了巨大的成功，但是不可否认，这些局 部搜索算法还存在一定的缺陷，尤其遇到具体问题更需要作具体的分析和改 进。这些局部搜索算法一直在被不断的改进一些成功的改进包括：在局部搜 索算法运用不同的邻域解产生操作 8 9 ；在局部搜索算法运用动态的解评估 函数 1 0 1 1 ：在局部搜索算法运用改进的新解产生和接受准则 1 2 。关于近 年来的局部搜索算法的一些改进策略的综述见 1 3 上述的改进策略可以使局部搜索算法在解决不同问题时变得更有效，但是 这些改进后的局部搜索算法还是基于单邻域的，也就是说它们在整个迭代的搜 索过程中，只在一种邻域结构内对问题的解空间进行搜索。单邻域的局部搜索 算法存在着一些缺陷，比如说有的邻域结构并不能覆盖整个解空间，也就是说 在整个搜索过程中有些状态是不可达的；另外尽管一些单邻域的局部搜索算法 采用了一些策略来避免陷入局部最优，但是在一些情况下这些算法还是会不可 避免地陷入局部最优。尤其当问题规模，复杂度比较大，那么基于单邻域的局 部搜索算法一般很难实现高效的优化。 本文正是针对传统局部搜索算法的缺点，创新地将多邻域的思想加入传统 的局部搜索算法中，形成了基于多邻域的局部搜索算法。为了测试基于多邻域 的局部搜索算法的优化性能，我4 f jz j 入时间表问题作为我们的测试对象。试验 表明在试验数据规模大的情况下，基于多邻域的局部搜索算法的优化性能要远 远优于传统的局部搜索算法。本文的结构如下： 在本文的第一章和第二章中，我们首先介绍了局部搜索算法的历史，相关 概念和它的一些应用实例。接着我们介绍了局部搜索算法中最典型的三种算 法：爬山法，模拟退火法和禁忌搜索法，这三种算法分别对应着三种不同的算 法设计理念：简单，基于概率和有记忆特性。在这两章的最后，我们讨论了局 部搜索算法的统一框架和并行局部搜索算法的实现方案。 在文章的第三章中，首先我们介绍了传统局部搜索算法的一些缺点。其主 要的缺点就是在问题比较复杂，规模比较大的情况下，局部搜索算法很容易陷 入整个问题解空间中的局部最优解。为了克服这传统局部搜索算法中主要的 缺陷，我们将多邻域搜索的思想融入传统的局部搜索算法。我们称这种改进后 上海大学硕士学位论文 的算法为：基于多邻域的局部搜索算法( m - n b l s ) 。在这一章的第二部分中， 我们讨论了几种将多邻域搜索和传统局部搜索算法结合起来的方式，并按结合 方式的不同将基于多邻域的局部搜索算法分为四个小类。在这一章的最后，我 们给出了基于多邻域的局部搜索算法几种可能的并行方式。 在第四章中，为了验证基于多邻域的局部搜索算法的优化性能，我们将 基于多邻域的局部搜索算法应用于一个典型的n p 难的组合优化问题时间 表问题。在这一章中我们做了大量的编程和试验的工作，首先我们就时间表问 题设计和实现了四种不同的基于多邻域的局部搜索算法和各种传统局部搜索 算法。通过多组实验数据，我们发现基于多邻域的局部搜索算法的优化性能要 比各种传统局部搜索算法好的多。同时通过观察四种不同的基于多邻域的局部 搜索算法的实验数据，我们还发现了这四种基于多邻域的局部搜索算法之间的 一些差异。 在本文的最后，我们提出了基于多邻域的局部搜索算法中一些需要进一 步试验和研究的地方，包括：将基于多邻域的局部搜索算法和遗传算法结合起 来；在基于多邻域的局部搜索算法中加入扰动操作；一些关于基于多邻域的局 部搜索算的理论研究方向；建立网格非数值计算平台。 上海大学硕士学位论文 第2 章局部搜索算法 2 1 局部搜索算法简介 随着近些年来工业的发展，各类优化问题变的越来越突出。局部搜索算法 1 4 1 5 是一类可以有效解决优化问题的通用算法。它的基本原理是在邻近解 中迭代，使目标函数逐步优化，直至不能在优化为止。局部搜索算法用法灵活， 适用面广，能求解各类的组合优化问题，并能在有限时间内给出较好的优化解。 局部搜索算法可以这样描述：假设问题的解空间表示为s ，局部搜索算法 从一个初始解i s 开始，然后根据具体问题定义的具体邻域结构，在当前解 i 的邻域s i 内按一定规则找到一个新解，再用这个新解取代i 成为当前解， 判断是否满足算法结束条件，如不满足再对当前解继续使用算法，如满足则算 法结束，当前解就作为算法的最终解。 纵观上述算法流程，局部搜索算法具有以下特点 1 4 ： 1 算法结构通用易实现。只要定义好具体问题相关的邻域，就能有效的 求解该问题。 2 算法性能和领域的定义以及初始状态有关。邻域定义的不同或初始状 态选取的不同会对算法的性能产生决定性的影响。 3 算法的局部优化特性。算法容易陷入局部最优，达到全局最优比较困 难。 局部搜索算法主要包含五大要素： 1 目标函数：用来判断解的优劣。 2 邻域的定义：根据不同问题，有着不同的邻域定义。 3 初始解的产生规则 4 新解的产生和接受规则 5 算法的终止准则 其中前两个要素的定义和算法要解决的特定问题有关，而且不同的人对同 一问题可能会有完全不同的定义。后三个要素定义的不同则会产生各种不同的 局部搜索算法，而它们的效率和最终解的质量也会有很大的差异。现在流行的 上海大学硕士学位论文 几种局部搜索算法其实就是在后三个要素定义上各不相同，导致产生各自的优 点和缺点。下面将介绍现在比较流行的几种局部搜索算法的流程，参数的选取， 以及它们的并行化。 2 2 几种经典的局部搜索算法 2 2 1 爬山法 爬山法 1 6 的主要特点只接受比当前解好的或相等的解作为当前解，这里 所谓解的好或相等是根据问题的目标函数的值的大小来判断的。爬山法初始接 的产生一般是随机的。爬山法新解的产生规则可以是在当前解的邻域内随机选 取或选取最优的，而后者会比较耗时。爬山法算法的终止准则般有三种a 算法总的迭代次数达到一定数目b 最优解没有更新的迭代次数达到一定数目 p r o o e d u r eh ic l i m b i n g c h o o s ea ni n i t i a is o l u t i o n ； w h i l e n e i g h b o r h o o do ft h ec u r r e n t s o l u t i o nc o n t a i n sab e t t e rs o l u t i o n1 3 0 c h o o s et h eb e s ts o l u u o n 仃o mt h en e i g h b or h o o do f t h ec u r r e n ts o l u t i o na n dm o v et ot h i ss o l u u o n n e n dh i l ic l i m b i n g 图2 一l 爬山法的算法框架 c 当前解的目标函数达到一定的值。该方法的主要优点就是可以在短时间内给 出解，缺点是该算法极容易陷入局部最优。图2 - 1 以伪代码的方式描述了爬 山法的整个过程。 爬山法的关键参数包括：初始解的产生规则，新解的产生和接受规则，算 法的终止准则。初始解产生的规则一般有两种，一种是取一个随机的解作为初 始解，另一种是随机产生一组解，取其中最优的那一个解作为初始解。但是两 种方式都不能保证最终解的质量，不过一般来说采用第一种方式产生初始解的 爬山法的运行时间比采用第二种方式产生初始解的爬山算法长。 新解产生的规则一般也有两种，一种是在当前解的邻域内随机产生一个新 上海大学硕士学位论文 解，另一种是遍历当前的整个邻域，取邻域中的最优解作为新解。后一种新解 产生的规则一般会产生质量较高的最终优化解，但是整个算法的运行时间会很 长。新解的接受规则一般是只接受比当前解更优的解，也可以是只接受不必当 前解质量差的解，这就是爬山法极容易陷入局部最优的更本原因所在。 算法的终止准则并没有一个严格的限定，根据实际应用需求的不同，可以 是以下三种之一： 设定一个算法的运行时间，也就是说算法在运行了这么多时间后停止。 设定一个算法的迭代次数，意味着算法迭代搜索了这么多次后停止。 设定一个算法的最大不改善迭代次数，也就是说如果算法在这么多次的迭 代搜索过程中都没有找到更优的解，算法就停止运行。 2 2 2 模拟退火法 为了克服爬山法极容易陷入局部最优的缺点，m e t r o p o l i s 等在1 9 5 3 年最 早提出了模拟退火算法的思想，在1 9 8 3 年k i r k p a t r i c k 等首先将其应用于组 合优化 4 。模拟退火法 1 7 是一个基于概率搜索的局部搜索算法，模拟退火 算法从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间 内随机寻找目标函数的全局最优解，即可以从局部最优解中概率地跳出并最终 趋于全局最优解。 模拟退火法算法的初始解也是随机产生，新解的产生规则可以是在当前解 的邻域内随机选取。新解的接受规则：如果新解s j 的优于当前解s i ，那么新 解则成为当前解：如果新解s j 不如当前解s i ，则先产生一个 o ，1 之间的数， 如果这个数小于等于e x p ( f ( s j ) 一f ( s i ) ) t ，新解就成为当前解， 反之则当前解保持不变。公式里的t 是一个随着迭代过程不断变小的一个数， 通常是在一定迭代次数j i 】后，将t 变的小一点。该算法的终止准则一般也有三 种a 算法总的迭代次数达到一定数目b 当前温度小于一定的值c 当前解的目 标函数达到一定的值。 模拟退火算法的流程图见图22 ： 上海大学硕士学位论文 图2 - 2 模拟退火算法的流程图 从算法的结摘可以看出，新袄态的产，圭丞数，新狄态的接受融数，退濑函 数，抽样稳邂准则毅退火结束准则以及初始温度是嶷接影响算法优化结果郝执 行时间的主要环节。模拟邋火算法的优点炬：由于它允许概率地撩受恶化解， 鼹数它裁不容易曦入禺部簸忧，贯势它弱期僮依簸蛙不强。毽是，为了寻浓最 优解，算法通常要求较高的初温，较慢的降温速率，较低的终止温度以及备温 震下是够多次靛袋群，嚣巍模瓠逡火算法往往霞讫过程较筏，这毽楚簇掇邀失 算法的主要缺点。 模掇邋火算法的关键参数 1 罚 1 圃 2 0 3 包括：耨状态酌产生蕊数，薪袄态 的接受函数，退温函数，抽样稳定准则，遐火结束准则以及初始濑度。下谢逐 一介绍这黧参数的选取方巢。 1 凝坟惑的产生蕊数 设计状态产生函数的出发点应该怒尽可能的保证产生的候选解遍布全 部鳃空阖。遴豢姨态产生丞数痊嚣部分缓戏：产生毅羧态弱方式窝毅状态 产生的概率分布。前者决定当前状态产生候选状态的方式，和具体问题相 关；薅兹决定痤i 当前状态产生豹不嗣静耨获态秘褫率。 2 新状态的接受函数 、抗态接受溺数一般珏概率的方式绘出，不同接受函数的蓑涮主要在于 上海大学硕士学位论文 接受概率的形式不同。设计状态接受概率，应该遵循一下原则： ( 1 ) 在固定温度下，接受优化解的概率要大于接受劣质解的概率。 ( 2 ) 随着温度的下降，接受劣质解的概率要下降， ( 3 ) 当温度趋于零的时候，只能接受优化解。 3 退温函数 即温度下降的方式，用于在每次抽样稳定准则后降温。般最常用的 温度更新函数为指数退温，即t k + 1 = m k 其中0 0 时，a ，j2 1 成立。 软条件： 1 任何一门课程在任何一个时间段安排的教室的容量不能小于该课程的 参加人数。 即：对v i f l ，2 ，m ) ，v j l ，2 ，p ，当t ， 0 时，y f ，s ，。 上海大学硕士学位论文 2 任何一门课程实际在一周内的时间跨度( 第一次课和最后一次课的时 间间隔) 尽量不要大于该门课程规定的时间跨度。 即：对vi l ，2 ，m ，如果j 】是在j l ，2 ，p ) 范围内满足t f f o 最小的数，而j2 是在j 1 ，2 ，p ) 范围内满足t f ， o 最大的数，则j ： 一j + l d 。成立。 我们可以将上述的硬软条件用符号简单的表示。h 1 ，h 2 ，h 3 ，h 4 表示四个硬 条件，而s 1 ，s 2 则表示两个软条件。我们再用f ( h i ) ，f ( h 2 ) ，f ( h 3 ) ，f ( h 4 ) 分别表示某一课程表违反硬条件h 1 ，h 2 ，h 3 ，h 4 的次数，用f ( s 1 ) ，f ( s 2 ) 分别 表示某一课程表违反软条件s l ，s 2 的次数。 那么课程表t 的优劣程度就可以用一个函数来衡量，该函数的定义如下： p e n a l t y ( t ) = 【f ( h 1 ) + f ( h 2 ) + f ( h 3 ) + f ( h 4 ) 】。l o o o + f ( s 1 ) + v ( s 2 ) 某时间表对应的该函数的值越小就表明该时间表的质量越高，在这个函数 中之所以给违反硬条件的次数一个很大的权重表明违反硬条件的严重性远大 于违反软条件的严重性，也说明我们在排课程表的过程中要优先满足硬条件。 现在求一个优化的课程表的问题就转化为求一个课程表，使得该课程表的对应 的p e n a l t y ( w ) 函数值最小化的问题。 4 2 课程表问题中两种邻域的定义 不论传统的局部搜索算法还是基于多领域的局部搜索算法，在解决某个具 体问题之前，都需要定义一个和多个邻域。邻域的重要性和邻域的构造准则在 第3 章已有详细的叙述，在这里就不赘述了。下面主要是介绍针对时间表问题， 我们定义了两种邻域r 和p ，后面各种算法在解决课程表问题时，都是利用的 这两个邻域中的一个或两个作为算法的搜索邻域。 课程表问题的定义我们已经在第二部分详细介绍了。但有个地方需要说明 一下，如果有m 门课程和p 个时间段，那么一个课程表可以用一个m p 的矩 阵来表示，为了算法描述的通用性，在后面的算法介绍中我们会常提到当前状 上海大学硕士学位论文 态，最优状态等，其实一个状态就代表着一个课程表，也用一个m p 的矩阵 来表示。现在我们定义课程表问题中和我们算法密切相关的两种操作：p 操作 和r 操作 p 操作 现在我们定义p 操作：从当前状态( 就是一个m p 的矩阵) 中任意选中 一门课程，再找到这门课程的任意一次课，将这一次课现在安排的时间 段替换为任意一个没有安排课的时间段。下面我们用一个示意图来表示p 操作( 见图4 一1 ) 。 图4 - 1p 操作示意图 r 操作 r 操作定义为：从当前状态( 就是一个m p 的矩阵) 中任意选中- - f 3 课 程，再找到这门课程的任意一次课，将这一次课现在安排的教室替换为 其他任意一个教室。下面我们用一个示意图来表示r 操作( 见图4 2 ) 。 图4 _ 2r 操作示意图 接着我们给出p 邻域和r 邻域的定义：我们称从某个状态可通过一次p 操 作到达的所有状态的集台则称为该状态的p 邻域。而从某个状态可通过一次r 4 2 上海大学硕士学位论文 操作到达的所有状态的集合则称为该状态的r 邻域。 4 3 各种基于多领域的局部搜索算法应用于课程表问题 在这一小节我们具体介绍如何将四种不同基于多领域的局部搜索算法应 用于课程表问题，这四种基于多领域的局部搜索算法分别是：单路内嵌式多邻 域局部搜索算法，多路内嵌式多邻域局部搜索算法，非交换型混合多邻域局部 搜索算法和交换型混合多邻域局部搜索算法。我们还将给出这四种算法解决课 程表问题的详细实验数据和一些试验数据的分析。 4 3 1 内嵌式多邻域局部搜索算法应用于课程表问题 从第3 章的介绍我们得知，内嵌式多邻域局部搜索算法分为两种：即单 路内嵌式多邻域局部搜索算法和多路内嵌式多邻域局部搜索算法。在单路内嵌 式多邻域局部搜索算法和多路内嵌式多邻域局部搜索算法中，运用不同的新解 产生规则，新解接受规则和算法停止准则，会产生出：单路或多路内嵌式多邻 域爬山法，单路或多路内嵌式多邻域模拟退火算法 3 3 和单路或多路内嵌式多 邻域禁忌搜索算法。 为了算法的可比性，我们将就课程表问题实现传统的单领域模拟退火算 法。单路内嵌式多邻域模拟退火算法和多路内嵌式多邻域模拟退火算法。在这 三种算法中，我们选用同样的算法参数：两个邻域p 和r ，初温t o ，降温率为 a ( a 1 ) ，采样频率为b ，收敛准则有两种：温度降到c 或目标函数的值为0 ( 得到最优解) 。 下面给出单路内嵌式多邻域模拟退火算法和多路内嵌式多邻域模拟退火 算法解决课程表问题的流程图，见图4 3 和图4 4 ： 接着我们给出试验数据及其分析，实现内嵌式多邻域局部搜索算法的语 言为c + + ，编译器为g + + 版本3 2 ，运行环境为r e d h a t l i n u x 8 0 。 我们准备了两组实验数据，第一组规模比较小，目的是比较单邻域模拟 退火算法和内嵌式多邻域模拟退火算法之间的优化性能的差异。我们会给出各 种算法在迭代过程中目标函数的变化情况，并分析这些变化产生的原因。第一 上海大学硕士学位论文 组规模比较大，目的是为了说明在大规模的数据下，单路内嵌式多邻域模拟退 火算法和多路内嵌式多邻域模拟退火算法的有效性。 1 单路内嵌式多邻域模拟退火算法 圈4 - 3 单路内嵌式多邻域模拟退火算法解决课程表问题的流程图 上海大学硕士学位论文 2 多路内嵌式多邻域模拟退火算法 图4 - 4 多路内嵌式多邻域模拟退火算法解决课程表问题的流 4 3 1 1 第一组实验数据的试验结果 第一组实验数据的规模见表4 1 4 5 上海大学硕士学位论文 课程总数教师总敷时间段总数教室总数 5 02 82 025 表4 - - i 第一组实验数据的规模 下面我们给出单邻域模拟退火算法，单路内嵌式多邻域模拟退火算法和多 路内嵌式多邻域模拟退火算法的试验数据。其中，基于p 邻域的单邻域模拟退 火算法用s a ( p ) 表示，基于r 邻域的单邻域模拟退火算法用s a ( r ) 表示，单路 内嵌式多邻域模拟退火算法用s e m s a ( p + r ) 表示，多路内嵌式多邻域模拟退 火算法用m e m s a ( p + r ) 表示。为了算法之间比较的公平性，四种算法都选取 相同的参数，相关参数如下： 初始温度( i n i t i a l j e m p e r a t u r e ) ：2 0 0 0 0 终止温度( s t o p _ t e m p e r a t u r e ) ：0 0 0 01 降温率( c o o l i n g r a t e ) ：0 9 9 采样频率( n e i g h b o r s s a m p l e d ) ：2 0 0 我们随机产生四个初始解，用s a ( p ) ，s a ( r ) ，s e m s a ( p + r ) ，m e m s a ( p + r ) 四种算法对每一个初始解分别进行优化，实验结果见表4 2 ： 翻始状态 违反硬条违反软条 最终状态目标函数的 目标函数所丽算法运行时问值 的值 件次数件次数 ( p e n a l t y ( t ) ) s a ( p 2 7 2 3 9 s09 69 6 2 1 4 1 1 6 s a ( r l 2 0 4 9 s1 5 92 81 5 9 0 2 8 s e m s a lp + 冈 5 7 2 8 3 so00 m e m s a 【p + 目 4 36 6 3 s000 s a ( p 3 1 2 3 4 so8 28 2 2 0 2 1 0 5 s a ( r 1 3 2 5 9 s1 3 53 41 3 5 0 3 4 s e m t j a 【p + r j 5 9 1 4 5 s044 m e m s a lp + r j 4 1 5 5 s0oo s a q 【p ) 2 9 6 2 8 s01 0 71 0 7 1 9 5 1 2 8 s a ( r 1 1 8 1 3 6 s1 4 33 01 4 3 0 3 0 s e m s a 【p + r ) 5 6 1 7 i s 0oo m e m s a lp 十r j 4 9 6 5 l s033 s a i 【p ) 3 6 1 9 2 s09 39 3 2 0 4 1 1 7 s a ( r 1 2 5 4 6 7 s1 4 93 11 4 9 0 3 i s e m s a 【p + 目 6 5 1 0 4 s0o0 m e m s a lp + 目 6 7 9 1 7 so22 表4 2 实验结果 上海大学硕士学位论文 观察以上实验数据上，可以发现在我们现在选定的试验参数下，s a ( p ) 花 费的优化时间要多于s a ( r ) 所用的优化时间，但s a ( p ) 所求出解的质量明显优 于s a ( r ) 所求出的解的质量。从表4 2 中我们还可以发现s a ( p ) 的特点是可以 有效的减少课程表违反硬条件的次数，而s a ( r ) 的特点则是可以有效的减少课 程表违反软条件的次数，所以针对不同的需要应该选用不同的算法。同时我们 注意到不论s a ( p ) 或s a ( r ) ，它们都没有给出最优解，即目标函数( p e n a l t y ( t ) ) 的值为零的解，这正是我们引入内嵌式多邻域模拟退火算法的原因。从 实验结果我们也可以发现，两种内嵌式多邻域模拟退火算法的优化效果都远远 好于任何一种单邻域的模拟退火算法。在四个随机初始解的优化过程中，总有 一种内嵌式多邻域模拟退火算法( 单路内嵌式多邻域模拟退火算法或多路内嵌 式多邻域模拟退火算法) 可以将初始解优化为最优解。s e m s a ( p + r ) 和m e m s a ( p + r ) 无论是在减少违反硬条件的次数还是在减少违反软条件的次数方面都 有出色的表现。但是究竟单路内嵌式多邻域模拟退火算法和多路内嵌式多邻域 模拟退火算法各自适合什么样的初始解，还是一个值得研究的问题。 为了进一步了解，各种算法在运行过程中，迭代次数和课程表违反软，硬 条件次数的对应关系，我们就第一个初始解( 2 1 4 1 1 6 ) ，分别给出四种算法在 运行过程中课程表违反软，硬条件次数的变化情况，见图4 5 和图4 6 。 违 反 硬 条 件 的 次 数 1 21 34l51 6 【71 81 92 0 2 t 2 22 t 龃拍2 62 7 9 82 9 3 03 13 ： 连代次羲( 1 0 0 0 0 ) 图4 5 四种算法在运行过程中，课程表违反硬条件次数的变化情况 上海大学硕士学位论文 违 反 救 条 件 的 次 数 2415 678 91 0i i2 1 3l ti51 6l781 9 2 02 i2 2 2 3 2 4 2 52 1 i2 7 2 8 2 9 3 03 i3 2 逮代擞款( 1o o0 0 ) 图4 6 四种算法在运行过程中，课程表违反软条件次数的变化情况 通过图4 5 和4 6 中我们可以清楚的发现，s a ( p ) 可以有效的减少课程 表违反硬条件的次数，在3 2 0 0 0 0 次的迭代过程中，违反硬条件的次数从2 1 4 次减少到了0 次，但是s a ( p ) 在减少课程表违反软条件的次数方面却表现一般， 在3 2 0 0 0 0 次的迭代过程中，只把违反软条件的次数从1 1 6 次减少到了9 6 次。 而s a ( r ) 的情况正好相反，s a ( r ) 可以有效的减少课程表违反软条件的次数， 在3 2 0 0 0 0 次的迭代过程中，违反软条件的次数从1 1 6 次减少到了