Graph Coloring Based On Ant Colony System Genetic Algorithm

Graph coloring is extended in meaning the original "Four Color Theorem", and gradually, many researchers applied it to solve some actual problems, such as Channel allocation problem, Task scheduling problem, Slots allocation problem and so on. It is difficult to confirm the graph coloring number, although graph coloring was used extensively. Lots of researchers put forward many kinds of algorithm to the solution, including about completely algorithm and approximation algorithm. Completely algorithm is acquired of the precise and optimal solution according to the strict mathematical method, but it is so great complexity that it’s only as a ideal method but applied to actual solution. Approximation algorithm is acquired of the optimal solution by virtue of its property of fast search, and it is widely used in the research area.There are many kinds of approximation algorithm to solve the graph coloring problem, such as genetic algorithm and ant colony algorithm, and these algorithms have been applied and developed gradually. Genetic algorithm depends on its self-organization, self-adaptive, and global convergence to get the optimal solution. However, its settings of complex structure (including coding scheme, fitness function, and genetic operators) will influence the consequence. As a result, it is suggested some appropriate coding methods and genetic operator-transposition operator, shift operator, cut operator, joint operator, symbolic coding method can be described the constraint condition of the problem, transposition operator and shift operation can make sure the next generation going the more optimal orientation, so decreasing some invalid time of search, besides, cut operator and join operator can make sure the diversity of the population.Although the revised algorithm is more effectively to solve the graph coloring problem than traditional genetic algorithm, the original population is very signal, and it will result some unnecessary time confusing, so it’s suggested that take search results of another algorithm as the original population of revised algorithm. As greedy algorithm is too simple, tabu search is so great dependent on original value that it can’t solve the same problem which the revised algorithm faced. Simulated annealing algorithm although avoid the reliance of original value, its solution can’t be transferred to the original value’s structure of revised algorithm. Ant colony algorithm has great local convergence, and it can exactly describe the constraint condition of the graph coloring problem, and its results can be easily changed into the original value’s structure. In this article, it is firstly introduced traditional genetic algorithm and how to solve graph coloring problem and what’s the imperfections. In allusion to the specificity of graph coloring problem, it is suggested revised genetic algorithm with specific coding method and operators, that using symbolic coding, and replace prima cross operator as transposition operator and shift operator, as a result, the solution can be developed into the better way. Then, as the original population of revised algorithm is signal, it is suggested that making results of ant colony algorithm as the original value of revised genetic algorithm. Lastly, it is introduced the solution procedure of fusion algorithm, and made simulation experiment on standard coloring samples and graphs which are generated randomly by Matlab7.0, the results of the test can prove the effectiveness of the new algorithm.