An Electromagnetism-Like Approach for Solving the Low Autocorrelation Binary Sequence Problem
Keywords:
low autocorrelation binary sequence problem, electromagnetism-like metaheuristic, combinatorial optimizationAbstract
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.
References
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. http://dx.doi.org/10.1116/1.3245997
J. Bernasconi, Low Autocorrelation Binary Sequences: Statistical Mechanics and Conguration State Analysis, Journal Physique, Vol.48, pp.559-567, 1987. http://dx.doi.org/10.1051/jphys:01987004804055900
S.I. Birbil, S.C. Fang, An Electromagnetism-like Mechanism for Global Optimization, Journal of Global Optimization, Vol.25, pp.263-282, 2003. http://dx.doi.org/10.1023/A:1022452626305
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. http://dx.doi.org/10.1007/3-540-46004-7_4
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. http://dx.doi.org/10.1088/0305-4470/33/48/304
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. http://dx.doi.org/10.1016/j.asoc.2009.03.005
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. http://dx.doi.org/10.1007/978-3-540-85958-1_57
B.W. Kernighan, S. Lin, An Efficient Heuristic Procedure for Partitioning Graphs, Bell System Technical Journal, pp.291-307, 1970. http://dx.doi.org/10.1002/j.1538-7305.1970.tb01770.x
S. Mertens, Exhaustive Search for Low-autocorrelation Binary Sequences, Journal of Physics A: Mathematical and General, Vol.29, pp.473-481, 1996. http://dx.doi.org/10.1088/0305-4470/29/18/005
S. Mertens, H. Bauke, Ground States of the Bernasconi Model with Open Boundary Conditions, Available online at http://odysseus.nat.uni-magdeburg.de/~mertens/bernasconi/open.dat
B. Militzer, M. Zamparelli, D. Beule, Evolutionary Search for Low Autocorrelated Binary Sequences, IEEE Transactions on Evolutionary Computation, Vol.2, pp.34-39, 1998. http://dx.doi.org/10.1109/4235.728212
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.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
