A design of genetic algorithm-based meta-heuristic method: an application to the graph coloring problem

摘要

In this paper, a meta-heuristic method that combines the global search power of Genetic Algorithms with the local search power of local optimization algorithms is described. First of all, a metric function between two solutions, or phenotypes, is defined by the shortest Hamming distance between sets of isomorphic genotypes. The phenotypic distance is useful to analyze and control the behavior of genotypes in the search space from the view point of the problem space. Then, by using the phenotypic distance, a new crossover technique named Harmonic Crossover is proposed in which children always come to the position between their parents in the problem space. Finally, in order to get maximum efficiency of the meta-heuristic method, the best timing in employing the local optimization algorithms is discussed. The experimental results indicate that the local optimization algorithms should be synchronized with the Harmonic Crossover to find high quality solutions in reasonable time.