《基于粒子群的图顶点着色算法》由会员分享，可在线阅读，更多相关《基于粒子群的图顶点着色算法（58页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 基于粒子群的图顶点着色算法 姓名：王小琼 申请学位级别：硕士 专业：系统工程 指导教师：许进 20070125 华 中 科 技 大 学 硕 士 学 位 论 文华 中 科 技 大 学 硕 士 学 位 论 文 I 摘摘 要要 组合优化是一个新兴的领域，它与数学最优化一样是运筹学的一个重要组成部 分，而且是偏重应用的数学领域。本文对图与组合优化问题中的一个典型问题，即 图的顶点着色问题进行了研究。图的顶点着色问题是典型的 NP 完全组合问题，在 调度安排、时间表编制等方面有许多应用，构造求图顶点着色问题的近似最优算法 有重要的现实意义。 粒子群算法是一种新的基于群体智能的
2、随机优化算法，同其它的进化算法相比， 其最具吸引人的特征是简单容易实现和更强的全局优化能力。为此，粒子群算法一 经提出，立刻引起了演化计算等领域的学者们的广泛关注，并在短短的几年时间里 出现大量的研究成果，形成了一个研究热点，在函数优化、神经网络训练、工业系 统优化和模糊系统控制等领域得到了广泛的应用。 本文给出了标准粒子群的图顶点着色的算法，设计了图顶点着色问题的编码方 法和适应度函数，确定了粒子群的飞行方式。并通过引入模拟退火算法克服了标准 粒子群陷入局部最优的缺点，提高了粒子群体的搜索性能。随后，通过对粒子群飞 行速度进化方程的本质性的研究，由它的进化特点与遗传算法的相应部分进行类比，
3、设计出了遗传粒子群算法，通过遗传算法中交叉和变异算子的作用，同样的实现了 粒子速度的更新。并且，实验结果证明，这种遗传粒子群算法在图顶点着色问题中 比标准粒子群算法搜索的准确性更好。但是由于遗传算法在收敛速度上的不足，我 们在粒子飞行过程中加入了模拟退火算子，大幅地提高了算法的收敛速度。 关键词：关键词：图的顶点着色；粒子群算法；遗传算法；模拟退火算法 华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract As an emerging research field, combination optimization has become an important compon
4、ent of operation research just as mathematic optimization. Combination optimization emphasizes more on application field compared to other operation research field. This paper researches on graph vertex coloring problem which is a typical combination optimization. Graph vertex coloring problem (GVCP
5、) is a NP-complete problem having good application such as scheduling and timetabling. Therefore, the construction of new approximating optimization algorithm to solve graph vertex coloring problem is of great realistic meaning. Particle swarm optimization (PSO) is a brand-new stochastic computation
6、al technique based on swarm intelligent. The most attractive features of PSO are reduced memory requirement, computationally effective and easier to implement compared to other evolutionary algorithms (GA). For that reason, since been presented, PSO, which has broad applications in function optimiza
7、tion, instruction system optimization, fuzzy system control etc., has gained general attention of different fields especially evolution computing, and gradually becomes a very popular area. In recent years, abundance of good efforts has been obtained. In this paper, we present a particle swarm optim
8、ization algorithm for graph vertex coloring problem, designing GVCP coding method, fitness function and fly mode of swarm. Also, simulated annealing algorithm is added to avoid local optima, which advances the searching performance. Then, a hybrid algorithm is presented by the analysis of velocity e
9、volution mode and the analogy between PSO and GA, which accomplish the update of particle velocity successfully by cross-over operator and mutation operator. Experimental result shows that the hybrid algorithm based on GA has a more accuracy searching ability. In the end a simulated annealing operat
10、or is added to improve the convergence rate. Key Words：Graph vertex coloring; Particle swarm optimization; Genetic algorithm; Simulated annealing 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学
11、位论文作者签名： 日期： 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期：2007 年 1 月 25 日 日期：2007 年 1 月 25 日 本论文属于 华 中 科 技 大 学 硕 士 学 位 论 文
12、1 1 绪绪 论论 1.1 研究目的和意义研究目的和意义 现实生活中，许多问题都可归结为一个由点和线组成的图形的问题。图论就是 研究这些由点和线组成的“图形”问题的一门学科。由于图论在生产生活中有着广 泛的应用，这个学科成为了离散数学中十分活跃的分支。在自然界和人类社会的实 际生活中，用图形来描述某些对象（或事物）之间具有某种特定关系常常感到特别 方便。例如，用工艺流程图来描述某项工程中和工序之间的先后关系，用网络图来 描述某通讯站之间的信息传递关系，用交通图来描述地区内各城市之间的铁路连接 关系，用原理电路图来描述某器件内各元件之间的连接关系，等等。图形中的点表 示对象（如工序、通讯站、城市
13、、元件等） ，两点之间的有向或无向连线表示两对 象之间具有某种特定的关系，这样就可以把要研究的问题抽象为一组点和联接着点 的一组线所构成的图，从而用图论方法使实际问题得到解决。 在图论中，最出名的且持续了很长时间才被解决的问题莫过于四色问题，该问 题起源于一个著名猜想，称为四色猜想，由此而激发了对图着色问题的深入研究。 更重要的，图着色问题受到科学领域内不同学科学者的兴趣和关注还在于其在各个 领域中都有广泛的应用，如： (1)课程考试安排问题：设某一学校有 n 门课程由学生选修。学期终了要进行考 试，当然每个学生每场只能参加一门课程的考试。显然没有共同学生的两门课的考 试可以在同一时间进行。试
14、问这次考试最少要进行几场? 在平面上取 v1,v2,vn ， n 个顶点分别表示这 n 门课程，若有同学同时选了 课程 i 和课程 j，则过 vi 和 vj 两点连一条边，结果得一有 n 个顶点的图G。考试 的安排问题相当于图 G 的顶点着色问题。 着同一颜色的顶点对应的课程可同时进行 考试。使图 G 的相邻顶点有不同颜色的最少颜色数目，便是进行考试的最少场数。 (2)物资储存问题：设有 n 种物资要存放在仓库里，但有的物资不能放在同一房 间里，否则将引起损坏，甚至发生危险。问存放这 n 种物资最少耍几个房间? 华 中 科 技 大 学 硕 士 学 位 论 文 2 和问题(1)相类似，在平面上取
15、 n 个顶点 v1,v2, vn 分别表示 n 这种物资。设 vi 和 vj 为不能放在一起的两种物资， 则过 vi 和 vj 点连一条边， 得一 n 个顶点的图 G。于是问题又变为图 G 的顶点着色问题。 (3)时间表问题：设 x1,x2,xm 为 m 个工作人员，y1,y2,yn 为 n 种设备。设工 作人员 xi 对设备 yj 提出使用要求，使用时间假定均以单位时间计算。自然每一个 工作人员在同一个时间只能使用一种设备，一种设备在同一个时间里只能为一个工 作人员所使用。问应如何合理安排，使得在尽可能短时间里满足工作人员的要求? 问题转化为讨论关于X=x1,x2,xm，Y=y1,y2,yn
16、的二部图G。工作人员要求 使用设备 yj，每一单位时间对应一条从 xi 到 yj 的边，这样所得的二部图过xi、yj 的 边可能不只一条。问题变为对所得的二部图G的边着色问题。有相同颜色的边可以安 排在同一时间里。 由于图着色问题所具有的广泛应用背景以及它的算法复杂度，图着色问题已经 引起了众多学者广泛而深入的研究。图着色问题是一个NP-问题1，NP问题是指不存 在多项式时间优化算法对该问题进行求解，虽然科学家们发展了单纯型法、加权匹 配、拟正交、线性规划等有效算法，但对众多复杂问题仍然没有有效的算法。随着 图的规模的扩大，计算量将会呈指数性增加，即使对于中等规模的问题，也是难以 解决的，如何找到一个高效的算法就成为了解决有关问题的关键和突破点。 另一方面，粒子群算法作为一种新型的基于群智能方法的演化计算，以其快速 性和易实现性受到广泛关注，并应用于函数优化、神经网络权值和网络模型结构优 化、信号处理、机器人应用等各个领域。但是粒子群算法也存在一些不足之处，比
