Optimal Recombination in Genetic Algorithms
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
We propose a new genetic algorithm with optimal recombination for the asymmetric instances of travelling salesman problem. The algorithm incorporates several new features that contribute to its effectiveness: (i) Optimal…
Analysis of Optimal Recombination in Genetic Algorithm for a Scheduling Problem with Setups
In this paper, we perform an experimental study of optimal recombination operator for makespan minimization problem on single machine with sequence-dependent setup times ($1|s_{vu}|C_{\max}$). The computational experimen…
SchedulingRecombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem
The maximum clique problem (MCP) is a fundamental problem in graph theory and in computational complexity. Given a graph G, the problem is that of finding the largest clique (complete subgraph) in G. The MCP has many imp…
Mathematical perspective on genetic algorithms with optimization guided operators
Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems. The basic mutation and recombination operators involved are qualitatively different from those stu…
Reinforcement LearningPerfect Edge-Transmitting Recombination of Permutations
Crossover is the process of recombining the genetic features of two parents. For many applications where crossover is applied to permutations, relevant genetic features are pairs of adjacent elements, also called edges i…