Computer Science – Neural and Evolutionary Computing
Scientific paper
2011-02-06
Computer Science
Neural and Evolutionary Computing
This is an extended version of our CSR 2011 paper. 31 pages
Scientific paper
Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems. For example, the class of all binary-value functions has a black-box complexity of $O(\log n)$ in the previous black-box models, but has a ranking-based complexity of $\Theta(n)$. For the class of all OneMax functions, we present a ranking-based black-box algorithm that has a runtime of $\Theta(n / \log n)$, which shows that the OneMax problem does not become harder with the additional ranking-basedness restriction.
Doerr Benjamin
Winzen Carola
No associations
LandOfFree
Ranking-Based Black-Box Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Ranking-Based Black-Box Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ranking-Based Black-Box Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506034