The easiest hard problem: now even easier

Horn, Ruben; Thomson, Sarah L.; Berg, Daan van den; Adriaans, Pieter

doi:10.1145/3638530.3664099

The easiest hard problem: now even easier

Publication date

2024-08-01

Document type

Konferenzbeitrag

Author

Horn, Ruben

Thomson, Sarah L.

Berg, Daan van den

Adriaans, Pieter

Organisational unit

High Performance Computing

DOI

10.1145/3638530.3664099

URI

https://openhsu.ub.hsu-hh.de/handle/10.24405/22899

Conference

Genetic and Evolutionary Computation Conference (GECCO 2024) ; Melbourne, Australia (hybrid) ; July 14–18, 2024

Publisher

ACM

Book title

GECCO '24 companion : proceedings of the Genetic and Evolutionary Computation Conference Companion

First page

97

Last page

98

Part of the university bibliography

✅

Language

English

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.

Version

Published version

Access right on openHSU

Metadata only access