（计算机软件与理论专业论文）健壮性着色问题的研究.pdf

健壮性着色问题的研究 专业：计算机软件与理论 硕士生：孔颖 撂导教黪：蠡嵩由 摘要 健壮性图着色问题( r o b u s tg r a p hc o l o r i n gp r o b l e m r g c p ) 是经典图着色问 题的一种新的扩展，它有很大量的实际应用，比如说人员排班、排课等等。经典 舀着色溺题豹嚣蠡跫寻我最小懿萋色鼗。瑟r g c p 刘着重镑j c 重凑垒方寨熬壤壮 性，使之能处理现实中经常出现的不可预见韵突发事件。为了实现这个健壮性的 目标，在图着色中，除了给相邻点赋予不同颜色外，还需要考虑不相邻点的边出 现的情况。 搴论文将对r g c p 邈季亍深入懿磷究，绘赉它懿辩阐复杂凄。讨论r g c p 在褥豫 情况下的最优解计算，由此推导与证明了平均颜色定理，以及把它推广刻般 r g c p 。利用这个定理，本文还研究与试验了各种智能优化算法解r g c p 问题的 效率，激终缮出曩翡鼹决这拿阍题最好款一耪滋合算法。本文邀将列出蚤耱葵法 下的实验结果。 关键诵：蔫色阅题，健壮性，平均颜色定理，留糍优化算法 r e s e a r c ho i lr o b u s t g r a p hc o l o r i n gp r o b l e m i i l a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：y i n gk o n g s u p e r v i s o r ：s o n g s h a ng u o a b s t r a c t t h er g c p ( r o b u s tg r a p hc o l o r i n gp r o b l e m ) i san e wv a r i a n to ft h et r a d i t i o n a l g r a p hc o l o r i n gp r o b l e m i th a sn u m e r o u sp r a c t i c a la p p l i c a t i o n si nr e a lw o r l d l i k e t i m e t a b l i n ga n dc r e ws c h e d u l i n g 。t h e t r a d i t i o n a lg r a p h c o l o r i n gp r o b l e m f o c u s e so n m m l t m l z l n gt h en u m b e r o fc o l o r su s e di nt h eg r a p h r g c pf o c u s e so nt h er o b u s t n e s s o ft h ec o l o r i n gs ot h a tt h ec o l o r i n gi sa b l et oh a n d l eu n c e r t a i n t yt h a to f t e no c c u r si n t h er e a lw o r l d 。b yt h a t ，w em e a nt h a tg i v e naf i x e dn u m b e ro fc o l o r sw ew o u l dl i k et o c o l o rt h eg r a p hs ot h a ta d j a c e n tv e r t i c e sa r ea s s i g n e dd i f f e r e n tc o l o r sw i t ht h e c o n s i d e r a t i o no ft h ep o s s i b l ea p p e a r a n c eo ft h em i s s i n ge d g e s i nt h i sp a p e r ，lr e s e a r c hr g c p d e e p l y t h ec o m p u t a t i o n a lc o m p l e x i t yo f t h e r g c pw i l lb eg i v e no u t + t h e o p t i m a ls o l u t i o no f t h es o m e s p e c i a lr g c p w i l lb e r e s e a r c h e d a n dt h em e a nc o l o rt h e o r e mw i l lb er a i s e da n dw i i lb ep r o v e d t h e t h e o r e mc a nb eu s e di ut h eg e n e r a lr g c p ia l s or e s e a r c ha n dd os o m ee x p e r i m e n t s a b o u ts o m em e t a h e u r i s t i c sa l g o r i t h m st os o l v et h er g c rt h ee x p e r i m e n tr e s u l t s s h o wo u rh y b r i da l g o r i t h mi st h eb e s tw a yt os o l v er g c e k e yw o r d s ：g r a p hc o l o r i n g ，r o b u s t ，m e a n c o l o rt h e o r e m ，m e t a h e u r i s t i c s a l g o r i t h m s 引言 健壮性图着色问题( r o b u s tg r a p hc o l o r i n gp r o b l e m r g c p ) 的经典图着色问题的 一种新的扩展。 经典图着色问题是一个著名的n p 完全问题。在实际中在大量商业和工业上的应 用( p a r d a l o s1 9 9 6 ) ，包括时间表安排( o p s u t1 9 8 1 ) 、频率分配( o a m s t1 9 8 6 ) 、寄存器分 配( c h a i t i o n1 9 8 2 ) 、生物学与考古学上的数据分析( b a r t h e l e m y1 9 9 1 ) 。 经典图着色问题的目标，是使用最小的颜色数，使一个图中所有的相邻点对都 有不相同的颜色。经典图着色问题可以转化成c 着色( cc o l o r i n g ) p l j 断问题，即给定 c 种颜色、一个图g ，判断使用c 种颜色是否满足图g 着色。 r g c p 首先是一个cc o l o r i n g 判断问题，就是说它必须能够使用c 种颜色满足着色 的条件。其次，r g c p 研究着色方案的健壮性，使之能处理现实中经常出现的不可 预见的突发事件。为了实现这个健壮性的目标，在图着色中，除了给相邻点赋予不 同颜色外，还需要考虑不相邻点的边出现的情况。这种考虑在r g c p 问题中转化成 一个目标函数，目标函数的最小值，就是r g c p i 司题的最优解。用一句话概括：r g c p 问题是一个满足c c o l o r i n g 条件下，求目标函数晟优的问题。 第1 章简介 r g c p 有很大量的实际应用，大部分经典图着色问题，都可以在健壮性上找到有 实际意义的应用，比如说人员排班、排课等等，这些会在第2 章中论述。 r g c p 是一个n p 完全问题，但在一些特殊情况可以直接计算最优解，这种计算 及其平均颜色的原理对一般情况都有指导意义，这个原理及其证明将会在第3 章中论 述。 对于n p 完全问题的优化，目前比较有效的方法是使用智能优化算法，本文主要 使用邻域搜索算法进行求解r g c p 。它需要定义一个解的表示方法与解空间。在第4 章中，将会介绍与从理论上比较：两种不同的解编码基于顺序( o r d e r b a s e ) 的解 编码与基于分类( p a r t i t i o n b a s e ) 的解编码、两种不同的邻域函数单点颜色改变与 k 颜色交换、两种初始解生成的算法随机初始解与严格颜色平均分布7 初始解。 在第5 章中，将会具体给出局部搜索算法( l o c a ls e a r c h ) 解决r g c p 问题的过程， 从实验数据上比较第4 章中的各种不同搜索策略，还有具体中使用的剪枝策略、搜索 策略，最终得出目前解决这个问题最好的一种混合算法。各种算法下的实验结果也 将会被列出。平均颜色的原理也会应用到这些搜索算法中，显示出其价值。几种针 对r g c p 的新方法，例如基于分类编码( p a r t i t i o n b a s e ) 、改进图( i m p r o v eg r a p h ) 、k 环交换( k e x c h a n g ec y c l i c ) 等也将会一一进行论述。 在第6 章中，其它几种智能优化算法，例如遗传算法、模拟退火算法，在解决r g c p 中的实际算法与实验结果也将会给出。 最后第7 章是全文的总结，并介绍本文的不足之处与r g c p 进一步的研究方向。 2 1 实际问题 第2 章问题描述 r g c p 有很大量的实际应用，大部分经典图着色问题，都可以在健壮性上找到 有实际意义的应用。下面介绍三个问题：机组人员分配问题、聚类问题、地图着色 问题。这三个问题原来都是经典图着色问题，当考虑到着色方案的健壮性时，就产 生了这些r g c p 问题。 2 1 1 机组人员分配问题 假设一个航空公司的航线管理部门，负责管理一组航线与几个机组人员的组。 健壮性机组人员分问题的目标，就是要找出一个最健壮的分配方案，把每一组的机 组人员分配到某几个航线，使得同一组人员分配的航线不能在时间上重叠。 这里的“健壮性”的定义是考虑到航线实际运营中的一些不可预知的突发事件， 这些突发事件是很常见的，比如说天气条件、飞机的临时调度等等。这些突发事件 会导致航班延误。 最健壮的人员分配方案是指，当预定的航班时间表发生不可预知的改变的情况， 能够最大程度的不修改躁方案丽适应改变。 为了更好瀚穗述这个褫缍人员分配游遴，这里举一个饲子。在寝梧l 里，有一 个每天的往返航班时间表，上面有5 条航线的情况，包括编号、航线的起始地、离 开和返程抵达航空公司中心机场( 广州自云机场g z ) 的时间。航空公司一共有4 缝鳇瓤组人爨，分羧是a ，b ，c ，d 蝗。我翻篱要把每一个誊晁缝人员分醚到每一条簸线， 满足以下条件：( 1 ) 每条航线有且只有一组税组人员；( 2 ) 每一组枫缀人员在任何时 候只能在一祭航线上服务；( 3 ) 每一组机组人员服务完条航线之聪，必须有6 0 分 钟或更多的体息时间，才能割下一条航线服务。 表2 - l ：一夺每天强定靛线的时溺表 | 编号航线出发时间返程到达时间 【1 g z p e k w g z0 9 ：0 01 6 ：0 0 1 2g z s i n g z0 9 ：0 01 4 ：o o l 3g z n r 誊g z1 5 ： 2 2 ：0 0 i4g z p e k g z1 6 ：0 02 3 ：0 0 l 5g z n r b g z0 8 ：0 01 5 ：0 0 在解决撬缎人员分配闷题中，最重要的关系是航线之闻的对阈黧叠关系，像翻 2 1 中表示酌。这辩重囊关系可鞋疆鑫然瓣转仡戒蚕豹关系，圈静簿令结点表示每 条航线，当两条航线在时间段上有重叠，这两个结点之间就有一祭边。对于表2 一l 的航线时间袭，转化成图就是图2 2 。 闰2 - l ：时间表1 的时间段跨腹图 图2 - 2 ：时间淡2 - 1 对应的网 到了这里，机组人员分配问题就被转化成对一个图的健壮性着色问题。对于图 2 2 ，很容易就可以知道最小的颜色数是3 。这表示只需要3 组的机组人员就可以服 务全部5 条航线，并满足全部的限制条件。对图2 - 2 其中一个最优的着色方案 f c o l o r i n g1 ) 是 c ( 1 ) = l ，c ( 2 ) = c ( 3 ) = 2 ，c ( 4 ) = c ( 5 ) = 3 接下来考虑经常发生的航班延误情况。例如，由于新加坡( s i n ) 出现坏天气， 2 号航班发生延误，在1 6 ：0 0 才返程到达广州( g z ) 。 这个突发的改变使得2 号航 班的时间段与3 号和4 号都发生重叠。新的图就变成图2 - 3 所示，粗线表示新增的 边。 图2 - 3 ：2 号航班延误到1 6 ：0 0 返回之后的图 对于图2 - 3 3 ，已经不能再用3 种颜色满足所有的边关联的一对结点是不同的颜 色这个条件。如果前面的着色的方案( c o l o r i n g2 ) 变成 c ( 1 ) = l ，c ( 2 ) = 2 ，c ( 3 ) = 3 ，c ( 4 ) = c ( 5 ) = 4 ， 很明显，在上面这种突发的改变之下，这种方案不需要改动，仍然是满足条件 的。 在很多的情况下，我们需要一个更健壮的方案而不是最优的方案。在机组人员 分配这个问题上，健壮的方案就意味着在对应的图上，能够最大程度的包容未知的 新增边，使得着色方案对新的图也是满足的，即颜色数保持不变。 对于未知的新增边，可以定义它出现的概率。在健壮性机组人员分配问题上， f 面的等式用于估算新增边出现的概率，它考虑到两个航班i 和j 之间重叠的可能 一| 生。 州棚5 磊瓦而历盎币丽m a l 7 匆( f ) t 勘( j ) 一r n l “p 岛( j ) ，1 南( j ) + 。 丁赫( f ) 和k ，( f ) 表示航班i 的出发时间与返程到达时间 个航班之间的最短休息时间，a 是一个常量。 l ，表示机组人员在两 基于上面的对新增边的出现概率的估算方法，我们可以得到这样个所有可能 的新增边的出现概率矩阵h ，对应于图2 - i 的时间表。f ci ss e tt oi o ) + 0 8 60 4 6一 + 0 8 6 进步，我们可以给出这个问题上的健壮性定义，即问题的目标函数。 m i n r ( g ) ；一l o g( 1 一p ( j ，j ) 1 ( f j 】e e ，c ( i ) - - c ( j ) 这里g ( e ”表示图 对于c o l o r i n g1 ，目标函数就是 r = 一l o g ( ( 1 - p ( 2 ，3 ) ) ( 1 - p ( 4 ，5 ) ) ) = 一l o g ( o 0 1 9 6 ) = 1 7 0 8 对于c o l o r i n g2 ，目标函数就是 r = 一l o g ( i - p ( 4 ，5 ) ) = l o g ( o 1 4 ) = o 8 5 4 由计算的结果可以看出，c o l o r i n g2 是比c o l o r i n g l 更健壮的。 2 1 2 聚类问题 典型的聚集问题，是给定一个集合，把它的元素按某个性质的相似性，分类成 预定数目的子集( 聚类) 。元素的聚类相似性，可以表现为一个元素间的差异度函数。 v 表示元素的集合对应的结点，e 定义为每对元素i ，j v 2 _ 间的边，它们的差异度d ( i j ) 小于a ，d o 是一个给定的临界值。这个图上的c 着色问题，就定义了划分c 个聚 类的问题。h a n s e n 和d e l a t t r e ( s e eh a n s e ne ta 1 3 ) 已经任何一个c 着色问题， 都定义了最小直径的把整个集合分成c 个聚类。下面给出这个问题的一个例子： 设v = i 2 ，3 ，4 ，5 ) ，d 是差异度矩阵 d = 4 o o l0 0 20 0 50 0 4 + 0 0 40 0 30 0 4 + 0 0 60 0 7 8 o 0 3 对于不同临界值n ，可以定义不同的图吒和着色函数：例如a = 0 0 5 ，图嚷有 两条边，即e ： ( 3 ，4 ： 3 ，5 ) ，这个图可以表示成图2 4 。考虑这爪z ( g 0 0 5 ) = 2 的 情况，2 - 着色问题可以得到着色方案c j ： c ( ”= l ，c ? ( 2 ) = l ，e ? ( 3 ) 1 2 ，口( 4 ) = l ，四( 5 ) = l 势液了两个聚类： k ( 1 ) = f l ，2 ，4 ，5 v ( 2 ) = ( 3 对于另一个合法的着色方案g ： ( | ) = l ，( 2 ) = 1 ，( 3 ) = | ，( 4 ) = 2 ，5 ) = 2 分成了两个聚类： ooo 图2 4 ：= 0 。0 5 的图强2 - s ：& = o 。0 4 静图 现在如果降低临界值an o 0 4 ，一条边( 1 ，4 将被加上。这时图瓯。变成图2 5 鬓示。对予联雀蕊善( 瓯。) - - 2 夔渡援，鄯凑色鼗( 聚粪数) 不变。饕惫方案留变德 不合法的，假着色方案讲仍然是合法的。 在聚类分析的问题中，找最小的聚炎数转化成找最小的颜色数。然而在一些实 际愤况下，聚类数是固定的，就是说颜惫数是固定的e ，阉题变成如髓找出一个解， 在临界值a 降低的情况下奄仍然保持会法的聚类。遥擎争健壮性的要求，使它变成了 个健壮性图着色问题。这个r g c p 在代数上的定义在 1 里有论述。 2 。1 。3 遗圈饕梵淹题 经典的4 色问题是对一个平面的地图找最少的颜钒数。这个问题已经被证明只 躅4 嵇颜色簸可以潢是了。 p b 厂l 圈2 ，6 ：乎耍圈g 设霞g 鼹一个地图对成的平面图，瓣阁2 - 6 所示。耳，弼是两个不同的4 色祷 融方案 l23 4 5678 奠 322l4223 c 324i32l4 _ 两种着色方案的颜色集合是： v ( 1 ) - - 4 ( 2 ) = 2 ，3 ，6 ，? ( 动= f 1 ，8 砭( 4 ) = 5 e ( 1 ) = 4 ，7 e ( 2 ) = f 2 ，6 h ( 3 ) = 王，7 k ( 4 ) = 3 ，8 可以注意到，第二种着色方案比第一种着色方案慰平均，所有的颜色都对两个 基域羞色。农瑷实翡地图中，会更德向使愆第二嵇着瞧方案。困为如果乎霞图发生 变纯，魏果菜释颜色的善氛点逝较多，这稀颜色静点之闻发生裙连瓣缀率裁会大。 因此这个问题也有一个健壮性的要求，也变成了一个德壮性图着色问题。这个r g c p 在代数上的定义在 1 里有论述。 2 2 问题一般描述 上蟊掰列麴这些闻趣都鸯耨个特点；一，这盛颓燕一个合法豹黎氇方案。二， 必须考虑可能新增的边对着色方案的影响。在经典着甑问题中要寻找的目标函数一 最小着色数，变成了一个固定的限制祭件。而且标函数，则变成对新增边有最好 的适应性的薏媳方案。 由筵，我们可戳绘啬键猛骼图着色阑髓我一般定义： ( 健壮性图着色问题r o b u s t g r a p h c o l o i n gp r o b l e m 。r g c p ) 给定个图g = ( k 日， | 卅= 地设整数c o 表示颜基数，设替边豢台为蓉，羚边繁台土的罚分黎含( p e n a l t ys e t ) 黜k ，( i ，) e 虿 ，r g c p 的萤标函数定义为 找出最小的r ( c ) ； p q ， ( 1 ，) e c ( f ) ：c ( ) 这里的c 怒羞色豹殃懿o 矿一 l ，2 + ，c ；满足c 8 ) # c ( n 硪l ，j ) 誊。 r g c p 可以被描述成溉c ，固 根据实际阀题的不同，p e n a l t ys e t 可以有不同的定义。比如在2 1 1 中描述的健 壮经撬缰入受分配强题上，爵强定义蔻： 脚l o g ( 1 嘞) 在实际的算法中，当c o l o r i n gc 不是一个合法着色方案时( 靼不满足经热 c c o l o r i n g 问越) ，r g c p 露禄函数仍然会鸯函数值。稳为了突整这静不合法静瑗象， 使之尽快变得合法，此时的目标函数值为变得非常大。具体定义如下： 凡( c ) 罩 期+ p l 8 s 瓴赫t c ( f ) = 曩j ) 这里酶s 表示c o l o r i n gc 中枢邻缨点簇色相同酶慧数，p l 取一个眈较大静芷数 ( 后面的算法中p 1 = 1 1 3 0 0 0 ) 。 2 3 计算复杂性分褥 对于这榉个新的翔题，有一个狠囊然豹阉题：是否可以在多项式时间内解决? 始采不可以，鄢这个闻寇r 戆在小援模的数攥上褥到最往解：对予大瓣模豹数据， 只能用近似算法得到较优解。 r g c p 的复杂性分析可以从相关的判定问题开始： d r c p 判定润题： 设一个圈g 叠( k d ，一个正整数o - - i v l 。补遮集合拦上的罚分聚合( p e n a l t ys e t ) p = k ，( f ，j ) e 科，和一个上界f 。 闻：是否存在一个g 酾e c o l o r i n g c ，使褥冀( e ) = 如 = f 。 悒ii x e c m = c n 引理：d r c p 是n p - c o m p l e t e 。 涯骥： d r c p n p ，因为检查个0 - c o l o r i n g 魁否满足所有祭件，只需要个非确 定算法在多项式时间内完成。 设d m c p 表示最小圈着氛润题的关联戴鞭间题，繇： d m c p ： 设一个图g = ( u 聊，一个正熬数k = i v l 。 耀i 是否存褒掇g 的k - c o l o r i n g 。 我们可以把d m c p 变换成d r c p 。给定一个实例，gd 。，设罚分集合p 魄= o ，v ( f ，j ) e 蚕，颜色数c - - - k ，并设目标函数值上界f = o 。则努一个实 倒，( f ) 0 。簸可以构造懑来。并且这个浃骞孝，是莓以在多壤式辩瀚完藏 的。 丽d m c p 已经被证明是n p - c o m p l e t e g a r e y a n dj o h n s o n ，1 9 7 9 1 ，所以d r c p 电 是n p c o m p l e t e 。 西 因此，r g c p 墩是n p c o m p l e t e 。 2 。4 已蠢装研究 j a v i e r y a n e z ，j a v i e r r a m i r e z 在( 1 1 中提出了r g c p 这个问题，缭出了这个问题在实 琢中菲鬻毒用的的三个铡子，并绘如了解决这个阕题装一秘最蒸本我方法。 龟髑是 使用最熬本的遗传算法求出较倪解，遗传算法中使用基于预穿酌方式对解遴行编羁， 这样使得求解收敛得比较慢，最优解也不能保证存在于这种解空间。 由于r g c p 是图论中一个缀新的问题，世界上已经进行的研究不多。只能参考 经典饕惫| 、藏戆爨臻究残莱，麸中我爨遥台子r g c p 蠢题麴方法。 经熟图着色问题中，有两个主臻的研究课题；一个是为小规模数据找最优解的 算法( k u b a l e1 9 8 5 ) ：另一个是对大规模数据的近似算法。由于经典图着色问题已经 菠证明疑n p 完全淘题( g a r e y1 9 7 9 ) 。摄多智能优化算法提出采解较大规模的闻题。 包括有贪心着色算法( g r e e d yc o l o r i n g a l g o r i t h m ，k o r t e2 0 0 2 ) ，f s u c c e s s i v e a u g m e n t a t i o n ，b r e l a z1 9 7 9 ) ，基于禁忌搜索的算法( t a b us e a r c hb a s e da l g o r i t h m d o r n e 1 9 9 8 ) ，基于模拟退火的算法( s i m u l a t e da n n e a l i n gb a s e da l g o r i t h m ，j o h n s o n 1 9 9 l ，c h a i n s1 9 8 7 ) ，基于进化计算的算法( e v o l u t i o n a r yb a s e d a l g o r t h mc o s t a1 9 9 5 ) 另外，目前最好的“最坏情况率”( w o r s t c a s er a t i o ，即目前最好的着色数除以最 优着色数) 已经被保证了( h a l l d o r s s o n1 9 9 0 ) 。还有一个很有名的d m i a c s 性能挑战 ( j o h n s o n1 9 9 6 ) ，它是设立了一套标准的测试数据与权威的最佳记录，去比较各种不 同算法解决经典图着色问题的质量与性能。 第3 章最优解的研究 尽管r g c p 是n p - c o m p l e t e 问题，但在一些特殊情况下，是可以直接计算其最 优解的目标函数的。这一章，将会考虑r g c p 的罚分集合都相等的隋况，给出这种 情况下的最优解计算，以及到达最优解所要遵守的平均颜色定理。 l 等罚分情况及平均颜色定理 等罚分情况是指不相邻点之间的罚分全部都相等。在这种情况下，r g c p 问 题的目标函数是有确定的最优解，可以通过公式计算出来。着色方案也可以通过多 项式时间的算法得出。 以下假设罚分集合中不相邻点的罚分值( p e n a l t y ) 都是1 。 3 1 1 最优解与平均颜色定理 对于n 个点用c 种颜色。 假设已经有一个合法的c o l o r i n g 方案c ，对于这n 个颜色值c ( i ) l = i = n ，如果 有存在c ( i ) = c o ) ，i j ，则i 与j 一定不相邻( 否则不是合法的c o l o r i n g ) 。因此， 对所有的c ( i ) = c o ) 情况，都会有p e n a l t y 值需要累加。因此总的p e n a l t y 值就与图的 拓扑结构与c o l o r i n g 具体方案无关，只与c ( i ) = c ( j ) ( 1 = i = n ，l 彤p ) ，即k ( a ) 一k ( b ) = h 1 。 翻( 鬈( 拄) 一 ) 2 + 瑟蠢) 十1 ) 2 = 蜀翻) 2 + 彭( 务) 3 + 2 ( 鬈参) 一爱缸) + l = 茁国) 2 琵) 2 2 t k ( d ) 2 + k ( 扫) 2 使得颜色为a , b 的颜色数髟( n ) ，彤( 6 ) 可以局部调整为更优的解：k ( 日) 一l ，( 6 ) + l 。 所以缀搜不成立，不存在l 爱( 8 ) 一定扫) l = + l 。 由( 1 ) n ( 2 ) n 7 - 归纳出：在最优解的情况下，对任意a ，b ( 1 9 “，b c ) ，都满足 l k ( a ) - 符( 6 ) l 1 。 定理得证。 3 。1 。2 最镌释基标鸶数谤募 根据等罚分平均颜色定理，可以直接计算出这种情况下r g c p 最优解的目标函 数值。 对予n ，e ，p ) 弱戆，最平均蠡毫餐包方案是霄nm o de 令簇魏数为卜，c j + l ，e 一国 m o d c ) 个颜色数为l n ，口j ，即： r ( c ) = ( n r o o dc ) + p ( 1n l c l + 1 ) + ( c - ( n r o o dc 1 ) + p ( l n c j ) = ( n r o o d e ) s ( i n t c j + 1 ) + l n t c j t 2 + ( c - 趣r o o d c ) ) 4 b ，c + ( l c j 1 ) 1 2 = ( ( n r o o dc ) + ( 1 n ，c j 十1 ) + ( c 一( n m o dc ) ) + ( l n l c j “i ) ) + l n l c j 2 = ( ( n m o d c ) + l n l c j + ( n m o dc ) + c 4 l n q e 一( n r o o d c ) 4 l ”，c j + ( n m o dc ) ) + l n c j 7 2 ：f 28 ( n m o d e ) + c 8 l e j e ) 4 l n l c j t z 3 - ( 4 ) 例如对于n = 5 ，c = 3 的情况，计算得到结果是2 。 对予一般静情况，蚤表3 - 1 ，使爝的算法是遗魇遗传算法g a ( 6 1 眷详细算法 描述) ，一种近似算法。这里对同一组参数使用5 0 个测试数据，取其r 的平均值与 时间平均值。可以看出，测试数据3 到8 的用搜索算法得出的结果与计算的结果完 全一致，第9 组参数，由于n 值比较大，有些情况下算法未能收敛到最优解，所以 还有一点的偏差。 表3 1 利用平均颜色定理的计算结果 测试编号参数改进g a 编码的算法 ( 4 ) 式的计算结果 r ( 均值)时间( 均值)r 值 a 35 01 84 6 0 02 8 54 6 a 41 0 03 59 5 o o42 09 5 a 52 5 07 03 3 00 01 28 73 3 0 a 62 5 08 02 7 00 01 3 5 32 7 0 a 72 5 09 02 3 0 o o1 4 2 52 3 0 a 85 0 02 0 04 0 00 05 8 8 34 0 0 a 91 0 0 03 0 01 2 0 26 72 8 5 4 51 2 0 0 3 2 不等罚分情况下的平均颜色定理应用 平均颜色定理在等罚分的情况得到很完美的结果。那么在不等罚分的情况下是 否仍然有价值呢? 在3 1 中的等罚分的情况分析中，由于假设所有不相邻点的罚分值( p e n a l t y ) 都是 l 。设在c o l o r i n gc 下所有颜色的分布为k ( a ) ( i = a = c ) 。由p ( k ( a ) ) 的定义，可以知 道实际上p ( k ( a ) ) 在数值上等于颜色为a 的结点集构成结点对的数目，即关于颜色a 的所有可能累加p e n a l t y 的补边总数。因此可以推出3 - ( 2 ) 式的结果在数值上等于整 个图全部可能累加p e n a l t y 的补边总数t ( c ) ，即 t ( c ) = f k ( a ) + ( k ( 口) 一1 ) 2 3 - ( 5 ) = 3 ( 4 ) 式就是整个图全部可能累加p e n a l t y 的补边总数的最小值k 。( c ) ，即 。( c ) = ( 2 ( n m o d c ) + c 4 l d c ) + l n l c j a 3 - ( 6 ) 因此，3 ( 6 ) 式对于一般情况r g c p 的意义是：不存在平均颜色定理以外的颜色 分布c ，使得t ( c ) l 。( c ) 。即r g c p 的目标函数是由若干个p e n a l t y 值累加其总 和，则p e n a l t y 累加的次数最小值等于民。( c ) a 由此可以看出平均颜色定理对一般r g c p 的意义，它给出了p e n a i t y 累加的次数 的最小值，而目标函数是求p e n a i t y 总和的最小值。由于这个差别，平均颜色定理 并不能对目标函数的最小值有直接的帮助。但是可以推断出，减少p e n a l t y 累加的次 数，实际上在大方向上是可以减少p e n a l t y 的总值的；就是说在求解过程中，对这个 t ( c ) 值的优化，与对目标函数的优化，方向是一样的。因此在后面的一般r g c p 求 解中，我们还是会使用平均颜色定理，从减少p e n a l t y 累加次数的角度对搜索过程提 供智能优化。 第4 章解空间 由于r g c p 是n p c o m p l e t e ，所以对于大规模的数据，只能在现实的时间内得 出较优解。目前求较优解最有效的方法，是各种智能优化算法( m e t a h e u r i s t i c s a l g o r i t h m s ) 。我主要使用其邻域搜索算法进行求解，邻域搜索算法都需要定义一个 解空l - 日 ( s o l u t i o ns p a c e ) 与解的邻域( n e i g h b o r h o o d ) 。 解空间定义了r g c p 问题在算法中如何表示、如何编码，直接决定了算法的规 模。解的邻域定义了在搜索中从一个解如何通过操作到达另一个解。在这一章里 我们会讨论影响r g c p 邻域搜索算法的3 个重要因素：解的编码、邻域定义与初始 解的生成。 4 1 优化算法概述 优化算法其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定 的途径或规则来得到满足用户要求的的问题的解。 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、 构造型算法、改进型算法、基于系统动态演化的算法和混合弄算法。 本文中解决r g c p 主要使用了改进型算法，即邻域搜索算法。 4 1 1 邻域搜索算法 邻域搜索算法从任一解出发，对其邻域的不断搜索和当前解的替换来实现优化。 邻域是邻域搜索算法的关键部分。我们把关于解x 的解空间子集n ( x ) 称为解x 的邻域，仅当对于任意x n ( x ) ，x 都能够从x 经过一次变换操作可以到达。这里 的变换操作就定义了邻域函数。 邻域搜索算法中最基本的算法是局部搜索算法( l o c a ls e a r c h ) 。它的基本意思， 就是通过对某一个初始解的不断优化，达到局部的最优解。优化的过程由一次一次 的迭代进行，每一次迭代前都有一个当前解。找出这个当前最优解的邻域，只接受 优于当前解的新解作为下一当前解，是爬山法：接受当前解邻域中的最好解作为下 一当前解，是最陡下降法。当某次迭代找不到更优的解为止。这时，一个局部的最 优解就产生了。 在很多情况下，通过这种快速的算法得到的局部最优解，都在可以接受的范围 之中，与耗费大得多的资源得到的全局最优解相比，显得更有实际价值。 r g c p 的l o c a ls e a r c h 算法( 爬山法) 流程框架： 1 生成一个初始的c o l o r i n g 没为当前c o l o r i n gc 2进入迭代循环： 2 1根据邻域的定义，对邻域中的每一个新解： 2 1 1 判断新解是否合法的c o l o r i n g 2 1 2 计算新解的r 值 2 1 3 如果新解的r 值比当前最优c o l o r i n g 的r 值小，则替换当前最优 c o l o r i n g 2 2如果本次迭代没有更新当前最优c o l o r i n g ，则退出循环 2 3用当前最优c o l o r i n g 替换当前c o l o r i n gc 3输出局部最优c o l o r i n g 4 2 解的编码方式比较 r g c p 问题中编码，就是要找出一种有效的方式表示每一个着色方案。下面会 介绍在经典图着色问题的研究中很常用的编码方式，基于顺序( o r d e r - b a s e ) 的编码。 然后再介绍一种新的能够适应r g c p 需求的编码方式，基于分类( p a r t i t i o n b a s e ) 的编 码。 4 2 1 基于顺序( o r d e r b a s e ) 编码 在经典图着色问题中的一种常用的编码方式，是基于着色顺序( o r d e r - b a s e ) 的编 码方式。这种方式，是把结点到颜色的映射这个解空间，转化成着色的顺序这个解 空间。设v 的结点先是被排好一个着色的顺序( o r d e o ，然后使用贪心的算法按顺序 着色( c o l o r i n g ) ：对于每一步着色的结点，它的颜色不能与前面已经着色的相邻点相 同，并找出满足这个条件下的最小的颜色编号。比如对于图2 中的图，如果o r d e r 是( 1 , 2 ，3 ，4 ，5 ) ，则对应的c o l o r i n g 是【c ( 1 ) = l ，c ( 2 ) = 2 ，c ( 3 ) = 2 ，c ( 4 ) = 3 ，c ( 5 ) = 3 。 o r d e r b a s e 这种编码方法的解空间规模是n ! 。 然而对于r g c p ，o r d e r b a s e 的最大问题是它不能覆盖整个可能着色方案的解空 间，比如对于c o l o r i n g ： c ( 1 ) = 1 ，c ( 2 ) = 2 ，c ( 3 ) = 3 ，c ( 4 ) = c ( 5 ) = 4 1 ，就不存在任何一 个o r d e r 使用贪心法可以得出，这是因为贪心法是追求最小的颜色数，与r g c p 的 目标函数不一致。在经典着色问题中，这些没有被覆盖的解空间，存在最优解的可 能性比较小。但是在r g c p 中，最优解是比较有可能在这些解空间中的。这样就造 成使用o r d e r - b a s e 解r g c p 有可能得不到最优解。这个问题在 1 中f i g i 的 4 - c o l o r i n g 中出现，使用o r d e r b a s e 的解是r = 0 2 1 6 7 ，比最优解0 0 7 7 5 ( 可以手工得 出) 有差距。而对于更大解空间的图，不能被o r d e r b a s e 编码而比较优的解则可能会 大量存在。 o r d e r b a s e 的另一个问题是效率问题。从o r d e r 到c o l o r i n g ，是需要个算法进 行转换的，最简单的是贪心法，也可以用比较复杂的算法。当使用类似l o c a ls e a r c h 的算法时，在求邻域中的每一个的新解的时候，都需要对原o r d e r 进行改变，得出 新的o r d e r ：但原c o l o r i n g 要做相应的转换，得出新的c o l o r i n g ，这时就不可能直接 转了，还需要对新的o r d e r 重新进行着色转换成新的c o l o r i n g 。如果从o r d e r 到 c o l o r i n g 转换的算法复杂，那可能根本不可能做小的调整就得出新的c o l o r i n g 。这 样的l o c a ls e a r c h 就会很低效率。 同样的理由，o r d e r 发生改变时，目标函数值会需要相应发生改变。由于c o l o r i n g 已经比较难进行调整，所以目标函数值也会比较难进行调整，而需要重新计算的目 标函数值。这样的效率也比较低。 4 2 2 基于分类( p a r t i t i o n b a s e ) 编码 基于分类的编码，是把相同颜色的结点集合作为一个类。就是说，一个可行解 可以被表示为( v l ，v 2 ，v c ，这里v i = ( jlc g ) = i ，l j n ，l i c 。例如： 对于图2 ，c = 4 时的一个解【c ( 1 ) = l ，c ( 2 ) = 2 ，c ( 3 ) = 2 ，c ( 4 ) = 3 ，c ( 5 ) = 3 1 ，它的 p a r t i t i o n b a s e 编