Reliable Cost Predictions for Finding Optimal Solutions to LABS Problem: Evolutionary and Alternative Algorithms
F. Brglez, Xiao Yu Li, Matthias F. M. Stallmann, Burkhard Militzer · 2003
The low-autocorrelation binary sequence (LABS) problem represents a major challenge to all search algorithms, with the evolutionary algorithms claiming the best results so far. However, the termination criteria for these types of stochastic algorithms are not well-defined and no claims have been made about optimality. Our approach to find the optima of the LABS problem is based on (1) experiments with problem sizes for which optimal solutions are known, (2) an asymptotic analysis of statistics generated by such experiments, (3) reliable predictions of the cost required to find optimal solutions for larger problem sizes. The proposed methodology provides a well-defined termination criterion for evolutionary and alternative search algorithms alike.