2013/07/21 by Anton V. Eremeev, Eremeev, Anton V., Julia V. Kovalenko +1
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #Scheduling and Optimization Algorithms #cs.DS #cs.NE
paper · pdf · doi:10.48550/arxiv.1307.5519
arxiv created 2013/07/21 · openalex publication_date 2013/07/21 · arxiv updated 2013/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.