RT Conference Proceedings
T1 Quasi-Optimal Recombination Operator
A1 Chicano-García, José-Francisco
A1 Ochoa, Gabriela
A1 Whitley, L. Darrell
A1 Tinós, Renato
K1 Computación evolutiva
K1 Optimización combinatoria
K1 Congresos y conferencias
AB 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^{\beta}(n+m)+n^2)$ time, for problems with $n$ variables, $m$ subfunctions and $\beta$ a constant. In this paper, we propose 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 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.
YR 2019
FD 2019-07-22
LK https://hdl.handle.net/10630/18104
UL https://hdl.handle.net/10630/18104
LA eng
NO Universidad de Málaga. Campus de Excelencia International Andalucía Tech.Ministerio de Economía y Competitividad y FEDER (proyecto TIN2017-88213-R)
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 24 ene 2026