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