解决图着色问题的一种新禁忌搜索算法

1、解决图着色问题的一种新禁忌搜索算法第29卷第2期2012年2月计算机应用与软件ComputerApplicationsandSoftwareV01.29No.2Feb.2012解决图着色问题的一种新禁忌搜索算法马艳萍吴晓军杨明成(陕西师范大学计算机科学学院陕西西安710062)(大唐移动西安分公司研发部陕西西安710061)摘要为了解决典型的组合优化问题一图顶点着色问题,结合增强SEQ算法和禁忌搜索算法的优点与缺点,提出一种基于增强SEQ的新禁忌搜索算法(SEQTS).该算法利用增强SEQ算法较强的构造较优解的能力来为禁忌搜索算法构造多个较优初始解,然后进行多初始解禁忌搜索以找到全局最优解.计

2、算机实验的结果表明该算法(SEQTS)有较好的寻优能力,增强了该算法的有效性.关键词禁忌搜索增强SEQ算法多初始解图顶点着色中图分类号TP301文献标识码AANEWTABUSEARCHALGoRITHMFoRGRAPHCoLoURINGMaYanpingWuXiaojunYangMingcheng(SchoolofComputerandScience,ShaanxiNormalUniversity,Xi'an710062,Shaanxi,China).(R&DDepartment,DatangMobileCompany,Xi'an710061,Shaanxi,C

3、hina)AbstractInthispaper,inordertofindtheglobaloptimumofatypicalcombinatorialoptimisationproblem,eolouringtheverticesofagraph,weproposeanewTabusearchalgorithm,SEQTS,basedonenhancedSEQincombinationwiththeadvantagesanddisadvantagesoftheenhancedSEQalgorithmandTabusechalgorithm.Itusesthestrongcapability

4、oftheenhancedSEQalgorithminstructuringoptimalsolutiontoconstructmultipleinitialoptimumsolutionsforTabusearchalgorithmatfirst,andthenperformsTabusearchontheseinitialsolutionsforgettingglobaloptimum.Itisprovedbycomputerexperimentalresultsthatthisnewalgorithm(SEQTS)haspreferablesearchabilitywhichstreng

5、thensitseffectiveness.KeywordsTabusearchEnhancedSEQalgorithmMultipleinitialsolutionsColouringverticesofgraph0引言自1986年美国科罗拉多大学系统科学家Glover教授首次正式提出算法以来,rrs首先在加工调度问题中得到了成功的应用J,并逐渐应用到模式识别,工程规划,布线系统,信号处理,通讯,图着色,专家系统,神经网络,计算机视觉等诸多领域,已取得了一些很好的效果.由于该方法属于一种新的优化方法,其框架灵活,通用性强,故而有着十分诱人的应用前景.因该方法提出时间不长,故其理论体系尚不完善

6、,需要进一步加以研究,其应用领域也正在拓宽.其中图着色问题是一典型的优化组合问题,由于它是NP难问题,不存在多项式时间的精确算法,因而应用启发式算法寻求其近似解成为现实的解决方案.本文针对禁忌搜索算法的不足,提出一种解决图结点着色问题的新禁忌搜索算法(SEQTS算法).1问题描述及算法原理色,其中最主要的一种是顶点着色.顶点着色问题可描述如下:给定一个无向图G=(,E),其中顶点集V=l,2,n,边集E=(i,)Ji,V,(i,)表示连接顶点i与顶点的一条边.若有:,CV,Vin=(i)V=u(1i,1k)且内部的任何两个顶点之间没有中的边可以使其直接相连通,则称(,)为的一个划分.图的顶点着

7、色问题可以描述为:求一个最小的k,使得(,)为的一个划分.1.2普通禁忌搜索算法原理禁忌搜索算法是模拟人的思维的一种智能搜索算法,即人们对已搜索的地方不会立即去搜索,而去对其它地方进行搜索,若没有找到,可再搜索已去过的地方.禁忌搜索算法从一个初始可行解出发,选择一系列的特定搜索方向(或称为"移动")作为试探,选择使目标函数值减少最多的移动方向.为了避免陷1.1图着色问题描述收稿日期:20110l一19.马艳萍,硕士生,主研领域:嵌入式系统图的着色问题可分类为边着色,顶点着色,List着色和全着开发,复杂算法.280计算机应用与软件2012生入局部最优解,禁忌搜索中采用了一种

