Simulated annealing

Summary

A MyM implementation of the simulated annealing optimisation algorithm. The search walks a 15×15 energy landscape, always accepting downhill moves and
taking uphill ones with a probability that falls as the temperature cools — with a live trail visualising where it explores.

Description

A worked example of the simulated annealing optimisation algorithm expressed as a MyM model. Starting from a fixed position on a 15×15 energy landscape,
the model repeatedly proposes a move to a neighbouring cell and either accepts or rejects it: downhill moves are always taken, while uphill moves are accepted with a probability that shrinks as the system “cools.” The temperature decays exponentially over time according to a simple annealing schedule, so early on the search explores freely and later settles toward a minimum. A decaying visualisation trail shows the current position and where the search has recently been, making the exploration-versus-exploitation trade-off easy to see at a glance.

Model

Model source

! simulated annealing

! constants

module main
begin

const 	MAXS 	= 15;
const 	XY	= 2;
const   X	= 1;
const	Y 	= 2;

! time

t.min 	 = 0.0;
t.max    = 100.0;
t.step   = 1.0;
t.sample = 1.0;

! dist

double dist;

real ex (dist) = [1, 1.0, 2, 0.9, 3, 0.8, 4 , 0.7, 5, 0.6, 6, 0.5, 7, 0.4, 
	8, 0.3, 9, 0.2, 10, 0.1, 11, 0.2, 12, 0.3, 13, 0.4, 14, 0.5, 15, 0.5];

real ey (dist) = [1, 1.0, 2, 0.9, 3, 0.8, 4 , 0.7, 5, 0.6, 6, 0.5, 7, 0.4,
	8, 0.3, 9, 0.2, 10, 0.1, 11, 0.2, 12, 0.3, 13, 0.4, 14, 0.5, 15, 0.5];

dist.min = 1;
dist.max = MAXS;
dist.step = 1;
dist.sample = 1;

! energy  solution space 

real 	es 	[MAXS, MAXS];

! coordinates

integer start 	[XY] = 1,1;
integer coord 	[XY] (t);

! neighborhood

integer neighbor[XY] (t);

! simulated annealing

real 	energy 	(t);
real 	delta_e (t);
boolean do_step	(t);

! annealing schedule

real 	temp (t);
real 	init_temp = 100.0;
real 	af = 0.01;

!visualization

real 	pos [MAXS, MAXS] (t);

!
! model in formulae
!

es [i, j] = ex (i) + ey (j), i = 1 to MAXS, j = 1 to MAXS;

coord = switch (t = 0 ? start, 
 	   	   do_step ? neighbor 
	           else coord (t-1));
real xpos (t), ypos (t);
xpos = coord [1]; ypos = coord [2];

neighbor = uniform (max (1, coord (t-1) - 1), min (MAXS, coord (t-1) + 1)+0.99);

energy	= es [coord [X], coord [Y]];
temp 	= INTEG (-af * temp, init_temp);

delta_e = es [neighbor [X], neighbor [Y]] - energy (t-1);

do_step = switch (delta_e <= 0 ? TRUE,
	          (uniform (0.0, 1.0) <= exp (-delta_e / temp)) ? TRUE 
	          else FALSE);

! visualization

real damp = 0.95;
pos [i, j]	= switch (i = coord [X] and j = coord [Y] ? 1,
	      	          t = 0 ? 0 
			  else damp * pos [i, j] (t-1)),
		  	  i = 1 to MAXS, j = 1 to MAXS;

end;