Faster Black-Box Algorithms Through Higher Arity Operators
Publication: Research - peer-review › Article in proceedings – Annual report year: 2011
We extend the work of Lehre and Witt (GECCO 2010) on
the unbiased black-box model by considering higher arity
variation operators. In particular, we show that already for
binary operators the black-box complexity of LeadingOnes
drops from (n2) for unary operators to O(n log n). For
OneMax, the
(n log n) unary black-box complexity drops
to O(n) in the binary case. For k-ary operators, k n, the
OneMax-complexity further decreases to O(n= log k).
| Original language | English |
|---|---|
| Title | FOGA '11 Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms |
| Publication date | 2011 |
| Pages | 163-171 |
| ISBN (print) | 978-1-4503-0633-1 |
| DOIs | |
| State | Published |
Workshop
| Workshop | 11th Foundations of Genetic Algorithms workshop Schwarzenberg |
|---|---|
| Number | 11 |
| Country | Austria |
| City | Schwarzenberg |
| Period | 05-01-11 → 09-01-11 |
| Internet address | http://www.sigevo.org/foga-2011/index.html |
| Citations | Web of Science® Times Cited: No match on DOI |
|---|
Keywords
- Pseudo-Boolean optimization, Runtime analysis, Black-box complexity, Theory
Loading map data...
ID: 5627172