Computational Physics

(Rick Simeone) #1
10.6 Further applications and Monte Carlo methods 327

exponent
−(βm−βn)(EXn−EXm) (10.59)


should be of order 1. Note that before the exchange,EXnwill be close to the equi-
librium energy at temperatureβn, and similarly forEXm. This implies that their
difference will be approximately


EXn−EXm≈C(βm−βn), (10.60)

whereCis the (total) specific heat, evaluated near the temperaturesβmandβn(we
assume thatC(β)does not vary too strongly between both temperatures – note that
this is not justified if the temperatures are close to a critical phase transition). We
see that for the acceptance rate to be of order 1, we should have


≡(βm−βn)(EXn−EXm)≈C(βm−βn)^2 =O( 1 ). (10.61)

From the fact that the total specific heat is an extensive quantity, we see that


βm−βn∼

1



N


. (10.62)


In practice, the set ofβvalues is determined dynamically, such as to make the
acceptance rate approximately constant. This is done as follows. We start with
a set of temperatures{βn}. For these we perform a number of MCS and replica
exchanges. The acceptance ratespmfor temperatureβmare stored and then the
latter are updated according to the recipe:


β 1 new=β 1 ;

βmnew=βmnew− 1 +(βm−βm− 1 )

pm
ptarget

,


whereptargetis the ‘target’ acceptance rate which is taken equal for all temperatures.
In this way we ensure that the replicas will cycle through all temperatures.
This method has been applied very successfully to spin-glasses and many other
examples.Forareview,seeRef. [48].


10.6.3 Walking in a rough landscape

In everyday life, we often encounter the problem of finding the optimum solution to a
problem among many candidate solutions. An example is the well-known ‘travelling
salesperson problem’ (TSP) which consists of finding the shortest path connecting a
set of cities to be visited by a salesperson. This problem is related to design problems
in electronic circuits, where the wiring must be done as efficiently as possible. The
TSP is an example of so-called combinatorial optimisation problems, as the aim is
to find the optimum among all permutations of the cities. Another type of problems

Free download pdf