一种求解图着色问题的蚁群遗传算法

• 作者: 冯珊珊 张新萍 张月琴
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 图着色 遗传算法 蚁群算法 NP 完全问题
• 年，卷（期）: 2014,（11）
• 所属期刊栏目: 图像处理与应用
• 页码范围: 207-209
• 页数: 3页
• 分类号: TP301
• 字数: 3258字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2014.11.052

摘要

遗传算法在图着色问题上已经得到广泛的应用，但对于顶点数较多的图，使用此类算法进行着色的结果就显得不够理想，运行效率也不够高。由于遗传算法具有全局收敛性，蚁群算法具有局部收敛性，因此，将遗传算法和蚁群搜索算法融合，提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解，然后利用遗传算法进一步遗传优化，同时在优化解上加强信息素强度，并反馈给蚁群搜索。实验结果表明，改进的算法在解决顶点数较大的图着色问题上有明显的优势。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张月琴	太原理工大学计算机科学与技术学院	49	336	10.0	16.0
2	冯珊珊	太原理工大学计算机科学与技术学院	3	11	2.0	3.0
3	张新萍	太原理工大学计算机科学与技术学院	1	3	1.0	1.0