%Filename: paper.tex
\documentstyle[preprint,revtex]{aps}
\begin{document}
\draft
% \preprint{SCCS-???}
% submit to Phys Rev A??
%
\begin{title}
Optimal annealing schedules using simulated tempering
\end{title}
%
\author{P.D.~Coddington, G.C.~Fox, E.~Marinari$^{\dag}$, C.-H.~Wu}
\begin{instit}
Northeast Parallel Architectures Center, Syracuse University, \\
111 College Place, Syracuse, NY 13244, U.S.A.
\end{instit}
%
\author{T.~Rose}
\begin{instit}
Department of Computer Science, University of Texas of the Permian Basin, \\
Odessa, TX ????, U.S.A.
\end{instit}
%
\author{M.~Shore}
\begin{instit}
Department of Computer Science, Florida State University, \\
Tallahassee, FL ????, U.S.A.
\end{instit}
%
\begin{center}
\today
\end{center}
%

% \begin{abstract}
\bigskip
\noindent
We introduce a novel approach to the application of simulated annealing 
to global optimization problems.
Our method is based on the related technique of simulated tempering,
which ensures that the system remains in thermodynamic equilibrium 
throughout the annealing procedure, thereby guaranteeing that the 
method probabilistically finds the optimum solution. 
This method also uses an improved adaptive annealing schedule, 
which is generally much faster than the logarithmic annealing
schedule which guarantees optimality for standard simulated annealing,
and we show that it can be as fast as
% or faster than ???
the more commonly used exponential annealing schedule.
% \end{abstract}
% \pacs{PACS numbers 02.70.+d, 05.90.+m, 75.10.Nr}

