  An optimal recombination operator for two parent solutions provides the best
solution among those that take the value for each variable from one of the
parents (gene transmission property). If the solutions are bit strings, the
offspring of an optimal recombination operator is optimal in the smallest
hyperplane containing the two parent solutions. Exploring this hyperplane is
computationally costly, in general, requiring exponential time in the worst
case. However, when the variable interaction graph of the objective function is
sparse, exploration can be done in polynomial time.
  In this paper, we present a recombination operator, called Dynastic Potential
Crossover (DPX), that runs in polynomial time and behaves like an optimal
recombination operator for low-epistasis combinatorial problems. We compare
this operator, both theoretically and experimentally, with traditional
crossover operators, like uniform crossover and network crossover, and with two
recently defined efficient recombination operators: partition crossover and
articulation points partition crossover. The empirical comparison uses NKQ
Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators
in terms of quality of the offspring and provides better results included in a
trajectory and a population-based metaheuristic, but it requires more time and
memory to compute the offspring.
