Conference Proceeding

Quasi-Optimal Recombination Operator



Chicano F, Ochoa G, Whitley D & Tinós R (2019) Quasi-Optimal Recombination Operator. In: Liefooghe A & Paquete L (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, 11452. EvoCOP 2019: European Conference on Evolutionary Computation in Combinatorial Optimization, Leipzig, Germany, 24.04.2019-26.04.2019. Cham, Switzerland: Springer International Publishing, pp. 131-146.

The output of an optimal recombination operator for two parent solutions is a solution with the best possible value for the objective function among all the solutions fulfilling the gene transmission property: the value of any variable in the offspring must be inherited from one of the parents. This set of solutions coincides with the largest dynastic potential for the two parent solutions of any recombination operator with the gene transmission property. In general, exploring the full dynastic potential is computationally costly, but if the variables of the objective function have a low number of non-linear interactions among them, the exploration can be done in O(4β(n+m)+n2) time, for problems with n variables, m subfunctions and β a constant. In this paper, we propose a quasi-optimal recombination operator, called Dynastic Potential Crossover (DPX), that runs in O(4β(n+m)+n2) time in any case and is able to explore the full dynastic potential for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with two recently defined efficient recombination operators: Partition Crossover (PX) and Articulation Points Partition Crossover (APX). The empirical comparison uses NKQ Landscapes and MAX-SAT instances.

Recombination operator; Dynastic potential; Gray box optimization

Title of seriesLecture Notes in Computer Science
Number in series11452
Publication date31/12/2019
Publication date online28/03/2019
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
ISSN of series0302-9743
ConferenceEvoCOP 2019: European Conference on Evolutionary Computation in Combinatorial Optimization
Conference locationLeipzig, Germany

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups