基于遗传和启发式算法的混合顶点着色算法

journal6 ›› 2008, Vol. 29 ›› Issue (5): 57-60.

基于遗传和启发式算法的混合顶点着色算法

（华东交通大学信息工程学院，江西南昌330013）

出版日期:2008-09-25 发布日期:2012-05-20
作者简介:廖辉传（1973-），男，江西万载人，华东交通大学信息工程学院讲师，硕士，主要从事图论、算法设计与分析研究.
基金资助:
华东交通大学科研基金资助项目（07XX01）

Vertex Coloring of a Graph Based on Genetic and Heuristics Search Algorithm

(School of Information Engineering,East China Jiaotong University,Nanchang 330013,China)

Online:2008-09-25 Published:2012-05-20

摘要/Abstract

摘要：图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法，该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度，可以获得问题高质量的解.

关键词： 图的着色, 启发式算法, 遗传算法, 时间复杂度

Abstract: Graph coloring is a typical NP-completely problem.This paper puts forward a new method of vertex coloring of a graph based on genetic algorithm and heuristics search algorithm.This algorithm involves the coding methods of chromosome,the design of fitness function and the selection operators.Experiments show that this new algorithm can improve time complexity and obtain solutions of excellent quality.

Key words: graph coloring;heuristics search algorithm;genetic algorithm, time complexity

廖辉传. 基于遗传和启发式算法的混合顶点着色算法[J]. journal6, 2008, 29(5): 57-60.

LIAO Hui-Chuan. Vertex Coloring of a Graph Based on Genetic and Heuristics Search Algorithm[J]. journal6, 2008, 29(5): 57-60.

[1]	段明秀，李钰，赖鹏飞，廖嘉琪. 自适应遗传算法求解运动员最佳配对问题[J]. 吉首大学学报（自然科学版）, 2019, 40(2): 31-33.
[2]	李洪刚，王亚琦，李雪晴，亢俊健. 基于模拟退火遗传算法求解整周模糊度[J]. 吉首大学学报（自然科学版）, 2018, 39(4): 9-14.
[3]	王磊，李克荣，唐惠，王娇娇，孙言. 城市交通信号灯的配时优化[J]. 吉首大学学报（自然科学版）, 2017, 38(5): 35-41.
[4]	鲁春林，方东辉，陈望学，钱文舒. 基于遗传算法Beta分布参数的极大似然估计[J]. 吉首大学学报（自然科学版）, 2016, 37(5): 13-15.
[5]	彭丽, 洪亮. “机器人”路径改进型单亲遗传算法规划及其仿真[J]. journal6, 2015, 36(4): 37-39.
[6]	郭庆焱, 辜丽川, 张友华, 曹梦如, 章登良. 一种基于遗传算法的优化查询方法[J]. journal6, 2013, 34(5): 37-41.
[7]	马桂雨, 王雪丹, 万丹 . 基于遗传小波神经网络的变压器故障诊断[J]. journal6, 2013, 34(1): 51-55.
[8]	段明秀. 基于遗传算法的模糊RBF神经网络设计及应用[J]. journal6, 2010, 31(1): 43-46.
[9]	尹鹏飞, 张晓丹. 一种基于简单遗传算法的K-Means改进算法[J]. journal6, 2009, 30(6): 43-45.
[10]	王改芬. 遗传算法在中小学排课系统中的应用[J]. journal6, 2009, 30(3): 44-47.
[11]	梅颖. 基于改进小生境免疫遗传算法的矩形件排样[J]. journal6, 2009, 30(2): 55-57.
[12]	杨艳玲, 冯林桥, 刘金玲. 改进遗传算法在配电网无功优化的应用[J]. journal6, 2008, 29(5): 68-71.
[13]	龙君, 曾三云. 模糊证券投资组合的期望值模型[J]. journal6, 2008, 29(3): 44-47.
[14]	王仙云, 方东辉. 遗传算法应用于方程求根的一点改进[J]. journal6, 2007, 28(4): 35-38.
[15]	傅文斌, 何缓. 基于最小反射准则的天线罩C-夹层遗传优化[J]. journal6, 2007, 28(3): 55-58.