Abstract

This paper describes the method that constructs low autocorrelation binary sequences (LABS) which have applications in various engineering domains. We use a meta-heuristic search approach employing local search method known as Tabu Search, which solves mathematical optimization problems. Our paper is an extension to the existing one [1]. We were able to achieve new optimal solutions with our improved algorithm (especially for instances greater than 60 and less than 101) to that of the previous method [1]. Instead of finding optimal solutions for odd skew- symmetric instances we found the optimal solutions for all the instances. We have conducted experiments over a large number of sequences thoroughly, for multiple times to ensure the results.

References

• J. E. Gallardo, C. Cotta, A. J. Fernandez, "Finding Low Autocorrelation Binary Sequences with Memetic Algorithms "
• Abhisek Ukil, "Low autocorrelation binary sequences: Number theory-based analysis for minimum energy level, Barker codes".
• J. E. Gallardo, C. Cotta, A. J. Fernandez, A Memetic algorithm for the low autocorrelation binary sequence problem, in: D. Thierens, et al. (Eds. ), 9th Annual Conference on Genetic and Evolutionary Computation (GECCO 2007), ACM Press, New York, USA, 2007, pp. 1226-1233.
• P. Moscato, Memetic algorithms: A short introduction, in: D. Corne, M. Dorigo, F. Glover (Eds. ), New Ideas in Optimization, McGraw-Hill, Maidenhead, Berkshire, England, UK, 1999, pp. 219-234.
• P. Moscato, C. Cotta, A gentle introduction to memetic algorithms, in: F. Glover, G. Kochenberger (Eds. ), Handbook of Metaheuristics, Kluwer Academic Publishers, Boston MA, 2003, pp. 105-144.
• W. E. Hart, N. Krasnogor, J. E. Smith, Recent Advances in Memetic Algorithms, Vol. 166 of Studies in Fuzziness and Soft Computing, SpringerVerlag, Berlin Heidelberg, 2005.
• N. Krasnogor, J. Smith, A tutorial for competent memetic algorithms: model, taxonomy, and design issues, IEEE Transactions on Evolutionary Computation 9 (5) (2005) 474-488.
• F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers, Boston, 1997.
• B. Militzer, M. Zamparelli, D. Beule, Evolutionary search for low auto correlated binary sequences, IEEE Transactions on Evolutionary Computation 2 (1) (1998) 34-39.
• M. J. E. Golay, The merit factor of long low autocorrelation binary sequences. IEEE Transactions on Information Theory 28 (3) (1982) 543-549.
• M. J. E. Golay, Sieves for low autocorrelation binary sequences, IEEE Transactions on Information Theory 23 (1) (1977) 43-51.
• S. D. Prestwich(2013), Improved Branch-and-Bound for Low Autocorrelation Binary Sequences, Annals of Operations Research
• Steven Halim, Roland H. C. Yap, and Felix Halim, Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem. Cp-2008, Sydney, Australia, September 14-18, 2008
• Jozef Kratica, An Electromagnetism-Like Approach for Solving the Low Autocorrelation Binary Sequence Problem, INT J COMPUT COMMUN, ISSN 1841-9836 Vol. 7 (2012), No. 4 (November), pp. 687-694
• Jozef Kratica, "a mixed integer quadratic programming model for the low autocorrelation binary sequence problem", Serdica J. Computing 6 (2012), 385–400.
• S. Mertens, Exhaustive search for low-autocorrelation binary sequences, Journal of Physics A: Mathematical and General 29 (1996) 473-481.
• J. Bernasconi, Low autocorrelation binary sequences: statistical mechanics and configuration state analysis, Journal de Physique 48 (4) (1987) 559- 567.
• Q. Wang, Optimization by simulating molecular evolution, Biological Cybernetics 57 (1987) 95-101.
• C. de Groot, D. WÄurtz, K. Ho®mann, Low autocorrelation binary sequences: Exact enumeration and optimization by evolutionary strategies, Optimization 23 (4) (1992) 369-384.
• A. Reinholz, Ein paralleler genetischer algorithms zur optimierung der binarien autocorrelations-function, Diploma Thesis. UniversitÄat Bonn (October 1993).
• S. Prestwich, Exploiting relaxation in local search, in: J. Pearson, M. Bohlin, M. Agren (Eds. ), 1st International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS 2004), Toronto, Canada, 2004, pp. 49-61.