Skip header navigation

University of Stirling

×

Conference Proceeding

Quasi-Optimal Recombination Operator

Citation
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. https://doi.org/10.1007/978-3-030-16711-0_9

Abstract
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.

Keywords
Recombination operator; Dynastic potential; Gray box optimization

StatusPublished
Author(s)Chicano, Francisco; Ochoa, Gabriela; Whitley, Darrell; Tinós, Renato
Title of seriesLecture Notes in Computer Science
Number in series11452
Publication date31/12/2019
Publication date online28/03/2019
URLhttp://hdl.handle.net/1893/29468
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
eISSN1611-3349
ISSN of series0302-9743
ISBN9783030148119
eISBN9783030148126
ConferenceEvoCOP 2019: European Conference on Evolutionary Computation in Combinatorial Optimization
Conference locationLeipzig, Germany
Dates
Scroll back to the top