Ruben Horn
The Easiest Hard Problem: Now Even Easier
Horn, Ruben; Thomson, Sarah L; van den Berg, Daan; Adriaans, Pieter
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.
Citation
Horn, R., Thomson, S. L., van den Berg, D., & Adriaans, P. (2024, July). The Easiest Hard Problem: Now Even Easier. Presented at ACM Genetic and Evolutionary Computation Conference (GECCO) 2024, Melbourne, Australia
Presentation Conference Type | Conference Abstract |
---|---|
Conference Name | ACM Genetic and Evolutionary Computation Conference (GECCO) 2024 |
Start Date | Jul 14, 2024 |
End Date | Jul 18, 2024 |
Acceptance Date | May 2, 2024 |
Online Publication Date | Aug 1, 2024 |
Publication Date | 2024 |
Deposit Date | May 3, 2024 |
Publicly Available Date | Aug 1, 2024 |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Not Peer Reviewed |
Pages | 97-98 |
Book Title | Proceedings of the Genetic and Evolutionary Computation Conference Companion |
DOI | https://doi.org/10.1145/3638530.3664099 |
Keywords | The Easiest Hard Problem, Number Partitioning Problem, Combinatorial Optimization |
Files
The Easiest Hard Problem: Now Even Easier (accepted version)
(458 Kb)
PDF
You might also like
Channel Configuration for Neural Architecture: Insights from the Search Space
(2023)
Presentation / Conference Contribution
From Fitness Landscapes to Explainable AI and Back
(2023)
Presentation / Conference Contribution
Randomness in Local Optima Network Sampling
(2023)
Presentation / Conference Contribution
Universally Hard Hamiltonian Cycle Problem Instances
(2022)
Presentation / Conference Contribution
The Opaque Nature of Intelligence and the Pursuit of Explainable AI
(2023)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search