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

CREATORAndre Opris
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE172 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01256

Browse the full library · About the Tower of Babel