求解图着色问题的混合遗传算法

论文摘要

遗传算法是模拟自然界生物进化过程与机制来求解优化问题的一类自组织、自适应的随机搜索算法,其编码技术和遗传操作比较简单,对优化问题的限制性条件要求很低,具有很强的并行性和全局搜索能力。它能解决很多类实际问题,目前已经在机器学习、模式识别、图像处理、优化控制、组合优化和管理决策等领域得到了很好的应用。首先,图着色问题是一种经典的NP-完全问题。针对图着色问题对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了求解图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。其次,基于顶点分割的特点,提出了图着色问题的一种新解法。采用概率矩阵表示种群中的解,大大地节省了存储空间;为了加快算法的收敛速度,结合了一个局部搜索算子提高杂交产生的后代个体的质量;当概率矩阵中的元素取1或0时,算法停止。通过对标准图着色问题的仿真实验,并和已有的算法比较,结果表明,新的算法具有求解性能好、收敛速度快的优点。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 遗传算法的发展与现状
• 1.3 本文的主要工作及安排
• 第二章 遗传算法简介
• 2.1 遗传算法概述
• 2.2 遗传算法的基本框架
• 2.3 遗传算法的基础理论研究概述
• 2.4 遗传算法的研究方向与应用
• 第三章 求解图着色问题的一种新的遗传算法
• 3.1 引言
• 3.2 图着色问题的研究与发展
• 3.3 问题表述
• 3.4 新的遗传算法设计
• 3.5 新的混合遗传算法
• 3.6 收敛性分析
• 3.7 数值仿真及结论
• 第四章 求解图着色问题的一种压缩遗传算法
• 4.1 引言
• 4.2 问题表述
• 4.3 新的压缩遗传算法
• 4.4 数值模拟
• 4.5 结论
• 结束语
• 致谢
• 参考文献
• 在读期间的研究成果