Simulated Annealing

Examples using this package can be found in The N Queens Problem (SA), The Travelling Salesman Problem (SA) and Graceful Tree Labelling (SA).

/* This is the procedure to be invoked by the application program, in      */
/*   which size/1, perturb/2, energy/2 and output/3 must be defined.       */
anneal:-
  size(Size),
  N is 10 * Size,             /* Number of iterations per temperature      */
  MaxSucc is 1 * Size,        /* Maximum number of changes per temperature */
  repeat,
    perm_rand(Size, Xs),
    energy(Xs, EnergyXs),
  EnergyXs =\= 0, !,          /* Avoid division by zero in oracle/3        */
  Temp is EnergyXs / Size,    /* Initial temperature                       */
  anneal_1(100, N, Temp, 0.90, MaxSucc, s(Xs,EnergyXs), s([],32767), 
           s(Ys, EnergyYs), Result),
  output(Result, Ys, EnergyYs).

/* anneal_1(M, N, Temp, Factor, MaxSucc, State, s([],32767), Best, Result) */
/*   is true if Best is the best state (a list and its energy) obtained by */
/*   annealing the State at M different temperatures (or after no changes  */
/*   have been made at a given temperature, or if the energy becomes zero),*/
/*   with N iterations per temperature (or after the state has been        */
/*   changed MaxSucc times at this temperature).  Temp is the initial      */
/*   temperature, and it is multiplied by Factor at each iteration. Result */
/*   indicates the result of the annealing: optimal - an optimal solution  */
/*   has been found; iterations - all iterations have been executed        */
/*   without finding an optimal solution; nochanges - no changes were made */
/*   at a given temperature and an optimal solution has not been found.    */
anneal_1(_, _, _, _, _, _, s(Xs, 0), s(Xs, 0), optimal):-!.
anneal_1(0, _, _, _, _, _, Best, Best, iterations):-!.
anneal_1(M, TempIters, Temp, Factor, MaxSucc, State0, Best0, Best, Res):-
  anneal_2(TempIters, MaxSucc, MaxSucc, Temp, State0, State1, Best0, Best1),
  !,
  M1 is M - 1,
  Temp1 is Temp * Factor,
  anneal_1(M1, TempIters, Temp1, Factor, MaxSucc, State1, Best1, Best, Res).
anneal_1(_, _, _, _, _, _, Best, Best, nochanges).

/* anneal_2(N, MaxSucc, MaxSucc, Temp, State0, State, Best0, Best) is true */
/*   if State0 (a list and its energy) is transformed into State after N   */
/*   iterations at this Temp, or after the state has been changed MaxSucc  */
/*   times. Best0 is the previous best-so-far, and Best is the new best-   */
/*   so-far state.  It fails if, at the end of N iterations, no changes    */
/*   have been made.                                                       */
anneal_2(0, Success, MaxSucc, _, State, State, Best, Best):-!,
  Success < MaxSucc.
  /* All iterations have been performed and at least one change made */
anneal_2(_, 0, _, _, State, State, Best, Best):-!.
  /* The specified number of changes have been made */
anneal_2(N, Success, MaxSucc, Temp, s(Xs0, Energy0), State, Best0, Best):-
  perturb(Xs0, Xs1),
  energy(Xs1, Energy1),
  oracle(Energy0, Energy1, Temp), !,
  better(Best0, s(Xs1, Energy1), Best1),
  Success1 is Success - 1,
  N1 is N - 1,
  anneal_2(N1, Success1, MaxSucc, Temp, s(Xs1, Energy1), State, Best1, Best).
anneal_2(N, Success, MaxSucc, Temp, State0, State, Best0, Best):-
  N1 is N - 1,
  anneal_2(N1, Success, MaxSucc, Temp, State0, State, Best0, Best).

/* oracle(EnergyXs, EnergyYs, Temp) is true if EnergyYs < EnergyXs         */
/*   or Random < exp((EnergyYs - EnergyXs) / -Temp).                       */
oracle(EnergyXs, EnergyYs, _):-
  EnergyYs < EnergyXs, !.
oracle(EnergyXs, EnergyYs, Temp):-
  ln(rand(1)) < (EnergyXs - EnergyYs) / Temp.

/* better(State0, State1, State) is true if State is the better of State0  */
/*   and State1.  (The state with the lower energy is the better state.)   */
better(s(_, Energy0), s(Xs1, Energy1), s(Xs1, Energy1)):-
  Energy1 < Energy0, !.
better(State, _, State).

/* perm_rand(N, Perm) is true if Perm is a pseudo-random permutation of    */
/*   the integers 1 to N inclusive.                                        */
perm_rand(N, Perm):-
  N >= 0,
  perm_rand_1(N, N, [], Perm).

perm_rand_1(0, _, Perm, Perm):-!.
perm_rand_1(M, N, Perm0, Perm):-
  repeat,
    random(N, Rand),
  \+ member(Rand, Perm0), !,
  M1 is M - 1,
  perm_rand_1(M1, N, [Rand|Perm0], Perm).

/* random(I, J) is true if J is a pseudo-random integer in the range       */
/*   1..J.                                                                 */
random(I, J):-J is int(rand(I))+1.

/* member(X, Ys) is true if the element X is contained in the list Ys.     */
% member(X, [X|_]).
% member(X, [_|Ys]):-member(X, Ys).

/* repeat/0 always succeeds.                                               */
% repeat.
% repeat:-repeat.

LPA Index     Home Page

Valid HTML 4.01 Strict