基于独立集划分的图着色算法

针对经典的图着色问题,在顶点集随机划分的基础上,设计了一种寻求集合个数最少的独立集划分遗传算法.运行算法获得的独立集个数即为图的色数.算法引入了模块化函数思想,采用了单向传递交叉算子.通过贪婪局部优化初始种群和杂交后代个体,使算法具有较好的收敛速度.对四个经典算例的仿真结果表明,本文提出的算法可获得问题的高质量解,是一种有潜力的算法.

Graph Coloring Algorithm Based on Parting Vertexes into Several Independent Sets

Based on parting vertexes into several sets randomly,this paper proposes a genetic algorithm to find independent sets with least members for the classical graph coloring problem.That number of members is the chromatic number of graph.This algorithm induces the idea of modularity function,and uses one way cross-over operator.Through local optimized initial population and filial generation,this algorithm can converge quickly.The simulation results on five standard benchmark problems show that the proposed algorithm can obtain good quality solution and it is a potential algorithm for the problem studied.