基于遗传和启发式算法的混合顶点着色算法.pdfVIP

第 29卷 第 5期 吉首大学学报 (自然科学版) V0l_29 No．5 2008年 9月 JournalofJishouUniversity(NaturalScienceEdition) Sept．2008 文章编号：1007—2985(2008)05—0057—04 基于遗传和启发式算法的混合顶点着色算法 廖辉传 (华东交通大学信息工程学院，江西 南 昌 330013) 摘 要：图的着色问题是一种典型的NP一完全 问题．提出了基于遗传算法和启发式算法的新型混合顶点着色算法，该 算法在实现过程中涉及到染色体的编码方法、适应度函数的设计 以及遗传算子的选择等．实验仿真结果表明此算法改善了 求解的时间复杂度 ，可以获得 问题高质量的解． 关键词 ：图的着色；启发式算法 ；遗传算法 ；时间复杂度 中图分类号 ：TP311．1；O157．5 文献标识码 ：A 图的着色问题是现代 图论在离散数学中的一个最主要 的课题之一，无论在理论上还是工程应用上均有 良好 的应用背 景，诸如 电路布线问题、工序 问题、排课表 问题 以及存储 问题 ，均有直接 的应用．然而 ，无论是求解一个 图G的色数c(G)的算 法，还是对一个给定图G进行正常k一顶点着色算法、正常k一边着色算法 以及正常k一全着色算法，都是NP一完全问题． 因此，当图G的顶点数较大时，用常规的方法很难得到图的正常k一顶点、正常k一边 以及全着色．于是，人们设想寻求其他 途径 以求得这些问题的算法．不管是从事数学研究的图论学者 ，还是从事 电路与系统等工程技术方面研究的图论学者，或 是其他领域内的科学家 ，对图的着色问题都表示 了极大的关注与兴趣 ．_1 近年来迅速发展起来的遗传算法是一种全局优化方法，该方法依照生物学中的 “优胜劣汰，适者生存”的原理，提供了 一 种强大的快速有哪些信誉好的足球投注网站能力，能够快速有哪些信誉好的足球投注网站到问题的最优解或近似最优解．[5-6]自从遗传算法提出后，有许多的NP一完全问 题得到了解决，如最小生成树问题、TSP问题、作业调度问题等．因此，笔者将 以遗传算法为主要研究内容，并尝试将遗传算 法应用于图的着色问题 中，在使用遗传算法 的过程 中，并结合启发式算法对种群 中的染色体进行着色． 1 启发式着色算法 启发式着色算法是一种具有线性计算复杂度 的启发式着色算法 ，在应用启发 式着色算法 的着色进行求解时，须指定一个顶点序列．该算法 的着色过程是用编上 号的颜色，按照给出的顶点排列顺序 ，逐点为每个顶点着编号尽可能小的颜色．对 于图的每一种顶点排列顺序，都可以用启发式着色算法得到一个确定的着色方案． 首先对每个点的颜色序号进行赋值，初始的时候将他们的颜色序号为 0，表示 尚未 着色．然后从颜色序号 1开始，按顶点排列顺序依次判断每个顶点是否可着颜色 1 (1个点着色颜色序号与它相邻 的所有点颜色序号是不能相同的)．颜色 1着色完 5 6 7 成后 ，选择颜色 2继续对满足条件 的顶点着色，以次类推．着色过程 中若某顶点的 图 1 着色示例 图 颜色序号不为 0时表示 已着色，不用再判断．如在 图 1中，按顶点顺序 1—2—3— 4—5—6—7进行着色时，顶点 1—3—5—7可着色颜色 1，顶点 2—4着色颜色 2，顶点 6着色颜色 3．因此 ，在该顶点序列中， 可用 3种颜色对该 图着色． 启发式着色算法具体描述如下： * 收稿 日期 ：2008—08—11 基金项 目：华东交通大学科研基金资助项 目(07XX01) 作者简介：廖辉传(1973--)，男，江西万载人，华东交通大学信息工程学院讲师，硕士，主要从事图论、算法设计与分 析研究． 58 吉首大学学报 (自然科学版) 第 29卷 functionColor { { 遍历所有节点，找出颜色 k所能着色的节点，即如果