Article

A memetic algorithm for the low autocorrelation binary sequence problem

Authors:

Jose E. Gallardo,

Antonio J. FernandezAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1226 - 1233

https://doi.org/10.1145/1276958.1277195

Published: 07 July 2007 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[15]

P. Moscato. Memetic algorithms: A short introduction. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 219--234. McGraw-Hill, Maidenhead, Berkshire, England, UK, 1999.

Digital Library

[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.

Cited By

Biełaszek SPiętak KKisiel-Dorohinicki M(2022)Reproduction operators in solving LABS problem using EMAS meta-heuristic with various local optimization techniquesJournal of Information and Telecommunication10.1080/24751839.2022.21180987:1(29-43)Online publication date: 30-Sep-2022
https://doi.org/10.1080/24751839.2022.2118098
Żurek DPietroń MPiętak KKisiel-Dorohinicki M(2022)A Deep Neural Network as a TABU Support in Solving LABS ProblemComputational Science – ICCS 202210.1007/978-3-031-08754-7_32(237-243)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-031-08754-7_32
Zhang MZhou ZYang MLiu ZYang Y(2021)A hybrid algorithm for the search of long binary sequences with low aperiodic autocorrelationsSoft Computing10.1007/s00500-021-06084-7Online publication date: 11-Aug-2021
https://doi.org/10.1007/s00500-021-06084-7
Show More Cited By

Index Terms

A memetic algorithm for the low autocorrelation binary sequence problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Stochastic control and optimization

Recommendations

Finding low autocorrelation binary sequences with memetic algorithms

This paper deals with the construction of binary sequences with low autocorrelation, a very hard problem with many practical applications. The paper analyzes several metaheuristic approaches to tackle this kind of sequences. More specifically, the paper ...
Memetic algorithm with route decomposing for periodic capacitated arc routing problem

Graphical abstractDisplay Omitted HighlightsWe solve the Periodic Capacitated Arc Routing Problem (PCARP).We propose a problem-specific Route Decomposition (RD) operator for minimizing the two objectives of PCARP simultaneously.A Memetic Algorithm with ...
A low-level hybridization between memetic algorithm and VNS for the max-cut problem
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

The Max-Cut problem consists of finding a partition of the graph nodes into two subsets, such that the sum of the edge weights having endpoints in different subsets is maximized. This NP-hard problem for non planar graphs has different applications in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
333
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Biełaszek SPiętak KKisiel-Dorohinicki M(2022)Reproduction operators in solving LABS problem using EMAS meta-heuristic with various local optimization techniquesJournal of Information and Telecommunication10.1080/24751839.2022.21180987:1(29-43)Online publication date: 30-Sep-2022
https://doi.org/10.1080/24751839.2022.2118098
Żurek DPietroń MPiętak KKisiel-Dorohinicki M(2022)A Deep Neural Network as a TABU Support in Solving LABS ProblemComputational Science – ICCS 202210.1007/978-3-031-08754-7_32(237-243)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-031-08754-7_32
Zhang MZhou ZYang MLiu ZYang Y(2021)A hybrid algorithm for the search of long binary sequences with low aperiodic autocorrelationsSoft Computing10.1007/s00500-021-06084-7Online publication date: 11-Aug-2021
https://doi.org/10.1007/s00500-021-06084-7
Biełaszek SPiętak KKisiel-Dorohinicki M(2021)New Extensions of Reproduction Operators In solving LABS Problem Using EMAS Meta-HeuristicComputational Collective Intelligence10.1007/978-3-030-88081-1_23(304-316)Online publication date: 30-Sep-2021
https://doi.org/10.1007/978-3-030-88081-1_23
Russek PJamro EDąbrowska-Boruch AWiatr K(2019)A study of the loops control for reconfigurable computing with OpenCL in the LABS local search problemThe International Journal of High Performance Computing Applications10.1177/1094342019868515(109434201986851)Online publication date: 12-Aug-2019
https://doi.org/10.1177/1094342019868515
Mow WDu KWu W(2015)New evolutionary search for long low autocorrelation binary sequencesIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2014.13051851:1(290-303)Online publication date: Jan-2015
https://doi.org/10.1109/TAES.2014.130518
Leukhin APotekhin E(2014)Exhaustive Search for Optimal Minimum Peak Sidelobe Binary Sequences up to Length 80Sequences and Their Applications - SETA 201410.1007/978-3-319-12325-7_14(157-169)Online publication date: 18-Nov-2014
https://doi.org/10.1007/978-3-319-12325-7_14
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Ukil A(2010)Low autocorrelation binary sequencesDigital Signal Processing10.1016/j.dsp.2009.08.00320:2(483-495)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.dsp.2009.08.003
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents