Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^k-1)\) for duplicate elimination/minimisation, \(O(n^2 n)\) for maximising the convex hull, \(O(n n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n n)\) for maximising the Hamming distance, \(O(n n)\) for fitness sharing, \(O(n n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
%0 Journal Article
%1 dang2017escaping
%A Dang, Duc-Cuong
%A Friedrich, Tobias
%A Kötzing, Timo
%A Krejca, Martin S.
%A Lehre, Per Kristian
%A Oliveto, Pietro S.
%A Sudholt, Dirk
%A Sutton, Andrew M.
%D 2017
%E Tan, Kay Chen
%I IEEE
%J IEEE Transactions on Evolutionary Computation
%K testing typo3
%T Escaping Local Optima Using Crossover with Emergent Diversity
%X Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^k-1)\) for duplicate elimination/minimisation, \(O(n^2 n)\) for maximising the convex hull, \(O(n n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n n)\) for maximising the Hamming distance, \(O(n n)\) for fitness sharing, \(O(n n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.
@article{dang2017escaping,
abstract = {Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the \((\mu+1)\) GA using uniform crossover on the fitness function \(Jump_k\). All previous results in this context only hold for unrealistically low crossover probability \(p_c=O(k/n)\), while we give analyses for the setting of constant \(p_c < 1\) in all but one case. Our bounds show a dependence on the problem size \(n\), the jump length \(k\), the population size \(\mu\), and the crossover probability \(p_c\). For the typical case of constant \(k > 2\) and constant \(p_c\), we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of \(\mu\): \(O(n^{k-1})\) for duplicate elimination/minimisation, \(O(n^2 \log n)\) for maximising the convex hull, \(O(n \log n)\) for det. crowding (assuming \(p_c = k/n\)), \(O(n \log n)\) for maximising the Hamming distance, \(O(n \log n)\) for fitness sharing, \(O(n \log n)\) for the single-receiver island model. This proves a sizeable advantage of all variants of the \((\mu+1)\) GA compared to the (1+1) EA, which requires \(\Theta(n^k)\). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.},
added-at = {2017-09-19T19:36:41.000+0200},
author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.},
biburl = {https://www.bibsonomy.org/bibtex/2fe6a9bbde04fc94795585fbc4e7bd501/typo3tester},
editor = {Tan, Kay Chen},
interhash = {8c2a23be463f8a9c20c40db9cbc3fd81},
intrahash = {fe6a9bbde04fc94795585fbc4e7bd501},
journal = {IEEE Transactions on Evolutionary Computation},
keywords = {testing typo3},
month = aug,
publisher = {IEEE},
timestamp = {2018-03-30T01:44:13.000+0200},
title = {Escaping Local Optima Using Crossover with Emergent Diversity},
year = 2017
}