Dynastic Potential Crossover Operator
| Autor: | Chicano, Francisco, Ochoa, Gabriela, Whitley, L. Darrell, Tinós, Renato |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Recombination operator
Computational Mathematics COMPUTAÇÃO EVOLUTIVA TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY MathematicsofComputing_NUMERICALANALYSIS Gray box optimization ComputingMethodologies_ARTIFICIALINTELLIGENCE Algorithms Computación evolutiva Dynastic potential MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | RIUMA. Repositorio Institucional de la Universidad de Málaga instname Evolutionary Computation Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual) Universidade de São Paulo (USP) instacron:USP |
| ISSN: | 1530-9304 |
| Popis: | 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. This research is partially funded by the Universidad de M\'alaga, Consejería de Economía y Conocimiento de la Junta de Andalucía and FEDER under grant number UMA18-FEDERJA-003 (PRECOG); under grant PID 2020-116727RB-I00 (HUmove) funded by MCIN/AEI/10.13039/501100011033; and TAILOR ICT-48 Network (No 952215) funded by EU Horizon 2020 research and innovation programme. The work is also partially supported in Brazil by São Paulo Research Foundation (FAPESP), under grants 2021/09720-2 and 2019/07665-4, and National Council for Scientific and Technological Development (CNPq), under grant 305755/2018-8. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|