Correlation Structure of Landscapes of NP-Complete Optimization Problems at Finite Temperatures
Wolfgang Gehring, Peter B. Salamon, Roger Whitney, Paolo Sibani · Open Systems & Information Dynamics · 2004
We analyze the autocorrelation function of a time series of energy values sampled in the energy landscapes of four different combinatorial optimization problems by a Metropolis random walk. The temperature of the walk and the size of the investigated problems are systematically varied. We find that, in a suitably defined high temperature region the autocorrelation decays in an exponential fashion. We extract the temperature and system size dependence of the corresponding correlation time, which turns out to be of the Arrhenius form. Energetic and entropic contributions to the correlation time (barriers) are identified and shown to be asymptotically independent of system size.