8、灵活的"记忆"技术,即对己经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是禁忌表的建立的原因.禁忌表中保存了最近若干次迭代过程中所实现的移动,凡是处于禁忌表中的移动,在当前迭代过程中是不允许进行的,这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解,从而防止无限制的循环,帮助算法摆脱局部最优解.另外,为了尽可能不错过产生最优解的"移动",禁忌搜索还采用"特赦准则"的策略.禁忌搜索算法尽管在车间调度问题,模式识别,工程规划,布线系统,信号处理,通信,专家系统,神经网络,计算机视觉等诸多领域中得到成功应用.但是普通禁

9、忌搜索算法仍然有其不足之处J,如:(1)对初始解的依赖性较强,好的初始解有助于搜索,可能很快达到最优解,而较坏的初始解往往会使搜索很难或不能达到最优解;(2)迭代搜索过程是串行的,仅是单一状态的移动,而非并行搜索.图4结点D已着色c3由上可知,可以通过增强SEQ算法得到图顶点着色的较优方案,并且利用增强SEQ算法解决图着色问题的时候是以度数最大优先的顺序进行的,而图中顶点以顶点的度数最大优先的排序方法不唯一,这样就可以通过增强SEQ算法得出多个解决图着色问题的较优方案.基于上述两种算法的特点,针对禁忌搜索算法对初始解的依赖性强及串行搜索的不足,本文提出了一种基于增强SEQ的SEQTS算法.图着

10、色问题是典型的组合优化问题,以它为例来验证新算法的有效性.1.3增强SEQ算法描述2SEQTS算法增强SEQ算法的基本思想:按照图中顶点度由大到小的次序逐个给顶点着色,着色时使用的颜色编号是当前最小的可用颜色.一个顶点着色后将与它相关联的边看作从图中去掉后并重新计算未着色顶点的度.重复上述过程,直到图中不存在顶点间相互关联的边时,把剩余所有未着色顶点都着同一种色,这样图中所有结点都被着色就可以产生一种图着色的较优方案.所用颜色的最大编号即为所用颜色数.如图1的着色过程:其中图1是包含6个顶点的图,按顶点度数从大到小排序为:A,B,D,C,F,E.图2一图4分别为给顶点A着红色,B着绿色,D着灰

11、色后的图,此时图中已经没有边相关联,剩余的点c,E,F则可着同一种颜色,在此为黑色.由此可知,图1的着色数为k=4,按字母顺序,其解的形式可以写为1,2,4,3,4,4.但是根据实际情况可以有k=3,图着色的解为1,2,2,3,1,1.由此可知,增强SEQ算法得到的只是较好解,并不是最优解.图2图1原图图3结点B已着色c22.1SEQTS算法思想受文献7启发,本文根据TS算法对初始解的依赖性和增强SEQ在构造较优解时的优越性提出了SEQTS算法,先利用增强SEQ算法求得多个较优的解,然后把已搜索到的较优解当作Ts算法的初始解继续进行禁忌搜索,这势必大大加快搜索的速度,使之能够更有效地搜索最优解

12、.集中性搜索和多样性搜索是禁忌搜索算法中的两个重要策略,以往的算法只是从一个初始解出发进行搜索,虽然在一定程度上保证了集中性搜索,但是在多样性方面往往显得不足.SEQTS算法从多个初始解出发进行搜索,既保证了搜索的集中性,同时又兼顾了搜索的多样性.该算法的直观意义在于,优先处理使用旧颜色(目前已用过至少一次的颜色)着色容易发生冲突的顶点,且在着色时尽可能使用旧颜色,使着色数k尽量变小.2.2SEQTS算法步骤第1步随机生成需要对顶点着色的相关图,得出生成图的关联矩阵NodeMatrix,用SEQ算法得出多个着色的可行方案,将每个可行的着色方案作为并行禁忌搜索的初始解InitValue,可获得图

13、着色所需的颜色数PanK及各顶点的着色值g_aiNodeValue.第2步while(PaaK-一);初始化禁忌表,设禁忌长度Tabu,=7,禁忌表置空TabuList=,并将第1步中得出已知图的一种可行的顶点着色方案作为禁忌搜索的当前最优解NowBesto第3步设禁忌搜索解的次数MaxCount=0,如果当前解NowBest对应的搜索次数满足MaxCount<5(当k值减小后执行5步以内的搜索,所有的解都不满足,()=0时),则MaxCount+,继续以下步骤;否则,输出结果NowBest,算法停止.第4步对于候选解集中的最好解AeraBest,判断其是否满足特赦准则(其值优于

14、当前解对应的k值).如果满足,更新特赦准则(候选解集中最好的解从禁忌表中解禁),更新当前解NowBest=AeraBest,转第6步;否则继续以下步骤.第5步选择候选解集中不被禁忌的最好解更新为当前解NowBest,转第2步.第6步更新禁忌表TabuList-AeraBest,TabuLt.第2期马艳萍等:解决图着色问题的一种新禁忌搜索算法281第7步转第3步.3实验仿真及分析为了证明此算法的普遍适用性,在本实验室中在Windows操作系统中,采用Pentium(R)DualCoreCPU,内存为2GB配置的计算机,在VC+6.0软件开发环境下,用c语言随机产生图顶点数据,其生成语句如下:fo

