Stochastic Optimisation—When a Poor Pseudo-Random Number Generator Is Better

In global optimisation, the conventional approach is to use a stochastic algorithm based on a pseudo-random number generator (PRNG). Such a generator, together with its seed, produces a sequence of numbers that is sufficiently long for no cycle to be encountered during a typical run. However, when objective-function evaluations are costly, other approaches may be preferable. The list-based one not only uses much shorter sequences, which are repeated cyclically, but can also sometimes achieve equivalent or even better results with a smaller evaluation budget. As a proof of concept, we consider GA-MPC, the winner of the CEC 2011 competition, and define LB-GA-MPC, a deterministic, list-based version of this algorithm. We apply it to a few problems from the competition benchmark. For every problem considered, there is at least one list length for which LB-GA-MPC outperforms GA-MPC, in some cases by a substantial margin.