双目标进化算法求解图着色问题

根据图着色问题的特征,提出了求解图着色问题的双目标模型;设计的有效、简洁的杂交算子和变异算子,均直接产生可行的后代个体;理论分析表明算法以概率1收敛到问题的最优解集.对标准算例进行了仿真实验,结果表明,双目标进化算法可以获得问题高质量的解,即对图进行着色所使用的颜色接近图的色数.

Bi-objective evolutionary algorithm for the graph coloring problem

The graph coloring problem(GCP) is an NP-hard problem.A new bi-objective 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 this novel 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.