Unlimited budget analysis
Jun He, Thomas Jansen, Christine Zarges · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2019
Performance analysis of randomised search heuristics is a rapidly growing and developing field. We contribute to its further development by introducing a novel analytical perspective that we call unlimited budget analysis. It has its roots in the very recently introduced approximation error analysis and bears some similarity to fixed budget analysis. The focus is on the progress an optimisation heuristic makes towards a set goal, not on the time it takes to reach this goal, setting it far apart from runtime analysis. We present the framework, apply it to simple mutation-based algorithms, covering both, local and global search. We provide analytical results for a number of simple example functions for unlimited budget analysis and compare them to results derived within the fixed budget framework for the same algorithms and functions.