基于粒子群算法的图染色理论及应用

论文总字数：20748字

目 录

1 引言 1

1.1 研究目的和意义 1

1.2 国内外研究现状 1

1.2.1 图染色问题研究现状 1

1.2.2 粒子群算法研究现状 2

1.3 本文内容及结构 2

2 图染色问题和粒子群算法简介 3

2.1 图染色问题 3

2.1.1 基本概念 3

2.1.2 图染色问题的意义及其应用 3

2.1.3 图染色问题的常见求解算法 4

2.2 粒子群算法 4

2.2.1 粒子群算法的原理 4

2.2.2 粒子群算法的形式化描述 4

2.2.3 粒子群算法的流程 5

3 基于粒子群算法的图染色问题 6

3.1 图染色问题描述 6

3.2 编码方式 7

3.3 适应度函数的设计 7

3.4 初始化及参数确定 8

3.5 求解图染色问题的粒子群算法 9

3.5.1 算法步骤 9

3.5.2 算法流程图 9

3.6 合法化过程 9

4 结果与分析 14

4.1 实例 14

4.2 结果分析 17

5 总结与展望 17

5.1 总结 17

5.2 展望 18

参考文献 19

致谢 20

基于粒子群算法的图染色理论及应用

纪晓捷

,China

Abstract: Graph coloring problem is a classical research object in combinatorial mathematics. It is infeasible to find the best coloring scheme for general graphs because of the difficulty of NP, therefore, it is necessary to design polynomial time algorithms to give the approximate optimal solution of the problem. Some researchers have proposed solutions based on local search, genetic algorithm and so on. Particle swarm optimization is rarely mentioned in this problem, so we design a general algorithm based on particle swarm optimization to solve graph coloring problem.

In this paper, we introduce the research status of graph coloring problem and PSO. Then,we design the particle coding scheme and the fitness function. Finally, we propose particle legalization process based on greedy method. The results show that PSO can also solve the problem of graph coloring. At the same time, PSO can be a new choice for solving graph coloring problem because of its learning mechanism.

Key words: Graph coloring problem; Particle swarm optimization; Legalization process

1 引言

1.1 研究目的和意义

在我们的生活中，组合优化问题扮演着非常重要的角色，无论是科学、经济，还是工程应用，在很多领域我们都能看到它的身影。

图染色问题简单地说就是将给定图的顶点或者边等等这些元素根据某些规则分为不同的类别进行染色，染色方案也是多种多样的，除了我们熟知的顶点染色、边染色，还有完备染色等[1]。现实生活中，很多问题都涉及到类似思想，例如考试安排问题、物品储存问题、学生选课系统设计等等，它们都能转变为图染色问题。如物品储存问题：我们现在需要将个物品进行装箱，但是有些物品不能放在同一个箱子里，否则物品将会被损坏，那么储存这个物品至少需要几个箱子?转换为图染色问题，它相当于给定一个有着个顶点的平面图，若物品相排斥就给这两个顶点之间画一条线，代表它们相邻，现在我们要给这个顶点进行染色，相邻顶点必须染不同颜色，那么将所有顶点全部染色需要的最小颜色数即所需的箱子数。其它问题类似，都可这样转换。

众所周知，图染色问题的求解是颇具挑战性的。特别是当问题规模较大时，计算量也会相应增加，这时，如果有一个运行速度更快、效率更高的算法出现，我们的工作量将大大降低。为此越来越多人加入到寻找新算法的队伍中。最终经过大家的努力，粒子群算法诞生了。

粒子群算法是从模仿大自然中动物的行为逐渐发展成熟起来的[2]。粒子群算法是以鸟群捕食行为模拟为基础而提出的，鸟之间共同合作、及时分享所得信息，从而使整个鸟群都趋于食物，这就是最优的情况。它作为一个新型算法，因为具有快速性和易实现性在提出之后就受到了大家广泛的关注，在函数优化、模式分类、神经网络训练、机器人应用、模糊系统控制等各个领域备受欢迎。但是目前有关粒子群算法理论上的研究还很少，没有能够充分地发挥自身优势应用于求解生活中的问题，仍有许多问题亟待解决。因此，对粒子群算法的研究很有意义。

虽然求解图染色问题的算法很多，但遗憾的是:涉及到粒子群算法的文献资料却寥寥无几，所以我们可以尝试着将粒子群算法应用于求解图染色问题。

