Performance analysis of randomised search heuristics is a rapidly growing field. The focus of this paper is on the solution quality an optimisation heuristic achieves, not on the time it takes to reach it.
Performance analysis of all kinds of randomised search heuristics is a
rapidly growing and developing field. Run time and solution quality are two
popular measures of the performance of these algorithms. The focus of this
paper is on the solution quality an optimisation heuristic achieves, not on the
time it takes to reach this goal, setting it far apart from runtime analysis.
We contribute to its further development by introducing a novel analytical
framework, called unlimited budget analysis, to derive the expected fitness
value after arbitrary computational steps. It has its roots in the very
recently introduced approximation error analysis and bears some similarity to
fixed budget 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 pseudo-Boolean functions for unlimited
budget analysis and compare them to results derived within the fixed budget
framework for the same algorithms and functions. There are also results of
experiments to compare bounds obtained in the two different frameworks with the
actual observed performance. The study show that unlimited budget analysis may
lead to the same or more general estimation beyond fixed budget.