摘要
为了提高图染色算法的寻优能力和收敛速度,结合禁忌搜索算法和遗传算法的优缺点,提出了一种混合优化算法(GA-HM)。该算法利用遗传算法生成初始解,将染色元素分到不同的色集中,然后通过禁忌算法进行变领域搜索来更新顶点染色。实验结果表明,GA-HM对求解相同的目标解具有更好的全局最优性和收敛性。
This paper developed a new graph coloring algorithm-a hybrid optimization algorithm（ GA-HM）, based on the ad- vantages and disadvantages of tabu search algorithm and genetic algorithm. It could improve search ability and convergence speed of a graph coloring algorithm. GA-HM used genetic algorithm to generate better initial solution which assigned the dyeing elements into different color classes at first, then performed alternately search by tabu algorithm for updating the dyeing. Ex- perimental results show that this algorithm has better global optimality and convergence.
出处
《计算机应用研究》
CSCD
北大核心
2016年第1期98-100,共3页
Application Research of Computers
基金
江西省教育厅科技项目(GJJ14432
GJJ14431)
关键词
组合优化
图染色
禁忌搜索算法
遗传算法
变领域搜索
色集
combinatorial optimization
graph colonng
tabu search algorithm
genetic algorithm
variable neighborhoodsearch
color classes