1.2 国内外研究现状

1.2.1 图染色问题研究现状

对图染色问题的研究，从1852年至今已经有了160多年的历史。Guthrie通过对地图染色的研究而意识到四色猜想，这个猜想一经提出便引发了大家的热议，直观上来说，这个猜想是无可非议的，但是当人们尝试结合数学知识给出严谨的证明时却发现困难重重。在1976年，美国的两名数学家 Appel和 Haken[3]尝试着验证它，最终经过成千上万次的逻辑判断，借助了三台计算机共同运作，耗时近1200小时终于得出结果，难题得以解决，“四色定理”也随之诞生。

在图染色问题发展演变的过程当中，如何快速地求解出问题的答案成为了当务之急，越来越多人加入到寻找求解算法的队伍中来。当然求解图染色问题的算法也在不断的更新当中，我们做一个简单的分类：

第一类是直接启发式算法，例如文献[4] 中D.de Werra提出的增强SEQ算法和文献[5]中D.Brelaz提出的的DSATUR算法。增强SEQ算法，将给定图的顶点根据度数递减的顺序排列，依次染色。当一个顶点被染色之后，就把这个点和它所有的邻点组成的子图从给定图中删除，这时候剩下的顶点都会有一个新的度数。在完成所有顶点的染色之前反复做上面的步骤。最后在染色过程中所使用的颜色的最大编号就是给这个图染色所需要的颜色数；DSATUR算法，用当前可选择的编号最小的颜色对邻域内已经使用最多颜色的顶点优先染色,直到给定图的所有顶点都染上颜色。

第二类是元启发式算法，它们在启发式算法的基础上作出了改进，如神经网络算法[6]、禁忌搜索算法[7]、遗传算法[8]等。神经网络算法通过模拟神经网络的布局，将染色问题与之对应，当神经网络消耗能量最少并且趋于稳定的状态也就是图染色问题的解达到最优的状态；禁忌搜索算法将禁忌搜索算法的初始搜索空间与图染色的初始解空间对应起来，给出算法参数的设定方法，结合图染色问题中需要注意的约束条件进行求解；而遗传算法充分利用遗传算法可以在高维空间进行寻优的优势，在允许的范围内可以寻找到合适的解，在算法中结合贪心策略，来弥补算法搜索能力。

第三类是基于生物计算的智能算法，如DNA算法[9]，通过模拟生物学中的DNA模型，将顶点染色与DNA分子链进行对应，在生物反应的过程当中，调整分子链的排列方式，当所需循环次数最小时也就是染色最优的情况。

1.2.2 粒子群算法研究现状

粒子群算法作为一种相对较新颖的进化算法，已经在很多领域被广泛使用，文献[10]-[13]中分别介绍了它在配对测试、交互试验等方面的应用。

粒子群算法还可以结合混合蛙跳算法、小波分析的概念还有神经网络的一些理论，给出基于混沌序列和反向学习机制的量子粒子群概念以及相应的算法来应用于电磁学[14]以及工程设计与优化、电力系统、机器人控制[15]等领域。

粒子群算法中有一些参数在算法执行前需要进行设定，具体的规则详见文献[16]。

1.3 本文内容及结构

本文在求解图染色问题的过程中有建设性地加入了粒子群算法的思想，借助粒子群算法的迭代来不断更新当前的染色情况，同时还要对迭代过程中出现的不合法解及时合法化。

第一章是引言，概述性地介绍了研究图染色问题和粒子群算法的目的、意义以及当前它们的研究现状，并对本文的内容和框架进行粗略地罗列；

第二章给出图染色和粒子群算法的一些概念，对粒子群算法的原理和算法流程等作详细解释；

第三章结合前面的一些理论知识具体地给出了求解图染色问题的粒子群算法，设计出有针对性的编码方式以及适应度函数，给出合法化的方法并做详细的解释；

第四章结合具体的实例对求解图染色问题的粒子群算法进行验证，并结合实际进行分析，总结该算法的优缺点；

第五章先对本文做了一个系统的分析总结，然后对接下来我们需要在图染色和粒子群算法这两个方面的研究工作进行了展望。

2 图染色问题和粒子群算法简介

剩余内容已隐藏，请支付后下载全文，论文总字数：20748字

相关图片展示：