（应用数学专业论文）最大独立集问题及其成长算法的研究.pdf

￥。6 2 0 3 4 9 最大独立集问题及其成长算法的研究 摘要 最大独立集问题( 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 ) 是图沦中经典的组合优化问题。本文综述了国内外学者对此问 题的研究成果，包括该问题的应用背景，界的估计，求解的难 点及现代优化算法的设计。 通过对遗传算法的研究，并模拟了生物个体的成长机制， 本文提出了一种新的启发式算法一成长算法( g r o w n u p a l g o r i t h m ，简称g u a ) 。该算法将组合最优化问题解的演进分为 诞生和成长两个阶段，诞生阶段产生一个近似解，成长阶段让 这个近似解象生物个体一样成长为一个满意解，并且诞生和成 长均在确定性和随机性的双机制作用下演进变化。与遗传算法 相比，其主要特点是利用诞生算子强化了遗传算法的初始化过 程，利用成长算子使解的进化有了定向的机制。 本文主要研究了g u a 在m i s 问题中的应用，详细探讨了诞 生算子和成长算子的构造，算法的效能分析等，并在d i m a c s 图 上进行了测试，取得了良好的效果，表明了g u a 有效的运行机 制，值得进一步研究。 关键词：最大独立集，成长算法，启发式算法，诞生算子，成长算 子 s t u d yo nm a x i m u mi n d e p e n d e n ts e t p r o b l e ma n di t sg r o w n u p a l g o r i t h m a b s t r a c t t h em a x i m u mi n d e p e n d e n ts e tp r o b l e mi sac l a s s i c a lp r o b l e m i nc o m b i n a t o r i a lo p t i m i z a t i o n i nt h i sp a p e rw eg i v eas u r v e yo f r e s u l t sc o n c e r n i n ga p p l i c a t i o n ，b o u n d s ，a l g o r i t h m s ，a n dh e u r i s t i c s b a s e do n s t u d y i n g o f g e n e t i c a l g o r i t h m sa n do r g a n i s m 、 g r o w n - u p ，t h i sp a p e rg i v e an e wh e u r i s t i c s ，c a l l e dg r o w n u p a l g o r i t h m ( g u a ) i td i v i d e se v o l u t i o n a r y o fs o l u t i o n o f c o m b i n a t o r i a lo p t i m i z a t i o ni n t ot w os t e p s ：b i r t ha n dg r o w n u p b i r d lp r o d u c eaa p p r o x i m a t i o ns o l u t i o n g r o w n - u pc u l t i v a t et h e s o l u t i o nt oaa c c e p t i v es o l u t i o n i t sc o r ei sb o ma n dg r o w n u p t h i sp a p e rs t u d ya p p l i c a t i o no f g u ai nm i s t h ec o n s t r u c t i o n o fb o r no p e r a t o r ( i b ) ，g r o w n u po p e r a t o r ( i g ) a n dt h ee f f i c i e n c y a n a l y s i so ft h eh e u r i s t i c sa r ea c c o m p l i s h e df o rs o l v i n gm i s t h e i l i h e u r i s t i c si st e s t e do nb e n c h m a r kg r a p h sp r o v i d e db yd i m a c s e x p e r i m e n t s h o w st h a tt h e p e r f o r m a n c e o ft h eh e u r i s t i c s o u t p e r f o r m st h a to fh g ap r o v i d e db y 5 2 】 k e yw o r d s ：m a x i m u mi n d e p e n d e n ts e t ；g r o w n u pa l g o r i t h m ； h e u r i s t i c s ；m a x i m u mc l i q u e 太原理人学顾f ? 研究生学伉论文 一绪论 1 最大独立集问题及其实际意义 给定一个无向图g = ( v ，e ) ，其中v = 1 , 2 。，月) 是图g 的顶点集， s v x y 是图g 的边集。图g = ( v ，d 的补图是指g = ( 矿，动，这罩 e = ( i ，) 1 f ，i ，矿，i ，月，( f ，_ ，) e e ) 。 称矿的一个子集s v 为独立集，如果它的顶点两两互不相邻。如 粜一个独立集刁i 是其它任何一个独立集的真子集，则称浚独立集为图g 的极大独立集。最大独立集问题( t h em 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 ) 就是寻求一个基数最大的独立集，最大独立集的基数一般称之为图 g 的独立数，记为a ( g ) 。如果给图的每个顶点i 矿赋予一个正实数w ， 、 称之为权。图的一个顶点集矿矿的权w ( v ) 就是指矿中所有顶点的权 之和。所谓最大加权独立集问题( t h em a x i m u mw e i g h ti n d e p e n d e n ts e t p r o b l e m ，m w i s ) 就是在图g 中寻求一个权和最大的独立集。显然，最大 独立集问题可以看作最大加权独立集问题的特例。本文主要讨论最大独 立集问题。 图的一个翻c 是指顶点集矿的一个子集，其项点在图g 中两两相互 邻接。如果一个团不是其它任何一个团的真子集，则称垓团为图g 的极 大团。基数最大的极大团称为浚图的最大团。这个基数称为该图的团数， 电为( g ) 。最大团问题( t h em a x i m u mc i j q u ep r o b l e m ，m c ) 就是在给 太原理i 人学硕f ：研究生学仿论文 定的图g 巾寻找陔图的摄大团。所谓最大加权团问题( t h em a x i m u m w e i g h t e dc 1 i q u ep r o b l e m ，m w c ) ，就足寻找一个权和最大的团。 称图g 的一个顶点覆盖为顶点集矿的一个子集，如果图g 的每条边 ( f ，j ) e 都至少有一个端点在这个子集中。包含顶点数最少的顶点覆盖称 为图g 的一个最小顶点覆盏，最小顶点覆盖的顶点数称为图g 的覆盖数， 记为f l ( g ) 。最小顶点覆蔬问题( t h em i n i m u mv e r t e xc o v e rp r o b l e m ，m v c ) 就是要在给定图g 中寻找一个最小顶点覆盖。同理，最f l , ) j h 权顶点覆盖 问题( t h em i n i m u mw e i g h t e dv e r t e xc o v e rp r o b l e m ，m w v c ) 就是在图g 中刁找权和最小的顶点覆盖。 显然，s 是图g 的一个团当且仅当s 是其补图石的独立集，或者叭s 是其补图弓的一个顶点覆盖。这三个问题中任一个获得的结果都可以立 即转化为其它两个问题的等价形式，即，口( g ) = 甜( 万) ， a ( g ) + f l ( g ) = 。 这三个问题都是盈合优化领域著名的n p 一完全问题m ，可在多项式时 削内归约为询：多知名的雉题，如三元精确覆盖问题( x 3 c ) ，h a m i l t o n 回 路问题，旅行商问题( t s p ) 等，所以从理论上来讲，对最大独立集问题 的研究可以获得关于n p 一完全理论问题的结果，起到窥一斑而见全豹的作 用。 另外，独立数a ( g ) ，团数珊( g ) 和覆盖数f l ( g ) 是一个图的重要参数， 对j ：刻划图的特征有着极为重要的意义，与其它一些重要参数，例如色 数z ( g ) 也有着密切关系。著名的三明治定理( t h es a n d w ic ht h e r o e m ) 。“ 就指出，图g 的补图石的l o v a s z 数0 4 介丁二团数c o ( g ) 和色数z ( g ) 之 2 太原理人学硕十研究生学位论文 这个定理订意思的是，l o v a s z 数目在多项式时问内是可求的，而求一个 图的团数甜和色数z 却是n 。完全问题。同时，这个定理也说明了完美图 ( 有性质国= z ) 的个特征：能在多项式时问内求出它的最大团或最大 独立集。 存实践中，这三个问题也具有相当，“泛的应用背景，许多问题都能 转变为有关它们的数学模型。例如，一个印刷电路板的检测器需要把一 个探头放到电路板l ，这个探头能确定这块电路板的一部分是否正常工 作。由于探头有固定的数目，在一个周期内不是每一个元件都能被检测 到。那么，在一个周期内如何使能被检测到的元件数最大的问题可描述 成一个最大团问题：其中每个顶点代表一个元件，当两个元件离得的很 近，能被探头同时检测剑时，则相应的顶点连一条边。这个图的团就是 在一个周期能被检测到的元件集合。对这一问题的研究可参见文献 5 ， 6 。 另外，最大独立集问题或最大团问题在编码理沧“、故障诊断。1 、几 何学。“、经济学”“、计算机视觉“、电台信息传送“。3 、生物学1 、聚类 分析、信息检索、移动通信、图象显示、模式识别、和v l s i 电路设计等 领域都有重要的应用，洋细的讨论可参见文献 1 5 2 4 。 2 国内外研究现状 1 9 7 9 年，m i c h a dr g a r e y 和d a v i ds j o h n s o n 证明了在一般 图上求解最人独立集问题足n p h a r d 问题“1 ，即不可能存在一个多项式 3 z 0 就选择v 加入当前的独立集， 否则就另选一点。 、 局部搜索局部搜索也足一种很常用的搜索技术，绝大多数启发式 算法都融入了局部搜索技术，比如模拟遐火算法、禁忌搜索技术等”1 。 局部搜索算法的框架见表卜1 。 局部搜索算法解的效果直接依赖于初始可行解x 。的选取和邻域 n ( x “) 定义。为改善解的质量，当然应该扩大搜索的邻域以包含更好的 解，侗这是以增加搜索时间为代价的。对最火独立集这样的一完全问题 来说，扩大到一定地步就变得不可行了。因此一个变通的方法就是引入 随机的因素， 。个较为精细的算法可见文献 6 3 。另外，文献 g 4 也提 出了个随机的局部搜索算法。 8 太原理i ：人学硕十研究生学位论文 表卜1 局部搜索算法的框架 模拟退火模拟退火本质上足一种蒙特卡洛( m o n t ec a r l o ) 方法 蒙特卡洛方法与局部搜索算法的主要区别在s t e p 3 ： 表卜2蒙特卡洛方法的s t e p 3 模拟退火以均匀的概率 从中选取一点，以概率 1 p2 丽 一洒卜p 一铆 接受一个较坏的解，以跳出局部极小的陷阱“。最早将模拟退火算法用 9 太原理i ：人学硕十研究生学佛论文 来求解最大独立集问题的是1 e r r u m 6 5 ，他在理论上证明了用固定温度 的模拟退火算法来对付最大独立集问题并不是很有效。然丽，实验的结 果却恰恰相反。文献 6 6 报告了模拟退火算法在随机图和d m a c s 基准图 上执行的结果，证明了其良好的效果。 人工神经网络 i j 上个世纪八十年代中期l t o p f i e l d 和t a n k 6 7 将 人工神经网络改造并应用于求解组合优化问题以来，就有大批学者将其 应用于最大独立集问题。但山于其优点难于执行，所以少有实验结果报 告。直到1 9 9 2 年，l in 和l e e 6 8 将他们的算法应用于3 0 0 个顶点的随 机圈上，结果虽然略差于 6 9 中的精确算法的结果，但速度却快了很多。 g r o s s m a n 7 0 提出了离散的| l o p f i e l d 模型求解最大独立集问题，在 d i m a c s 图上执行的结果虽然满意，但不敌模拟退火算法。j a g o t a 7 1 7 2 对此作了大量工作，其结果是基于人工神经网络的算法优于一些简单的 启发式算法。与更精细的启发式算法( 比如模拟退火算法) 相比，解的质 量要差，但运行r f t f j 却大为节省。利用人工神经网络求解最大独立集或 最大团的一些其它尝试可见文献 7 3 7 4 。 、 产生这种现象的原因我认为是由于人工神经网络的模型本质上要求 发展神经网络计算系统来替代当前的计算机，对输入进行并行处理，通 过神经兀的内部相连关系达到信息存铭的目的。只有当人工神经网络硬 件系统得到发展，才能使现有的人工神经网络模型产生更好的效果。 遗传算法 遗传算法是来自自然界系统演化机制的并行搜索算法， 与传统的优化算法相比，遗传算法是作用于一个群体，而不是单个点。 简唯遗传算法的总体框架见表3 2 。 较早将遗传算法应用二最大独立集问题的是c a r t e r 和p a r k 7 5 ，在 发现简单的遗传算法甚至在规模 醴小的随机图上都表现不佳后，他们作 了改进的尝试，但没有达到满意的效= ；! 。他们的结论是，遗传算法要想 1 0 太原理1 人学硕十研究生学位论文 与其它算法相匹敌，更需要针刈具体图度身定制。后来的一些尝试 7 6 7 8 似乎也是在为这一结论作注脚。 但遗传算法的简单易行性，且对群体进化的优点深深地吸引着研究 者的日光，多年来不断有改进的算法出现，近来的一些改进及实验 7 9 8 0 还是令人鼓舞的，而且遗传算法也很容易与其它技术融合，一 些混合算法 5 5 也产生了良好的效果。本文提出的成长算法秉承遗传算 法的进化思想，不仅注意到了生物学对人类进化的改造，更看到了社会 学对人类进化的改造，模拟人在社会中的成长过程而提出的。实验的结 果表明成长算法具有优于简单遗传算法的进化机制，同时也说明遗传算 法在求解组合优化问题上的潜力仍有待丌发。 禁忌搜索禁忌搜索是一种人工智能算法，是局部搜索算法的扩 展，它的主要思想是利用禁忌表存贮已得到的局部最优解，并在进一步 的迭代中避7 1 ：这些局部最优解。禁忌搜索算法的框架见表卜3 。 表1 - 3 禁忌搜索算法的框架 可以看到，豢患搜索算法与局部搜索的区别主要是如何选墩当前最 1 1 太原理i 人学硕十研究生学位论文 优解。 1 9 8 9 年，f r i d e ne t a 1 8 1 提出了基于禁忌搜索技术的启发式算 法用于求解m i s 问题。而文献 8 2 8 3 中提出了三种求解最大纠问题的 禁忌搜索算法，在d i m a c s 基准图上执行的效果相当不错 8 4 。日前公认 最好的禁忌搜索算法是文献 8 5 中提出的，其算法的复杂性是 o ( m a x n ，州) ，这里| l 和珊分别是图的项点数和边数。实际上很多算法也 采用了相似的一些手段来避免重复搜索已搜索过的区域，比如文献 8 6 f _ j _ t 的于臣绝域。 4 本文所用到的概念和记号 本文只考虑有限无向简单图g = ( v ，e ) ，设v = 1 , 2 ，订 为其顶点 集，e = 豫，e ：，e 。) ，显然iv | - n ，le 卢m 。图g 的邻接矩阵为 a “= ( d “) 。，其中当( j ) e 时，a u = 1 ；当( f ) 仨e 时，“口= 0 。对每个 顶点i v ，( f ) = 0 v l ( f ) e ) 表示顶点i 在g 中的邻集，记 r ( f ) = ( f ) u 日。d i 为顶点f 在圈g 中的度，“，正i 和j 分别表示图g 的 最大度，最小度和平均度。n ，= 2 m n 2 为图g 的边密度( 图的边密度也 可这样定义：n ，= 2 m c 2 = 2 m n ( n - 1 ) ，在本质上没有区别) 。 如果联) v ( g ) ，则称图为g 的予图，、己为h c g 。当h g ， 但h g 时，记为hcg ，并称为g 的真子图。如果日g ，且 v ( h ) = v ( g ) ，则称h 为g 的_ i 成予图。 设矿7 是y 的非空子集，以矿7 为顶点集，两端点均在v 中的边的全 12 太原理i 人学硕十研究生学位论文 体为边集所形成的子图，称为g 的山矿导山的子图，融为g v 】。g e v v 记为g v ，它足从g 删除v 的顶点以及与这些顶点相关联的边所得到 的予图。同理，设f 是e 的非空子集，以f 为边集，以f 中边的两端点 全体为顶点集所形成的子图，称为g 的山f 导出的子图，记为6 e7 。 g 【e e 简记为g e ，它是从g 删除f 的边所得到的子图。 其它这里未提到的记号和术语，或者下文中有解释，或者与文献 3 5 中的相同。 1 3 太原理l ：人学硕十研究生学位论文 二界和估计 对独立数( 或团数) 界的估计是最大独立集( 或最大团) 理论研究中 的重要方面，其一，对刻划图的特征有重要意义，它可以告诉我们图上 的哪些变量( 如顶点数，边数，最大度或是其它) 与独立数或团数有更 为密切的关系，从而可以表征出独立数不超过k 的图的特征。其二，山 于n p - 难问题的最大障碍在于巨大的搜索空间，且搜索空间随问题规模 的增长而呈指数性增长。所以独立数的界的估计对算法的直接作用就是 减少搜索空划。本文主要对这一问题进行了较为系统的讨论。我们仅讨 沦在任意图上独立数的上下界，并且我们只关注那些形式较为简单直观 的界。虽然这样的界较为粗糙，但计算量却很小，那些设计精巧的界往 往是以牺牲计算量为代价的，用来对付n p - 完全问题常常是顾此失彼。 、 1 下界 很容易看到，任何一个寻找独立集的算法都可以给出一个具体图独 立数的下界，且这个下界常常比任何精确的界来的更强。遗憾的是，由 算法得到的界常常与所处理图的特征相联系，并不能推广到一般图上去。 一个简单的结果是 邢) 南( 2 - 1 ) 这是蒋名的t u r a n 定理。”的结果，1 9 7 0 年e r d 6 s 给出这个定理的一个精致 证明m 3 。 1 4 太原理1 ：人学硕十彬f 究生学位论文 通过对一种贪婪算法的研究，本文提出下面的f 界： 口( g ) 2 昙( 打丽一d ) ( 2 2 ) ( 2 - 2 ) 式的证明见第四章的定理5 。 而w i l f 8 8 和b u d i n i c h 8 9 贝l j , i j 用m o t z k i n s t r a u s 定理加强了 ( 2 - 1 ) ，因不是本文讨论的重点，不再详述。c a r o 9 0 和w e ic 9 1 独立的将 公式( 2 - 1 ) 加强为如下离散形式： 叫g ) 善志 心门) 文献 9 2 有上式的一个概率证明。文献 9 3 9 4 得到一个更为精细的结 果：v v v ( g ) ，汜k 。为g ( f ) 】的最大度，t ( g ) = m a x k ，) ，则 口( g ) 恐兀+ ，( d ) ( 2 - 4 ) 这。 ! f ( o ) = 1 且当工 0 ， = f 糟 5 ) 同公式( 2 - 3 ) 列公式( 2 1 ) 的改进一样， 9 5 将公式( 9 ) 改进为： 口( g ) - e 五+ ，( d 。) ( 2 6 ) 文献 9 3 9 4 和 9 5 给出了函数( 2 - 5 ) 的一些性质，其中下文我们要使用 的一个性质是： 定理1 啉“”函数( 2 - 5 ) 分别对k 和x 单调下降，且它是正值函数，满 足微分方程 x ( x j i ) 月( x ) + ( x + 1 ) 五( x ) = 1 2 上界 太原理i ：人学硕+ 研究生学位论文 我们先证明网个简单的上界。 定理2 若图g 没有孤立点，则 口( g ) s 罢 ( 2 7 ) 证明：设是图g 的最大独立集，对v v i ，令 e ，= 瓴e ie ，是与顶点v 关联的边 则对v ，v ，有& n e = 矿。因此 a ( g ) x 6 d 。= f e ，i 小 舢f l j a ( g ) 罢。 0 定理3 若口( g ) 昙，则 邢m 一罢( 2 - 8 ) 证明：t h i n = 三z , t 。，则 室“o 要= 上2 a 以! = 旦22 鲁鲁 所以当口( g ) 兰时，有口( g ) + 罢n ，命题得证。 另外一个只涉及顶点数和边数的界是由 9 6 得到的： 口( g ) 3 + 、 9 + 4 n ( n - 1 ) - 8 ( n + m ) ，。 ( 2 9 ) 其它一些更精确的上界需要用到图的邻接矩阵及其特征值，特征向 量等概念，详细的讨论町见文献 8 9 ，9 7 9 8 。 最近的一个结果是m b u d i n i c h 8 9 得到的： 1 6 太原理l ：人学硕十研究生学位论文 口( g ) 船 这啦r a n k a 是图g 的邻接矩阵a 的秩。 ( 2 一l o ) 3 在简单例图上的实验结果 本节我们通过几个简单的例图给出上面这些界的数值实验结果，所 选用的例图选自文献 9 9 。如图2 - 1 所示，图中黑色顶点所组成的集合 即是相应图的最大独立集。 鳓 例图1例图2 豢，一 例图3 图2 - 1 数值实验所用的四个例图”7 f i g 2 lf o u rg r a p h su s e di nn u m e r i c a lt e s t 例图4 表2 - 1 是实验的结果。其中胛，m 分别表示相应图的顶点数和边数，a 1 7 太砸理i ：人学硕卜研究生学位论文 表示棚应图的独立数，最厉两列分别是用本文所提到的几个公式对棚应 图估计出的下界和上界。其中公式( 2 8 ) 成立是有条件的，我们将其结 果列出，仅供比较。从表中可以看出，我们提 f 的下界( 2 - 2 ) 及上界( 2 - 7 ) 、 ( 2 - 8 ) 是有竞争力的。 表2 - 1在四个例图上的实验结果 下界 上界 例图 订，竹 口 2 12 22 32 42 72 82 - 92 一l o l 71 2 31 5 81 8 9 1 6 0 7 444 4 3 5 2 1 1 2 841 8 12 0 81 9 31 1 777 57 3 56 5 31 61 595 5 76 9 35 2 56 q 51 51 4 9 31 0 44 6 6 91 91 1 51 3 9 3ii 51 4 92 32 34 4 4 22 3 太原理i ：人学硕+ 研究生学位论文 三成长算法 本章我们提出一种新的启发式算法，即所谓成长算法。首先我们介 绍其基本思想，并与经典的遗传算法相比较。下一章我们将应用成长算 法求解最大独立集问题。 1 成长算法的基本思想及总体框架 基于对生物群体自然进化机制的思考，h o l l a n d 提出了他著名的遗 传算法。遗传算法着眼于群体和进化，但是它并没有关注一个生物群体 之内个体的成长机制对接个群体进化的影响。我们先看一下生物界内 个好的个体是如何成长起来的? 我们知道生物体的外在特征和适应性是由染色体的编码结构( 基因) 所规定的。因此一个好的个体的形成酋先要有“好”的染色体的编码( 基 因) ，而这种染色体的编码来自于父代染色体的变异和重组过程，发生在 两性交合的一瞬问。能够产生一个怎样的编码既是确定的，又是随机的。 其确定性表现在生物个体的基因遗传了父代的编码，从而也遗传了父代 的适应性。其随机性表现在新基因诞生时的变异机制，这种变异是非定 向的，从而既可能强化也可能弱化父代的适应性。不论是哪个方面成为 基因诞生的主要矛盾，总之，如果在生物体或基因诞生之时具有适应性 相对较好的编码，那么它就更有可能成为一个“好”的个体。 生物学家现在还不完全清楚染色体编码和译码过程的细节，然而可 以肯定基因决定性状不足线性的。这就为生物体在诞生之后向“好”的 1 9 太原理1 人学硕| 研究生学位论文 个体转变提供了又一次机会。从幼体到成体的成长过程，通过向外界环 境的学习，一方面可以弥补自身基因的某些不适应性，另一方面激发和 强化生物体在某些方面的适应性。这一过程同样既是确定的，又是随机 的。其确定性表现在生物体j | j 有什么样的基因就能适应什么样的环境： 其随机性表现在环境刈生物体的影响方式是随机的。因而，一个好的个 体就是在这种确定性和随机性的双机制作用下产生的。 综上所述，一个个体的成长过程可分为两个阶段：诞生阶段和成长 阶段。诞生阶段以内在的染色体重组为其变化的主要动力，成长阶段以 外在的环境影响为其变化的主要动力，两个阶段均在确定性和随机性的 双机制作用下变化。 生物个体的这种成长模式既保证了整个生物群体稳定的适应性，又 使生物体的性状向多样化发展，保证优异性状的不断出现。 剥于一个组合优化问题而占，我们要寻找的最优解就好比要形成一 个好的个体。模拟上述生物体的成长模式，我们可以把把问题分成两个 阶段来解决：第一个阶段诞生一个近似解，第二阶段让这个近似解象生 物个体一样成长为一个满意解。使这个过程重复进行，并保证两个阶段 在确定性和随机性的双机制下变化，那么就能琢在生物群体中涌现出 “好”的个体一样，出现一个“好”的满意解。 根据上面的想法，我们提出了如下的所谓成长算法( g r o w n u p a l g o r i t h m ，以下简称g u a ) 。除非特别强调，我们都假设算法用于解决下 面的组合最优化问题： m a xf ( x 1 s 。t g ( x ) 0 ( 3 一】) x d 其中厂( ) 为目标函数，g ( ) 为约束方程，d = 兀口为可行域，x 是解 i = l 2 0 太原理1 i 人学硕 。研究生学何论文 向量， x ，h 是其分量，口，i = 1 , - - 月是其分量的定义域。 我们提出的求解( 3 一i ) 的g u a 算法框架见下表3 一l 。 表3 1f i u a 的算法框架 。 算法的核心是s t e p l 解的诞生阶段和s t e p 2 解的成氏阶段，我们分别 称之为诞生算子和戚长算予。 显然任何一个启发式算法都能产生( 3 - 1 ) 式的一个近似解，然而它未 必可以作为g u a 算法的一个诞生算子出现。就如同随便挑一个人，即使 经过精心的培养和_ l 练，成为一个奥运会知短跑冠军的机会也是很小的。 但是如果我们能保证所挑选的人百米成绩在1 3 秒以内，那么最后成为一 个奥运会短跑冠军的机会就大大提高。同样为了找到最优解或至少是一 个相当满意的解，我们要求诞生算子产生的仞始解兄。质量有一定的保 证，我们称之为诞生算子具有确定性，即 定义3 1如果存在、一个实数，使得对任意执行一次某算法产生的 初始解正，均有 2 l 太原理1 人学硕十赴玎究生学位论文 厂( x o ) d ( 3 - 2 ) 成立，则称浚算法对问题( 3 1 ) 是d 一确定的。d 称为该算法对这个问题 的确定度。 显然，确定度越大。解的质量就越好。设x 是问题( 3 - 1 ) 的最优 解，当d = f ( x ) 时，这个算法就是一个精确算法。对n p 一完全问题来说， 这一般是不现实的。 在保证确定性的同时，诞生算子还必需具有随机性，即对任一个满 足( 3 2 ) 式的可行解托，执行一次诞生算子产生该可行解的概率小于1 。 随机性的作用有二，其一是跳出局部最优陷阱的内在要求；其= 是使g u a 算法同遗传算法一样具有群体进化的特征。 只有满足确定性和随机性双机制要求的启发式算法才能作为g u a 算 法的诞生算子，这是g u a 算法的核心之一。 s t e p 2 是成长算子，成艮算子的起点足诞生算子得到的初始解工。， 山上面的讨论可知，柳始解x 。已经是一个相当不错的解，这一步我们让 其阳外在的“环境”学习。定义一个邻域n ( x 。) ，相当于初始解x 。的成 长环境，它是可行域d 的予集，我们要在n ( x 。) u x 。上得到一个局部最 优解。即将x 。“溶解”在环境( 蜀) 中，再从中重生一个最优解，用一 句话总结就是“风凰涅磐，浴火重生”。这就是我们这罩所说的成跃，是 g u 算法的另一个核心概念。 设成k 算子产生的局部撮优解为x ，则厂( x ) ( x o ) d ，这是成 长算子的确定性，它由诞生算予的确定性决定，即所谓基因决定性状。 成长篼予的随机性表现在环境n ( x 。) 的产生足随机的。此时n ( x 。) 的选 2 2 太原理i ：大学硕十研究生学位论文 择是一个关键步骤，对n p 一完全问题来说n ( x 。) 太大，将消耗过多的计算 时间：而v ( k ) 太小时，山于学习的环境有限，初始解得不到真币的成 民。下一章我们在最大独立集问题中应用g u a 算法时，产生n ( x 。) 的机 制是随机地给当前的独立集添加一些顶点，使之不再是一个独立集，这 样就保证算法有足够的机会跳出局部最优解的陷阱。 s t e p 3 是不同个体之间的竞争，向量“保存当前的最优解。 算法g u a 可以对群体进行操作，在步骤s t e p l 产生若干初始解构成一 个秽j 始群体，在步骤s t e p 2 让这个群体成长为一个更成熟的群体，以此 重复进行。可以谠g u a 秉承了遗传算法的基本特征，但它与遗传算法又 有明显的不同。f 一节我们将比较g u a 算法与遗传算法的异同。 2 成长算法与遗传算法的比较 上个世纪六十年代，美国密歇根大学的j h o l l a n d 教授和他的学生 们提出了遗传算法( e n e t i ca l g o r it h m s ，g a ) “”3 。八十年代，德国柏 林工业大学的i r e c h e n b e r g 和h p s c h w e f e l 采用生物变异的思想优化 物体形状并逐渐形成了进化策略( e v o l u t i o n a r ys t r a t e g i e s ，e s ) “川。 此后还出现了进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) ，遗传编程 ( g e n e t i cp r o g r a m mjn g ，g p ) 等一系列算法。与其它算法相比，这类算 法具有鲜明的特色，这就足群体和进化，它给研究人员以广阔的想象空 川，山此发展了一类通川的算法，现在称之为进化计算( e v o l u t i o n a r y c o m p u t a t i o n ，e c ) 。 进化计算的主要特点是： 1 ) 模拟生物的进化过程； 太原理j ：人学硕十研究生学何论文 2 ) 随机性； ：j ) 钊对群体操作，从而具有并行计算的特点： 4 ) 自适应性。 山此可知，我们提出的g u a 算法也是属于这类进化计算的一种启发 式算法。但足，它自身又有显著的特色，下面我们以典型的进化计算方 t 法一遗传算法为例，表3 - 3 比较了它与g u a 算法的不同。为方便理解， 我们先给出简单遗传算法的一般框架，见表3 2 。 表3 - 2 简单遗传算法的总体框架 g a 的核心在于选择、杂交平l 变异，通过这三个算子的共同作用实现 演化和对问题的求解。g u a 用成长算子来代替这三个算子，通过对环境的 学习米实现自身的成 王= 和问题的求解。所带柬的好处足使进化有了定向 机制，成长算子的结果一定是局部最优解。另外，选择、杂交和变异的 机制主要是随机机制。而成长算。于不仅蕴含着随机机制，还从诞生算子 太原理i ：人学硕十研究生学位论文 那单继承了确定性机制，使其搜索效率大为提高。 表3 - 3g a 与g u a 的比较 g a g u a 模拟角度生物群体自然演进的宏观生物群体自然演进的微观 原因 机制 初始化随机选择机制确定性和随机性的双机制 作用下的诞生算子 进化机制选择，杂交和变异成长 进化结果非定向定向，局部最优解 g u a 中并不是只有成长算子一个进化机制，诞生算子实际上强化了许 多进化计算的初始化过程，是g u a 中一个重要的机制。g u a 中的初始化过 程不仅仅是随机选择一个初始解那么简单，而足利用确定性和随机性的 双机制作用产生一个“好”的初始解，再送到成长算予那里进化。 从模拟生物进化的角度看，g a 模拟的是生物学群体进化的宏观特征， 而g u a 看到的是保持生物学群体进化中，一个生物群体的多样性和进化 中的定向性之问的协调机制。 总之，g u a 从一个与g a 不同的全新角度诠释生物群体的进化，模拟 其中的特征。从下一章的计算结果来看，g u a 是一种值得研究丌发的新的 启发式算法。 太原理i ：人学硕十研究生学位论文 四最大独立集问题的成长算法 基于上一章的讨论，本章我们给出最大独立集问题的g u a 算法。