（运筹学与控制论专业论文）最大团问题的熵正则化方法研究.pdf

大连理工大学硕士学位论文 摘要 最大团问题是组合优化中的一个经典的n p 完全问题。此问题自被人们发现之后， 广为研究和应用。但是因为问题本身的复杂性，所以人们将研究的重点放在了问题的近 似计算上，即启发式算法，并且得到了一系列的研究成果。 最大团问题有相当多的等价的数学描述，并且针对不同的模型具体的研究方法也有 一定的差别。本论文的研究是基于1 9 6 5 年m o t z k i n 和s t m u s 给出的一个二次连续化模 型。该模型的优点就是将最大团问题的研究方法和工具推进到了连续的领域。在此问题 模型的基础上，针对该模型中因为图的邻接矩阵在一般的情况下多是退化矩阵而导致的 病态，人们进行了一系列处理，并且得到了不错的结果。 对于m s 模型，它的另外一个优点，或者说更为重要的是。该模型的约束条件表 示为一个单纯形的形式。根据该形式，我们可以运用信息论的知识来进行研究。正是基 于此，我们给出了最大团问题的信息论方法熵函数方法和叉熵函数方法，以及d 函 数正则化方法。其中我们在第三章中给出的是熵正则化方法和叉熵正则化方法，第四章 给出的是d 函数正则化方法，这两章是本文的主要工作，我们分别从模型建立、模型分 析和算法设计三部分展开论述。为了方便起见，在第五章，我们给出了这两种方法的简 单对比、数值试验及简单分析。由此可以说明这两种方法可以减轻原模型的病态，初步 的数值试验表明与其他类似的复杂方法相比较，这两种方法可以得到类似的结果，从而 也就说明了方法的有效性，是值得进一步研究的两个方向。 关键词：最大团问题；信息论方法i 同伦方法；熵正则化；d 函数正则化 最大团问题的熵正则化方法研究 r e s e a r c ho i lt h ee n t r o p i cr e g u l a r i z a t i o nm e t h o d f o rt h em 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 mi so n eo ft h ec l a s s i c a ln 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 e v e rs c i e n c et h ep r o b l e mw a sp r o p o s e d ，m a n yr e s e a r c ha n d a p p l i c a t i o n sh a v eb e e nd o n e b u tf o rt h ec o m p l e x i t y , m o r er e s e a r c h e sa r ef o c u s e do nt h e a p p r o x i m a t i o nm e t h o d ，i no t h e rw o r d s ，h e u r i s t i c ，a n dg e tm a n y r e s u l t s t h em a x i m u mc l i q u ep r o b l e mh a ss o m ee q u a ld e s c r i p t i o n s ，a n dt h er e s e a r c hm e t h o d s d i f f e ro nd i f f e r e n tm o d e l s t h cr e s e a r c ho ft h i sp a p e ri sb a s e do nt h ec o n t i n u o u sq u a d r a t i c m o d e lw h i c hw a sp r o p o s e db ym o t z k i na n ds t r a u si n1 9 6 5 n l em e r i to ft h i sm o d e li st h a ti t e n a b l eu su s et h et o o l sf o 肿c o n t i n u o u sf i e l d b u tf o rt h ea d j a c e n tm a t r i x e si nt h i sm o d e la l e a l w a y sd e g r a d e d ，t h ep r o b l e m sa r ei l l - p o s e d s om a n yt e c h n i q u e sa r eu s e dt or e l e a s et h e i l l - p o s n e s sa n dg e t as e r i e so f r e s u h s m l a t si m p o r t a n t , t h ec o n s 仃a i n tc o n d i t i o ni nt h em o d e li se x p r e s s e da sas i m p l e x a n d t h i se n a b l eu sl l s et h ei n f o t i n a t i o nt h e o r y a sar e s u l t t h ei n f o r m a t i o nt h e o r ym e t h o df o rt h e m a x i m u mc l i q u e - - - e n t r o p yf u n c t i o nm e t h o da n dg l o s s e n 仃o p yf u n c t i o nm e t h o d ，a n d d - f u n c t i o nr e g u l a r i z a t i o nm e t h o da r e i n t r o d u c e dh e r e i nc h a p t e r3 t h ee n t r o p yr e g u l a r i z a t i o n m e t h o da n dc r o s s e n t r o p i cr e g u l a r i z a t i o na r ei n t r o d u c e d ，a n di nc h a p t e r4t 1 1 ed - f u n c t i o n r e g u l a r i z m i o nm e t h o di si n t r o d u c e d t h e s et w oc h a p t e r sa r et h em a i n w o r ko f t h ep a p e r b y i n t r o d u c i n gt h ef o u n d a t i o no ft h em o d e l s ，t h ea n a l y s i so ft h em o d e l sa n dt h ea l g o r i t h m s d e s i g n w eg i v ea no v e r a l li n t r o d u c t i o no fo u rm e t h o d s i nt h ec h a p t e r5 s o m es i m p l e c o m p a r i s o n st h en u m e r i c a le x p e r i m e n t sa n ds i m p l ea n a l y s i so f t h em e t h o d sa r eg i v e n s i m p l e a n a l y s i ss h o w st l l a to u rt w om e t h o d sc a nr e l e a s et h ei l l p o s e n e s s a n dc o m p a r i n gw i t ho t h e r c o m p l e xm e t h o d s ，w en e a r l yg e tt h es a m er e s u l t s ，s ot h ev a l i d i t ya n dt h es t a b i l i t yo fo u r m e t h o d sa r es h o w n j 乃口st h e ya r ew o r t h 缸 t h e rr e s e a r c h i n g k e yw o r d s ：m a x i m u mc l i q u ep r o b l e m ；i n f o r m a t i o nt h e o r ym e t h o d ；h o m o t o p y m e t h o d ；e n t r o p yr e g u l a r i z a t i o n ；d f u n c t i o nr e g u l a r i z a t i o n 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 莹痉垒日期：迦! ：坌型 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 二参髫垄 大连理工大学硕士学位论文 l引言 作为一个经典的组合优化问题，最大园问题在国外有相当广泛的研究1 1 1 ，而国内的 研究则刚刚起步，研究成果相对较少，因此有必要对最大团问题的一些相关知识和应用 背景给予介绍，以便更好地理解这一问题。正是基于此，本章就最大团问题的基本定义、 数学描述、理论意义和实际应用进行了简单的论述，并且详细介绍了有关的研究工作， 给出了最大团问题的一个比较全面的介绍。 1 1 最大团问题的定义 给定一无向图( u n d i r e c t e dg r a p h ) g = ( v ，e ) ，其中v = 1 ，n ) 表示该图的结点集合、 e v x 矿为图的边集合。如果对v 中的每一个结点i ，对应一个正的权，其中w 础， 则称该图为加权图。对称矩阵彳r 为该图的邻接矩阵，其中彳= ( ) 。满足：当 边( j ，j ) e 时= 1 ，当边( i ，j ) 芒e 时口。= 0 。如果个图g = ( v ，e ) 满足所有的结点都 成对相连接，即v f ，j v ，其中i ，都有( f ，) e ，则称该图为完全( c o m p l e t e ) 图( 有 的译作完备图) 。如果某个图g 的一结点子集c 诱导的子图g ( c ) = ( c ，e n ( c x c ) ) ( s u b g r a p h ) 是完全的，则称c 为该图的一个 ( c l i q u e ，有的译作“派 ) 。与团紧紧联系在 一起的两个广为研究的闽题就是极大团( m a x r e a lc l i q u e ) 和最大团恤a x i m u mc l i q u e ) 。 定义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 p r o b l e m ，m s s p ，或者称为最大独立集问题，m a x i m u mi n d e p e n d e n ts e tp r o b l e m ，m i s p ) 、最 小结点覆盖问题( m i n i m u mv e r t e xc o v e r p r o b l e m ，m v c p ) 等问题。关于它们之间的关系， 我们可以结合图1 1 给出直观解释： 最大团问题的熵正则化方法研究 2 4o o 5 1 09 工 o 6 3 图1 j 最大团问题及其相关问题 f i 9 1 1m c p i t sr e l a t e dp r o b l e m 在图1 1 中，由结点l 、2 、3 组成的团是该图的最大团，而由7 、8 两个结点组成的 图是孩图的一个极大团，如果再加上结点9 ( 图中虚线表示该边不存在，只是为了叙述 方便加上的) ，则就不能组成极大团了，因为结点8 和结点9 之间没有边相连接，由结 点4 、5 、6 组成的是图的一个稳定集( 独立集) ，加上结点9 之后，就组成该图的一个 最大稳定集，而这个图的最小结点覆盖则有 l ，2 ，7 、 1 ，3 ，7 、 2 ，3 ，7 ) 及f l ，2 ， 8 ) 、 l ，3 ，8 和 2 ，3 ，8 六个。关于这几个问题的严格定义，我们这里给出： 最大矬立集问题，就是寻求一个包含结点最多的结点集矿的子集，并且这个子集中 的结点两两不相邻接；最小结点覆盖问题，就是寻求结点集v 的一个包含y 中结点最少 的子集v ，使得该子集满足边集合e 的每一条边至少有一个顶点在这个子集矿中。为 了便于理解它们之间的关系，我们给出下面的关系式： 结点子集c 矿是图g 的一个最大团结点子集c 矿是图g 的补图 g = ( 矿，( y x y ) e ) 的最大独立集v c 是图g 的补图g 的一个最小结点覆盖。 其它的相关概念及其加权情况的概念可以参看文献f 1 1 。 最大团问题是一个经典的n p 一困难问题i ”，事实上即便很好的近似计算也是一个 n p 一困难问题1 3 】。所以为了避免或者解决最大团问题的计算复杂性，人们运用多种方法 进行研究。 1 2 最大团问题的数学描述 在最大团问题的研究过程中，人们针对不同的特点给出了不同的等价数学描述，这 些数学描述反过来又充实了最大团问题的研究。在研究过程中，模型的选择对于研究的 大连理工大学硕士学位论文 效果和结果其有看非常重要的作用，所以我们下面介绍在最大团问题的研究中常见的几 个数学描述。 数学描述一【1 】： 首先，关于最大团问题的最简单的公式是边公式( e d g ef o r m u l a t i o n ) ： m a x 厂( x ) = 葺 j j + 1 ，v ( i ，- ，) e ( 1 1 ) x i o ，l r i = 1 ，卅 定义变换设f ：( o ，1 ) 一2 ，f ( 工) = f v ：= 1 ) ，v x o ，1 ) ”，则( 1 一1 ) 等价于下面的 公式： m i n ，( z ) = 一x i s ， + x j 1 ，v ( i ，) 吾( 1 - 1 ) x o ，1 ” 并且如果x 是( 1 一1 ) 的最优解，则集合c = t ( x ) 是图g 的一个最大团，且 l c l = 一f ( x ) 。 数学描述二【。】： 设变换f 如上面所定义，# a v s 2 ”，贝l j x = t “( s ) = t ：f _ 1 ，2 ，聆 ， 其中t = 慨1 , i 堙e s s ，行为图的结点的个数。又因为一，_ o ，1 ，所以+ _ 1 的 充要条件是x ，= 0 。我们可以利用这个关系来表示( 1 一1 ) 中的约束，即( 1 一i ) 中的约束 可以通过在目标函数上加上二次项来消除，问题( 1 一1 ) 。的目标函数变为 ，( z ) = 一x 。+ 2 x , x s = ，( 白- i ) xa 其中南表示图g 的补图否的邻接矩阵，二次 项表示用来惩罚违反蕾= 0 的条件。从而得到下面的结论： 最大团问题等价于下面的全局二次0 - 1 问题： m i n 厂( x ) = 一a x ( 1 2 ) nx o ，1 ”其中4 = 南- i 最大团问题的熵正奂u 化方法研究 并且若z 为( 1 2 ) 的最优解，则由c = t ( x ) 定义的集合c 为g 的最大团，且 1 c j = 一，( f ) 。 数学描述三： 1 9 6 5 年，m o t z k i n 和s 廿a u s 在中给出了最大团问题的二次规划模型： m a xx t 4 x 2 旺t=1(1-3) t 0 , i = 1 ，栉 其中爿表示图g 的邻接矩阵，x ，的值表示第i 个结点选入最大团的可能性。 并且在该文中给出如下定理： 定理1 1( m o t z k i n - s t r a u s 定理) 如果令口表示问题( 1 3 ) 的最优值，则图g 有一个规模为k = 1 ( 1 2 口) 的最大团。这 个最大值可以通过如下方法得到：对于f c ，令t = 东；对于堙c ，令= 0 。 对于上述定理，需要说明的是它虽然描述了一种寻求最大团规模的全局优化方法， 但是并不能直接给出这个团的构成结点。根据定理1 1 可知，若最大团c 已知，则由 t = i k ( i c ) 和= 0 ( i 仨c ) 定义的点z 是目标函数五在约束条件上的全局极大 点。因此，不同的最大团给出问题( 卜3 ) 不同的最优解。然而逆命题不成立。可以参看 下面的例子： 例1 1 考虑图g ，它有3 个结点1 、2 、3 ，两条边( 1 ，3 ) 和( 2 ，3 ) ，则它的 邻接矩阵为 r o 0 1 、 肚：j 和目标函数为t o = 2 ( x l x 3 + x 2 x 3 ) 。具体意义和表示如图1 2 所示： 大连理工大学硕士学位论文 i 、， 、 ：j 一? 、。、j 一。- 一 图1 2 f i g i 2 利用约束等式关系可以将问题转化成线性约束凸极小化问题，根据k k t 条件，或 者直接验证，可以知道满足五+ 工2 = 1 1 2 的每组2 0 和x 2 0 是全局最优解，因此每个 点z = 圭一s j 1 】( 。s 三) 是五在约束条件上的全局极大点。但是图g 只有两个最大 团，即 1 ，3 ) 和 2 ，3 ) 。关于这一问题及其解决办法，我们在本章的1 4 2 中给出。 数学描述四： i m b o m z e 等在”1 给出了( 1 3 ) 的一个等价模型，具体变换如下： 为了去除t o ，i = l ，竹，将蕾用一代替，其中置= 卫2 ，从而t = 1 变成了f l y l l 2 = 1 ， 其中洲表示欧氏模。 从而模型( 1 - 3 ) 变成如下的球约束二次规划问题( b a l l c o n s t r a i n t sq u a d r a t i c o p t i m i z a t i o np r o b l e m ，b q p ) ： m a xf x ) = 圭y 7 x a x y s 1 陟旷= 1 ( 1 4 ) 其中z ：f 0 。 1 00 基于上述四个模型，人们对最大团问题展开了大量的研究，也取得了一系列的研究 成果。关于最大团问题的有关研究，我们在1 4 中进行详细的论述。 最大团问题的熵正则化方法研究 1 3 最大团问题的实际应用和理论意义 在实际应用中，很多问题可以写成一个最大团问题或者在问题的求解过程中包含一 个最大团问题作为子闯题。作为一个比较经典的组合优化问题，最大团问题在诸如市场 分析、方案选择、电路板设计、信息检索、信息恢复、容错、实验设计、模式识别、机 器人、密码理论、信号处理与计算机视觉等方面有着广泛的应用e l l ，并且因为最大团问 题在计算上和最大独立集问题和最小结点覆盖等诸多n p h a r d 问题等价，并且在多项式 时间内可以转化成h a m i l t o n 圈问题、h a m i l f i o n 轨问题、货郎担问题等【6 i ，所以在理论 上也具有很大的借鉴意义。 1 4 最大团问题的相关研究 上面介绍的关于最大团问题的四个数学描述，因为模型0 4 ) 是最近才提出来个 比较具体的改进形式。据我们所知，研究结果也仅限于文献口l ，并且该文中研究的也是 一般的标准二次优化问题，所以这里就不再详细介绍，具体问题可以参看该文献。而模 型( 1 3 ) 和模型( 1 一1 ) 、( 1 1 ) 及( 1 2 ) 明显不同就是。模型( 1 3 ) 是一个连续化的模型， 所以运用这三个模型的研究方法上有着很大的区别，所以对于连续化模型的相关研究的 介绍，我们单独列出来，以区别于另外两个离散模型。而这两个离散模型，因为其间有 着密切的关系，相关的研究在很多情况下并没有很严格的界限，所以我们归为一类进行 介绍。 1 4 1 基于离散模型的相关研究 基于离散模型( 1 1 ) 、( 1 2 ) 的研究从可以分为确定性算法和启发式算法两大类，但 是需要说明的一点就是这些方法的分类并不是那么严格，往往在一篇论文中几种方法结 合起来使用。由于确定性算法本身的局限性，对于结点数目比较小，边密度比较低的图 而言，确定性算法还可以，但是随着研究的深入，确定性算法在解决结点增多和边密度 增大等复杂最大团问题中遇到的困难越来越大。正因为此，人们开始应用启发式算法来 研究最大团问题，它的优点体现在随着结点和边密度的增加，运算时间和确定性算法的 运算时间之比越来越小。现在广为应用的启发式算法主要有序列启发式算法、局部启发 式算法和包括遗传算法、神经网络、模拟退火及禁忌搜索等在内的高级启发式算法。但 是这些启发式算法不一定能找到最优解，有时只能得到近似最优解。有关确定性算法和 启发式算法在最大团问题中应用的研究成果十分丰硕。下面进行详细的介绍： 大连理工大学硕士学位论文 1 4 1 1 确定性算法 确定性算法包含枚举法和隐式枚举法两大类，其中后者是对前者的一种改进。 ( 1 ) 枚举法 所谓枚举法( e n u m e r a t i v ea l g o r i t h m s ) ，就是将一个图的团全部给出，然后寻求最大 团。 枚举法肇始于1 9 5 7 年h a r y 和r o s s 的论文f 7 l 。受矩阵模拟( m a t r i xm a n i p u l a t i o n ) 的启 发，在该文中，他们给出了一个诱导方法。该方法的思路就是首先确定个带有不超过 三个团的图的所有团，然后把更一般的图过渡到这样的图上来进行求解。 随后的研究有p a u l l 和u n g e r t ”，及m a r c u s i9 】提出的最小化一系列开关函数( s w i t c h f u n c t i o n ) 的流水盘( f l o wt a b l e ) 的行数的算法：b o n n c r ”1 论述了信息系统的聚点问题； b e d n a r e k 和t a u t b e e i ”1 提出的生成一个集合的所有极大链和定义其上的二元关系。尽管 这些问题来此不同的应用领域并且处理的问题也差别很大，但是它们可以用来枚举一个 图的所有团。只是跟于当时技术的局限性，早期的这些算法只适用于一些具有特殊结构 的图。 1 9 7 0 年a u g u s t o n 和m i n k e r t ”o 研究了在信息系统中应用的一些图的聚点技术，在 他们的工作中，他们比较了b i e r s t o n e 和b o r m e r 算法。在这两个算法中应用的方法称为 结点序列方法( v e r t e xs e q u e n c e m e t h o d ) 或者点移除方法( p o i n tr e m o v a l m e t h o d ) ，通过比较 发现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 1 2 1 之中。 1 9 7 3 年，a k k o y u n l u 1 3 1 及b o r n 和k e r b o s c h f 4 1 分别提出的两种算法中运用了后退方 法( b a c k t r a c k i n gm e t h o d ) 。这一方法具有两个优点：一是后退方法消除了在生成同样团的 过程中多余的元索：第二个，也是更重要的是仅仅要求多项式时间的存储，在他们的试 验中的一个非常有意思的现象就是c p u 时间和图的结点数之间的比率几乎不倚赖于图 的规模。他们发现他们的算法比b i e r s t o n e 的算法更为有效。 在七十年代，更多的枚举算法得以提出，o s t e e n 和t o u n 5 1 将点移除方法进行了改进。 m e e u s e n 和c u y v e r s “】的算法则是将图分解成满足图的子集链法n ( t h ec h a i no fs u b s e t s ) 的子集。这样的一个分解使得每一个团至少完全包含在一个子图里，基于这一点，他们 给出了一个算法来寻求一个图的所有的团。j o h o s t o n 的主要工作n 7 】则包含了一系列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 l d y a m a ”1 等人结合文献1 1 2 , 1 4 1 和a k k o y u n l ur ”1 方法给出 最大团问题的熵正则化方法研究 了一个更强的界限。g e r h a r d s 和l i n d e n b e r g 的论文【1 9 】给出的算法对于一般图而言并没有 很大的改进，但是对于稀疏图而言则要有效的多。 在8 0 年代，人们也给出了一些其他的算法l o u k a k i s 和t s o u r o s t 2 们给出了一个名为 深度优先枚举法( d e p t h - f i r s te n u m e r a t i v e ) 的算法，该算法能够按照字典顺序生成全部 极大团并且试验表明他的算法对于多达2 2 0 个结点的图比1 1 4 1 中的算法要快2 到1 5 倍。 1 9 8 8 年，j o h n s o n 等在 2 1 1 中提出了个算法可以将图的极大独立集按照字典顺序全部给 出，并且这个结果在计算复杂度上比1 2 0 1 有了改进。t o m i t a 等在1 中给出了b o r n 和 k e r b o s c h i “l 中算法的改进，它的计算复杂度为0 ( 3 3 ) ，并且这个结果是具有3 州3 个极大 团的m o o n m o s e r 图的最好的结果。 ( 2 ) 隐式枚举法 如果仅仅寻求图的一个最大团或者最大团的规模，那么对于上面的枚举法而苦可以 节省很多的工作。因为一旦找到一个团，我们只需找到所有其他的比当前晟大团大的团 即可。基于这思想，修正枚举法就得到隐式枚举法( i m p l i c i te n u m e r a t i v ea l g o r i t h m s ) 。 在最大团问题的研究中运用最为广泛的隐式枚举法就是分支定界法( b r a n c ha n d b o u n dm e t h o d ) 。关于分支定界法的背景知识可以参看文献怛3 11 2 “。最大团问题的分支定 界法的关键就是：如何找到一个好的下界，即一个大的团数：如何找到最大团规模的一 个好的上界；如何分支，亦即如何将问题分解成若干子问题。 上世纪7 0 年代d e s l e r 和h a k i m i t ”1 和h o u c k l 2 6 】的工作给出了最大团问题的隐式枚 举法的最早研究。随后的十多年，人们将这一方法迅速的应用到了其它和最大团问题相 关的问题之中，取得了很多成果，反过来这些成果又推动着最大团问题的研究。 关于隐式枚举法在最大团问题应用的研究中，8 0 年代最重要的成果之一就是b a l a s 和y u 在文【2 7 1 中给出的。他们的算法中将隐式枚举法以一种新的方式加以应用。其主要 思想就是：首先找到图g 的一个极大诱导三角剖分子图( m a x i m a li n d u c e dt r i a n g u l a t e d s u b g r a p h ) d ，然后找出d 的一个最大团，这个团给出了原最大团问题的一个下界和一个 可行解，再运用启发式染色过程( h e u r i s t i cc o l o r i n gp r o c e d u r e ) 将d 扩展到更大的( 极大) 子 图，使得没有比当前最大团更大的团，这一步的重要性体现在它减少了由搜索树的每一 个结点生成的子问题的数目，从而减少了整个搜索树的规模。他们在多达4 0 0 个结点 3 0 0 0 0 条边的图上进行数值试验并和其他方法进行了比较，结果表明他们的算法不仅只 产生了较小的搜索树，而且需要的c p u 时间也短。 在8 0 年代后期，也有新的算法提出。t o m i t a 等在1 2 引中运用贪婪着色算法( g r e e d y c o l o r i n ga l g o r i t h m ) 得到最大团数的一个上界。p a r d a l o s 和r o d g e r s 在文 2 9 1 中基于最大团 大连理工大学硕士学位论文 问题的一个无约束二次o 一1 规划模型公式，并且运用了贪婪和非贪婪两种不同的分支 准则进行了试验。 进入9 0 年代以后，关于这一类的研究仍在发展，也出现了相当多的成果。b a b e l 和t i n h o f e r 在文中给出了最大团问题的一个分支定界方法，该方法的主要构成部分 是利用快速的并且可以相对较好的解决最小着色数问题的启发式算法。在 3 h 中， b o u r o l l y 等提出了一个嵌入在分支定界方法中的列生成方法( c o l u m n g e n e r a t i o n m e t h o d ) ，从而得到最大团问题的一个较好的下界和最小结点覆盖问题的线性松弛的一 个有效割。 运用分支定界方法研究最大团问题的最新成果还有m j ，在该文中，t o r s l e n f a l b e 结 合运筹学和约束优化，运用域过滤( d o m a i nf i l t e r i n g ) 方法和上下界技术来改进分支定界方 法得到了最大团问题的一系列新结果，并且结果显示该方法得到的结果优越于先前单一 应用有关技术的结果。 1 4 1 2 启发式算法 因为最大团问题的计算复杂性，事实上即便近似求解也非常困难，所以近来更多的 研究则侧重于设计有效的近似算法。尽管这些研究不能保证解的质量，但是具有着很大 的实用价值，因此应用近似算法来研究最大团问题也成为一个热点。 1 4 1 2 1 序列贪婪启发式算法 序列贪婪启发式算法( s e q u e n t i a lg r e e d y h e u r i s t i c s ) 就是反复向一个团中添加结点，或 者从一个不是团的子图中反复去除结点直至得到一个团。k o p f 和r t t h e 在( 3 3 1 中将其分别 定义为最优进( b e s ti n ) 和最差( w o r s to u t ) 启发式算法。至于如何决定下个结点谁进谁 出，则依照候选点的一定指标参数。例如，在构造个极大团的最优进启发式算法中， 反复加入结点使得在所有候选结点中具有最大度( d e g r e e ) 的即可，在这种情况下，指标 就是结点的度数。相反的，在最差出启发式算法中。对于所有的结点集合反复移除结点 直至成为一个团。 在口3 1 中。k o p f 和r u h e 进一步将上面的最优进和晟差出启发式算法分成新和旧两种 启发式算法。即，如果在一个结点加入或者移除的时候指标得到改善，则成该启发式算 法为一个新的启发式算法，否则就称为旧的启发式算法。我们可以看到最大团问题的很 多启发式算法都可以归为其中的一个，如j o h n s o n 圳和t o m i t a t ”1 等人的启发式算法。这 些启发式算法的差别就是指标集的选取以及指标如何得到改善。总体而言，这一类启发 式算法的计算还是比较快的。 最大团问题的熵正则化方法研究 1 4 1 2 2 局部搜索启发式算法 上面介绍的序列启发式算法的一个缺点就是都只能找到一个极大团，并且一旦找到 一个极大团，搜索就停止。我们可以从另一个不同的角度看待这类启发式算法：设& 为 图g 的所有极大团的集合，序列启发式算法就是寻求其中的一个元素，并且希望它就是 至少接近最大团。这就提示我们，如果扩大搜索范围就可以改善搜索结果，从而得到了 局部搜索启发式算法( 1 0 c a ls e a r c hh e u r i s t i c ) ，详尽论述可以参看文献口“。 在局部搜索启发式算法中，如果我们搜索s 最更多的相邻元素，那么得到一个更 好解的可能性就增加了。根据邻域的定义和搜索方式不同，应用不同的局部搜索启发式 算法，我们可以得到不同的结果。1 0 一交换启发式算法( k i n t e r c h a n g eh e u r i s t i c ) 就是一个 比较典型的局部搜索启发式算法。这一方法就是基于一个可行解的1 0 一邻域实现的，因 此影响此方法复杂性的主要因素就是邻域的大小和搜索方式，并且这一方法随着邻域规 模的增大，搜索代价之高逐渐超出承受能力。而对于不同的，设计的一类启发式算 法称为随机启发式算法( r a n d o m i z e d h e u r i s t i c ) 。在实际应用中，往往把随即启发式算法和 局部搜索结合起来，如文 3 7 1 ，在该文中，二者结合以后的算法在解决大规模的随机生 成图的最大独立集问题相当有效。 局部搜索启发式算法的一个缺点就是只能找到一个局部最优解，这就在一定程度上 限制了算法的作用。 1 4 1 2 3 高级启发式算法 随着现代优化算法的发展，针对局部搜索启发式算法的缺点，人们基于局部搜索启 发式算法，提出了很多有效的算法。主要包括模拟退火、神经网络、遗传算法、禁忌搜 索和其他启发式算法。 ( 一) 模拟退火启发式算法 模拟退火( s i m u l a t e da n n e a l i n g ) 惮l ，是一种随机算法，多用于复杂的组合优化问题 及n p 问题m 1 。它是一种解决组合优化问题的通用算法，并且只要优化问题能提供一个 对候选方案的适应性函数或费用函数，即可使用模拟退火算法对它求解。有关模拟退火 启发式算法的理论和应用的论述可以参看h o j 【4 ” a a r t s 和k o r s t 在文1 中建议结合罚函数方法使用模拟退火算法来解决独立集问题， 但是没有给出具体的数值试验。j e r r u m 等人1 4 2 1 则在随机图上，对模拟退火在m e t r o p o l i s 过程( 模拟退火过程在固定温度时) 能找到的解的效果进行了理论分析，但是在期望的 时间内模拟退火方法所需要的时间比简单的贪婪启发式算法要多。而且随着结点个数的 大连理工大学硕士学位论文 增加，所需要的时间增长速度要比任何多项式还大，因此他认为模拟退火方法不适合解 决最大团问题。 然而，实际数值试验得到的结论和j e r r u m 的结果相矛盾。在h 卸中，h o m e r 和p e i n a d o 比较了模拟退火启发式算法和j o h n s o n 的贪婪启发式算法 3 4 1 、b o p p a n a 和h a l l d o r s s o n 的子图排除算法( s u b g r a p he x c l u s i o n ) 1 4 4 1 的随机形式，结果显示模拟退火启发式算法比其 他的算法要好，并且成为解决1 9 9 3 年d l m a c s 中最大团问题的最好的启发式算法之一。 尽管如此，模拟退火算法存在的主要问题是运行时间太长，其性能有时甚至还不如 简单的枚举算法。模拟退火算法本身具有内在的串行化要求( 下一点的选取直接依赖于 上一点) ，不易实现高效的大规模并行化处理；其次，模拟退火算法的性能对参数及初 始值的选取十分敏感，不同的参数可能导致算法性能的巨大差异。而优化参数设置和具 体的问题是密切相关的，这些方面都限制了模拟退火算法的应用效果。 ( 二) 神经网络启发式算法 神经网络算法( n e u r a ln e t w o r k s ) ，又称人工神经网络算法( a r t i f i c i a ln e u r a ln e t w o r k s ) ， 是在人类对其大脑神经网络认识理解的基础上人工构造的能够实现某种功能的神经网 络，它是理论化的人脑神经网络的数学模型，是基于模仿大脑神经网络结构和功能而建 立的一种非算法的信息处理系统。它具有高度并行性、高度非线性全局作用、良好的容 错性与联想记忆功能和十分强的自适应、自学习功能。人工神经网络在自动控制、系统 辨识、模式识别、机器人等多个领域得到了广泛的应用，详细讲解可以参看l 。 上世纪八十年代，h o p f i e l d 和t a n k m l 首先将神经网络算法应用到旅行商问题，从 而开创了神经网络在组合优化中应用的先河，并且为用神经网络来求解其他组合优化问 题提供了一个总体思路。此后人们开始应用神经网络来求解最大团问题及其相关问题， 这些早期的结果可以参看f 4 l 】| 4 ”，只是这些早期的研究成果没有或者很少有数值试验， 所以很难评断算法的优劣。l i n 和l e e 在中利用二次o 1 模型作为神经网络启发式算 法的基础，试验结果表明本方法对于多达3 0 0 个结点的随机图丽言优于隐式枚举法。 g r o s s m a n 【4 ”给出了一种离散的确定性的h o p f i e l d 模型来求解最大团问题，这个模型使 用了一个用来决定网络是否处于稳定态的临界参数。 j a g o t a ”1 给出了h o p f i e l d 模型的几个变形来逼近最大团问题，有离散的，也有连续 的。后来，他又在泓j 中进行了改进。与其他简单启发式算法相比，这些结果可以得到更 大的团，但是时间上稍微长些；而与其他复杂的启发式算法相比，虽然找到的最大团较 小，但是速度较快。 最大团问题的熵正m 化方法研究 最近，a b e s o m 等人在文m 1 中给出了基于一系列离散时间的h o p f i e l d 模型的神经 网络算法一迭代h o p 矗e l d 网算法。数值试验表明，该算法的计算稳定性，并且该算法对 于d i m a c s 考题而言，可以和任何己知的启发式算法相媲美；对于随机图而言，可以 和一些基于h o p f i e l d 团网络的算法相媲美。此外，该算法因为不涉及到参数更改，并且 算法简单，易于程序实现。 ( 三) 遗传启发式算法 遗传算法( g e n e t i ca l g o r i t h m ) ，是一种基于自然选择和群体遗传激励的平行搜索算法， 它模拟自然选择和自然遗传过程中发生的复制、交叉和变异现象。关于遗传算法的相关 论述可以参看 5 3 1 。 1 9 9 3 年，c a r t e r 和p a r k e r 在文口4 】进行了应用遗传算法来求解最大团问题的最早尝 试之一。在发现遗传算法解决大规模图、甚至是小规模的随机图的的最大团中的缺点后， 他们进行了一系列的修改，但是并没有取得令人满意的结果。因此，他们认为如果要想 得到和传统方法类似的结果，需要做很大的调整，并且计算量太大。后来在文1 5 5 他们证 明了遗传算法不如模拟退火算法有效。但是几乎与此同时，b a c k 和k h u r i p 6 1 在研究最大 独立集问题的时候得到了相反的结论。这就说明，应用遗传算法解决最大团问题的时， 适应函数( f i t n e s sf u n c t i o n ) 的选择对于得到好的结果具有非常关键的作用。 1 9 9 5 年，b u i 和e p p l e y m 】应用了一个杂交策略( h y b r i ds t r a t e g y ) ，并得到不错的结果。 这一策略就是在遗传算法中的每一代都结合了局部优化算法和结点排序预处理过程 ( v e r t e x - o r d e r i n gp r e p r o c e s s i n gp h a s e ) 。而f t e u r e n t 和f e r l a n d 巧目则使用了杂交遗传框架 ( h y b r i dg e n e t i cs c h e m e ) ，这一框架是把禁忌搜索( t a b us e a r c h ) $ 口其他的局部搜索技术结合 起来作为交叉变异算子进行的。虽然计算结果质量不错，但是计算时间太长。 m a r c h i o r i ”1 研发了一个简单的基于启发式算法的遗传算法，在该算法中作者结合 了简单遗传算法和简单贪婪启发式算法过程( n a i v eg r e e d yh e u r i s t i cp r o c e d u r e ) 。对 d i m a c s 标准考题的数值试验表明，这一算法无论在得到的解的质量上，还是计算时间 上，比以前的遗传算法都要好。