（计算机软件与理论专业论文）组合优化问题的启发式算法分析与设计.pdf

中国科学技术大学博士学位论文 摘要 摘要 随着计算机科学研究和工程技术的发展，许多科学研究领域和工程应用都涉 及到了一些组合优化问题，它们中很多都是n p 难解( n p h a r d ) 的，因此对陔 类问题的研究具有十分重要的理论意义和广泛的应用背景，其研究成果对科学研 究的发展以及国民经济的建设都起着极大的推动作用。 目前对求解该类问题的研究主要有两个方向：完全算法能保证得到全局最优 解，但是运行时间是指数复杂度的，因而难以适应大规模问题实例的求解；启发 式算法能够在多项式时间内找到比较好的可以满足实际应用要求的解，但并不一 定是全局最优解。考虑到，在大多数实际的工程应用中，使用有限的时间得到较 好的可以满足实际需求的解是至关重要的，因此算法研究主要集中在启发式算法 匕。 本文围绕着以t s p 问题为代表的一类n p 难解问题，开展了以下研究工作： 1 ，综述了求解该类问题的启发式算法研究：详细介绍了这些问题的定义、应用 背景、现有理论成果和已有算法分类。 2 分析了这类问题的启发式算法统计模型分布：通过大量实验，获得了求解t s p 问题的循环局部搜索算法的运行时间分布并证明了该分布可以用来自寿命分 布中的一种重要的理论分布很好的拟合；首次提出了解的性能分布并分析了 它对实际求解该类问题的指导意义。 3 提出了该类问题的解空间概率统计模型：通过对解空间的f d c ( f i 恤e s s d i s t a n c ec o 仃e l a t i o n ) 分析以及概率统计和实验分析，给出了解空i 铷的概率统 计模型；根据该模型进一步揭示了构成局部最优解与全局最优解的最基本单 元之间的关系。 4 设计了高效的启发式算法：在上述研究的基础上，通过对多个局部最优解交 集的分析，检测和提取那些以很高的概率出现在全局最优解中的基本单元； 由此得到了许多启发式信息并利用它们为t s p 问题、g p p 问题、q a p 问题之 类的n p 难解问题设计了高效的启发式和宏启发式算法。 5 分析并设计了高效的演化算法：根据演化算法中交叉算子的设计特性，对大 部分已有的交叉算子进行了分类；研究并改进了e a x 交叉算子、局部搜索算 子以及群体更新策略，为t s p 问题设计了高效的演化算法。 通过对以t s p 问题为代表的一类n p 难解问题的研究，本文的主要贡献和创 新点可归纳如下： 1 在求解该类问题的算法模型研究方面：证明了循环局部搜索算法的运行时间 中国科学技术大学博士学位论文摘要 分布很好的服从两参数的威布尔分布，首次定义并获得了算法的解的性能分 布；突破传统的适应度地貌分析将解看作最基本单元的局限，提出了解的概 率统计模型并揭示了解空间内部更加精细的特性，由此得到了基于多个局部 最优解的交集和并集的启发式信息。 2 ，在启发式算法设计方面：通过获得的启发式信息，提出了几种新的高效的求 解该类问题的启发式和宏启发式算法，这些算法在求解时间和获得解的质量 上对已有最好的算法做出了一定的改进。包括：基于交集归约算法、多级归 约算法、近似骨架导向的快速蚁群算法和尺度缩放算法。 3 在演化算法分析和设计方面：打破传统的m e m e t i c 算法中只使用一种局部搜 索算子来优化群体的局限，提出了一种随机多搜索的局部搜索算子来增加群 体的多样性；通过改进著名的e a x 交叉算子，提出了m e a x 交叉算子，对 原算子在求解速度和效率上均获得了较大的改进：首次提出了带m e a x 交 叉算子的m e m e t i c 算法和随机多搜索的m e m e t i c 算法它们显著地改进了已 有的算法。 关键词：组合优化，组合优化问题，n p 难解问题，启发式算法，演化算法，运 行时间分布，解的性能分布，概率统计模型 2 中国科学技术大学博士学位论文摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e rs c i e n c ea n de n g i n e e rt e c h n 0 1 0 9 y l o t so f c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa r i s ef r o mn u m e r o u ss c i e n t i f i cr e s e a r c hf i e l d s a n de n g i n e e r i n ga p p “c 确o n s m a n yo f 由e ma r en p h a r dp r o b l e m s t h e r e f o f e ，i th a s i m p o r t a n tt h e o r e t i c a 】m e a n i n ga 1 1 de x 把n s i v ea p p 】i c a t i o nb a c k g m u n d t or e s e a r c ht h e s e p r o b l e m s a n dt h e s er e s e a r c h e sc a ng r e a t l yf 的i l i t a t e t h ed e v e l o p m e n to fc o m p u t e r s c i e n c ea n dc o n s t r u c t i o no f n a t i o n a le c o n o m y p r e s e n t l mm e r ea r em a i n l yt w ok i n d so fa l g o r i t h m sf o rt h e s ep r o b l e m s ：e x a c t a l g o r i t h m sa n dh e u r i s t i ca 】g o r i t h m s t h e e x a c ta l g o r i t h m sc a no b t a i nt h e 9 1 0 b a l o p t i m a ls 0 1 u t i o n s ，b u tt h e i rc o m p u t i n gc o r r l p l e x i t i e sa r ee x p o n e n t i a l s ot h e ya r en o t s u i t a b l ef o rv e r y1 a r g e - s c a l ei n s t a n c e s t h eh e u r i s t i ca l g o r i t h m sc a n6 n d “g o o d e n o u 曲”s o l u t i o n s ，w h i c hc a nm e e tt h ed c m a n do fp r a c t i c a la p p l i c a t i o n sb u ta r en o t a l w a y st h eg l o b a lo p t i m a ls 0 1 u t i o n s s i n c ei t i sv e 叫i m p o n a n tt oo b t a i ns o l u t i o n si n r e a s o n 8 b ! e m p u t i n gt i m e f o rm o s te n g i n e e d n ga p p l i c a t i o n s ，t h ef e s e a r 世【e so f a i g o r i t h m sm a i n l yf o c u so n h e u r i s t i ca l g o r i t h m s t h em a i nr e s e a r c hw o r k s p r e s e n t e di nt h i sd i s s e n a t i o na r ec o n c e n t r a t e d o n s e v e r a ln p _ h a r d p r o b l e m sr e p r e s e n t e db y t s p 1 s u m m a r i z e dt h eh e u r i s t i ca l g o r i t h m sr e s e a r c h e so f t h e s ep r o b l e m s w ei n t i 0 d u c e dt h e d e n n i t i o n s ，a p p i i c a t i o n sb a c k g r o u n d s ，e x i s t e d m e o r e t i c a l r e s u l t sa n dc l a s s m c a t i o n so f m ei m o w n a l g o r i t h m si nd e t a i l 2 a n a i y z e dt h ed i s t r i b u t i o n so fs t a t i s t i c sm o d e lo fh e u r i s t i ca l g o r i t h m st o t h e s ep m b l e m s a r e ral o to fe x p e “m e n t s ，w eo b t a i n e dt h er l l n n i n gt i m ed i s 岫b u t i o no ft h e i t e r a t e dl o c a ls e a i ha l g o n t h mt ot s pa n d p r o v e d t h i sk i n do fd j s t r i b u t i o nc a nb ew e l l a p p r o x i m a t e db ya ni m p o n a mt h e o r e t i c a ld i s m b u t i o n ，w h i c hc o m e sf r o m1 i f e s p a n d i s t r i b u t i o n s a tt h es a m et i m e ，w e p r o p o s e d ，f o r t h ef i r s tt i m e ，t h es 0 1 u t i o n p e r f o n n a n c e d i s t n b u t i o na n do b t a i n e ds o m ep r a c t i c a lc o n c l u s i o n st h a tm a yg i v e g u i d a n c e t os o l v i n gt h e s ep r o b l e m s 3 p r o p o s e dt h ep r o b a b n i t ys t a t i s t i c s m o d e io fs o l u t i o n ss p a c e so ft h e s e p r o b l e m s u s i n gf d c ( f i n l e s sd i s t a n c ec o r r e l a t i o n ) a n a l y s i s o fs o l u t i o n s s p a c e s a n d p r o b a b i l i t ys t a t i s t i c sa n a l y s i s ，w eg a v e dm ep r o b a b i l i t ys t a t i s t i c sm o d e lo f s o l u t i o n s 3 中国科学技术大学博士学位论文 摘要 s p a c e sf o rt l l e s ep r o b l e m s f u n h e 咖o r e ，w ef o l l n dt h er e l a t i o n s h i pb e t 、v e e nt h em o r e b a s i cb u i l d 恤g b l o c k so f t h eg l o b a lo p t i m aa n d l o c a l0 p t i m 4 d e s i g n e dt h ee f f i c i e n th e u r i s t i ca l g o r i t h m s b a s e do n l ea b o v er e s e a r c h e s ，w ei n v e s t i g a t e da 1 1 do b t a i n e dt 1 1 em o s tb a s i cu n i t s o f 】o c a lo p t j m a ，w c hc a na p p e a ri nt h eg l o b a lo p t i m aw i l hh i 曲p r o b a b j l i t ya r e r a n a l y z i n g t h ei n t e r s e c t i o no fs e v e r a l l o c a lo p t i m a 5 a n a l y z e d a n d d e s i g n e dt h ee f l i c i e n te v o i u t i o n a r ya i g o r i t h m s b a s e do nt h ec h a r a c t e r i s t i c so fc r o s s o v e ro p e r a t o r s ，w ec l a s s m e da l m o s ta l lo f t h e e x i s t e dc m s s o v e r o p e r a t o r s a f t e rr e s e a r c h i n g a n di m p r o v i n ge a x c r o s s o v e r o p e r a t o i 1 0 c a ls e a r c ho p e r a t o r sa n dt h es t r a t eg ) ，o fu p d a t i n gg e n e r a t i o n s ，w ed e s i g n e de 伍c i e n t e v o l u t i o n a r ya l g o r i t h m st ot s p t h em a i nc o n m b u t i o na n di n n o v a t i o no ft h i sd i s s e r t a t i o nf o rf h er e s e a r c ho f t h e n p _ h a r d p r o b l e m sr e p r e s e n t e db y t s pc a nb es u m m a r i z e da sf o l l o w s ： 1 i nt h er e s p e c to f s t a t s t i e a lm o d e i w ep r o v e dt h er u n n i n gt i m ed i s t r i b u “o nc a nb ew e l la p p r o x j m a t e db yw e i b u l l d i s t r i b u t i o nw i lt w op a r a m e t e r s a n dw ep r o p o s e d ，f o rt h e 矗r s tt i m e ，t h es o l u t i o n p e r f b m a n c ed i s t r i b u t i o n b r e a k i n gt h r o u g ht h el i m i t a t i o nt oi o o kt h es o l u t i o na st h e m o s tb a s i cu n i ti nt h et r a d i t i o n a lf i t f l e s si a n d s c a p ea n a l y s i s ，w ep r o p o s e dt h es o l u t i o n p r o b a b 认姆s 枷s t i c a lm o d e i a n dp r q v i d e dm o r ep r e c i s ec h 龃a c t e r i s t i co f 也es 0 1 u t i o n s d a c e t 1 1 e nw eo b t a i n e dal o to fh e u r i s t i ci n f b m l a “o nb a s i n go n t h ei n “：r s e c t i o na n d u n i o n 2 i nt h el - e s p e c to fh e u r i s t i ca l g o r i t h m sd e s i g n u s i n 窟t h eo b t a i n e dh e 嘶s t i ci n f o m a t i o n ，w ed e s i g n e d s e v e r a ln e we m c i e n t h e u r i s t i ca n dm e t a _ h e u r i s t i ca i g o r i t l l m st ot h e s ep r o b l e m s 。t h e s ea l g o r i t h m sh a v e s i 鲥f i c a n t l yi m p r o v e d t h ek n o w nb e s ta l g o r i t sb o t hi nt h ec o m p u t i n gt i m ea n dt h e q u a l i t yo fm eo b t a i n e ds 0 1 u t i o n s t h e ya r e m er e d u c t i o na l g o r i t h mb a s i n go nt h e i n t e r s e c t i o n ，t h em u l t i l e v e l r e d u c t i o n8 l g o r i t h m ，t h e 印p r o x i m a t e _ b a c k b o n eg u i d e d f a s ta n ta l g o r i 廿1 ma n dm es i z e s c a l ea l g o r i m m 3 1 nt h er e s p e e to fe v o l u t i o n a l ya l g o r j t h m sa n a l y s sa n dd e s i g n b r c a k i n gt h m u g h t h e1 i m i t a t i o no f u s m go n l y o n el o c a ls e a r c ho p e r a t o rt 0i m p r 0 v e t | 1 eg e n e m t i o n si nt h e 仃a d i t i o n a lm e m e t i ca 1 9 0 r i t h m s ，w ep r o p o s e dam f l d o mm u l t i l o c a ls e a r c ho p e r a t o rt oe n h a n c et h ed i v e r s i t yo f t h eg e n e r a t i o n s a r e ri m p m v i n gt h e 4 中国科学技术大学博士学位论文摘要 f h m o u se a xc r o s s 0 v e ro p e r a t o r w ed e s i g n e dt h em - e a xc r o s s o v e ro p e r a t o rt o i m p m v et h ec o m p u t i n gt i m e a n de f f i c i e n c yo ft h ee a x w ep r o p o s e dt h en e w e f n c i e n le v o l u t i o n a r ya l g o r i t h m st h em e a xm e m e t i ca l g o r i t h ma n dt h em u l t i l o c a l s e a r c hm e m e t i c a l g o r i 七h m ， w h i c h s i g n m c a n t l yo u t p e r f o m t h ek n o w nm e m e t 记 a l g o n l h m s k e y w o r d s ：c o m b i n a t o r i a io p t i m i z a t i o np r o b l e m s ，n p - h a r dp m b l e m s ，h e u r i s t i c a l g o “t l l m ，e v o l u t i o n a r ya l g o r i t h m s ，r u n n i n gt i m ed i s t r i b u t i o n ，s o l u t i o n p e r f b n n a n c e d j s t m u t i o n ，p m b a b i l i t ys t a t i s t i c a lm o d e l 5 中国科学技术大学博士学位论文第1 章全文梗概 1 全文梗概 本章摘要；本章首先介绍了几个典型的组合优化问题的背景知 识、现有理论成果及算法分类；然后提出了本文的研究内容，并 综述了文中取得的研究成果；最后给出了全文的组织结构。 1 1 研究背景 随着科学研究和工程技术的发展，许多科学研究领域和工程应用如电路控 制、交通调度和自动控制等都涉及到了一些组合优化问题，它们中很多都是n p 难解( n p - h a r d ) 的 i ，所以对该类问题的研究具有十分重要的理沦意义和广泛 的应用背景，其研究成果对科学研究的发展以及国民经济的建设都起着极大的推 动作用。 在j p p 的假设下，n p 难解问题找不到一个算法能保证在多项式时间内得 到全局最优解【2 】。目前对于该类问题的研究有两个方向，完全算法和启发式算 法：完全算法能保证得到最优解，但是运行时间是指数复杂度的，因而难以适应 大规模问题实例的求解：启发式算法则能够在多项式时间内找到比较好的能够满 足要求的解，但并不一定是全局最优解。 由于在实际的工程应用中的很多情况下，使用有限的时间得到较好的可以满 足实际需求的解( 并不一定必须是全局最优解) 是至关重要的，因此对于以t s p 问题为代表的一类n p 难解问题，算法研究主要集中在启发式算法上，国内外许 多著名的学者为这一类问题设计了各种各样的启发式算法，同时近两年来，许多 学者利用基于生物进化启发式信息得来的演化算法对t s p 等问题进行求解，这 些启发式算法为求解组合优化问题特别是n p 难解问题的做出了巨大贡献。 1 2 组合优化问题与n p 难解问题 组合优化问题又称离散优化问题，是一类重要的优化问题。随着计算机科学、 1 0 中国科学技术大学博士学位论文第l 章全文梗概 管理科学和现代化生产技术等的日益发展，这类问题与日俱增，越来越受到运筹 学、应用数学、计算机科学及管理科学等诸多学科的高度重视。虽然某些组和优 化问题有悠久的历史渊源，被费马( f e m l a t ) 、欧拉( e u l e r ) 等众多著名数学家 研究过，但作为运筹学的一个独立分支而发展壮大起来还是近几十年的事。它是 一门新兴的学科分支。 组合优化问题万是一个极小化问题，或者是一个极大化问题，它由下述三部 分组成： ( 1 ) 实例集合： ( 2 ) 对每一个实例，有一个有穷的可行解集合s ( ，) ； ( 3 ) 目标函数厂，它对每一个实例，和每一个可行解仃s ( ，) ，赋以一个有理 数厂( ，回，如果石是极小化问题( 极大化问题) ，则实例的最优解为这 样一个可行解盯s ( ，) ，它使得对于所有仃s ( ，) ，都有 ，( ，) ，( ，回( ，( ，巧) ，( ，仃) ) 一个组合优化问题如果己找到了多项式时间算法，那么就称它为多项式时间 可解问题，把所有这样的问题集合记为p ，因此多项式时间可解问题就称为j d 类 问题。所有复杂度高于多项式时间的算法都被称为指数时间算法，而不管它的时 间复杂度是不是准确的指数量级。假设一台计算机的计算速度为每秒1 0 亿次。 表l 。2 ，l 比较了具有几种不同时间复杂度函数的算法在输入规模增加时运算时间 增氏的情况，从表中可以看出，指数时间算法在输入规模增加时运算时间急剧增 ，最终将达到天文数字的量级。 表1 2 1 不同时间复杂度函数下算法性能的比较 时间输入问题规模” 复杂度 1 02 03 0 4 01 0 0 h 1 0 纳秒2 0 纳秒3 0 纳秒4 0 纳秒1 0 0 纳秒 以1 0 9 咒1 0 纳秒2 6 纳秒4 4 3 纳秒6 4 1 纳秒 2 0 0 纳秒 矸21 0 0 纳秒4 0 0 纳秒9 0 0 纳秒1 6 微秒 1 0 微秒 2 41 o 微秒 1 0 毫秒1 1 秒1 8 3 分4 o 世纪 甩13 6 毫秒7 7 1 年8 4 1 0 ”世纪2 6 1 0 ”世纪3 o l o ”9 世纪 中国科学技术大学博士学位论文第l 章全文梗概 一个问题如果未找到多项式时间算法，那么直觉上它是“难解”的，但又往 往无法证明其多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一 定意味着这样的算法不存在，这就给理论工作者提出了一个难题：一方面证明一 个问题不存在多项式时间算法是困难的，至今尚未给出：另一方面有越来越多的 问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此在 2 0 世纪7 0 年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数学猜 想，这个理论就是n p 完全性理论【1 3 。 在关于问题能否有有效算法的讨论中，人们发现，如果把所有问题都转化成 只要求简单回答“是”或“否”的形式，将会带来许多方便，使差别很大的不同 问题进行比较成为可能。我们称答案为“是”或“否”的问题为判定问题。给定 一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例，该算法 首先给出一个猜想，该猜想规模不超过，的输入氏度的某个多项式函数，且验证 猜想的正确性仅需多项式时间，则称该问题属于p 类。易知尸p ，但是多 项式时间可验证性不能保证多项式时间可解性。如果问题厅p ，那么存在一一 个多项式p 使得石能用时河复杂性为以2 加) 的确定型算法求解，这里n 表示石 的实例的输入长度。 设有两个判定问题丑玎：，如果对丌的任一实例，可以多项式时间构造出 厅，的一个实例，：，使，的答案为“是”当且仅当，的答案为“是”，则称万。可 以多项式时间归约到厅，。如果p 类中所有问题都可以多项式时间归约到p 类 中某个问题丌，则称7 r 是 r 尸一完全问题( m 9 一c o m p l e t e 或n p c ) 。如果一是a p 一 完全问题，石：p ，且丌可以多项式时间归约到丌：，则万：也是肿一完全问题。 如果某 驴完全问题有多项式时间算法，则 p 类中所有其他问题也有多项式时 间算法。因此胛完全问题是p 类中最难解问题。另一方面，如果一个p ，完 全问题没有多项式时间算法，则所有p 完全问题也没有，因此所有m ，完全问 题是同等难度的。到目前为止，这些问题既没有找到多项式时间算法，也无法证 明多项式时间算法不存在性。要解决此问题，需要理论上有重大突破。 对于一个组合优化问题，为了证明它的难解性，需先给出它的判定问题，然 后证明该问题是p 完全的，显然，回答判定问题不会比解决原优化问题困难， 因为如果能求出最优解，只要把它与判定问题中给定的上界或者下界比较，就可 回答判定问题。如果某组合优化问题石的判定问题是尸一完全的，则称问题丌是 俨难解的( ，户_ h a r d 或n p c ) 。如果存在一一个 p 难解问题丌可以多项式时间 中国科学技术大学博士学位论文第l 章全文梗概 归约到石：，则石：也是p - 难解的。除非p = 尸，p 难解问题没有多项式时 间算法。 1 2 1 旅行商问题( t s p ) 1 2 1 1t s p 问题的定义 t s p 问题( t r a v e l i n gs a l e s m a np r o b l e m ，旅行商问题) 的描述如下：要求一个 商人从一个城市出发，不重复地访问所有城市，并回到出发点，闯什么样的环路 最短? t s p 问题的形式化定义为：给定加权图g = ( 矿，e ，w ) ，矿为顶点集， 1 矿 ，e 为边集，w ：e j 为边权函数，g 中一个卿环路就是一条不重复 地访问矿中所有顶点的h a m i l t o n 环路，记为s = ，其中 v l f ，sh ，u 0 且对l s f 以， e ，记s ( g ) 为g 中所有御环 路的集合。定义w ( ，) = w ( t ，_ ，) + 。，叫c l ，。，) ，要求您p 环路s + ，使得 以p ) = m i n 。“s ) 。相关综述文章请参见 4 6 】。 t s p 问题具有古老的历史。术语“旅行商”虽早出现于1 9 3 2 年出版的本 德文书旅行商应该如何做以及做什么才能获取酬金并在事业上取得成功，该 书的作者是一位老练的旅行商。t s p 由r a n d 公司于1 9 4 8 年引入，公司的声誉 使得t s p 问题成为一个知名且流行的问题。t s p 问题在科学、工程及经济的各 个方面具有广泛的应用。它们包括电路板钻孔、交通调度、机器人控制、矿物结 晶学、超大规模电路板印刷和基因组测序等。现实世界中的t s p 问题的规模通 常都非常大：在文献【7 】中提到的电路板钻孔应用相当于1 7 ，0 0 0 个城市的t s p ； 在文献 8 中提及的x 射线检晶体器例子相当于1 4 ，0 0 0 个城市的t s p ；而在文献 9 】中报道的v l s i 构造有1 ，2 0 0 ，0 0 0 个“城市”之多。 1 2 1 2t s p 问题的分类及变种 1 t s p 问题的分类 在长期的研究过程中，人们按照不同划分标准，对于t s p 问题作了不同的分 类。根据t s p 问题顶点之间不同方向上的距离是否相同，将t s p 问题分为s t s p ( s y t n m e t r i ct f a v e l i n gs a 】e 姗a np r o b 】锄) ，对称旅行商问题和a t s p ( a s y i n m e | r j c t r a v e l i n gs a l e s m a np r o b l e m ) ，非对称旅行商问题两大类：根据t s p 问题顶点之间 距离计算方法不同，将t s p 问题分为欧氏空间上的旅行商问题非欧氏空间上的 中国科学技术大学博士学位论文第1 章全文梗概 旅行商问题两大类：前者的每对顶点之问的距离可以用欧氏空间上的距离函数计 算，该类实例的表示方法有坐标和距离矩阵两种；而后者的每对顶点之间距离刁i 可以用欧氏空间上的距离函数计算，该类实例一般用距离矩阵来表示。根据t s p 问题彼此连接的三条边的距离是否满足三角不等式关系，可以将t s p 问题分为 满足三角不等式的t s p 问题和不满足三角不等式的t s p 问题 2 t s p 问题的变种 在对t s p 问题研究的过程中，出现了许多与t s p 问题极其相似的其他问题， 这些问题在使用s o n e t 技术的光纤网络设计、飞机航班的调度以及路由、物流、 航运、邮局系统、自动化生产环境等领域都具有很广泛的应用背景，它们是双色 旅行商问题【l o 1 4 】、多旅行商问题【1 5 一1 7 】、带回程的旅行商问题【1 8 2 2 和带时问 限制的旅行商问题 2 3 2 6 。双色旅行商问题的顶点分为黑色和白色两种。它的优 化目标是寻找一条最短的h a m i l t o n 环路，使得环路上连续的两个黑色顶点间白 色顶点的数目和路径长度不超过某个给定的上限。多旅行商问题是指m 位旅行 商从一个固定的起点城市出发，访问n 个城市后回到起点，求一组长度最短的 环路，使得每个城市( 起点城市除外) 恰好披其中一位旅行商访问一次，且每位 旅行商至少访问了一个城市。带回程的旅行商问题将顶点分成两大类：l i n e h a u l 和b a c l ( 1 1 a u l ，问题的要求是找到一条最短的h 啪i l t o n 环路，使得旅行商从起点 城市开始，先连续访问l i n e h a u l 的顶点，然后连续访问b a c l ( h a u l 的顶点并回到 出发点。带时限的旅行商问题要求对于每个顶点的访问必须在给定的最早时间和 最晚时间之间。 1 2 1 3 求解t s p 问题的算法 因为t s p 问题形式简单易于描述、且属于典型的_ ，p 一胁坩问题，因此其作 为算法研究与验证的平台而被广泛研究。在t s p 问题上取得的理论或者实验成 果，可以应用于其他的n p 难解问题。实际上，求解n p 完全问题的许多方法都 源自于t s p 问题的研究。例如：目前广泛使用的分支界限( b r a n c ha n db o u n d ) 方法，就是首先使用在t s p 问题上的【2 7 2 8 。同时值得一提的是，t s p 问题的 研究也是推动上个世纪7 0 年代以来蓬勃发展的计算复杂性理论 3 ( c o m p u t a t i o n a lc o m p l e x 时t h e o r y ) 的重要力量。 目前求解t s p 问题的算法主要可以分为完全算法( e x a c t a l g o r i t h m ) 和启发 式算法( h e u r i s t i ca l 印r i t h m ) 两大类。 1 完全算法 它可以确保算法在一定的步数得到全局最优解。到目前为止，完全算法可以 求解顶点数目达1 0 2 量级t s p 问题。目前最有效的完全算法是割平面 1 4 中国科学技术大学博士学位论文第1 章全文梗概 ( c u t t i n g p 1 a n e ) 【2 9 3 1 和分支界限算法 2 7 2 8 ，这类的算法都非常复杂，而且 对计算机的计算能力要求也相当高。例如，对于2 0 0 0 多个顶点的对称t s p 问题， 应用完全算法求解，在一台超级计算机上面需要花费长达2 7 个小时的时间【3 0 】。 而若要求解7 0 0 0 多个顶点的t s p 实例，对于一个大的s p a r c 2 工作站机群，需 要花费时问估计在3 0 年左右f 3 1 1 。相对而言，对称t s p 阚题比非对称t s p 问 题更难求解【3 2 】 3 3 。目前通过使用完全算法已经被解决的最大的对称t s p 问题 是p l a 7 3 9 7 ( 实例来自t s p l i b 见本章1 2 1 4 小节) 。 2 启发式算法 启发式算法是指能够在多项式时间内找到比较好的能够满足实际要求的解 的算法。与完全算法相比较而言，启发式算法不能保证一定获得全局最优解。目 前，求解t s p 问题的启发式算法主要可以分为环路构造算法( t o u rc o n s t m c t i o n a l g o r i t h m ) 和环路改进算法( t o u ri m p m v e m e n t a l g o r i t l l m ) 两大类。 2 1 环路构造算法 它通过在算法的每一步加入新的顶点，从而逐步构造一个完擅的环路，其中 主要包括贪心算法m 3 6 1 、c l a r k e w r i 曲t 算法1 3 7 】和c 1 1 r i s t o f i d e s 算法f 3 8 】等。 贪心算法。主要分为两类，最近邻算法和多片段算法。最近邻算法每次 选择一个与当前顶点距离最近的，且没有被访问过的顶点。利用这一方法构造了 一个顶点序列k ，( ：) ，k ( 。，其中初始顶点”州) 的选择完全随机。对应的环路 按照这一序列依次访问各个顶点，在访问k 。，后回到m 。最近邻算法的时间复 杂度为0 ( 月2 ) 。多片段算法将t s p 实例看成一个完全图。一条t s p 环路就是该 完全图上的一条h a m i l t o n 环路，也就是说一组边的集合，其中每个顶点的度为2 。 算法在构造环路时，每次加入一条新的边。算法从最短的边开始，依次加入剩余 有效边中最短的边。这里，一条边是有效的，当且仅当它不在环路中并且加入后 不会产生一个度大于2 的顶点或者边数小于n 的子环路。多片段算法的运行时间 复杂度为 ( n 2 1 0 9 月) 。贪心算法的近似比为( 1 0 9 2n + 1 ) 2 oc l a r k e - w r i g h t 算法。该算法从一个伪环路( p s e u d ot 0 u r ) 开始。该伪 环路以一个随机选定的顶点作为轴心( h u b ) ，访问一个顶点后，在访问下一个 顶点前，商人都回到轴心。( 换句话说，c l a r k e w r i g h t 算法从个m u l t i g r 印h 开 始，在这个图上，每一个非轴心顶点都与轴心顶点之间有两条边相连) 。对于每 对非轴心顶点，结余( s a v i n g s ) 是指商人直接从其中一个非轴心顶点到另外一 中国科学技术大学博士学位论文第1 章全文梗概 个非轴心顶点而不经过轴心时总的环路可以缩短的距离。接下来，类似于贪心算 法的处理方法，算法处理按照结余非增的顺序依次处理非轴心顶点，只要它不会 生成一个非轴心顶点的环路或者导致某个非轴心顶点和多个( 大于2 ) 的非轴心 顶点相邻。该构造算法在仅有两个非轴心顶点和轴心相邻时结束。此时算法得到 一个完整的环路。c l a r k e w 魄h t 算法的运行时间复杂度为 ( n 2i o g h ) ，而算法的 近似比为( l o g ：n 1 + 1 ) 0c h r i s t o n d s 算法。该算法首先为所有的顶点构造一棵最小生成树，注意 这样的一棵最小生成树的长度比最优环路短，因为删除最优环路上的任意一边即 可得到一个生成树：其次，对于最小生成树上的度为奇数的顶点，计算一个最小 长度的匹配m 。匹配m 和最小生成树构成了一个连通图，在该图上，任意一个 顶点的度均为偶数。这样，这个图上必定包含了一个欧拉回路( e u l e rc v c l e ) ， 也就是说一个回路经过每条边一次且刚好一次，并且这样的回路易于获得。这样 一条t s p 环路可以通过遍历该欧拉回路并利用捷径( s h o r t c u t ) 避免多次访问同 一个顶点而得到，显然该t s p 环路长度不超过该欧拉回路。c h r i s t o n d s 算法的运 行时间复杂度为o ( n 3 ) ，算法的近似比为3 2 。 2 2 环路改进算法 这类算法通过对环路进行一系列操作( 交换或移动) ，将一个环路转换成另 外一个环路。给定一个可行环路，算法对其进行一系列的操作( 每次操作可以减 少当前环路的长度) ，直到不能得到更好的环路为止。此时的环路称为一个局部 最优环路，该类算法主要包括局部搜索9 3 1 、禁忌搜索“5 引、模拟退火阡6 1 1 和遗 传算法【6 2 7 3 等。 局部搜索( l o c a is e a r c h ) 。在局部搜索算法中，最著名的是2 一o p t 、3 一o p t 和l i n k e m i 曲a n 算法。2 一o p t 算法最早由c r o e s 提出【3 9 】，尽管此前f 1 0 0 d 已经提 出了基本的交换操作 4 ”。该交换删除两条边，这样将环路打破为2 条路径，然 后以别的方式连接这两条路径。对于3 一o p t 4 0 【4 2 】而言，算法利用3 条新的边取代 当前环路上的3 条边，得到新的环路。l i n k e m i g h a n 算法( l k l 4 j j ) 是求解t s p 问题最常见也是最有效的算法之一。在长达1 6 年( 1 9 7 3 1 9 8 9 ) 的时间里，l k 算法一直被认为是世界上求解t s p 问题最有效的启发式算法。到目前为止，至 少有j o h n s o n 【7 4 】、a p p l c g a t e 1 7 ”、n e t o 【7 6 】、n g u y e n 等科学家分别实现了l k 算法及其变体。目前求解t s p 问题最好的两个算法：i l k 【7 3 7 8 。7 9 1 与l k h 【8 0 ，均 是在l k 算法的基础上发展而来的。 1 6 中国科学技术大学博士学位论文第l 章全文梗概 。禁忌搜索( t a b u ) 。禁忌搜索考虑到局部最优解之间的相关性( 局部最 优解的聚集性) ，也就是说对于任意的局部最优解，一个更好的解可能就在附近。 如果