Name
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 (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability pc=O(k/n), while we give analyses for the setting of constant pc k, the population size μ, and the crossover probability pc. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ: O}(nk-1) for duplicate elimination/minimisation, O}(n2 log n) for maximising the convex hull, O(n log n) for det. crowding (assuming pc = 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 (μ+1) GA compared to the (1+1) EA, which requires θ(nk). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2908812.2908956 | GECCO |
Keywords | Field | DocType |
Genetic algorithms, recombination, crossover, diversity, run time analysis, theory | Binary logarithm,Mathematical optimization,Crossover,Local optimum,Convex hull,Fitness function,Hamming distance,Time complexity,Genetic algorithm,Mathematics | Conference |
Citations | PageRank | References |
10 | 0.52 | 14 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Duc-Cuong Dang | 1 | 190 | 13.08 |
| Tobias Friedrich | 2 | 54 | 8.19 |
| Timo Kötzing | 3 | 443 | 38.58 |
| Martin Krejca | 4 | 82 | 9.47 |
| Per Kristian Lehre | 5 | 627 | 42.60 |
| Pietro Simone Oliveto | 6 | 212 | 25.56 |
| Dirk Sudholt | 7 | 1063 | 64.62 |
| Andrew Sutton | 8 | 91 | 9.72 |