Experiments with Hybrid Genetic Algorithm for the Grey Pattern Problem

Article type: Research Article

Authors: Misevičius, Alfonsas

Affiliations: Department of Practical Informatics, Kaunas University of Technology, Studentų 50-400a/416a, LT-51368 Kaunas, Lithuania, e-mail: alfonsas.misevicius@ktu.lt

Abstract: Recently, genetic algorithms (GAs) and their hybrids have achieved great success in solving difficult combinatorial optimization problems. In this paper, the issues related to the performance of the genetic search in the context of the grey pattern problem (GPP) are discussed. The main attention is paid to the investigation of the solution recombination, i.e., crossover operators which play an important role by developing robust genetic algorithms. We implemented seven crossover operators within the hybrid genetic algorithm (HGA) framework, and carried out the computational experiments in order to test the influence of the recombination operators to the genetic search process. We examined the one point crossover, the uniform like crossover, the cycle crossover, the swap path crossover, and others. A so-called multiple parent crossover based on a special type of recombination of several solutions was tried, too. The results obtained from the experiments on the GPP test instances demonstrate promising efficiency of the swap path and multiple parent crossovers.

Keywords: combinatorial optimization, heuristic algorithms, genetic algorithms, crossover operators, grey pattern problem, quadratic assignment problem

Journal: Informatica, vol. 17, no. 2, pp. 237-258, 2006