Python Programming for Biology: Bioinformatics and Beyond

Simulated annealing

The  next  section  of  this  chapter  relates  to  an  adjustment  to  the  Monte  Carlo  method

termed  simulated  annealing,

6

,

7

 and  this  may  be  applied  to  both  the  combinatorial  and

function optimisations already described. Here the main principle is to have the same kind

of random selection and acceptance rules as before, but the degree of acceptance of non-

improving  states  diminishes.  As  the  data  sampling  proceeds  the  acceptance  criterion

becomes  stricter,  and  the  range  of  accepted  steps  effectively  becomes  narrower.  This

enables an initially wide search that will hopefully sample enough to explore close to the

globally best solution, but which will later settle on a refined optimum. Using simulated

annealing will counter some of the later moves which would otherwise cause the state to

jump  out  of  a  globally  optimum  solution.  For  some  problems  the  simulated  annealing

approach need not be used, as it does not sample as widely as plain Monte Carlo, in the

same  number  of  steps,  and  has  a  greater  tendency  to  get  stuck  in  sub-optimal  minima.

However, when used with care it makes a better refinement protocol, and at the end of the

search  the  last  state  will  tend  to  be  close  to  an  optimum  (local  or  otherwise),  which  can

remove  the  need  to  record  good  solutions  during  the  search.  Often  simulated  annealing

will be used in situations where it is not required to have the absolute best solution, just a

reasonably good one in a short time.

The term simulated annealing reflects a similar physical process that occurs in materials

science, when a solid is heated and slowly cooled to create a more ordered state, e.g. with

bigger  crystals.  The  term  that  we  introduce  into  a  Monte  Carlo  search  to  diminish  the

likelihood  of  accepting  less  optimal  states  is  analogous  to  temperature  in  physical

annealing.  Here  we  introduce  the  variable  cool,  which  represents  the  sampling

‘temperature’, or more generally the annealing schedule. The Python examples will only

use  a  simple  exponential  decay  to  provide  the  value  of  cool,  but  in  other  situations  it  is

commonplace  to  have  more  complex  annealing  schedules.  For  example,  the  solutions  to

some problems that have been caught in sub-optimal states may be rescued by restarting

the  annealing  from  a  recorded  earlier  state  and  temperature,  or  by  re-raising  the

temperature (‘shake and bake’). Another approach that is worth mentioning, but which we

do  not  have  room  to  describe  in  detail,  is  ensemble-based  methods,  where  multiple,

separate  copies  of  a  Monte  Carlo  search  are  done  in  parallel.  Each  of  the  replicas  in  an

ensemble  of  concurrent  Monte  Carlo  searches  will  find  different  solutions  and  may

operate  under  different  conditions.  A  method  called  parallel  tempering  or  replica

exchange  Monte  Carlo  will  perform  the  separate  searches  at  different  temperatures  and

occasionally swap solutions between the different temperatures, searching both widely and

precisely while maintaining detailed  balance.  Another  common  ensemble  approach  is  to

use  a  genetic  algorithm,  whereby  different  replicas  exchange  part  of  their  states:  the

genetics analogy is with the mutation and crossover of DNA strands when parents produce

offspring.

---