Document 
Eur. Phys. J. B 44, 317-326 (2005)
DOI: 10.1140/epjb/e2005-00131-6
Comparing extremal and thermal explorations of energy landscapes
S. Boettcher1 and P. Sibani21 Physics Department, Emory University, Atlanta, Georgia 30322, USA
2 Theoretical Physics, Oxford University, 1 Keble Rd, Oxford OX1 3NP, UK
sboettc@emory.edu
(Received 23 June 2004 / Received in final form 8 December 2004 / Published online 28 April 2005)
Abstract
Using a non-thermal local search, called Extremal Optimization (EO),
in conjunction with a recently developed scheme for classifying the
valley structure of complex systems, we analyze a short-range spin
glass. In comparison with earlier studies using a thermal algorithm
with detailed balance, we determine which features of the landscape
are algorithm dependent and which are inherently geometrical.
Apparently a characteristic for any local search in complex energy
landscapes, the time series of successive energy records found by EO
is also characterized approximately by
a Poisson statistic with logarithmic time arguments.
Differences in the results provide additional insights into the
performance of EO. In contrast with a thermal search, the extremal
search visits dramatically higher energies while returning to more
widely separated low-energy configurations. Two important properties
of the energy landscape are independent of either algorithm: first, to
find lower energy records, progressively higher energy barriers need
to be overcome. Second, the Hamming distance between two consecutive
low-energy records is linearly related to the height of the
intervening barrier.
05.40.-a - Fluctuation phenomena, random processes, noise, and Brownian motion.
75.10.Nr - Spin-glass and other random models.
02.60.Pn - Numerical optimization.
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag 2005