Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms
Although differential evolution (DE) algorithms perform well on a large variety of complicated optimization problems, only a few theoretical studies are focused on the working principle of DE algorithms. To make the first attempt to reveal the function of binomial crossover, this paper aims to answe...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2022-08-01
|
Series: | Mathematics |
Subjects: | |
Online Access: | https://www.mdpi.com/2227-7390/10/16/2850 |
_version_ | 1797443689591603200 |
---|---|
author | Cong Wang Jun He Yu Chen Xiufen Zou |
author_facet | Cong Wang Jun He Yu Chen Xiufen Zou |
author_sort | Cong Wang |
collection | DOAJ |
description | Although differential evolution (DE) algorithms perform well on a large variety of complicated optimization problems, only a few theoretical studies are focused on the working principle of DE algorithms. To make the first attempt to reveal the function of binomial crossover, this paper aims to answer whether it can reduce the approximation error of evolutionary algorithms. By investigating the expected approximation error and the probability of not finding the optimum, we conduct a case study comparing two evolutionary algorithms with and without binomial crossover on two classical benchmark problems: OneMax and Deceptive. It is proven that using binomial crossover leads to the dominance of transition matrices. As a result, the algorithm with binomial crossover asymptotically outperforms that without crossover on both OneMax and Deceptive, and outperforms on OneMax, however, not on Deceptive. Furthermore, an adaptive parameter strategy is proposed which can strengthen the superiority of binomial crossover on Deceptive. |
first_indexed | 2024-03-09T13:00:41Z |
format | Article |
id | doaj.art-5206985fa501494da38b205ff2089456 |
institution | Directory Open Access Journal |
issn | 2227-7390 |
language | English |
last_indexed | 2024-03-09T13:00:41Z |
publishDate | 2022-08-01 |
publisher | MDPI AG |
record_format | Article |
series | Mathematics |
spelling | doaj.art-5206985fa501494da38b205ff20894562023-11-30T21:54:25ZengMDPI AGMathematics2227-73902022-08-011016285010.3390/math10162850Influence of Binomial Crossover on Approximation Error of Evolutionary AlgorithmsCong Wang0Jun He1Yu Chen2Xiufen Zou3School of Science, Wuhan University of Technology, Wuhan 430070, ChinaDepartment of Computer Science, Nottingham Trent University, Clifton Campus, Nottingham NG11 8NS, UKSchool of Science, Wuhan University of Technology, Wuhan 430070, ChinaSchool of Mathematics and Statistics, Wuhan University, Wuhan 430072, ChinaAlthough differential evolution (DE) algorithms perform well on a large variety of complicated optimization problems, only a few theoretical studies are focused on the working principle of DE algorithms. To make the first attempt to reveal the function of binomial crossover, this paper aims to answer whether it can reduce the approximation error of evolutionary algorithms. By investigating the expected approximation error and the probability of not finding the optimum, we conduct a case study comparing two evolutionary algorithms with and without binomial crossover on two classical benchmark problems: OneMax and Deceptive. It is proven that using binomial crossover leads to the dominance of transition matrices. As a result, the algorithm with binomial crossover asymptotically outperforms that without crossover on both OneMax and Deceptive, and outperforms on OneMax, however, not on Deceptive. Furthermore, an adaptive parameter strategy is proposed which can strengthen the superiority of binomial crossover on Deceptive.https://www.mdpi.com/2227-7390/10/16/2850binomial crossoverdifferential evolutionfixed-budget analysisevolutionary computationapproximation error |
spellingShingle | Cong Wang Jun He Yu Chen Xiufen Zou Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms Mathematics binomial crossover differential evolution fixed-budget analysis evolutionary computation approximation error |
title | Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms |
title_full | Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms |
title_fullStr | Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms |
title_full_unstemmed | Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms |
title_short | Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms |
title_sort | influence of binomial crossover on approximation error of evolutionary algorithms |
topic | binomial crossover differential evolution fixed-budget analysis evolutionary computation approximation error |
url | https://www.mdpi.com/2227-7390/10/16/2850 |
work_keys_str_mv | AT congwang influenceofbinomialcrossoveronapproximationerrorofevolutionaryalgorithms AT junhe influenceofbinomialcrossoveronapproximationerrorofevolutionaryalgorithms AT yuchen influenceofbinomialcrossoveronapproximationerrorofevolutionaryalgorithms AT xiufenzou influenceofbinomialcrossoveronapproximationerrorofevolutionaryalgorithms |