doiSerbia

Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II

Eremeev Anton V. (Sobolev Institute of Mathematics, Laboratory of Discrete Optimization, Novosibirsk, Russia)
Kovalenko Julia V. (Omsk F.M. Dostoevsky State University, Institute of Mathematics and Information Technologies, Omsk, Russia)

This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations: the Travelling Salesman Problem, the Shortest Hamilton Path Problem and the Makespan Minimization on Single Machine and some other related problems. The analysis indicates that the corresponding ORPs are NP-hard, but solvable by faster algorithms, compared to the problems they are derived from.

Keywords: Genetic Algorithm, Optimal Recombination Problem, complexity, crossover, permutation problems