Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
Benjamin Doerr, Martin S. Krejca, Günter Rudolph · 2024
Read Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces by Benjamin Doerr, Martin S. Krejca, Günter Rudolph (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11684.txt.
Description
Benjamin Doerr, Martin Krejca, and Günter Rudolph study how long randomized search methods take when choices are whole numbers with no upper bound. Such methods, modeled on evolution, are strong problem solvers, yet theory covers mostly yes-no or smooth number choices. Whole-number spaces with no cap, common in scheduling and design, were nearly untouched.
The team analyzes algorithms that juggle several goals at once, testing three ways of making random changes: small steps of one, medium jumps, and jump sizes that follow a heavy-tailed rule. On a standard test problem, small steps crawl when the start is far from the best trade-off curve. The heavy-tailed rule, which needs no tuning, did well across all settings. Experiments back the math, and the results guide how to set mutation strength in practice.
Catalog record
| CREATOR | Benjamin Doerr, Martin S. Krejca, Günter Rudolph |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11684