%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 }