Effective energy recomputation for low autocorrelation binary sequence problem

Hulianytskyi L., Sokol V.

Int. J. "Information Theories and Applications". – 2011. – 18, N. 4.– P. 344–357.


This paper deals with finding low autocorrelation binary sequences which is a hard combinatorial optimization problem. Recent developments in this area analyzed, in order to understand characteristics of a problem. Emphasis is put on effective energy recomputation operators. Different types of these operators are tested to achieve full picture of LABS solvers development process. It is shown that latest state-of-the-art metaheuristics in fact all based on simplest Tabu Search framework, achieving performance boost by means of energy recomputation operators’ optimization. In this paper we construct variation of memetic algorithmincorporating latest developments to reach higher performance than it’s original. Comparison to a state-of-the-art TSv7 approach completed on instances with known optimums as well as on some unsolved larger ones. It is concluded that these approaches shows similar performance as they both have the same built-in heuristic. As further research proposed a comparison of different metaheuristic frameworks applied to this problem.

Ключові слова: combinatorial optimization, low autocorrelation binary sequences, memetic algorithm,stochastic local search, tabu search.

Завантажити файл публікації