List-Based Optimisers: Experiments and Open Questions

List-Based Optimisers

Most stochastic optimisers make use of a coded random number generator (RNG), like KISS ( Marsaglia & Zaman, 1993 ), or Mersenne-Twister ( Matsumoto & Nishimura, 1998 ), or those that are embedded in a language like C. As these are not based on a hardware system, they are in fact deterministic, at least if we always use the same seed. They generate a long list of pseudo-random numbers (typically in ), whose length is ideally far bigger than what is needed to solve a problem, even if the algorithm is executed several times. In such a case all runs are different, in the hope that it improves the probability of finding a good solution.

So, we can, in fact, assume that we have a predefined list of numbers in , say . During the optimisation process, whenever we need a “random” number, we pick it up sequentially and cyclically in , i.e., for the -th random number we pick . In order to avoid any confusion with true random numbers, from now on we will call these l-random numbers. The idea here is to reduce the length of the list as much as possible, and simultaneously, to improve the performance. So, we will speak of a List-Based Optimiser (LBO) only when L is relatively small (typically at most one hundred l-random numbers for a 30D problem).