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. | Yugoslav Journal of Operations Research 24 (2014) Number 2,165-186 DOI: OPTIMAL RECOMBINATION IN GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIYATION PROBLEMS – PART II Anton V. EREMEEV Sobolev Institute of Mathematics, Laboratory of Discrete Optimization 630090, Novosibirsk, Russia eremeev@ Julia V. KOVALENKO Omsk . Dostoevsky State University, Institute of Mathematics and Information Technologies, 644077, Omsk, Russia juliakoval86@ Received: July 2013 / Accepted: October 2013 Abstract: 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. MSC: 90C59, 90C10. Performance of genetic algorithms (GA) depends significantly upon the choice of the crossover operator, where the components of parent solutions are combined to build the offspring. This survey is devoted to complexity and solution methods of the Optimal Recombination Problem (ORP), which consists in finding the best possible offspring as a result of a crossover operator, given two feasible parent solutions (see Part I for a formal definition). The experimental results of M. Yagiura and T. Ibaraki [30], C. Cotta, E. Alba and . Troya [8], W. Cook and P. Seymour [6], D. Whitley, D. Hains and A. Howe [29] indicate that optimal recombination may be used successfully in the GAs .
