Many-Objective Problems Where Crossover is Provably Essential
Andre Opris · 2025
Read Many-Objective Problems Where Crossover is Provably Essential by Andre Opris (2025) 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-2505-01256.txt.
Description
Andre Opris wrote a 2025 mathematics paper on how fast NSGA-III, a well-known search algorithm, finds the best trade-offs when the list of objectives is long. The algorithm is built for problems with more than three objectives. When and why it runs well was not well understood. Proofs, not tests on real machines, are the method of the paper.
Opris proves runtime limits for the algorithm on four known benchmark problems, at any number of objectives. With a large population of candidate solutions, the limits beat earlier marks. On two of the problems with two objectives, the algorithm even beats its own famous relative, NSGA-II. A key trick is a chance-based way to swap members of the population in and out. On one hard problem type, that trick speeds the run up enormously, and tight limits are set for two fixed sizes.
Catalog record
| CREATOR | Andre Opris |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 172 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01256