Extra Credit: Simulated Annealing#

Extra Credit

This page is 10+10 points extra credit

The Ising model is useful for lots of things, one of which is helping us learn about optimization.

The goal of optimization is to extremize (maximize or minimize) a particular function O, called an objective function, which depends on a bunch of parameters \((p_1,p_2,...,p_n\)). One way to go about this is to compute the objective function’s derivatives with respect to the parameters, \(\partial O/\partial i\). When fed a particular vector of parameters \(p\), the derivatives identify the direction in which O changes most significantly. Iteratively “walking” in this direction — a procedure called gradient descent (for minimization) — leads to an extremum of \(O\). Unfortunately this procedure only finds local extrema; it can get you up the nearest hill or down the nearest valley, but there might be a mountain or gorge someplace further away that you’ve missed. Avoiding this situation requires an algorithm that finds global extrema.

In general it is impossible to find global extrema quickly (although we will soon see a way to go about it slowly). More generically, though, there are a number of heurestic algorithms that allow us to find global extrema, many of which are inspired by physics or nature. The most famous of these is simulated annealing. In simulated annealing you essentially run a simulation at very high temperature and then slowly cool things down. The intuition behind this is that at high temperatures you will be able to sample the entire landscape of the objective function, and then as you cool down you end up falling into the lowest minima.

In our case, our objective function will be to find the configuration of spins in an Ising model (our parameters) which minimizes the energy (our objective function). In the model that we’ve studied thus far, where all the coefficients \(J\) are the same, this isn’t very interesting (you can probably find the ground state without a computer). On the other hand, if we choose random signs on each of the coefficients, finding the ground state will be hard.

Grading

Modify your Ising model to work with arbitrary coupling constants on each bond.

Simulated Annealing#

Local Optimization#

Let’s start with a poor approach to optimization. Start in the configuration where all spins are up. Loop through the spins over and over again, flipping one anytime its opposite orientation reduces the energy. Stop after visiting N sequential spins without having performed any flips. This is a local minimum.

Go ahead and start with various random configurations. Do you get to the same local minima each time? If not, this means that typically you’re not finding global minima.

Grading

On a 20x20 latttice, you need to set up a set of random coupling constants and tried to find minima using local optimization. To do this, you should start with 100 different initial conditions and do local optimization until you can’t decrease the energy any longer. Report how many different minima it finds and how often it finds them.

Simulated Annealing#

Simulated annealing modifies the above algorithm in a very natural way. Instead of running at zero temperature (which always goes downhill), in simulated annealing we start by running at a high temperature. Over time, we slowly decrease the temperature until we get to zero temperature. The intuition here is that we end up in a deep minima. In fact, you can show that (in some unrealistic cases where you cool very slowly) you are guaranteed to get a global minima.

The algorithm concretely is:

  • Run Monte Carlo at high temperature \(T\) for a while

  • Every so often decrease the temperature

  • When you get to \(T=0\) which is equivalent to our local optimization) stop after your optimization doesn’t go down any more.

Now the only trick is to figure out what “temperature schedule” we want to use (i.e. how do we go from infinite temperature to zero). Let’s go ahead and run our optimization doing a couple different things:

  • try a linear temperature schedule

  • try an exponential temperature schedule

  • try a logarithmic temperature schedule

To have a fair test, use the same initial conditions and same values of \(J\).

Grading

Now using the same random coupling constants as the \(T=0\) case, try to find a minima using simulated annealing with a couple different temperature schedules. You should produce a graph that shows:

  • the average energy of the minima using local optimization

  • the lowest energy of the minima using local optimization

  • the different energies of minima you find using different simulated annealing temperature schedules. Good schedules to test are:

    • linear decrease in temperature

    • logarithmic decrease in temperature

    • exponential decrease in temperature

Extra Credit

Below is where you can get the extra +10 points.

HP Model#

The model that you just did simulated annealing with (random Ising model) is a spin glass. Is is interesting but it is not that often that you are trying to optimize a random spin glass. Here we would like you to do simulated annealing on a more realistic model: the HP-model for protein folding (see https://en.wikipedia.org/wiki/Hydrophobic-polar_protein_folding_model).

Here we would like you to minimize the energy of a given protein. In particular, take a random length 30-string (of random H and P). Then try to find the folding sequence (can be represented by a sequence of right, left, or straight turns) that produces the lowest energy of this model using simulated anneling.

All you need to do this is to be able to take this combination of turns and then return its energy. Once you have that, you can write a Monte Carlo code and then use it as a simulated annealing.