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. We consider efficient reductions of the ORPs. Part I presents the basic principles of optimal recombination with a survey of results on Boolean Linear Programming Problems. | Yugoslav Journal of Operations Research 24 (2014) Number 1, 1-20 DOI: Invited Review OPTIMAL RECOMBINATION IN GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS – PART I Anton V. EREMEEV Sobolev Institute of Mathematics, Omsk Branch 644099, Omsk, Russia eremeev@ Julia V. KOVALENKO Omsk . Dostoevsky State University, 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. We consider efficient reductions of the ORPs, allowing to establish polynomial solvability or NP-hardness of the ORPs, as well as direct proofs of hardness results. Part I presents the basic principles of optimal recombination with a survey of results on Boolean Linear Programming Problems. Part II (to appear in a subsequent issue) is devoted to the ORPs for problems which are naturally formulated in terms of search for an optimal permutation. Keywords: Genetic Algorithm, Optimal Recombination Problem, complexity, crossover, Boolean Linear Programming MSC: 90C59, 90C10. 1 INTRODUCTION The genetic algorithms (GAs) originally suggested by J. Holland [20] are randomized heuristic search methods using an evolving population of sample solutions, based on analogy with the genetic mechanisms in nature. Various modifications of GAs have been widely used in operations research, pattern recognition, artificial intelligence, and other areas (see . [28, 31, 32]). Despite numerous experimental 2 . Eremeev, . Kovalenko / Optimal Recombination studies of these algorithms, the theoretical analysis of their efficiency is currently at an early stage [7]. Efficiency of GAs depends significantly on the choice of crossover operator, that combines the given parent solutions, aiming to produce .
