Anytime Benchmarking of Forty-Five PAES-25 Configurations on Multi- and Many-Objective Variants of Leading Ones Trailing Zeros Functions

The Leading Ones Trailing Zeros (LOTZ) benchmark is a well-established bi-objective pseudo-Boolean function (of scalable size) that has both a linear-sized Pareto front and also a front that is ‘far away’ from a random solution. As such it is a useful function for understanding the behaviour of multi-objective optimisation algorithms, especially regarding their ability to approach the front and expand and maintain solutions all along it. It has contributed to both algorithm design and theoretical analysis. In this article, we make use of three variants of LOTZ, recently introduced, which generalised it to the many-objective case in different ways while aiming to maintain similar properties of the original. We add further detail to the mathematical description of the benchmarks and use them to analyse the performance of a simple multi-objective local search algorithm (PAES-25) (based on (1+1)-PAES) with plug-in modules for archiving, neighbourhood, selection method (from the archive or not) and acceptance function. We measure the anytime performance of PAES-25 in different variants by observing a suite of online measures that give an insight into the dynamics of the algorithm and provide guidance as to choice of configuration depending on factors such as time available and size of Pareto approximation set desired. We believe that the benchmarks and the anytime, multi-dimensional methods used for analysis might motivate further theory (especially of many-objective optimisation and archiving) and may also contribute usefully to algorithm design ideas.