Download:
[PostScript] [PDF]

Titel:
Landscape statistics of the low autocorrelated binary string problem

Author(s):
Fernando F. Ferreira, José F.\ Fontanari, Peter F. Stadler

Submitted to:
J. Phys. A: Math. Gen.

Abstract:
The statistical properties of the energy landscape of the low autocorrelated binary string problem (LABSP) are studied numerically and compared with those of several classic disordered models. Using two global measures of landscape structure which have been introduced in the Simulated Annealing literature, namely, depth and difficulty, we find that the landscape of LABSP, except perhaps for a very large degeneracy of the local minima energies, is qualitatively similar to some well-known landscapes such as that of the mean-field 2-spin glass model. Furthermore, we consider a mean-field approximation to the pure model proposed by Bouchaud and Mézard (1994, J. Physique I France 4 1109) and show both analytically and numerically that it describes extremely well the statistical properties of LABSP.

Keywords: Landscapes, Low autocorrelated binary string problem, Depth and Difficulty of Landscapes, Metastable States
PACS Numbers 75.10.Nr, 05.50.+q, 64.60.Cn

Return to 2000 working papers list.