基于多目标优化的图的强可区别染色算法研究

摘要

图论中的一个经典难题——图染色问题，属于图论的一个分支，也是科学计算与工程设计中的基本问题。现实世界中有很多问题都可以转化为图的问题来解决，例如比赛安排问题、网络通信问题、排课表问题、物资存储问题、无线通讯频道分配，印刷电路板设计及变址寄存器数目分配等等，这些问题的解决都涉及到图的染色理论，所以染色问题是图论中极具研究意义的领域之一。随着现实世界中交通运输、计算机网络通信、军事、生产管理等实际问题需求的发展，以及经典智能优化算法所存在的不足以及局限性的演变，我们对快速而准确地实现染色结果并将其应用于实际的需求也逐步增大。
　　图的强可区别染色问题是一种多条件约束染色，是在可区别全染色的基础之上再增加约束条件，使得色集合的包含元素更多，共包括两种染色概念:邻点强可区别全染色、点强可区别全染色。目前在已公开发表的文献中对强可区别全染色的研究仅局限于圈图、轮图、完全图、树等特殊图，而对于一般随机图的强可区别染色研究尚无可行的解决方法。本文结合多目标优化的研究思想，设计了基于多目标优化的强可区别染色算法，算法通过设定多个子目标函数逐步寻优，使其最终的目标函数得到Pareto最优解，实现局部最优化到整体最优化的过程。同时文中还设计实现了有限点以内所有生成树算法以及所有简单连通图生成算法，为各类染色算法的研究及结果集测试奠定基础。本文的主要工作如下:
　　(1)介绍了图论以及图染色理论的基本概念、多目标优化问题的相关概念、遗传算法的基本思想以及应用于解决正常边染色的算法执行过程，同时对其优缺点进行分析总结。
　　(2)给出了两类随机图生成算法，第一类是输入顶点数目依照规则随机连边生成随机简单连通图算法;第二类是基于生成树生成有限点数内所有伪非同构图算法，因此第二类算法又包含了生成树算法;两种随机图生成算法为后续一系列染色算法的结果集测试、统计以及相关引理、猜想的证明提供基础研究数据，为各种染色算法的研究奠定良好的基础。
　　(3)设计并实现了基于多目标优化的图的邻点强可区别全染色算法、基于多目标优化的图的点强可区别全染色算法，同时设计了两类正常边染色算法、顶点染色算法、色集合调整算法等一系列子算法。强可区别全染色算法的最终目的是要确保顶点的色集合不同，色集合除了顶点颜色，顶点与其关联边颜色之外还加入了相邻顶点的颜色，所以色集合调整的难度变得更大。所以本文设计了更详细的的强色集调整规则，以及相应的过程评估函数来及时生成新的预染色组，从而更快速地搜索到最优解，在不提高算法时间复杂度的情况下，提高算法的运行效率。
　　(4)测试结果集为7个点以内所有的伪非同构图，15个顶点以内的特殊图、14个顶点以内的所有生成树以及1000个点以内部分随机连通图;并通过大量实验结果集的分析，给出了若干有意义的结论及猜想。

目录

声明

摘要

1 绪论

1．1 引言

1．2 研究背景、目的及意义

1．3 本文的研究内容及组织

2 图染色理论及经典优化算法概述

2．1 引言

2．2 图染色相关理论

2．3 多目标优化概念

2．4 遗传算法解决最优化问题

2．4．1 遗传算法的基本思想

2．4．2 遗传算法在图染色中的应用

2．4．3 遗传算法总结

2．5 本章小结

3 图的两种生成算法

3．1 引言

3．2 随机图的生成算法

3．2．1 随机图定义

3．2．2 算法设计

3．2．3 算法测试

3．2．4 实验结果

3．3 生成树算法

3．3．1 主要数据结构及生成树定义

3．3．2 算法设计

3．3．3 算法测试

3．3．4 实验结果

3．3．5 算法总结

3．4 生成有限点数所有伪非同构图算法

3．4．1 定义主要数据结构

3．4．2 算法设计

3．4．3 算法测试

3．4．4 实验结果

4 基于多目标优化的随机图的邻点强可区别全染色算法

4．1 引言

4．2 邻点强可区别全染色算法

4．2．1 构建多目标优化函数

4．2．2 主要数据结构定义

4．2．3 算法设计

4．2．4 算法流程示例

4．2．5 算法测试与结果分析

4．3 算法分析

4．4 算法总结

5 基于多目标优化的随机图的点强可区别全染色算法

5．1 引言

5．2 点强可区别全染色算法

5．2．1 构建多目标优化函数

5．2．2 算法设计

5．2．3 算法流程示例

5．2．4 算法测试与结果分析

5．3 算法分析

5．4 算法总结

结论

致谢

参考文献

附录

攻读学位期间的研究成果及参加的科研项目