\bigskip
\bigskip
\noindent
$^{\dag}$ {\footnotesize Permanent Address: Dipartimento di Fisica,
Universit\`a di Roma {\it Tor Vergata}, Via E. Carnevale, 00173 Roma, Italy.}

% \newpage

\noindent
\narrowtext

\section{INTRODUCTION}
\label{sec:intro}

Simulated annealing is a popular and effective method for 
tackling difficult global optimization problems~\cite{ANNEALING,BOOKS,INGBER}.
The main reasons for its popularity are that it is simple, it can be
applied to very general optimization problems, and it has been shown to
probabilistically find the optimum solution~\cite{INGBER,GEMAN}.

Simulated annealing is based on the ideas and techniques of statistical
mechanics~\cite{STATMECH}. 
The cost function to be minimized is identified with the energy function of a
thermodynamic system, a parameter analogous to temperature is introduced,
and at each temperature the system configuration is changed using a Monte
Carlo procedure~\cite{MONTE}, so that the energy of the system approaches 
an equilibrium Gibbs distribution~\cite{STATMECH}. 
The temperature parameter is gradually lowered
until the system reaches zero temperature, for which equilibrium 
is the state of minimum energy (the {\it ground state}), that is, the
solution of the optimization problem. This method is analogous to the
annealing of a metal, the process whereby the metal is heated to high
temperature, and then cooled very slowly so that it crystallizes into a
strong, stable formation with few defects. This is opposed to quenching,
where the metal is cooled very quickly and will generally be in a local
minimum of the energy which has many more defects and is not as robust.

The main problem with simulated annealing is that every time the temperature
is decreased, the system is driven out of equilibrium. In order to guarantee
that the system is still in (or near) equilibrium by the time zero temperature
is reached, the temperature must be decreased very slowly (logarithmically), 
which means that this technique can be extremely CPU intensive 
and time consuming.  This has led to the use of similar techniques which have
been called {\it simulated quenching}~\cite{INGBER}, which use a faster
(exponential) annealing but do not guarantee an optimum solution. 
In many cases this approach works extremely well, finding solutions which 
are close to optimal. 
However there is a trade-off here, since increasing the rate of annealing 
will reduce the time taken but will generally result in poorer solutions.
In many cases {\it ad hoc} or trial-and-error methods are used to find
a good {\it annealing schedule}, which governs how rapidly the 
temperature is reduced. 

Many methods have been proposed for creating {\it adaptive} annealing schedules,
which are determined dynamically using information on the statistical mechanics
of the system which can be measured at 
run-time~\cite{OTTEN,ROMEO,LAM,REES,SALAMON,HAJEK}.
These methods generally work better than predetermined exponential schedules,
since they allow the temperature to be reduced as rapidly as possible while 
still keeping the system ``close'' to equilibrium. However it has not been
proven that these methods will generate an optimal solution.

Recently a new Monte Carlo technique was introduced that is similar to
simulated annealing, but extends it so that Monte Carlo methods are used
for {\it both} aspects of annealing -- changing the system configuration
{\it and} changing the temperature -- in such a way that the system is
always in equilibrium~\cite{TEMPERING}.
Since in this case the temperature becomes a dynamic variable which can be
increased or decreased, this method is called {\it simulated tempering},
in analogy to the tempering of metals, where a metal is strengthened by
repeated heating and cooling cycles.

The idea of using simulated annealing for general optimization problems
was based on its use in Monte Carlo simulations of statistical mechanics
problems which involve finding the ground states of simple models of 
magnetism, such as the Ising Spin Glass~\cite{GLASS}. This model has many
states which have local minima of the energy which are close to the 
global minimum, so that finding the ground state is a hard global
optimization problem.
In most statistical mechanics problems the regions of interest,
such as phase transitions, are at {\it non}-zero temperature, where
it is the {\it free energy} (a combination of energy and entropy)
which is minimized~\cite{STATMECH}. Simulated tempering has been shown
to be very effective at finding the equilibrium behavior of the
Random Field Ising Model, a model with similar properties (frustration 
and disorder) to the Ising Spin Glass, but which has a phase transition
at non-zero temperature~\cite{TEMPERING}.

Here we introduce a novel approach to solving global optimization problems
which combines the techniques of simulated annealing and simulated tempering.
The basic idea is that of simulated annealing, however the temperature is
decreased {\it probabilistically}, using the Monte Carlo approach of 
simulated tempering, so that the system remains in thermodynamic equilibrium
throughout the annealing procedure, thus guaranteeing that this method 
can find an optimum solution. 
However the annealing schedule will generally be much faster than true 
simulated annealing, and we show for some test problems that it can be as
fast as simulated quenching.

We show that this method incorporates adaptive annealing in a natural and
``symbiotic'' way. 
Adaptive techniques can be used to determine the parameters (such as the
appropriate temperature changes) required for efficient simulated tempering,
and tempering can be used to improve on standard adaptive annealing schedules
which are generally hampered by large statistical errors in the run-time
data required to dynamically determine the schedule.
We believe that simulated tempering can be used to determine a near-optimal 
schedule for simulated annealing which probabilistically guarantees finding
the solution to a global optimization problem.


We present a brief overview of simulated annealing in 
section~\ref{sec:annealing}
and simulated tempering in
section~\ref{sec:tempering}.
In section~\ref{sec:method} we show how tempering can be applied to 
simulated annealing, and 
section~\ref{sec:adaptive} shows how this method can be improved by
incorporating an adaptive annealing schedule.
We present our results for 
the Ising Spin Glass
and Traveling Salesman problems %?? 
in section~\ref{sec:results}, 
and then discuss possible variations and improvements to the algorithm 
in section~\ref{sec:next}.



\section{SIMULATED ANNEALING}
\label{sec:annealing}

Background to annealing.

% Simulated annealing is based on the ideas of statistical mechanics,
% and in particular Monte Carlo simulation using the Metropolis
% algorithm~\cite{METROP,MONTE}.
%
% A simulated annealing algorithm is completely specified by two things:
% \begin{itemize}
% \item The method for updating the system (the {\it move class}).
% \item The {\it annealing schedule}, which is defined by:
%       \begin{enumerate}
%       \item the set of temperatures $T_{n}$.
%       \item the number of system updates $N_{n}$ at each temperature.
%       \end{enumerate}
% \end{itemize}
% 
% It has been shown that if the 
% 



\section{SIMULATED TEMPERING}
\label{sec:tempering}

Background to tempering.





\section{ANNEALING USING SIMULATED TEMPERING}
\label{sec:method}

Simple method we are currently doing (as implemented by Wu)
of annealing first to find energies, g's, etc,
then repeating the annealing but using tempering to stay in equilibrium.

Can we prove that tempering allows us to use an exponential
schedule in general and stay in equilibrium?
Or maybe we need to have a logarithmic part near a phase transition??
How about the adaptive schedule of Salamon et al.?? 
Can we relate the tempering schedule to  the Geman and Geman proof?




\section{AN ADAPTIVE ANNEALING SCHEDULE USING SIMULATED TEMPERING}
\label{sec:adaptive}

Background to previous attempts to do adaptive annealing schedules. \\
1) How we do it without tempering. \\
2) How we do it with tempering. \\
How adaptive schedules relate naturally to tempering, e.g. Salamon
et al. schedule looks very much like Enzo's result for choosing 
the change in temperature.




\section{RESULTS}
\label{sec:results}


\subsection{The Ising Spin Glass}
\label{sec:glass}


\subsection{The Traveling Salesman Problem}
\label{sec:tsp}




\section{FURTHER OPTIMIZATION BY SIMULATED TEMPERING}
\label{sec:next}

Outline the idea that once we have a good temperature schedule
and parameters, we can now run full tempering on it to continue
exploring many local minima without having to waste time
running at high temperatures, setting up the schedule, etc. 
We can even dynamically improve the schedule by adjusting the 
parameters so that the scceptances for changing temperature are
close to ${1 \over 2}$.
Reference the next paper~\cite{NEXT}.


\section{CONCLUSIONS}
\label{sec:conclusions}

We have done some really excellent work and gotten some truly
amazing results.


\acknowledgments

Work supported in part by the Center for Research on Parallel Computation
with NSF cooperative agreement No. CCR-9120008,
and by Department of Energy grants
DE-FG03-85ER25009 and DE-AC03-81ER40050. 
T.~Rose and M.~Shore were sponsored by the NSF Research Experience for 
Undergraduates Program in High-Performance Computing conducted by the
Northeast Parallel Architectures Center at Syracuse University,
funded by NSF Grant CDA-9200577, Syracuse University, and the
GE Foundation Faculty for the Future Program.

Anything else???

%
% REFERENCES
%
\begin{references}
%
\bibitem{METROP}
N.~Metropolis {\it et al.}, J. Chem. Phys. {\bf 21}, 1087 (1953).
%
\bibitem{MONTE}
K.~Binder ed., {\it Monte Carlo Methods in Statistical Physics}, 
(Springer-Verlag, Berlin, 1986);
K.~Binder and D.W.~Heermann, {\it Monte Carlo Simulation in Statistical 
Physics}, (Springer-Verlag, Berlin, 1988);
H.~Gould and J.~Tobochnik,
{\it An Introduction to Computer Simulation Methods, Vol. 2},
(Addison-Wesley, Reading, Mass., 1988).
%
\bibitem{ANNEALING}
M.~Pincus, 
% A Monte Carlo method for the approximate solution of certain types of
% constrained optimization problems,
Oper. Res. {\bf 18}, 1225 (1970);
S.~Kirkpatrick, C.~D.~Gelatt, Jr. and M.~P.~Vecchi, 
% Optimization by Simulated Annealing,
Science {\bf 220}, 671 (1983).
%
\bibitem{BOOKS}
P.J.M.~van Laarhoven and E.H.L.~Aarts,
{\it Simulated Annealing: Theory and Applications},
(D.~Reidel, Dordrecht, the Netherlands, 1987).
%
\bibitem{INGBER}
L.~Ingber, ``Simulated annealing: Practice versus theory'',
to be published in Statistics and Computing, 1993.
%
\bibitem{GEMAN}
S.~Geman and D.~Geman, 
% {\em Stochastic Relaxation, Gibbs Distribution
% and the Bayesian Restoration in images}, 
IEEE Trans. Patt. Anal. Mac. Int. {\bf 6}, 721 (1984).
%
\bibitem{STATMECH}
Some good stat mech books???
%
\bibitem{TEMPERING}
E.~Marinari and G.~Parisi,
% {\em Simulated Tempering: a New Monte Carlo Scheme,}
Europhys. Lett. {\bf 19}, 451 (1992);
%
%
%% ADAPTIVE ANNEALING SCHEDULES
%% ===========================
%
\bibitem{OTTEN}
R.~Otten and L.~van~Ginneken, 
% Stepwise Layout refinement,
in IEEE Proceedings of the International Conference on Computer Design
(Port Chester, New York, 1984).
%
\bibitem{ROMEO}
F.~Romeo, A.~Sangiovanni-Vincentelli and C.~Sechen,
in IEEE Proceedings of the International Conference on Computer Design
(Port Chester, New York, 1984).
%
\bibitem{LAM}
J.~Lam and J.-M.~Delosme, 
in IEEE Proceedings of the International Conference on Computer Design
(1986).
%
\bibitem{REES}
S.~Rees and R.C.~Ball, 
% Criteria for an optimal simulated annealing schedule for problems
% of the traveling salesman type,
J. Phys. A {\bf 20}, 1239 (1987).
%
\bibitem{SALAMON}
P.~Salamon {\it et al.}, 
% Simulated annealing with constant thermodynamic speed,
Comp. Phys. Comm. {\bf 49}, 423 (1988);
J.D.~Nulton and P.~Salamon, 
% Statistical mechanics of combinatorial optimization,
Phys. Rev. A {\bf 37}, 1351 (1988);
B.~Andresen {\it et al.}, 
% On lumped models for thermodynamic properties of simulated annealing
% problemS
J. Phys. {\bf 49}, 1485 (1988).
%
\bibitem{HAJEK}
B. Hajek,
% Cooling schedules for optimal annealing,
%
%% ===========================
%
\bibitem{SOKALREV}
A.D.~Sokal, in {\em Computer Simulation Studies in Condensed Matter
Physics:  Recent Developments}, eds.\ D.P.~Landau {\em et al.}
(Springer-Verlag, Berlin-Heidelberg, 1988);
A.D.~Sokal, in Proc. of the International Conference on Lattice Field Theory,
Tallahassee, October 1990, Nucl. Phys. B (Proc. Suppl.) {\bf 20}, 55 (1991).
%
\bibitem{GLASS}
K.~Binder and A.P.~Young, Rev. Mod. Phys. {\bf 58}, 801 (1986);
D.~Chowdhury, {\it Spin Glasses and Other Frustrated Systems},
(Princeton University Press, Princeton, NJ, 1986);
M.~Mezard and G.~Parisi, {\it Spin Glass Theory and Beyond},
(World Scientific, Singapore, 1987).
%
\bibitem{TIMESERIES}
M.B.~Priestley, {\it Spectral Analysis and Time Series}, 
(Academic Press, London, 1981).
%
\bibitem{NEXT}
P.D.~Coddington, G.C.~Fox, E.~Marinari, and C.-H.~Wu,
``Optimization by simulated tempering'', in preparation.
%
\end{references}



\newpage

THINGS WE NEED TO DO: 
\begin{enumerate}
\item 
See if tempering works for an exponential temperature schedule on
a large system ($256^2$).
\item 
Compare the relaxation of the minimum energy for the exponential schedule
with and without tempering, and for different exponents $\alpha$.
\item 
Get a good adaptive schedule working.
\item 
Compare the relaxation of the minimum energy for the adaptive schedule
with and without tempering.
\item
Try it on the TSP, and compare with other annealing methods and results.
\item 
A rigorous proof that tempering guarantees (probabilistically) finding
the optimal solution.
\end{enumerate}



\end{document}

