SECTION 1
INTRODUCTION
1.1 Non-Convex Combinatorial Optimization and Stochastic Search Algorithms
A wide variety of engineering applications lend themselves to formulations which
require the solution of combinatorial optimization problems. Typically, the optimization
problem is nonconvex and is defined over a very high dimensionality search space (e.g.
inverse vision problems, in which an image array of 512X512 pixels at 8 bits/pixel might
be encountered, resulting in a search space dimensionality of -2M). Consequently, direct
solution is usually intractable.
An alternative to direct solution is to select one of a variety of iterative improve-
ment solution techniques, usually some variant of gradient search. But by definition,
deterministic iterative improvement techniques terminate in local extrema, and they
ordinarily provide no means of assessing the amount by which the selected local extre-
mum deviates from the global extiemum. A typical means of avoiding local extrema
entrapment is to implement the iterative improvement solution method stochastically.
The most commonly employed stochastic algorithm approach to combinatorial opti-
mization is simulated annealing [KiGe83, LaAa871, which is also sometimes referred to
as probabilistic hill climbing [RoSa85]. It exploits the analogy of combinatorial
optimization to the annealing of crystalline solids, in which a solid is cooled very gradu-
ally from some elevated temperature and thereby allowed to relax toward its low energy
states. The appeal of the algorithm class derives from the fact that provided certain
constraints on an algorithm control parameter (analogous to absolute temperature) are
observed, asymptotic convergence to a global extremum is guaranteed.