E V O L U T I O N A R Y   S E A R C H   F O R   L O W   A U T O C O R R E L A T E D   S E Q U E N C E S


The search for low autocorrelated binary sequences (LABS) is a classic optimization problem for binary sequences. Competing requirements to reduce different autocorrelation functions lead to a high degree of frustration (in the sequence search space but also in humans). The fitness landscape of the binary sequences has been compared to a golf course with many local minima spaced far apart.

We have applied evolutionary strategies to optimize binary sequences of different length L, and developed a novel mutation operator for this fitness landscape using a preselection scheme. For details please read our article. In 1996, when Dieter Beule, Michele Zamparelli, and I worked together on this project, our best sequence of length L=100 with fitness 7.84 set a new record:

Since then computers are much faster and many of our results have been improved. An up to date list of of the current records can be obtained here. The table below shows the best sequences we found in 1996 with our evolutionary strategy based on the preselective mutation operator.

In a more recent article, F. Brglez, X.Y. Li, M.F. Stallmann, and I, analyzed how the computational cost to find the optimal sequence scales as a function of L. First, we showed that the search time to find the optimum for a given L is distributed exponentially. Therefore the average search time is well a defined quantity. Using the known optimal sequences for L<60, we could show that

< CPU time > = c * AL

Where c and A depend on the particular search algorithm. c also depends on the CPU speed and on the implementation of the algorithm, while A does not! A is more important parameter since it dominates cost for large L. Different search algorithms can have very different scaling properties as the following comparison shows,

A
Algorithm
Type
2.00 Simple exhaustive search exact
1.85 Branch-and-bound algorithm by Mertens exact
1.65 Stochastic search by Golay stochastic
1.4 +- 0.1 Kernighan Lin type solver by Brglez, Li and Stallmann stochastic
1.4 +- 0.1 Evolution strategy with preselection by Militzer, Zamparelli, and Beule stochastic

Our analysis could not destiguish A for the last two algorithms with the error bars. However, for small L, KL was faster because of a smaller c factor.

In conclusion, stochastic algorithms are found to be much more efficient because they avoid searching the complete sequences space but still find the optimum. How exactly so many sequences are left out is often not clear. However, using a scaling analysis, one can terminate such a stochastic algorithm so that the optimal sequence has been found with a arbitrary probability.

