用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。

The Hybrid Genetic Algorithms for the Adjacent Strong Edge Coloring of Graphs

The algorithm for the adjacent strong edge coloring of graphs is an NP-complete problem. In this paper, the hybrid genetic algorithm for the adjacent strong edge coloring of graphs is presented. When the crossing and mutation methods are designed, the methods of crossing at two points and local scanning are combined. In this way, the degeneration of population can be avoided, which is advantageous to searching for the best solution region quickly. Based on the practical applications, the structural property of the graph and the times of iteration are compared. and the terminating condition of the algorithm is designed. The results of simulation experiments show that the hybrid genetic algorithm may obtain good quality solutions. That is to say, the number of the colors used in coloring the adjacent strong edges of graphs is near to the adjacent strong edge chromatic number of graphs.