摘要
根据图着色问题的特征,提出了求解图着色问题的双目标模型;设计的有效、简洁的杂交算子和变异算子,均直接产生可行的后代个体;理论分析表明算法以概率1收敛到问题的最优解集。对标准算例进行了仿真实验,结果表明,双目标进化算法可以获得问题高质量的解,即对图进行着色所使用的颜色接近图的色数。
The graph coloring problem （GCP） is an NP-hard problem. A new bi-objeetive model is presented according to the characteristics of GCP. Based on this new model, an effective crossover and simple mutation operator are designed to generate the feasible offspring directly. The theoretical analysis shows that the proposed algorithm converges to the global optimal set at a probability of 1. Experimental results demonstrate that thisnovel evolutionary algorithm can obtain good quality solutions. That is to say, the number of the colors used in coloring the vertices of graphs is near to the chromatic number of graphs.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2008年第10期2011-2013,2018,共4页
Systems Engineering and Electronics
基金
国家自然科学基金资助课题(60873099)
关键词
图着色问题
进化算法
NP-完全问题
graph coloring problem
evolutionary algorithm
NP-complete problem
