Abstract
We present an exponential decay function that characterizes the number of solutions to instances of the Number Partitioning Problem (NPP) with uniform distribution of bits across the integers. This function is fitted on the number of optimal solutions of random instances with lengths between 10 and 20 integers and may be used as a heuristic either directly by new algorithms for the NPP or as a benchmark to evaluate how well different Evolutionary Algorithms (EAs) cover the search space. Despite the long history of the NPP, it seems such a characterization does not yet exist.
Original language | English |
---|---|
Title of host publication | GECCO '24 Companion |
Subtitle of host publication | Proceedings of the Genetic and Evolutionary Computation Conference Companion |
Publisher | Association for Computing Machinery, Inc |
Pages | 97-98 |
Number of pages | 2 |
ISBN (Electronic) | 9798400704956 |
DOIs | |
Publication status | Published - 2024 |
Event | 2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion - Melbourne, Australia Duration: 14 Jul 2024 → 18 Jul 2024 |
Conference
Conference | 2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion |
---|---|
Country/Territory | Australia |
City | Melbourne |
Period | 14/07/24 → 18/07/24 |
Bibliographical note
Publisher Copyright:© 2024 Copyright held by the owner/author(s).
Keywords
- combinatorial optimization
- number partitioning problem
- the easiest hard problem