A Michigan memetic algorithm for solving the vertex coloring problem

Genetic algorithms (GAs) can be divided into two broad approaches, Michigan and Pittsburgh Approaches. In Pittsburg approach, one of the individuals (chromosomes) in the population becomes the solution of the problem being solved whereas in Michigan approach the whole population represents the solution. For example in the problem of vertex coloring, in Michigan approach, each chromosome encodes a color of a vertex and the set of all chromosomes in the population represents the solution which is a coloring for the graph whereas in the Pittsburgh approach each individual encodes a coloring for the whole graph. Combining a genetic algorithm (GA) with a local search produces a type of evolutionary algorithm (EA) known as a memetic algorithm (MA). MA uses the local search method to either accelerate the discovery of good solutions, for which evolution alone would take too long to discover, or to reach solutions that would otherwise be unreachable by evolution or a local search method alone. In this paper a Michigan memetic algorithm for solving vertex coloring problem is proposed. The initial population is a set of chromosomes each of which is associated to a vertex of the input graph. Each chromosome is a part of the solution and represents a color for its corresponding vertex. The proposed algorithm is a distributed algorithm in which each chromosome locally evolves by evolutionary operators and improves by a learning automata based local search. To evaluate the efficiency of the proposed algorithm several computer experimentations have been conducted. The results show the superiority of the proposed algorithm over existing algorithms in terms of running time and the required number of colors.