Graph Vertex Coloring Problem Algorithm Based On Particle Swarm Optimization

As an emerging research field, combination optimization has become an important component of operation research just as mathematic optimization. Combination optimization emphasizes more on application field compared to other operation research field. This paper researches on graph vertex coloring problem which is a typical combination optimization. Graph vertex coloring problem (GVCP) is a NP-complete problem having good application such as scheduling and timetabling. Therefore, the construction of new approximating optimization algorithm to solve graph vertex coloring problem is of great realistic meaning.Particle swarm optimization (PSO) is a brand-new stochastic computational technique based on swarm intelligent. The most attractive features of PSO are reduced memory requirement, computationally effective and easier to implement compared to other evolutionary algorithms (GA). For that reason, since been presented, PSO, which has broad applications in function optimization, instruction system optimization, fuzzy system control etc., has gained general attention of different fields especially evolution computing, and gradually becomes a very popular area. In recent years, abundance of good efforts has been obtained.In this paper, we present a particle swarm optimization algorithm for graph vertex coloring problem, designing GVCP coding method, fitness function and fly mode of swarm. Also, simulated annealing algorithm is added to avoid local optima, which advances the searching performance. Then, a hybrid algorithm is presented by the analysis of velocity evolution mode and the analogy between PSO and GA, which accomplish the update of particle velocity successfully by cross-over operator and mutation operator. Experimental result shows that the hybrid algorithm based on GA has a more accuracy searching ability. In the end a simulated annealing operator is added to improve the convergence rate.