Imagen de Portada
Código QR

LOW AUTO-CORRELATION BINARY SEQUENCES EXPLORED USING WARNING PROPAGATION.

The search for binary sequences with low auto-correlations (LABS) is a computationally hard discrete combinatorial optimization problem. We analyze two physically inspired algorithms to explore the low energy space of this model. The greedy, T = 0, Monte Carlo (MC) method gets trapped into the expon...

Descripción completa

Publicado en:Revista Cubana de Física Vol. 38; no. 1; pp. 25 - 32
Autores principales: MARTÍNEZ-DURIVE, O. E., KOTSIREAS, I., MULET, R., LAGE-CASTELLANOS, A.
Formato: Artículo
Publicado: Universidad de La Habana jul2021
Materias:
Binary sequences
Combinatorial optimization
Warnings
Algorithms
Acceso en línea:Ver este registro en EBSCOhost
Sumario:The search for binary sequences with low auto-correlations (LABS) is a computationally hard discrete combinatorial optimization problem. We analyze two physically inspired algorithms to explore the low energy space of this model. The greedy, T = 0, Monte Carlo (MC) method gets trapped into the exponentially many 1-Spin-Flip stable configurations, that are typically low in energy, but still far from the global optimum. The more elaborated Warning Propagation (WP) algorithm also gets trapped into local minima. However, these local minima, are more stable to spin flips than the ones obtained by the greedy MC. We also compare the behavior of both algorithms in randomized versions of LABS, showing that the low energy space of the 4-Spin model is easier to explore than the one of LABS.
La búsqueda de Secuencias Binarias de Baja Autocorrelación (LABS) es un problema de optimización combinatoria difícil. Analizamos dos algoritmos inspirados en la física para explorar el espacio de bajas energías de este modelo. El algoritmo de Monte Carlos (MC) a T = 0 queda atrapado entre la cantidad exponencial de estados semi-estables que se encuentran en la región de bajas energías pero lejos del mínimo global. El algoritmo de Warning propagation (WP), más elaborado que MC, también queda atrapado en esta región. No obstante los estados de baja energía que se obtienen con WP son más estables que los obtenidos por MC. Además comparamos el comportamiento de ambos algoritmos en versiones aleatorizadas de este modelo, mostrando que la región de baja energía del 4-Spin es más fácil de explorar que en LABS.