资源描述：
《图节点着色问题中的禁忌搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图节点着色问题中的禁忌搜索算法09-03-25作者： 编辑：校方人员图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有
2、效的应用于一些典型NP问题，如TSP。但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。1图节点着色问题图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的一种是节点着色。节点着色问题可描述如下： 给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接
3、(i,j)的一条边。若，且Vi内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,Vn)为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,Vn)为V的一个划分。例1.1：如图1.1所示，6节点的无向图G=(V,E)，其中一种着色方案：V1={C,E,F},V2={A},V3={B,D}通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算
4、法和贪婪算法。Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。2禁忌搜索算法的设计禁忌搜索是对局部领域搜索的扩展。传统局部邻域搜索是基于贪婪思想在当前解的邻域中进行搜索，搜索性能完全依赖于邻域结构
5、和初始解的选取，搜索结果容易陷入局部极小而无法保证全局最优。而禁忌搜索从一个初始可行解s开始，通过变换得解的邻域函数V(s)，按照某种选择策略从中选取一个解s*，从s移动到s*，把s*作为一个新解，重新叠代搜索，直到满足退出机制。为避免循环和陷入局部最优，禁忌搜索使用禁忌表记录已经到达的局部最优点，也即最近进行的移动状态。在下一步的搜索中利用规定的禁忌规则，在一定搜索次数内不允许选择这些已被禁的搜索点，从而可以跳出局部最优的限制。2.1解的数据结构为了数据结构的简化，我们设顶点集合为有序，1,2,…n各代表一个顶点，如例子中的顶点ABC
6、DEF分别编号为1,2,…n。对于颜色集C，用C={1,2,…m}来表示。这样便可用一个行向量来作为解的数据结构，其中下标1,2,…n依次代表各个顶点，向量中下标对应的分量对应所着色，着色相同的即在同一划分集Vi。如例子的解可表示为：s=[231311]，共3种颜色。2.2领域的选择首先确定解的变化形式。一般而言，变化形式分为解的简单变化、向量分量的变化和目标值的变化[3]。鉴于解的数据结构，采用分量变化形式，即对于顶点i，其颜色值从s[i]变为j，其中j属于颜色集C。对于领域，每一个解s的领居由那些满足上面的变化且只有一个分量变化的解
7、组成，每一个分量可以选择m个颜色中的一个，那么对每一个解，共有n*(m-1)个邻居。例如，对于例子中的解s=[231311]，它的一些领居为s1=[131311],s2=[331311],s3=[211311],s4=[221311]等。解的领域即为所有这些邻居组成的集合。2.3目标函数的选择和候选集的构造对于图节点着色问题，目标函数的构造是一个难点。由图论的知识，对一个正常点着色，各个顶点与其相邻的顶点所着颜色不同，即各个顶点同与之有边相连的顶点不在同一个划分集Vi中，则：E(V1)+E(V2)+…+E(Vn)=0，其中E(Vi)表示
8、顶点集Vi中包含的边数。那么选取目标函数为：f(s)=E(V1)+E(V2)+…+E(Vn)，对于那些非正常点着色的不可行解，f(s)>0。在进行禁忌搜索时，每次从领域中以目标函数值最小为依据来选取解。在禁
