Generating functions and the performance of backtracking adaptive search (Q995932)

Backtracking adaptive search (BAS) has been introduced in the paper by \textit{G. R. Wood, D. W. Bulger, W. P. Baritompa} and \textit{D. L. J. Alexander} [J. Optim. Theory Appl. 128, No. 3, 547--562 (2006; Zbl 1112.90105)] and used in [\textit{G. R. Wood, D. L. J. Alexander D. W. Bulger}, J. Global Optim. 22, No. 1-4, 271--284 (2002; Zbl 1045.90041)] as an initial model for the study of the convergence behaviour of stochastic global optimisation algorithms. BAS is a simplified stochastic optimisation procedure which permits the acceptance of worsening objective function values. In this paper the authors develop tools to examine the performance of BAS. Specifically, they consider and link three performance measures: the distribution of objective function values at a given iteration, the probability that the algorithm has reached a pre-set level (the success rate) at a given iteration, and the distribution of the number of iterations until a present level is reached. This work computes a number of generating functions using a formal power series approach. These generating functions are used to examine the performance of BAS. Examples are given to illustrate the use of this methodology.