An Electromagnetism-Like Approach for Solving the Low Autocorrelation Binary Sequence Problem


  • Jozef Kratica Mathematical Institute, Serbian Academy of Sciences and Arts Kneza Mihaila 36/III, 11 000 Belgrade, Serbia


low autocorrelation binary sequence problem, electromagnetism-like metaheuristic, combinatorial optimization


In this paper an electromagnetism-like approach (EM) for solving the low autocorrelation binary sequence problem (LABSP) is applied. This problem is a notoriously difficult computational problem and represents a major challenge to all search algorithms. Although EM has been applied to the topic of optimization in continuous space and a small number of studies on discrete problems, it has potential for solving this type of problems, since movement based on the attraction-repulsion mechanisms combined with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of the overall EM system.

Author Biography

Jozef Kratica, Mathematical Institute, Serbian Academy of Sciences and Arts Kneza Mihaila 36/III, 11 000 Belgrade, Serbia

Department of Mathematics and Computer Science


S.K. Barber, P. Soldate, E.H. Anderson, R. Cambie, W.R. McKinney, P.Z. Takacs, D.L. Voronov, V.V. Yashchuk, Development of Pseudorandom Binary Arrays for Calibration of Surface Profile Metrology Tools, Journal of Vacuum Science and Technology B: Microelectronics and Nanometer Structures, Vol.27, No.6, pp.3213-3219, 2009.

J. Bernasconi, Low Autocorrelation Binary Sequences: Statistical Mechanics and Conguration State Analysis, Journal Physique, Vol.48, pp.559-567, 1987.

S.I. Birbil, S.C. Fang, An Electromagnetism-like Mechanism for Global Optimization, Journal of Global Optimization, Vol.25, pp.263-282, 2003.

F. Brglez, X.Y. Li, M.F. Stallman, B. Militzer, Reliable Cost Prediction for Finding Optimal Solutions to LABS Problem: Evolutionary and Alternative Algorithms, Fifth International Workshop on Frontiers in Evolutionary Algorithms, Cary, NC, USA 2003.

A.V. Eremeev, C.R. Reeves, Non-parametric Estimation of Properties of Combinatorial Landscapes, Lecture notes on Computer Science, Vol.2279, pp.31-40, 2002.

F. Ferreira, J. Fontanari, P. Stadler, Landscape Sstatistics of the Low Autocorrelated Binary String Problem, Journal of Physics A: Mathematical and General, Vol.33, pp.8635-8647, 2000.

J.E. Gallardo, C. Cotta, A.J. Fernandez, Finding Low Autocorrelation Binary Sequences with Memetic Algorithms, Applied Soft Computing, Vol.9, No.4, pp.1252-1262, 2009.

R. Garello, N. Boujnah, Y. Jia, Design of Binary Sequences and Matrices for Space Applications, Proceedings of the 2009 International Workshop on Satellite and Space Communications - IWSSC'09, art. no. 5286416, pp.88-91, 2009.

M.J.E. Golay, The Merit Factor of Long Low Autocorrelation Binary Sequences, IEEE Transactions on Information Theory, Vol.28, pp.543-549, 1982.

S. Halim, R.H.C. Yap, F. Halim, Engineering Stochastic Local Search for the Low Autocorrelation Binary Sequence Problem, Lecture Notes in Computer Science, Vol.5202, pp.640-645, 2008.

B.W. Kernighan, S. Lin, An Efficient Heuristic Procedure for Partitioning Graphs, Bell System Technical Journal, pp.291-307, 1970.

S. Mertens, Exhaustive Search for Low-autocorrelation Binary Sequences, Journal of Physics A: Mathematical and General, Vol.29, pp.473-481, 1996.

S. Mertens, H. Bauke, Ground States of the Bernasconi Model with Open Boundary Conditions, Available online at

B. Militzer, M. Zamparelli, D. Beule, Evolutionary Search for Low Autocorrelated Binary Sequences, IEEE Transactions on Evolutionary Computation, Vol.2, pp.34-39, 1998.

S. Prestwich, Exploiting Relaxation in Local Search for LABS, Annals of Operations Research, Vol.156, pp.129-141, 2007.

A. Ukil, Low Autocorrelation Binary Sequences: Number Theory-Based Analysis for Minimum Energy Level, Barker codes, Digital Signal Processing: A Review Journal, Vol.20, No.2, pp.483-495, 2010.



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.