XSEDE12contest annealing

From Earlham Cluster Department

Jump to: navigation, search


Simulated annealing is a method for finding the minimum of a multi-valued, non-linear function. The algorithm likens a vector of input to the position of a particle moving in a potential energy distribution with Brownian motion. The Brownian motion is determined by a “temperature” parameter that allows for energetically unfavorable moves, according to a Boltzmann distribution. New positions are calculated at a variable step size until an equilibrium step size is determined, at which time the temperature is reduced and a new equilibrium step size is determined.


  1. Determine initial guess x, temperature T, and step size D. Compute E =f(x) for your initial guess.
  2. For some number of trial steps
    1. compute a random step d of size D
    2. Determine the “energy” of your guess Eguess=f(x+d)
    3. Choose whether to accept or reject your new guess
      1. if (rand(0,1)<exp(-(Eguess-E)/T) accept else reject
    4. If you accept, update x and E
  3. If you accept significantly more often than you reject, increase step size D
  4. If you reject significantly more often than you accept, decrease step size D
  5. If you accept and reject about as often, decrease T
  6. Repeat starting from step 2 until D is small.

Using this algorithm, solve for the most likely position of 7 particles that interact according to a potential of the form given below. Assume the first particle is fixed at the origin, and that all other particles can move in 3 dimensions. For the equation below, rij = Rij.jpg.


The total energy is given by


You may need to perform an ensemble solution, running the simulation many times and comparing results. Are there cooling factors and step size changes that result in better performance?

Personal tools
this semester