Finding low autocorrelation binary sequences with memetic algorithms |
| |
Authors: | Jos E. Gallardo, Carlos Cotta,Antonio J. Fern ndez |
| |
Affiliation: | aDepartamento de Lenguajes y Ciencias de la Computación. Universidad de Málaga, Campus de Teatinos, 29071 Málaga, Spain |
| |
Abstract: | 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 provides an analysis of different local search strategies, used as stand-alone techniques and embedded within memetic algorithms. One of our proposals, namely a memetic algorithm endowed with a Tabu Search local searcher, performs at the state-of-the-art, as it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature. Moreover, this algorithm is also able to provide new best-known solutions for large instances of the problem. In addition, a variant of this algorithm that explores only a promising subset of the whole search space (known as skew-symmetric sequences) is also analyzed. Experimental results show that this new algorithm provides new best-known solutions for very large instances of the problem. |
| |
Keywords: | Low autocorrelation binary sequences Memetic algorithms Tabu Search Combinatorial optimization |
本文献已被 ScienceDirect 等数据库收录! |
|