基于蚁群遗传算法的最小图着色数研究

摘要

图着色问题由最初的“四色猜想”问题引申而来，研究者们不断将其应用于解决各类实际问题，包括频道分配问题、任务调度问题、停机位分配问题等组合优化问题。虽然图着色问题的应用范围非常之广，但是确定图的着色数却是一个十分困难的事情。关于图着色的算法研究非常之多，大体分为精确算法和近似算法。精确算法借助严格的数学方法来获得最精确最优解，但其复杂度相当高，因此只能把它当作一种理想的求解算法而一般不应用于实际求解。近似算法凭借其快速搜索的性能而获得问题的更优解，在问题研究领域中得到广泛应用。
　　目前关于图着色问题的近似算法求解方法很多，而遗传算法和蚁群算法作为最具代表的两种算法，在图着色问题上得到不断应用和改进。遗传算法由于自身具有的特性（自组织、自适应性、全局收敛性等特点），因此能够寻求更优解。但是由于其复杂的结构设计（包括编码方式、适应度函数的设定、遗传算子的设定），微小的设计偏差都会影响算法求解的结果。因此针对图着色这一特殊问题，提出了合适的编码方式和采用特殊的遗传算子—换位算子、切断算子、拼接算子等;借助符号编码方式来很好的描述问题的约束条件;借助换位算子来保证下一代群体始终向着更优解的方向搜索，加快收敛到最优解的速度;借助切断算子和拼接算子为染色体种群的多样性发展提供了更多可能。
　　在使用改进的遗传算法求解图着色问题时，虽然比传统的遗传算法的收敛速度更快，但是其初始群体比较单一，为了减少初始种群的个数从而达到求解更优解的目的，提出用一种算法的搜索结果作为改进遗传算法的初始解。由于贪心算法实现简单，寻优度不高;禁忌搜索算法本身也是对初始群体依赖性较大，也不适于解决改进遗传算法所要解决的问题;模拟退火算法虽避免了对初值的依赖性，但是求解结果并不能方便的转换为传统遗传算法的初始解结构。蚁群算法具有局部收敛性，能准确的描述图着色问题的约束条件，并且所求解的结果能很方便的转换为传统遗传算法的初始解结构，因此更适合于进行初始化搜索。
　　本文首先介绍了传统遗传算法的设计及其用于求解图着色问题时存在的缺陷，针对图着色问题的特殊性，根据遗传算法的编码方式和特殊算子，提出了改进的遗传算法模型，即编码方式采用符号编码，而遗传算子的设计则采用基因换位算子、拼接算子、切断算子来取代原来的交叉算子，使求解过程始终朝着更优的方向发展，加快了收敛速度。然后针对改进遗传算法的求解模型存在的初始群体单一性问题，提出了用蚁群搜索算法为其提供初始解的思想。最后总体介绍了融合算法的求解过程，并用Matlab工具对标准着色算例的图和大量随机生成的图进行仿真实验，实验结果证明了本文提出的算法的有效性。

目录

声明

摘要

第一章 绪论

1．1 选题背景

1．2 相关算法研究现状

1．2．1 遗传算法研究现状

1．2．2 蚁群算法研究现状

1．3 本文主要内容和组织结构

1．3．1 本文主要内容

1．3．2 论文的组织结构

1．4 本章总结

第二章 图着色理论

2．1 图着色理论

2．2 图着色方法现状

2．2．1 精确算法

2．2．2 近似算法

2．2．3 已有的改进算法

2．3 图着色的几个应用模型的建立

2．3．1 考试安排问题的图着色模型建立

2．3．2 电视频道分配问题的图着色模型建立

2．3．3 化学药品贮藏问题的图着色模型建立

2．3．4 N皇后问题的图着色模型建立

2．4 本章小结

第三章 基于遗传算法的图着色问题

3．1 传统遗传算法

3．1．1 遗传算法概述

3．1．2 遗传算法的设计

3．1．3 传统遗传算法的优缺点

3．2 遗传算法的编码方式和特殊算子

3．2．1 遗传算法的编码方式

3．2．2 遗传算法的特殊算子

3．3 基于传统遗传算法的图着色问题研究

3．4 基于改进遗传算法的图着色问题研究

3．4．1 符号编码方式

3．4．2 特殊遗传算子

3．4．3 改进的遗传算法模型的实现

3．5 实验及分析

3．6 本章小结

第四章 基于蚁群算法的图着色问题

4．1 传统遗传算法

4．1．1 蚁群算法的基本思想

4．1．2 蚁群算法的实现

4．1．3 蚁群算法的优缺点

4．1．4 蚁群算法的应用研究

4．2 基于蚁群算法的图着色问题研究

4．2．1 相关参数定义

4．2．2 算法过程描述

4．3 本章小节

第五章 基于蚁群遗传融合算法的图着色问题

5．1 蚁群遗传算法融合的基本思想

5．2 融合算法的具体实现

5．2．1 算法基本步骤

5．2．2 算法的实现

5．3 实验介绍与分析

5．3．1 境与数据

5．3．2 实验评价指标

5．3．3 果与分析

5．4 本章小结

第六章 总结与展望

6．1 工作总结

6．2 研究展望

参考文献

致谢

攻读硕士学位期间发表的学术论文目录