Let f be a real valued function of the N variables
. We seek to find the values of
which will minimize 
. We denote
by 
. The set of allowed values of
may be infinite (discrete or continuous) or finite.
First begin with some randomly (or otherwise) chosen initial values for
the variables, denoted by 
. After this, CGO consists of a
three--step process which is iterated some given number of times.
Step (1): Determine, for each variable 
, whether 
is
to remain equal to 
or to change to some other value. Select a
random number 
between 0 and 1. If
then as described in step (2) a new value will be selected
for 
; otherwise, 
will remain equal to 
. In
Eq. (1) g is a real--valued function of 
; C is a real
number used for all 
for one iteration but which may change
each iteration; k is a constant (Boltzmann constant); T is the
``temperature'' of the system. The right side of Eq. (1) is the
Glauber probability of a spin flip and is derived by considering each
to have two states: remaining equal to 
or not.
Then by solving 
, and 
for 
we get equation
(1).
We can consider 
to be an ``energy'' associated with
remaining equal to 
, and C a threshold energy
associated with selecting a new value for 
. The choice
of the function g and the constant C are problem--dependent. For
problems based on particle interactions obeying a linear superposition
principle a clear choice is to take g so that 
.
For problems in which f is not derived from a superposition principle
one should attempt to choose g so as to divide the ``cost'' of f
among the variables. The value of C at a given iteration may depend
on the current values of the variables. In general, increasing C
decreases the probability that variables will change values; decreasing
C increases the probability.
Step (2): For each 
determined to remain
unchanged in step (1), set 
. For each 
determined to change in step (1), choose a new 
randomly
from the set of allowed values. The set of allowed values is problem
dependent. For example, certain problems may limit the number of
variables 
which can have the same value. If this is true then
special care must be taken in choosing the 
. One
such procedure for doing this is illustrated for the office assignment
problem below.
Step (3): Calculate 
and perform the Metropolis
algorithm: If 
then the new
arrangement is accepted. If 
then the new arrangement is rejected unless a random number R which is
selected is less than 
; if
the new arrangement is rejected, 
is set back to 
for all i.
The three--step process is iterated a certain number of times at a given
temperature, and then the temperature is lowered according to some
annealing schedule and the process iterated at that
temperature. Eventually the temperature becomes so low that the values
of the variables 
become frozen in.
Step (2) allows for potentially global rearrangements of a system, but
these arrangements are constrained by step (1) which in general only
allows those variables with excessively large energies to change
values. Also, rearrangements are ultimately limited by step (3), which
in general does not allow moves to values of 
with
larger values of f. CGO differs from SA in steps (1) and (2), and
shares the use of the Metropolis algorithm (step (3)) with SA.