15、r(iLineLoop=0:iLineLoop<g_iNodeNum:+iLineLoop)g_ppaiNodeConnetiLineLoopiLineLoop=0;for(iColLoop=iLineLoop+1;iColLoop<g_iNodeNum;+iColLoop)iRandNum=rand();iRandNum=iRandNum%2:g_ppaiNodeConnetiLineLoopiColLoop=iRandNum;g_ppaiNodeConnetiColLoopiLineLoop=iRandNum;其中顶点个数为giNodeNum,生成由0,1构成的

16、边密集度为50%,规模为giNodeNum×g_iNodeNum的对称矩阵,并以此作为无向图的邻接矩阵,图中的边集为均匀分布.对新提出的SEQTS算法,本文中针对传统禁忌搜索解决图着色问题的缺点进行改进,实验运用增强SEQ算法作为禁忌算法初始解的产生方式,使算法的初始解得到优化,并且在一定程度上实现了禁忌搜索算法并行搜索的能力,从而使算法的执行速度大大提高.以下是当g_iNodeNum为200,100,50时通过对新提出的禁忌搜索算法分别进行的仿真实验结果.其中,运用新禁忌搜索算法(SEQTS)对不同顶点规模的图进行仿真实验得到结果如表1,表2,表3,分别描述了g_iNodeNum=

17、200,100,50时k值变化与新SEQTS算法运行时长的仿真结果表,如表1,表2和表3所示.表l顶点数目H=50时对应的值变化及运行时长运行次数1234567891Ok值13131412l31214l31214时长(ms)406421421422437438406468421421表2顶点数目,l=100时对应的k值变化及运行时长运行次数12345678910值202122232222212O2021时长(ms)1203l187l1871203ll88l140l203l2031141l17l表3顶点数目,l=200时对应的k值变化及运行时长运行次数12345678910k值323537363

18、63536343637时长(ms)129843641548536563610370336563640361036254结语点数目为50,100时平均所需色数为13,22,且实验所得解的目标约束函数值都为0(说明所得解为可行解).与传统的禁忌搜索算法相比较说明,新提出的SEQTS算法与传统禁忌搜索算法对同等规模大小的图顶点着色的色数相当,但是运行时间却明显比传统的禁忌搜索算法要快得多,提高了搜索效率.本文对基于禁忌搜索算法的平面图的顶点着色问题进行了深入的研究,详细分析了图着色问题与增强SEQ算法的优点,并进一步确定禁忌搜索算法的缺点,进而提出了一种新的解决方案,克服了普通禁忌搜索算法对初始解的

19、依赖及串行运行的不足,从而大大提高了算法效率,并对普通算法思想与新提出的SEQTS算法分别做了仿真实验,实验结果证明新提出的SEQTS算法更有效.由于禁忌搜索算法有广泛的应用领域,以本文中提出的新禁忌搜索算法为鉴,利用其它智能算法与禁忌搜索算法结合来解决组合优化问题及NP难问题,可以很灵活地获取禁忌搜索的初始解,同时消除禁忌搜索算法对问题的依赖性.参考文献1邢文训,谢金星.现代优化计算方法M.北京:清华大学出版社,1999:5289.2汪定伟,王俊伟,王洪峰,等.智能优化方法M.北京:高等教育出版社,2007.3贺一.禁忌搜索及其并行化研究D.重庆:西南大学,2006.4韩丽萍,王宇平,兰绍江.基于有序划分编码的图着色算法J.电子,2010,38(1).5廖飞雄,马良,王攀.一种改进的禁忌搜索算法求解背包问题J.计算机应用与软件,2009,26(3).6张文化,刘素华,候惠芳.一种用于特征选择的禁忌搜索算法J.计算机应用与软件,2010,27(5).7武妍,周欣.一种适应于求解TSP问题的改进的禁忌搜索算法J.计算机工程与应用,2008,44(1).8王淑玲,李振涛,邢棉.一种优化神经网络的遗传禁忌算法J.计算机应用,2007,27(