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

AN ANT COLONY GENETIC ALGORITHM FOR GRAPH COLOURING PROBLEM

作　　者：张新萍[1] 张月琴[1] 冯珊珊[1] 

机构地区：[1]太原理工大学计算机科学与技术学院,山西太原030024

出　　处：《计算机应用与软件》2014年第11期207-209,共3页Computer Applications and Software

基　　金：山西省自然科学基金项目(2012011014-2)

摘　　要：遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。Genetic algorithm has been widely used in graph colouring problem,however,to the graphs with large amounts of vertices,colouring outcome using such algorithm is not ideal enough,its operational efficiency is not high as well.Since the genetic algorithm is good at global convergence and the ant colony algorithm has excellent ability of local convergence,so in this thesis we combine the genetic algorithm with ant colony algorithm,and propose a new algorithm（ ant colony system genetic algorithm） to solve the graph colouring problem.The algorithm first uses ant colony algorithm to rapidly search the good initial solution for genetic algorithm,and then further optimise the inheritance using genetic algorithm.At the same time,it further strengthens the intensity of pheromone on optimised solution,and feeds back to ant colony algorithm for search.Experimental results show that the improved algorithm has apparent advantage in solving the graph colouring problem with larger amounts of vertices.

关 键 词：图着色 遗传算法 蚁群算法 NP-完全问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]