is an initial candidate solution, p is a stochastic matrix which describes a stochastic state
transition mechanism (the composition of the next state generation and acceptance mech-
anisms discussed in Section 2.3) and t = {Tk} is a finite length monotone nonincreasing
sequence of positive control parameter values. The first parameter value in t is To and the
final value is Tf. P, incorporates the algorithm dependence on both C and T.
The algorithm generates a sequence of candidate solutions, {ik:0 k 5 f}, by
employing the state transformation mechanism (described by PT) to transform solution ik
into ik+1. At the k0 transition, T is completely determined by Tk. The solution sequence is
extended until T = Tf, at which point the current solution, if, is accepted as the solution to
the combinatorial optimization problem. Thus Tf signals algorithm termination. T, can be
allowed to depend on {ik} provided due regard is paid to the requirement for termination.
Since the solution state transition mechanism is stochastic, and since the conditional
dependence of the solution sequence only extends to one transition, the solution sequence
is a Markov chain by Definition Al. Its state transition matrix is PT (Definition A4).
The state transition matrix is decomposed into two parts for convenience in the fol-
lowing. It consists of the next state generation mechanism, Gj(T), which describes the
probability of generating state j given that the current state is i, and the state acceptance
mechanism, Aij(T), which describes the probability of accepting the generated state. Thus,
PT(i,j) is written as
Gj(T)Aij(T) j i
P3(i,j) = N Eq. 2.3
1- 2 G,,(T)A,(T) j=i
I=1,I^i
In this result, N = card(S) represents the cardinality of the solution space.
It is noted in passing that the usual form of the state acceptance mechanism is the so
called Metropolis criterion [Metr53], given by
A(T)= min 1, exp -( c(i]). Eq. 2.4
1 If T