Affine OneMax
This work provides a tunable benchmark for evaluating optimization algorithms, but it is incremental as it builds on existing OneMax functions.
The paper introduces Affine OneMax (AOM) functions as a new class of test functions for black box optimization, achieving tunable complexity with an upper bound on black box complexity as a polynomial in dimension, supported by experimental results.
A new class of test functions for black box optimization is introduced. Affine OneMax (AOM) functions are defined as compositions of OneMax and invertible affine maps on bit vectors. The black box complexity of the class is upper bounded by a polynomial of large degree in the dimension. The proof relies on discrete Fourier analysis and the Kushilevitz-Mansour algorithm. Tunable complexity is achieved by expressing invertible linear maps as finite products of transvections. The black box complexity of sub-classes of AOM functions is studied. Finally, experimental results are given to illustrate the performance of search algorithms on AOM functions.