图节点着色问题中的禁忌搜索算法

1图节点着色问题中的禁忌搜索算法龙非池(电子科技大学通信与信息工程学院成都610054)【摘要】本文针对图节点着色问题，提出了基于禁忌搜索的优化算法设计方案，能够跳出局部极小点，实现全局最优化。并提出禁忌搜索算法能较好的用于一般算法较难实现的着色问题的推广问题List着色。通过实验仿真，验证了算法的高效性和可靠性。【关键词】节点着色List着色全局优化禁忌搜索AlgorithmofGraphColoringBasedonTabuSearchLONGFei-chi(CollegeofCommunicationandInformationEngineering,Chengdu,610054)AbstractThispaperbringsforwardanalgorithmbasedontaboosearchtomeetgraphcoloringproblem.Thisalgorithmcanenlargethesearchspaceandimplementtheglobaloptimization.Itisprovedthatthealgorithmoftaboosearchcanbeeffectivelyimplementedintheproblemoflistcoloring.Theresultsofsimulationshowthehighefficiencyandreliabilityofthealgorithm.KeywordsGraphcoloringlistcoloringoveralloptimizationtabusearch1引言图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题[3]。目前解决该问题的算法很多[6]，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性[4]。禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP[5]。但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。2图节点着色问题图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的一种是节点着色。节点着色问题可描述如下：给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集{(,)|,}EijijV，其中(i,j)表示有连接(i,j)的一条边。若,(),iijiVVVVijVV，且Vi内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…Vn)为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,Vn)为V的一个划分。以6节点的无向图G=(V,E)为例，如图1所示，其中的一种着色方案为：V1={C,E,F},V2={A},【作者简介】龙非池(1987-)男，通信与信息工程学院通信工程专业2005级本科生，曾获2006电子科技大学高等数学竞赛特等奖、2007电子科技大学数学建模竞赛一等奖V3={B,D}图1.16节点图的着色AEFDCB211313图16节点图的着色通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。Welsh-Powell算法只能保证最多使用1(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。3禁忌搜索算法的设计禁忌搜索是对局部领域搜索的扩展。传统局部邻域搜索是基于贪婪思想在当前解的邻域中进行搜索，搜索性能完全依赖于邻域结构和初始解的选取，搜索结果容易陷入局部极小而无法保证全局最优[4]。而禁忌搜索从一个初始可行解s开始，通过变换得解的邻域函数V(s)，按照某种选择策略从中选取一个解s*，从s移动到s*，把s*作为一个新解，重新叠代搜索，直到满足退出机制。为避免循环和陷入局部最优，禁忌搜索使用禁忌表记录已经到达的局部最优点，也即最近进行的移动状态。在下一步的搜索中利用规定的禁忌规则，在一定搜索次数内不允许选择这些已被禁的搜索点，从而可以跳出局部最优的限制[3]。3.1解的数据结构为了数据结构的简化，我们设顶点集合为有序，1,2,…n各代表一个顶点，如例子中的顶点ABCDEF分别编号为1,2,…n。对于颜色集C，用C={1,2,…m}来表示。这样便可用一个行向量来作为解的数据结构，其中下标1,2,…n依次代表各个顶点，向量中下标对应的分量对应所着色，着色相同的即在同一划分集Vi。如例子的解可表示为：s=[231311]，共3种颜色。3.2领域的选择首先确定解的变化形式。一般而言，变化形式分为解的简单变化、向量分量的变化和目标值的变化[3]。鉴于解的数据结构，采用分量变化形式，即对于顶点i，其颜色值从s[i]变为j，其中j属于颜色集C。对于领域，每一个解s的领居由那些满足上面的变化且只有一个分量变化的解组成，每一个分量可以选择m个颜色中的一个，那么对每一个解，共有n×(m-1)个邻居。例如，对于例子中的解s=[231311]，它的一些领居为s1=[131311],s2=[331311],s3=[211311],s4=[221311]等。解的领域即为所有这些邻居组成的集合。3.3目标函数的选择和候选集的构造对于图节点着色问题，目标函数的构造是一个难点。由图论的知识，对一个正常点着色，各个顶点与其相邻的顶点所着颜色不同，即各个顶点同与之有边相连的顶点不在同一个划分集Vi中，则：E(V1)+E(V2)+…+E(Vn)=0，其中E(Vi)表示顶点集Vi中包含的边数。那么选取目标函数为：f(s)=E(V1)+E(V2)+…+E(Vn)，对于那些非正常点着色的不可行解，f(s)0。在进行禁忌搜索时，每次从领域中以目标函数值最小为依据来选取解。在禁忌搜索完毕时，给出目标函数值最小的解，若为0则得到一个正常点着色方案，若不为0，我们亦可以得到一个较好的方案，这也是用禁忌搜索来解决着色问题的优点之一。实际编程中还要设置候选集，以便从中选取下一个最优解。鉴于解的形式和目标函数，可用(n×(m-1))×(n+1)的矩阵来表示，其每行表示解的一个邻居和其对应的目标函数值。3.4禁忌表和特赦规则的构造禁忌表的构造和特赦规则的选取通常是禁忌搜索算法的难点，这也是禁忌搜索算法运用于通信系统中时的一个瓶颈。首先，禁忌对象的选择通常也有三种形式：解的简单变化、分量对换的变化和目标值的变化。由于简单变化的禁忌对象太少，计算时间过多，而目标值变化的对象过多，难以得到全局最优，故选择分量对换。那么禁忌表设为L×3的矩阵，其第一列储存分量所在下标i，对应图中的某点，第二列储存此点的颜色，即s[i]，第三列储存用来交换的颜色j。对于禁忌表长度，鉴于此参数较难设置，我们用经验式L=sqrt(n×(m-1))，在实际运用时可以通过实验来比较选取该值。对于特赦规则，其设置的好坏直接影响进行全局最优化时的效果。考虑当前解s对应的候选集中的最优解s*，若它被禁而同时它对应的目标函数值满足f(s)f(s*)，那么我们有理由将它特赦，因为直观上理解，我们会得到更好的解。3.5算法终止原则设置两目标值无改进的最大允许迭代次数k_max和目标值下界fl来保证算法的有穷性。3.6算法实现的框架3.6.1主函数的设计设计好算法后，现在不难给出算法的设计框架。在具体编程时，把一些功能放到外部函数中实现，只在主函数中留出接口。下面是主函数的框架,使用的是MATLAB的伪代码。初始化：a，m，n为a的维数；%图的邻接矩阵、颜色数、顶点个数k，best_k，k_max，fl；%迭代步数、最优解所在步、最大允许迭代数、下界L=n×m0.5取整，h=zeros(L,3)；%禁忌表的设置s=ones(1,n)，s_best=s，s_now=s，best；%形式、最优解、当前解、最终解V=zeros(1,n+1)，A=f(s_now)-1；%候选集、特赦值、f为目标函数开始：当f(s_now)fl且(k-best_kk_max)时，计算k=k+1；%迭代步数增加生成s_now的候选集V，其中的元素s是非禁忌或者特赦f(s)A在V中选择使目标函数值最小的解s_best若f(s_best)A，则A=f(s_best)-1，否则，A=f(s_now)-1；%更新特赦值若h未满，将对应的交换加入下一行，否则，覆盖第一行；%更新禁忌表若f(s_best)best，则best=s_best，best_k=k；%更新全局变量s_now=s_best；继续。结束3.6.2候选集生成函数的设计初始化：r=1；%候选集矩阵的行下标循环：i=1:n，j=[1:s_now(i)s_now(i+1):m]temp=s_now，temp(i)=j；%临时变量，储存当前解change=[i,s_now(i),j]；%对换的变化方式若禁忌表中没有一行和change相同或者是特赦f(temp)=AV(r,1:n)=temp，V(r,n+1)=f(temp)；%前n行储存解最后一行储存目标值r=r+1；end%增加迭代次数，继续4图节点着色问题的特例-List着色对一般着色，每个顶点都可从颜色集C中选取任一个颜色，而当限制了每个顶点专属的颜色集时，称为List着色[1]。图4.1图的List着色x1xyyx2123{1,2}{2,3}{1,3}{1,2}{2,3}图2图的List着色如图2所示，两组化学物品，X={x1,x2,x3}，Y={y1,y2}，不同组的物品不能放在一起。现将两组物品放于1、2、3三个仓库，且限制x1和y1只能放在1、2号仓库、x2和y2只能放在2、3号仓库，x3只能放在1、3号仓库，则怎样安排物品的存放？图论中的定理指出，对任意存在List着色的图，其所需颜色数在区间[+1]内。对于List着色，针对此问题的算法在各个文献中不多见。通过上面讨论的禁忌搜索算法的设计，我们可以看出，只改变领域的构造规则，便可以简单的实现List着色。具体实现是对每个顶点只选取那些变换，其变换后的颜色仍然存在于自己的颜色集中，而其他所有步骤同一般着色问题。对于上诉问题的解s=[13122](其解的下标依次对应于点x1、x2、x3、y1、y2所着颜色)，其领居选择为s1=[23122],s2=[12122],s3=[13322],s4=[13112]和s5=[13123]。由此可见，对禁忌搜索算法扩展，只变换领域的选择就能够较好的实现List着色，当不存在正常的List着色时，算法给出使目标函数值最小的着色方案，这是一般的算法难以媲美的。5算法的仿真实验由于禁忌搜索算法属于启发式算法，其性能分析一般较为复杂，我们采取大规模计算分析方法。用MATLAB随机产生实例的语句为：a=rand(n)/2(先产生[00.5]范围内的n×n矩阵)；a=round(a+a’)，则a最后表示随机生成的一个无向图的邻接矩阵，图中的边集为均匀分布。我们设置n=50或n=100，即随机产生有50或100个节点的无向图。则用MATLAB语言，