Dynastic potential crossover operator

Abstract

An optimal recombination operator provides an optimal solution fulfilling the gene transmission property: the value of any variable in the offspring must be inherited from one of the parents. In the case of binary variables, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. In general, exploring this hyperplane is computationally costly, but if the objective function has a low number of nonlinear interactions among the variables, the exploration can be done in $O(4^{\beta}(n+m)+n^2)$ time, for problems with $n$ decision variables, $m$ subfunctions composing the objective function and where $\beta$ is a constant. In this talk, we present a quasi-optimal recombination operator, called Dynastic Potential Crossover (DPX), that runs in $O(4^{\beta}(n+m)+n^2)$ time in any case and is able to act as an optimal recombination operator for low-epistasis combinatorial problems. We show some experimental results where the operator is integrated in DRILS (an ILS with recombination) and standard EA solving NKQ Landscapes and MAX-SAT.