Low-Autocorrelation Binary Sequences: on the Performance of Memetic-Tabu and Self-Avoiding Walk Solvers

Search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence (labs) problem, represents a formidable computational challenge. In 2003, two stochastic solvers reported computational complexity of $O(1.423^L)$ and $O(1.370^L)$, refined to $O(1.5097^L)$ and $O(1.4072^L)$ for L odd in this paper. New experiments, with the solver from 2009, demonstrate (a) the asymptotic average-case performance of $114.515*1.3464^L$ for L even, and (b) the asymptotic average-case performance of $320.36*1.3421^L$ for L odd. To mitigate the computational constraints of the labs problem, we consider solvers that accept odd values of L and return solutions for skew-symmetric binary sequences only - with the consequence that not all best solutions under this constraint will be optimal. We have analyzed three solvers. Two solvers are based on the version from 2009: the first uses an evolutionary algorithm to initialize the tabu search, the second initializes the tabu search with a random binary sequence. The asymptotic average-case performance of these two solvers are statistically equivalent: for the range 71 <= L <= 127 we observe $150.49*1.1646^L$ for the memetic-tabu version and $156.34*1.1646^L$ for the random-tabu version. Thus, for the labs problem, the evolutionary component of the first solver is not effective. Our solver relies on a single contiguous self-avoiding walk until memory constraints induce random restarts. Under random restarts, the solver reaches the target value with a number of independent contiguous self-avoiding walk segments. Under the fixed walk segment compromise and random restarts, we observe $650.07*1.1435^L$ for the range 71 <= L <= 127. We show that the solver with the best asymptotic average-case performance has the best chance of finding new solutions that significantly improve, as L increases, figures of merit reported to date.