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...
| Published in: | Revista Cubana de Física Vol. 38; no. 1; pp. 25 - 32 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Published: |
Universidad de La Habana
jul2021
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=lth&AN=151921573&site=ehost-live header: @attributes: shortDbName: lth uiTerm: 151921573 longDbName: MedicLatina uiTag: AN controlInfo: bkinfo: jinfo: jid: 02539268 UEW jtl: Revista Cubana de Física issn: 02539268 maglogo: N pubinfo: dt: jul2021 vid: 38 iid: 1 pid: 21208 pub: Universidad de La Habana artinfo: ui: 151921573 ppf: 25 ppct: 7 formats: fmt: @attributes: type: P size: 827KB tig: atl: LOW AUTO-CORRELATION BINARY SEQUENCES EXPLORED USING WARNING PROPAGATION. aug: au: MARTÍNEZ-DURIVE, O. E. KOTSIREAS, I. MULET, R. LAGE-CASTELLANOS, A. affil: Group of Complex Systems and Statistical Physics, Physics Faculty, University of Havana, Cubay Wilfrid Laurier University, Waterloo, Canada su: Binary sequences Combinatorial optimization Warnings Algorithms sug: subj: Binary sequences Combinatorial optimization Warnings Algorithms ab: 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. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y custom: Copyright of Revista Cubana de Física is the property of Universidad de La Habana and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. item: Revista Cubana de Física holder: Universidad de La Habana dt: @attributes: year: 2021 holdings: @attributes: islocal: N |
|---|