（计算数学专业论文）最大团问题的二元熵函数法及同伦方法.pdf

大连理工大学硕士学位论文 摘要 最大团问题是组合优化中的一个经典的n p c o m p l e t e 问题。此问题自被人们发现之 后，广为研究和应用。但是因为问题本身的复杂性，所以人们将研究的重点放在问题的 近似计算上，并且取得了一系列的研究成果。这篇文章的主要内容也是研究该问题的近 似算法，结构安排如下： 在第一章，介绍了最大团问题的有关定义和优化模型。概述了问题的特点和研究意 义所在。给出了最大团问题的相关研究工作。 在第二章，给出了求解最大团问题的一种方法，二元熵函数内点法。该算法基于一 个超方体约束的二次规划模型。在用二元熵函数构造的辅助项后，可得到一个新的模型。 通过求解这个新的模型来逼近原模型的解。在求解过程中，先是得到一个下降方向，并 证明了沿此方向进行一维搜索且步长不超过1 可以保证迭代点始终在可行域内部。在这 一章最后，给出算法收敛性证明。 在第三章，给出了求解最大团问题的一种同伦方法，基于复制子等式的同伦方法。 首先，介绍了复制子等式一些性质以及在求解最大团问题上的作用。其后，在求解的二 次规划模型上以同伦形式添上正则项得到同伦形式的正则化模型。然后通过调节同伦参 数，对每个不同的参数用复制子等式进行求解，从而得到原二次规划模型近似解。 在第四章，对以上两章的算法进行数值试验。介绍了在数值试验中一些细节处理， 包括如何进行一维搜索，在试验中一些初值的设定，以及同伦参数的调节问题。此外， 以表的形式给出了该文的数值试验结果与经典方法结果。 关键词：最大团；二元熵函数法；复制子等式；同伦方法 最大团问题的二元熵函数法及同伦方法 b i v a r i a t ee n t r o p yf u n c t i o nm e t h o da n dh o m o t o p ym e t h o d f o rm a x i m u mc l i q u ep r o b l e m a b s t r a c t t h em a x i m u mc l i q u ep r o b l e l ni so n eo ft h ec l a s s i cn p - c o m p l e t ep r o b l e m sf r o m c o m b i n a t o r i a lo p t i m i z a t i o n s i n c et h ep r o b l e mw a sp r o p o s e d ，i th a sb e e ns t u d i e di n t e n s i v e l y a n da p p l i e dt om a n yf i e l d s c o n s i d e r i n gt h ec o m p l e x i t yo ft h ep r o b l e m , m o s tr e s e a r c h e sw e r e f o c u s e do nt h ea p p r o x i m a t i o nm e t h o da n dm a n ya c h i e v e m e n t sh a v eb e e no b t a i n e d t 1 1 i s t h e s i si sa l s od e v o t e dt oa p p r o x i m a t i o nm e t h o d 珏em a i nc o n t e n t s 辩o r g a n i z e da sf o l l o w s ： i nc h a p t e r1 ，s o m ed e f i r t i t i o n sa n do p t i m i z a t i o nm o d e l sa b o u tt h em a x i m t m ac l i q u e p r o b l e ma r ei n t r o d u c e d t h e nt h ef e a t u r eo ft h ep r o b l e ma n dt h es i g a n i f i c a n c eo fs t u d i n gt h e p r o b l e ma r eo u t l i n e d a tt h ee n do f t l a ec h a p t e r , s o m e ：r e l a t e ds t u d i e sa r ep r e s e n t e d i nc h a p t e r2 aa l g o r i t h mn a m e db i v a r i a t ee n t r o p yf u n c t i o na l g o r i t h mi sp r o p o s e d 1 h e a l g o r i t h mi sb a s e do nq u a d r a t i co p t i m i z a t i o nm o d e lw i t hl a y p e e u b ec o n s t r a i n t 矗bt h e 如f p o fb i v a r i a t ee n t r o p yf - a n c t i o n , al l e wm o d e li so b t a i n e d w h i e l ac a nb es o l v e dt oa p p r o x i m a t e p r i m a lm o d e l w i 也r e g a r dt oh o wt os o l v et h en e wm o d e l ad e c e n td i r e c t i o ni so b t a i n e dt h e n i t sp r o v e dt h a ti f t h ei n i t i a lp o i n ti st h ei n t e r i o rp o i n to f h y p e r e u b ea n ds t e p l e n g t hi sc o n f i n e d t o ( o ，1 ) w h e nc a r r y i n go u t ed i m e n s i o ns e a r c hf o l l o w i n gt h ed i r e c t i o nm e n t i o n e da b o v ei n o r d e rt og e n e r a t en e x tp o i n t ，t h e na n yp o i n tg e n e r a t e db ys u e l ai t e r a t i o ni si n t e r i o rp o i n to f f e a s i b l ef i e l d m o r e o v e r , a tt h ee n do ft h i sc h a p t e r , t h ep r o p o s e da l g o r i t h mi sp r o v e dt ob e c o n v e r g e n t i nc h a p t e r3 ，h o m o t o p ym e t h o db a s e do nr e p l i e a t o rd y n a m i c si si n t r o d u c e d s o m eb a s i c p r o p e r t i e so fr e p l i e a t o rd y n a m i c sa n di t sa p p l i c a t i o nt o m a x j l l l u n lc l i q u ep r o b l e mf i l e p r e s e n t e d t h e n , ar e g u l a r i z e dq u a d r a t i co p t i m i z a t i o nm o d e li nt h ef o r mo fh o m o t o p yi s p r e s e n t e d 1 1 l ea p p r o x i m a t i o no f t h ep r i m a lq u a d r a t i co p t i m i z a t i o nm o d e l 啪b eo b t a i n e db y s o l v i n gt h er e g u l a r i z e do n ea n da d j u s t i n gt h eh o m o t o p yp a r a m e t e r i ne l a a p t e r4 ，n u m e r i c a le x p e r i m e n t sa r ep e r f o r m e d0 1 1t h ea l g o r i t h m si nt i l ef o r m e rt w o c h a p t e r s s o m ed e t a i l si nn u m e r i c a le x p e r i m e n ta l ea l s op r e s e n t e d , s u c h 髂h o wt oc f l , l t y o u t o n ed i m e n s i o ns e a r c h , h o wt os e ts o m ei n i t i a lv a l u e sa n dh o wt oa d j u s th o m o t o p yp a r a m e t e r b e s i d e s ，t h en u m e r i c a lr e s u l t so f t h i st h e s i sa n ds o m e ：c l a s s i cm e t h o da r ep r e s e n t e di nt h ef o r m o f t a b l e k e yw o r d s ：l v l * x i m u mc l i q u ep r o b l e m ；b i v a r i a t ee n t r o p yf t m e t i o am e t h o d ： l l e p l i e a t o rd y n a m i c s ；i t o m o t o p ym e t h o d 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均己在论文中做了明确的说明并表示了谢意。 名埤日躲皆 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 邋 金垒年上五月丝e t 大连理工大学硕士学位论文 1绪论 最大团问题是经典的组合优化问题，最大团问题在国外有相当广泛的研究【l l ，而国内 的研究较少，因此有必要对最大团问题的一些相关知识和应用背景给予介绍，以便更好 地理解这一问题。因此，本章就最大团问题的基本定义，数学描述，理论意义和实际应 用进行了简单的介绍，并且详细介绍有关的研究工作，给出了最大团问题的一个比较全 面的介绍。 1 。1 最大团问题的定义 给定一个无向图( u n d i r e c t e d g r a p h ) g = ( 矿，d ，其中v = l ，n 表示该图的结点 集合、e 矿矿为边的集合。如果对v 中的每一个结点i ，对应了一个正的权，其中 w r ”，则称该图为加权图。对称矩阵a 五为该图的邻接矩阵，其中a = ( 嘞) 。满 足；当边( f ，力e 时= l ，当边o ，) 叠e 时q = 0 。如果一个图g = ( v ，d 满足所有的 结点都相互连接，即v f ，v ，其中f _ ，都有( f ，) e ，则称该图为完全( c o m p l e t e ) 图。如果某个图g 的一个结点子集c 诱导出的子图g ( c ) = ( c ，e c 、( c x c ) ) 是完全的，则 称c 为该图的一个团( c l i q u e ) 。与团紧紧联系在一起的是两个非常重要的概念：极大团 ( m a x i m a lc l i q u e ) 和最大团( m a x i m u mc l i q u e ) 。 定义1 1 所谓极大团就是如果一个团不被任何其他团所包含，即它不是任何其他团的真 子集。 定义1 2 所谓最大团就是一个包含结点最多的团。 从上面的两个定义，我们可以看出，一个极大团不一定是最大团，但最大团一定是 极大团。而所谓的最大团问题( m a x i m u mc l i q u ep r o b l e m ，m c p ) 就是寻找一个给定图 的最大团。 和最大团问题紧密相连的一些经典问题有最大独立集问题( m a x i m u ms t a b l es e t ， m i s p ) 、最小结点覆盖问题( m a x i m u mv e r t e xc o v e rp r o b l e m ，m v c p ) 等问题。最大独 立集问题，就是寻找一个包含结点最多的子集v ，使得这个子集中的结点两两不相连接； 最小结点覆盖问题，就是寻找结点集y 的一个包含v 中结点最少的子集v ，使得矿满 足边集合e 的每一条边至少有一个顶点在旷中。 图g = ( 矿，固的补图记为舀= ( 矿，两，其中云= ( i ，歹) ：主 歹b ，只( f ，力壁e ，对称矩 阵= i = ( i ) 。满足：当( f ，) 面i 对一a v = 1 ，当( f ，) 萑面时i = o 。关于最大团、最大独立 集以及最小结点覆盖有如下关系【l 】： 最大团问题的二元熵函数法及同伦方法 结点子集c c v 是图g 的一个最大团c 是g = ( v ，e ) 的一个最大独立集营v c 是图g = ( 矿，e ) 的一个最小结点覆盖。 其它的相关概念极其加权情况的概念可以参看文献【”。最大团问题是一个经典的 n p 一困难问题( 2 1 。事实上即便找到一个很好的近似解也是一个卜咿一困难问题【3 1 。所以 为了避免或解决解决最大团问题的计算复杂性，人们运用多种方法进行研究。 1 2 最大团问题的数学描述 在最大团问题的研究过程中，人们针对不同的特点给出了不同等价的数学描述。这 些描述反过来又充实了最大团问题的研究。在研究过程中，模型的选择对于研究的效果 和结果有着非常重要的作用，下面我们介绍在最大团问题的研究中常见的几个数学描 述。 1 2 1 离散模型描述 关于最大团问题最简单的公式是边公式1 】： m a x f ( x ) = x j j - 1 s t x j + l ，v ( i ，) e ( 1 1 ) t o ，l ，扛l ，n 定义变换r ：f ( x ) - - i v ：- - 1 ，v x o ，1 ”。对问题( 1 1 ) 有如下结论：若，+ 是问题 ( 1 1 ) 的最优解，则集合c = r ( x ) 是图g 的一个最大团，且i c i = ，( j ) 。 考虑问题( 1 1 ) 的约束条件， o ，1 ，所以薯+ 1 的充要条件是t 一= o 。我们 可以利用这个关系来表示( 1 1 ) 中的约束，即( 1 1 ) 中的约束可以通过在目标函数加上二次 项来消除，问题( 1 1 ) 的目标函数就变为： 厂( x ) = 一t _ = ，( ，一- d ) x f = l 0 j ) e e 其中4 表示图g 的补图g 的邻接矩阵，为，骱单位矩阵，二次项是表示用来惩罚 违反x = 的条件。从而我们得到下面的结论：, x 0 最大团问题等价于下面的全局二次o 1 问题： m a x f ( x ) = x ( i - a ) x 豇x o ，l ”( 1 2 ) 大连理工大学硕士学位论文 且若r 是问题( 1 2 ) 的最优解，则c = t ( x ) 定义的集合c 是图g 的一个最大团，且 i c j = ( x + ) 。通常为了计算上的习惯，我们通过把目标函数八力换成，( 功把极大化问 题改为极小化问题。其它的一些离散模型描述方式和加权情形可参阅文献f i 】，在此不再 赘述。 1 2 2 连续模型描述 1 9 6 5 年，m o t z k i n 和s t r a u s 在1 4 1 6 p 给出了最大团问题的二次规划模型： m a x三苫7 爿x “ t = 1 ( 1 3 ) 玉o ，i = 1 ，刀 其中4 表示图g 的邻接矩阵，对于这个单纯型约束的二次规划模型m o t z k i n 和 s t r a u s 在该文中还给出了如下定理： 定理1 1 ( m o t z k i n s t r a u s 定理) 如果令口表示( 1 3 ) 的最优值，则g 有一个规模为k = 1 1 2 a 的最大团。设这个最大 团为c ，则这个最大值可通过令x = 1 k ，f cr ：t 及x j = o ，f 仨c 得到。 对于上述定理，需要说明的是它描述了一种寻求最大团规模的全局优化方法，但是 并不能给出这个最大团的构成结点。根据定理l 。1 可知，若最大团c 已知，则由置= l k ， i c 以及置= 0 ，f 萑c 得到目标函数在约束条件下的全局最优解石。因此不同的最大团 给出问题( 1 3 ) 不同的最优解。然而逆命题不成立。可以参看下面的例子： 例1 ，1 考虑图g ，它有3 个接点l 、2 、3 ，两条边( 1 ，3 ) 和( 2 ，3 ) ，则它的邻 接矩阵为 f o 01 止 纠 目标函数为( 力= 2 ( x ，x 3 + x 2 x 3 ) 。利用约束等式关系可以将问题转化成线性约束的 凸极小化问题，根据k k t 条件，或者直接验证，可以知道满足五十，：= l 2 的每组而0 和x 2 0 是全局最优解，因此每个点, , 0 2 一j ，s ，1 2 ) 其中0 ss 1 2 是 厂( 工) = 2 “玛+ x 2 x 3 ) 在约束条4 牛- t 的全局极大点。但是图g 只有两个最大团，即 l ，3 和 2 ，3 。 最大团问胚的二元熵函数法及同伦方法 对于子集s 矿，我们定义特征向量嬲f ：1 i s l ，f s 以及= o ，i 芒s 。从上面的例 向量形式的解。这个问题已经被b o m z e _ 5 1 解决。他考虑( 1 3 ) 的正则化形式： 一飘小2 小 2 l， s j e x , = l ( 1 4 ) 其中a 为图g 的邻接矩阵，肋册单位矩阵对于问题( 1 4 ) b o i i l z 【习给出了如下的定理： 1 、x = ，其中c 是图g 大小为j i = i c i 极大团； 科4 剖x = 弘去) b o m z e 等在文献m 中给出了模型( 1 3 ) 的一个等价模型，为了去除置o ，f = l ， 作替换= 拜，从而= l 变为圳| 2 = 1 ，其中00 表示欧式模。进而模型( 1 3 ) 变为球面 l y 7 x a x y 一 肚刎2 = 1 ( 1 5 ： 。 大连理工大学硕士学位论文 1 3 最大团问题的实际应用和理论意义 在实际应用中，很多问题都可以写成一个最大团问题或者在求解过程中包含一个最 大团问题作为子问题。这就使得研究最大团问题的精确和近似算法显得尤为重要。许多 关于计算复杂性的问题也与最大团问题有着很大的联系。如在1 9 9 1 年，c r e s c e n z i ， f i o r i n i 和s i l v e s t r i i v l 证明了如果最大团问题存在多项式时间的近似算法，那么任何的 n p 问题都能在准多项式时间内求解。 最大团问题作为一个经典的组合优化问题，在诸如市场分析、方案选择、电路板设 计、信息检索、信息恢复、容错、实验设计、模式识别、机器入、密码理论、信号处理 与计算机视觉方面都有着广泛的应用【”，并且因为最大团问题在计算上和最大独立集问 题和最小结点覆盖等诸多n p h a r d 问题等价，在多项式时间内可以转化成h a m i l t o n 圈 问题、h a m i l t o n 轨问题、货郎担问题等【射，所以在理论上也具有很大的借鉴意义。 1 4 最大团问题的相关研究 最大团问题的研究主要分为确定性算法和启发式算法两大类，但是需要说明的是这 些方法的分类并不是那么严格，往往一篇论文中几种方法结合起来使用。由于确定性算 法本身的局限性，对于结点数目比较少，边密度比较低的图而言，确定性算法还行，但 是随着研究的深入。正因为此，人们开始应用启发式算法来研究最大团问题，它的优点 是随着结点和边密度的增加，运算时间和确定性算法的运算时间之比越来越小。现在广 为应用的启发式算法主要有序列启发式算法、局部启发式算法和包括遗传算法、神经网 络、模拟退火及禁忌搜索等在内的高级启发式算法。但这些启发式算法不一定能找到最 优解，有时只能得到近似最优解。有关确定性算法和启发式算法在最大团问题中应用的 研究成果十分丰硕。下面进行详细的介绍： 1 4 1 确定性算法 确定性算法包含枚举法和隐式枚举法两大类，其中后者是对前者的一种改进。 ( 1 ) 枚举法 所谓枚举法，就是将一个图的所有团全部给出，然后寻求最大的团。枚举法肇始于 1 9 5 7 年h a r y 和r o s e 的论文【9 】。受矩阵模拟的启发，在该文中，他们给出了一个诱导方 法。该方法的思路就是首先确定一个带有不超过三个团的图的所有团，然后把更一般的 图过渡到这样的图上来进行求解。 随后的研究有p a u l l 和u n g e r 1 0 】，及m a r c u s 1 1 】提出的最小化一系列开关函数和流水 盘的行数的算法；b o n n e r 1 2 】论述了信息系统的聚点问题；b e d n a r e k 和t a u l b e e 【1 3 】提出的 最大团问题的二元熵函数法及同伦方法 生成一个集合的所有极大链和定义其上的二元关系。尽管这些问题来自不同的领域并且 处理的问题也差别很大，但是它们可以用来枚举一个图的所有团。只是限于当时技术的 局限性，早期的这些算法只适用于一些特殊结构的团。 1 9 7 0 年，a u g u s t o n 和m i n k e r 1 4 1 研究了在信息系统中应用的一些图的聚点技术，在 他们的工作中，比较了b i e r s t o n e 和b o n n e t 算法。在这两个算法中应用的方法称为结 点序列方法或者点移除方法，通过比较发现b i e r s t o n e 更有效。但是b i e r s t o n e 的早期 结果并没有发表，他的工作包含在a u g u s t o n 和m i n k e r 的工作之中。 1 9 7 3 年，a k k o y u n l u 1 5 1 及b o r n 和k e r b o s c h 16 】分别提出的两种算法中运用了后退方 法。这一方法具有两个优点：一是后退方法消除了在生成同样团的过程中多余的元素； 第二个，也是更重要的是仅要求多项式时间存储，在他们的试验中的一个非常有意思的 现象就是c p u 的时间和图结点数之间的比率几乎不依赖于图的规模。他们发现他们的算 法比b i e r s t o n e 算法更加有效。 在七十年代，更多的枚举算法得以提出。o s t e e n 和t o u 1 7 】将点移除方法进行了改进。 m e e u s e n 和c u y v e r s i 培】的算法则是将图分解成满足图的子集链法则的子集。这样的一个 分解使得每一个团至少包含在一个子图当中，因此，他们给出了一个寻求一个图所有团 的算法。j o h o s t o n 的主要工作【”】则包含了一系列b o r n 和k e r b o s c h 算法的改进。在该 文中，作者通过计算比较了一些算法，说明b o r n 和k e r b o s c h 的方法是最有效的方法之 一。t s u k i y a m a z 0 3 等人结合文献【1 4 t 16 】和a k k o y u n l u 方法给出了一个最强的界限。6 e r h a r d s 和l i n d e n b e r g 的论文1 2 l 】给出的算法对于一般的图而言并没有很大的改进，但是对于稀 疏图则要有效得多。 在8 0 年代，人们也给出了一些其他的算法。l o u k a k i s 和t s o u r o s 2 2 冶出了一个名 为深度优先枚举法的算法，该算法能够按照字典顺序生成全部极大团并且试验表明他的 算法对于多达2 2 0 个结点的图比中的算法要快2 到1 5 倍。1 9 8 8 年，j o h n s o n 等在【2 3 1 中提出了一个算法可以将图的极大独立集按照字典顺序全部给出，并且这个结果在计算 复杂性比【2 2 崤了改进。t o m i t a 等在【2 4 1 中给出了b o r n 和k e r b o s c h l l 旬中算法的改进，它 的计算复杂度为0 ( 3 邮1 ，且这个结果是具有3 邮个极大团的m o o n - m o s e r 图的最好的结 果。 ( 2 ) 隐式枚举法 如果仅仅寻求图的一个最大团或者最大团的规模，那么对于上面的枚举法而言可以 节省很多工作。因为一旦找到一个团，我们只需找到所有其他的比当前团大的团即可。 基于这一思想，修正枚举法就得到了隐式枚举法。 6 一 大连理工大学硕士学位论文 在最大团问题的研究中运用最为广泛的隐式枚举法就是分支定界法。关于分支定界 的背景知识可以参看文献【2 5 1 。最大团问题的分支定界法的关键是：如何找到一个好的下 界，即一个大的团数；如何找到最大团规模的一个好的上界；如何分支，也就是说如何 将问题分解成若干个子问题。 上世纪7 0 年代d e s l e r 2 6 1 和h o u c k 2 7 的工作给出了最大团问题的隐式枚举法的最早 研究。随后十多年，人们将这一方法迅速的应用到其它和最大团问题相关的问题之中， 取得了很多成果，反过来这些成果又推动着最大团问题的研究。 关于隐式枚举法在最大团问题应用中的研究中，8 0 年代最重要的成果之一就是 b a l a s 和y u 在文【2 8 】中给出的。他们的算法将隐式枚举法以一种新的方式加以应用。其 主要思想就是：首先找到图g 的一个极大诱导三角剖分子图d ，然后找到d 的一个最大 团，这个团给出了原最大团问题的一个下界和一个可行解，再运用启发式染色过程将d 扩展到更大的子图，使得没有比当前最大团更大的团，这一步的重要性体现在它减少了 由搜索树的每一个结点生成的子问题的数目，从而减少了整个搜索树的规模。他们在多 达4 0 0 个结点3 0 0 0 0 条边的图上进行了数值试验并和其它方法进行了比较，结果表明他 们的算法不仅只产生了较小的搜索树，而且需要的c p u 时间也短。 在8 0 年代后期，也有新的算法提出。t o m i t a 等在【2 9 】中运用贪婪着色算法得到最大 团数的一个上界。p a r d a l o s 和r o d g e r s 在文【3 0 】中基于最大团问题的一个无约束二次0 - 1 规划模型，并且运用了贪婪和非贪婪两种不同的分支准则进行了试验。 进入了9 0 年代以来，关于这一类的研究仍在发展，也出现了相当多的成果。b a b e l 和t i n h o f e r 在文【3 1 】中给出了最大团问题的一个分支定界方法，该方法的主要构成部分 是利用快速的并且可以相对较好的解决最小着色数问题的启发式算法。在【3 2 】中， b o u r j o l l y 等提出了一个嵌入在分支定界方法中的列生成方法，从而得到最大团问题的 一个较好的下界和最小结点覆盖问题的线性松弛的一个有效割。 运用分支定界方法研究最大团问题的最新成果还利3 3 】，在该文中，t o r s t e nf a l h e 结合运筹学和约束优化，运用域过滤方法和上下界技术来改进分支定界方法得到了最大 团问题的一系列新成果，并且结果显示该方法得到的结果优越于先前单一应用有关技术 的结果。 1 4 2 启发式算法 因为最大团问题的计算复杂性，事实上即便近似求解也非常困难，所以近来更多的 研究侧重于设计有效的近似算法。尽管这些研究不能保证解的质量，但是具有很高的实 用价值，因此应用近似算法来研究最大团问题也成为一个热点。 最大团问题的二元熵函数法及同伦方法 ( 1 ) 序列贪婪启发式算法 所谓序列贪婪启发式算法就是反复向一个团中添加结点，或者从一个不是团的子图 中反复去除结点直至得到一个团。k o p f 和r u h e 在【3 4 】中将其分别定义为最优进和最差出 启发式算法。至于如何决定下一个结点谁进谁出，则依照候选点的一定指标参数。例如， 在构建一个极大团的最优进启发式算法中，对于所有的结点集合反复移除结点直至成为 一个团。 k o p f 和r u h e 进一步将上面的最优进和最差出启发式算法分成新旧两种。即，如果 在一个结点加入或者移除的时候指标得到改善，则成该启发式算法为新的启发式算法， 否则就称为旧的启发式算法。我们可以看到最大团问题的很多启发式算法都可以归为其 中的一个，j o h n s o n 3 5 1 和t o m i t a 3 川等人的启发式算法。这些算法的差别就是指标集的选 取以及指标如何得到改善。总体而言，这一类启发式算法的计算还是比较快的。 ( 2 ) 局部搜索启发式算法 上面介绍的序列启发式算法的一个缺点就是只能够找到一个极大团，并且一旦找到 了一个极大团，搜索就停止。我们可以从另一个不同的角度看待这类启发式算法：设& 是图g 所有极大团的集合，序列启发式算法就是寻求其中的一个元素，并且希望它就是 至少接近最大团。这就提示我们，如果扩大搜索范围就可以改善搜索结果，从而得到了 局部搜索启发式算法，详细论述可以参阅【3 7 l 在局部搜索启发式算法中，如果我们搜索s & 更多的相邻元素，那么得到一个更 好解的可能性就加大了。根据邻域的定义和搜索方式不同，应用不同的局部搜索启发式 算法，我们可以得到不同的结果。k - 交换启发式算法就是一个比较典型的局部搜索启发 式算法。这一方法就是基于一个可行解的k _ 邻域实现的，因此影响此方法复杂性的主要 因素是邻域的大小和搜索方式，并且这一个方法随着邻域规模的增大，搜索代价之高逐 渐超出承受能力。而对于不同的晶，设计的一类启发式算法称为随机启发式算法。在 实际应用中，往往把随机启发式算法和局部搜索结合起来，如文【3 8 】，在该文中，二者结 合以后的算法在解决大规模的随机生成图的最大独立集问题相当有效。 局部搜索启发式算法的一个缺点就是只能找到一个局部最优解，这就在一定程度上 限制了算法的作用。 ( 3 ) 高级启发式算法 随着现代优化算法的发展，针对局部搜索启发式算法的缺点，人们基于局部搜索启 发式算法，提出了很多有效的算法。主要包括模拟退火、神经网络、遗传算法、禁忌搜 索和其他启发式算法。 模拟退火启发式算法 大连理工大学硕十学位论文 模拟退火【3 9 】，是一种随机搜索算法，多用于复杂的组合优化问题及n p 问题 4 0 9 。它 是解决组合优化问题的通用算法，并且只要优化问题能提供一个对候选方案的适应性函 数或费用函数，即可使用模拟退火算法对它求解。有关模拟退火启发式算法的理论和应 用的论述可以参看【4 1 】【4 2 】。 a a r t s 和k o r s t 在文【4 2 】中建议结合罚函数方法使用模拟退火算法来解决独立集问 题，但是没有给出具体的数值试验。j e r r u m 等人【4 3 】则在随机图上，对模拟退火 m e t r o p o l i s 过程能找到的解的效果进行了理论分析，但是在期望的时间内模拟退火方法 所需要的时间比简单的贪婪启发式算法要多，而且随着结点个数的增加，所需的时间增 长速度要比任何多项式还大，因此他认为模拟退火方法不适合解决最大团问题。 然而，实际数值试验得到的结论和j e r r u m 的结果相矛盾。在】中h o m e r 和p e i n a d o 比较了模拟退火启发式算法和j o h n s o n 的贪婪启发式算法、b o p p a n a 和h a l l d o r s s o n 的 子图排除算法【4 5 】的随机形式，结果显示模拟退火启发式算法比其他的算法还要好，并且 成为解决1 9 9 3 年d i m a c s 中最大团问题的最好的启发式算法之一。 尽管如此，模拟退火算法存在的主要问题是运行时间太长，起性能有时甚至不如简 单的枚举法。模拟退火算法本身具有内在的串行性要求，即下一点的选取明显依赖于上 一点，不易实现高效的大规模并行化处理；其次，模拟退火算法的性能对参数及初始值 的选取十分敏感，不同的参数可能导致算法性能的巨大差异。而优化参数设置和具体的 问题有密切的关系，这些方面限制了模拟退火算法的应用效果。 神经网络启发式算法 神经网络算法是在人类对大脑神经网络认识理解的基础上人工构造的能够实现某 种功能的神经网络，它是理论化的人脑神经网络的数学模型，是基于模仿大脑神经网络 结构和功能而建立的一种非算法的信息处理系统。它具有高度并行性、高度非线性全局 作用、良好的容错性与联想记忆功能和十分强的自适应性、自学习功能。神经网络在自 动控制、系统识别、模具识别、机器人等多个领域得到广泛的应用，详细讲解可参阅m 】。 上世纪8 0 年代，h o p f i e l d 和t a n k 4 7 1 首先将神经网络算法应用到旅行商问题，从而 开创了神经网络在组合优化中应用的先河，并且为用神经网络来求解其他组合优化问题 提供了一个总体思路。此后人们开始应用神经网络来求解最大团问题及其相关问题，这 些早期的结果可以参看1 4 2 1 1 4 8 1 ，只是这些早期的研究成果没有或者很少有数值试验，所以 很难评断算法的优劣。l i n 和l e e 在i 删中利用二次0 1 模型作为神经网络启发式算法的 基础，数值试验表明本方法对于多达3 0 0 个结点的随机图而言优于隐式枚举法。 g r o s s m a n 5 0 】给出了一种离散的确定性的h o p f i e l d 模型来求解最大团问题，这个模型使 用了一个用来决定网络是否处于稳定态的临界参数。 最大团问题的二元熵函数法及同伦方法 j a g o t a 5 1 】给出了了h o p f i e l d 模型的几个变形来逼近最大团问题，有离散的，也有 连续的。后来，他又在1 5 2 中进行了改进。与其他简单启发式算法相比，这些结果可以得 到更大的团，但是时间上稍微长些；而与其他复杂的启发式算法相比，虽然找到的最大 团较小，但速度较快。 最近，a b e r t o n i 等人在文【5 3 】中给出了基于一系列离散时间的h o p f i e l d 模型的神 经网络算法一迭代h o p f i e l d 网算法。数值试验表明，该算法的计算稳定性，并且该算法 对于d i m a c s 的考题而言，可以和任何已知的启发式算法媲美。此外，该算法因为不涉 及到参数更改，并且算法简单，易于程序实现。 遗传启发式算法 遗传算法是一种基于自然选择和群体遗传激励的平行搜索算法，它模拟自然选择和 自然遗传过程中发生的复制、交叉和变异现象。关于遗传算法的相关论述可参阅【洲。 1 9 9 3 年，c a r t e r 和p a r k e r 在文【5 5 】进行了应用遗传算法来求解最大团问题的最早尝 试。在发现遗传算法解决大规模图、甚至是小规模图的随机图的最大团中的缺点后，他 们进行了一系列的修改，但是并没有取得令人满意的结果。因此，他们认为如果要得到 和传统方法类似的结果，需要做很大的调整，并且计算量太大。后来在文【5 6 l 中他们证明 了遗传算法不如退火算法有效。但是几乎同时，b a c k 和k h u r i i 57 】在研究最大独立集问题 的时候得到了相反的结论。这就说明，应用遗传算法解决最大团问题时，适应函数的选 择对于得到好的结果具有非常关键的作用。 1 9 9 5 年，b u i 和e p p l e y 5 8 】应用了一个杂交策略，并得到不错的结果。这一个策略就 是在遗传算法中的每一代都结合局部优化算法和结点排序预处理过程。而f l e u r e n t 和 f e r l a n d ”】贝使用了杂交遗传框架，这一框架是把禁忌搜索和其他的局部搜索技术结合 起来作为交叉变异算子进行的。虽然计算结果质量不错，但是计算时间太长。 m a r c h i o r i 6 0 1 研发了一个简单的基于启发式算法的遗传算法，在该算法中作者结合 了简单遗传算法和简单贪婪启发式算法过程。对d i m a c s 标准考题的数值试验表明，这 一算法无论在得到解的质量上，还是计算时间上，比以前的遗传算法都要好。 蚁群算法是一种新型的模拟进化算法，受自然界中蚂蚁搜索事物行为的启发而提出 的一种智能优化算法。s e r g e 和c h r i s t i n es o l n o n 6 1 】应用蚁群算法进行了研究。数值试 验表明该算法对于很多d i m a c s 考题而言都可以找到最优解，但是并非对全部考题。 2 0 0 4 年，周旭东在他的硕士论文【6 2 】中采用了思维进化算法对最大团问题进行了求 解，并且在该文中，作者将其和反作用局部搜索和启发式遗传算法进行了比较，数值试 验表明该算法性能优于h g a ，和r l s 相当，是当前求解最大团问题的最好的启发式算法 之一。 一1 0 大连理工大学硕七学位论文 禁忌搜索启发式算法 禁忌搜索是由g l o v e r l 6 3 】畔】、h a n s e n 和j a u m a r d e 6 5 1 分别提出来的。它是为了解决局 部搜索中出现死循环并且开发新的搜索区域而对局部搜索算法的一种改进。正因为这些 优点，人们很快就将这一算法引入到最大团及其相关问题的研究之中。1 9 8 9 年，f r i d e n 等人【6 6 】以禁忌搜索为基础研究了最大独立集问题，从而开创了禁忌搜索在最大团问题研 究中应用的先河。文f 6 7 ) 【吲给出了解决最大团问题的禁忌搜索方法三个变形。最近，b a t t i 和p r o t a s i 6 9 通过引入反作用局部搜索将禁忌搜索方法进行了扩展，这一过程的特点就 是避免内在反馈圈的控制参数的人工选择，大量的数值试验表明了该算法的有效性。 其它启发式算法 除了上述的几大类启发式算法以外，还有一些方法研究较少也不容易归纳，所以我 们在此简单介绍。 子图方法，它是基于图g 的子图的团也是图g 的一个团这个事实而提出的。这一个 方法的优点是寻求了子图的最大团时，就已经搜索了子图的很多其他团。 受人类和动物在探究位置上的本能的激发，人们提出了一种基于群体的优化启发式 算法【7 0 】，并用其解决最大团问题。数值试验表明该算法和基于连续化的启发式算法相当， 但是不如反作用局部搜索方法。 近年来，由于d n a 算法的高平行性的优点，所以人们也应用这一技术来求解最大 团问题，如i 竭。还有很多其他的成果，这里就不再赘述，有兴趣的可以参阅文1 1 中的 介绍。 1 4 3 半定规划和半定松弛方法 上述两类方法所能求解问题的规模受到了很大的限制。随着内点算法在求解线性规 划问题取得的巨大成功，半定规划方法成为近期研究的热点，并成功地引进最大团和最 大割等组合优化问题。关于半定规划和经典内点法的有关知识可以参看【7 3 】，而关于半定 规划在组合优化中的应用，可以参阅 7 4 】f “，在该文中，m x ，g o m e m a n s 以最大稳定集和 旅行商问题和二次指派问题等为例给出了半定规划在组合优化中的应用的一个综述。此 外，k a r t i kk r i s h n a n 在报告【撕1 中，运用了协正定规划的半定松弛的方法给出了极大独立 集问题的求解的尝试。在【7 7 】中，l o v a s z 给出了最大稳定集一个新的模型公式，并且运用 该半定规划模型可以给出最大稳定集的稳定数的一个上界i o v a s zt h e t a 数。从理论上 讲，这一上界在应用隐式枚举法如分支定界方法来解决最大稳定集时非常实用。2 0 0 2 年，s b u r n e r 等人 7 8 1 结合l o v a s z t h e t a 数给出了最大稳定集问题的基于连续优化的启发 式算法。借助l o v a s zt h e m 数，人们对最大团问题及其相关问题展开了很多研究，这一 最大团问题的二元熵函数法及同伦方法 部分可以参看【7 8 】中的介绍。其中，最近，i g o r d u k a n o v i c 和f r a n zr e n d l 7 9 1 应用半定规划 和半定松弛得到了最大团极其相关问题的研究成果。 1 4 4 其他相关的一些研究方法 上面介绍的研究基本上都是基于离散模型展开的，但是对于优化领域中用来解决连 续形式的问题的研究工具和方法，就不能很好的应用。在很多离散优化问题的研究中， 人们会应用连续化方法将离散问题连续化，从而利用连续优化的工具进行研究。而( 1 3 ) 正好是一个连续化模型，我们可以很简单将研究工具推广到连续化领域。另外需要说明 的是