A memetic algorithm for the low autocorrelation binary sequence problem

ABSTRACT

Finding binary sequences with low auto correlation is a very hard problem with many practical applications. In this paper we analyze several meta heuristic approaches to tackle the construction of this kind of sequences. We focus on two different local search strategies, steepest descent local search (SDLS) and tabu search (TS), and their use both as stand-alone techniques and embedded within a memetic algorithm (MA). Plain evolutionary algorithms are shown to perform worse than stand-alone local search strategies. However, a MA endowed with TS turns out to be a state-of-the-art algorithm: it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature.

REFERENCES

• 1: J. Bernasconi. Low autocorrelation binary sequences: statistical mechanics and con?guration state analysis. J. Physique, 48:559--567, 1987.
• 2: F. Brglez, X. Y. Li, M. F. Stallman, and B. Militzer. Reliable cost prediction for ?nding optimal solutions to labs problem: Evolutionary and alternative algorithms. In Fifth International Workshop on Frontiers in Evolutionary Algorithms, Cary, NC, USA, 2003.
• 3: C. deGroot, D. Würtz,and K. Hoffmann. Low autocorrelation binary sequences: exact enumeration and optimization by evolutionary strategies. Optimization, 23:369--384, 1992.
• 4: V. de Oliveira, J. Fontanari, and P. Stadler. Metastable states in high order short-range spin glasses. J. Phys. A: Math. Gen., 32:8793--8802, 1999.
• 5: I. Dotú and P. V. Hentenryck. A note on low autocorrelation binary sequences. In F. Benhamou, editor, 12th International Conference on Principles and Practice of Constraint Programming (CP 2006), volume 4204 of Lecture Notes in Computer Science, pages 685--689, Nantes, France, September 2006. Springer.
• 6: F. Ferreira, J. Fontanari, and P. Stadler. Landscape statistics of the low autocorrelated binary string problem. J. Phys. A: Math. Gen., 33:8635--8647, 2000.
• 7: M. Golay. Sieves for low autocorrelation binary sequences. IEEE Transactions on Information Theory, 23:43--51, 1977.
• 8: M. J. E. Golay. The merit factor of long low auto correlation binary sequences. IEEE Transactions on Information Theory, 28(3):543--549, 1982.
• 9: W. E. Hart, N. Krasnogor, and J. E. Smith (eds.). Recent Advances in Memetic Algorithms, volume 166of Studies in Fuzziness and Soft Computing. Springer, 2004.
• 10: N. Krasnogor and J. Smith. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, 9(5):474--488, 2005.
• 11: J. Lindner. Binary sequences up to length 40 with best possible autocorrelation function. Electron. Lett., 11:507, 1975.
• 12: S. Mertens. Exhaustive search for low-auto correlation binary sequences. J. Phys. A: Math. Gen., 29::473--481, 1996.
• 13: S. Mertens and H. Bauke. Ground states of the bernasconi model with open boundary conditions. Available on line in http://odysseus.nat.uni-magdeburg.de/~mertens/bernasconi/open.dat, November 2004.
• 14: B. Militzer, M. Zamparelli, and D. Beule. Evolutionary search for low autocorrelated binary sequences. IEEE Transactions on Evolutionary Computation, 2(1):34--39, 1998.
• 15: Pablo Moscato, Memetic algorithms: a short introduction, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 16: S. Prestwich. A hybrid local search for low autocorrelation binary sequences. Technical Report TR0001, Department of Computer Science, National University of Ireland, Cork, Ireland, 2000.
• 17: P. Stadler. Landscapes and their correlation functions. J. Math. Chem., 20(1--45), 1996.
• 18: R. Turyn. Sequences with small correlation. In H. Mann, editor, Error Correcting Codes, pages 195--228. Wiley, New York, 1968.
• 19: R. Turyn and J. Storer. On binary sequences. Proc. Amer. Math. Soc., 12:394--399, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

General Terms:
Algorithms, Experimentation

Keywords:
autocorrelation binary sequences, memetic algorithms, tabu search