Optimal Recombination in Genetic Algorithms
This work addresses a theoretical bottleneck for researchers in evolutionary computation, but it is incremental as it builds on existing survey and complexity analysis.
The paper surveys the complexity of the optimal recombination problem in genetic algorithms, focusing on establishing polynomial solvability or NP-hardness through reductions and direct proofs.
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.