| 一种求解图着色问题的蚁群遗传算法 |
| |
| 引用本文： | 张新萍,张月琴,冯珊珊. 一种求解图着色问题的蚁群遗传算法[J]. 计算机应用与软件, 2014, 0(11) |
| |
| 作者姓名： | 张新萍 张月琴 冯珊珊 |
| |
| 作者单位： | 太原理工大学计算机科学与技术学院 山西 太原 030024 |
| |
| 基金项目： | 山西省自然科学基金项目(2012011014-2)。 |
| |
| 摘 要： | 遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。
|
| 关 键 词： | 图着色 遗传算法 蚁群算法 NP-完全问题 |
AN ANT COLONY GENETIC ALGORITHM FOR GRAPH COLOURING PROBLEM |
| |
| Zhang Xinping,Zhang Yueqin,Feng Shanshan. AN ANT COLONY GENETIC ALGORITHM FOR GRAPH COLOURING PROBLEM[J]. Computer Applications and Software, 2014, 0(11) |
| |
| Authors: | Zhang Xinping Zhang Yueqin Feng Shanshan |
| |
| Abstract: | |
| |
| Keywords: | Graph colouring Genetic algorithm Ant colony algorithm NP-complete problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