Optimal sequences from our article:
L=81
F=8.20		 - + - + - - + - - + - + - + + + + + - + + - - + - - - + - - - - + + + - + + - + + - - - + + + - + + - + - - - + - - - + + - - - + - + - - - - - - + + + - - - - -
L=91
F=8.68		 + + - + + - + + + + - + + + + + + - + - - + + - + - - + - + - + - - + - + + + - - + - - + + - - + + + - - + - - - - + + + + + + + - - - - + + - - - - + - + - + + + - + - - - + + + -
L=99
F=8.49		 - - - - - + + - - - - - + + + + + - - + - - + + - + + - - - - - - - - - - + + + - + - - + + - - - - + - + + - - + + + + - + + - + - + - + - + - - + + + - - + + + - - + - + - - + - + - - + + - + - +
L=100
F=7.84		 - - + + - - + + - + + + - + + + - + + + + + + - + + + - + - + + - - - + - + + - + - - - + - + + + - - - + + + - + - + - - + - - - - + + + - - + - + + - + + + + - - - - - - - + + - + + + + - - + - + -
L=101
F=8.82		 - - - - - - + + - - - - - + + + + + - - + - - + + - + + - - - - - - - - - - + + + - + - - + + - - - - + - + + - - + + + + - + + - + - + - + - + - - + + + - - + + + - - + - + - - + - + - - + + - + - + -
L=103
F=9.56		 - - + + + + - - - - - + + - - - - - - + + + + + + + + - + + - - + + - - + - - - + - + - - + + - - - - - + - + - - + + - - - - - + - - - + + - - + + - - - + - + - + - + + - + - + - - + + - + - + + - + - - +
L=105
F=8.78		 + - + + - + - - + - - - - - + - - + + + + + + - + + + - + - - + - - + - + - + - - + - - + - - - + + - - + + - - + + - + + + - - - + + + + + + + - - - + + + + - + + + - + - + - - + + + - + - + + + - - - - + + +
L=107
F=8.46		 - + + - - + - + - + - - + - - - - + - + - + - + + - + + + + + + - - + + - + - - - - + - - + - - + - + + - - + + - - - - + + + - - - + - + + + + - - + + - + - + - - - + + + + + + + + - + - - - + + + + + + + - - + +
L=109
F=8.97		 + - + + - + + - + - - - - - - - - + + - + - - + - - - - + - + + + + + + + - + + - + + - - + + - - + + - + - + + + + + - - + + - - + + - - - + + + - + - + - + + + + - + - - - + + + + - - + - + - + - + + + + - - - + + +
L=111
F=8.97		 - - + - + - + + + - - + + + - - - + + + - + + + - - + - + - + - - - + + + + + - + - - - - + + - + - - - + + + - - + - - + - - - - + + - + - - - - + - + - - + - - - - - - - + + - + + + - + + - + + - + + - - + - - - - - - +
L=113
F=8.49		 + - + - - + - + - - + - + - - + - + - - - + + - - - + - + + - - - + + + - - - + + - + - + - + - + - + - - - + + - - + + - + + + + + + + + + + + + - - + - - + - - + - - + + + + - + + - - + - - - - - + + + + + - - - - - + + + +
L=115
F=8.88		 + - + - + + - + - + + + + + - + + - + - + + + - + - - + - + - - + - - - - - + + - - - - + - - - + + + - - + + - - + + - - + + - - + - - + - - - + - + + - - + - + - - - + + + + + - - - - + - - - - - + + + - + - + + + + + - - - - -
L=117
F=8.71		 - - - + + + + + + + - + - - - - - - - + + + - + + - + - + + - - + - + - + - - - + + + - - + + - - + + + + - - + + + + - + - - + + - + - - + + - - + + - + + - + + + + + + + - - + + + + + - - - + - - + - + - + - - - - + - + - + - - + -
L=119
F=8.02		 + + + + - - + - + + - + + - + - + + + - + + - + - + + - - - + - - - + + - - - + + - + - + - - - - - + + - - - + - + - + + + + + + - + + - - + - + - - - - - - + + - + + - - + - - - + - - + + + + + - - - + - - - - - + + + - - - - + + - + -
L=121
F=8.67		 + + + + + + + + + - + - - - - - - - - - + - + + + - - - - + + - + - - - + + - + + - - - + - + + - + + - + + - - + + + - - + + - + + - - + + + - - - + + + + - + + - - - + + - + + + + - - + - + + - + + + + - + - + - + - + + + + - + - + - + - +
L=141
F=8.83		 - + - + - + - + + - + - + - + + - + - + - + + + - - - + + + + - - - + - + + + - - - + - + + + - + - - + + - + + + + - - + + - + + - + + - - + + - - + + + - - - + + - - + - + + + - - + + + + - + + + + - + + - + + + + - + + - + - - + - - + - - - - - - - + + + + + + + - - - - - - - -
L=161
F=8.39		 - + - - + - - + - + + - + + - - - - - - - - - - - - + - - - + - - + - + + - + + - + + - - - + - - + - + - - + + + - + + + - - + + - + - + + - + - + - - - - + + - - + + - + - - - - - - + + + + + - - + + - + + + - + + - - - - - + + + - + + - - - + + + - - - - + + + - + + + - + - + - + - + - + - - + + + - - - - + + + - - -
L=181
F=7.75		 + - + + - - + + - + + - + + + + + + + + + + - + + - + - - + + - + + - + + + - - + - + - - - - + - + - - - + + - + + + + - + + - + + - - + + - + - - - - + - - + - + - - + - + + + + + - + - + + + + - - - - - + + + - + - - - - + + - - + + + - - - + - + + + - - + - - - - - + - + + + + + - - + - - - + + + - - + + + + - - - + - + - + - + - + + + - - - + + - - + + +
L=201
F=7.46		 + + + + + + - - + + + - - - + - - - + + + - + + + - + + + - - - + + - + - + - + - - + + + - - - - + - - - - + + + - + - - + + + + - - - - - + - + - - - - + + + + - - - + + - + + - + - + - - - + + - + + - - - + + - + + + + + + - - - + + - + + - + - - + - + + + + + - + - + + - + - - + + + + - + + - + - - - + - + + - + + - - - - - - - - + + - + + - + + + - + + + - + + - + + + - + + - + + - - + - + - +




Last updated 09-03-03.