asa-readme.ms

simulated annealing code ASA

There are three files in the ASA archive that should be considered as
appendices to the ASA\-NOTES file:
http://www.ingber.com/asa_contrib.txt,
http://www.ingber.com/asa_examples.txt, and
http://www.ingber.com/asa_papers.html under WWW.
.PP
The file http://www.ingber.com/asa_contrib.txt in the ASA archive contains
some code contributed by users.  For example, references are giving
to asamin, a MATLAB gateway routine to ASA, and to function support
for ASA_PARALLEL.  There is a CONTENTS of sections headers that can
be used to search on topics in your browser or editor.  In this file I
have included the first 1987 VFSR code, the precursor to the ASA code,
as used on a specific project, including the RATFOR vfsr.r and vfsr_com.r
code, subsequently compiled into FORTRAN to run on a Lawrence Livermore
supercomputer.  I do not support this old RATFOR code.
.PP
The file http://www.ingber.com/asa_examples.txt in the ASA archive
contains some example problems using ASA.  There is a CONTENTS of
sections headers that can be used to search on topics in your browser
or editor.  This file contains some \*Qtoy\*U problems optimized using
ASA, which can provide immediate examples on how you can optimize your
own problem.
.PP
The file http://www.ingber.com/asa_papers.html is an addendum to the
ASA\-NOTES file in the ASA code, containing references to some patents
and papers using ASA or its precursor VFSR.
.PP
The file asa_new.txt in the ASA archive is a list of major changes in ASA.
The files ASA\-README.txt, ASA\-README.ps and ASA\-README.pdf included
with the code also are available independently as
http://www.ingber.com/ASA\-README.txt,
http://www.ingber.com/ASA\-README.ps.gz,
http://www.ingber.com/ASA\-README.html,
http://www.ingber.com/ASA\-README.pdf.
.PP
There is a set of ASA_TEMPLATE's available in the ASA\-Makefile and in the
user module (some also in the asa module) to illustrate use of
particular OPTIONS, as listed under ASA_TEMPLATE below.  You can search
on these ASA_TEMPLATE's in your browser or editor to see how these are
implemented.  Note that some OPTIONS require your input, as described
below, and code may fail until you add your own code.  Once you have
determined the most common set of DEFINE_OPTIONS you are likely to use,
you might place these in your own TEMPLATE at the top of asa_usr_asa.h
at the location specified, e.g.,
.nf
.in +3n
#if MY_TEMPLATE                 /* MY_TEMPLATE_asa_user */
  /* you can add your own set of #define here */
#define ... TRUE
#define ... 100
#endif
.in 0
.fi
.PP
See http://www.ingber.com/utils_file_formats.txt for some links to
information on gzip, PostScript, PDF, tar, and shar utilities.  The file
00index_utils in that directory gives short statements describing these
files, which may be accessed as http://www.ingber.com/index_utils.html
under WWW.
.NH 2
Use of Documentation for Tuning
.XS
\*(SN 		Use of Documentation for Tuning
.XE
.PP
I'm often asked how how I can help someone tune their system, and they
send me their cost function or a list of the ASA OPTIONS they are using.
Most often, the best help I can provide is based on my own experience
that nonlinear systems typically are non\-typical.  In practice, that
means that trying to figure out the nature of the cost function under
sampling in order to tune ASA (or likely to similarly tune a hard problem
under any sampling algorithm), by examining just the cost function, likely
will not be as productive as generating more intermediate printout, e.g.,
setting ASA_PRINT_MORE to TRUE, and looking at this output as a \*Qgrey
box\*U of insight into your optimization problem.  Larger files with
more information is provided by setting ASA_PIPE_FILE to TRUE.  Treat the
output of ASA as a simulation in the ASA parameter space, which usually
is quite a different space than the variable space of your system.
.PP
For example, you should be able to see where and how your solution
might be getting stuck in a local minima for a very long time, or where
the last saved state is still fluctuating across a wide portion of your
state space.  These observations should suggest how you might try
speeding up or slowing down annealing/quenching of the parameter space
and/or tightening or loosening the acceptance criteria at different
stages by modifying the OPTIONS, e.g., starting with the OPTIONS that
can be easily adjusted using the asa_opt file.
.PP
The ASA\-NOTES file that comes with the ASA code provides some guidelines
for tuning that may provide some insights, especially the section Some
Tuning Guidelines.  An especially important guide is to examine the output
of ASA at several stages of sampling, to see if changes in parameter and
temperatures are reasonably correlated to changes in the cost function.
Examples of useful OPTIONS that often give quick changes in tuning in some
\*Qtoy\*U problems are in the file http://www.ingber.com/asa_examples.txt
under WWW.  Some of the reprint files of published papers in the
ingber.com provide other examples in harder systems, and perhaps you
might find some examples of harder systems using ASA similar to your
own in http://www.ingber.com/asa_papers.html under WWW.  This is the
best way to add some Art to the Science of annealing.
.PP
While the upside of using ASA is that is has many OPTIONS available for
tuning, derived in large part from feedback from many users over many
years, making it extremely robust across many systems, the downside is
that the learning curve can be steep especially if the default settings
or simple tweaking in asa_opt do not work very well for your particular
system, and you then must turn to using more ASA OPTIONS.  Most of these
OPTIONS have useful guides in the ASA_TEMPLATEs in asa_usr.c, as well
as being documented here.  If you really get stuck, you may consider
working with someone else who already has climbed this learning curve
and whose experience might offer quick help.
.NH 1
Availability of ASA Code
.XS
\*(SN 	Availability of ASA Code
.XE
.LP
.NH 2
ingber.com
.XS
\*(SN 		ingber.com
.XE
.PP
The latest Adaptive Simulated Annealing (ASA) code and some related
papers can be accessed from the home page http://www.ingber.com/ under
WWW, or retrieved via anonymous ftp from ftp.ingber.com.
.KS
.PP
Interactively [brackets signify machine prompts]:
.in +8n
.nf
[your_machine%] ftp ftp.ingber.com
[Name (...):] anonymous
[Password:] your_e\-mail_address
[ftp>] binary
[ftp>] ls
[ftp>] get file_of_interest
[ftp>] quit
.in 0
.fi
.KE
.PP
The home page http://www.ingber.com/ under WWW, and the
ASCII version 00index.txt, contain an index of the other files.
.PP
The latest version of ASA, ASA\-x.y (x and y are version numbers),
can be obtained in two formats: http://www.ingber.com/ASA.tar.gz and
http://www.ingber.com/ASA.zip.  The tar'd versions is compressed in gzip
format, and ASA.tar.gz.  In the zip'd version, ASA.zip, all files have
been processed for DOS format.
.PP
Patches ASA\-diff\-x1.y1\-x2.y2 up to the present version can be
prepared if a good case for doing so is presented, e.g. to facilitate
updating your own modified codes.  These may be concatenated as
required before applying.  If you require a specific patch, contact
[e-mail].
.NH 2
Electronic Mail
.XS
\*(SN 		Electronic Mail
.XE
.PP
If you do not have WWW or FTP access, get the Guide to Offline Internet
Access, returned by sending an e\-mail to mail\[e-mail] with
only the words \*Qsend
usenet/news.answers/internet\-services/access\-via\-email\*U in the body
of the message.  The guide gives information on using e\-mail to access
just about all InterNet information and documents.  You will receive
the information in utils_access\-via\-email.txt in the ASA
archive.
.NH 1
Background
.XS
\*(SN 	Background
.XE
.LP
.NH 2
Context
.XS
\*(SN 		Context
.XE
.PP
Too often the management of complex systems is ill\-served by not
utilizing the best tools available.
For example, requirements set by decision\-makers often are not formulated
in the same language as constructs formulated by powerful mathematical
formalisms, and so the products of analyses are not properly or maximally
utilized, even if and when they come close to faithfully representing the
powerful intuitions they are supposed to model.
In turn, even powerful mathematical constructs are ill\-served, especially
when dealing with multivariate nonlinear complex systems, when these
formalisms are butchered into quasi\-linear approximations to satisfy
constraints of numerical algorithms familiar to particular analysts,
but which tend to destroy the power of the intuitive constructs developed
by decision\-makers.
.PP
In order to deal with fitting parameters or exploring
sensitivities of variables, as models of systems have become more
sophisticated in describing complex behavior, it has become
increasingly important to retain and respect the nonlinearities
inherent in these models, as they are indeed present in the complex
systems they model.
ASA can help to handle these fits of nonlinear models of real\-world data.
.PP
It helps to visualize the problems presented by such complex systems
as a geographical terrain.
For example, consider a mountain range, with two \*Qparameters,\*U
e.g., along the North\-South and East\-West directions.
We wish to find the lowest valley in this terrain.
ASA approaches this problem similar to using
a bouncing ball that can bounce over mountains from valley to valley.
We start at a high \*Qtemperature,\*U where the temperature is an
ASA parameter that mimics the effect of a fast moving particle in a hot
object like a hot molten metal, thereby permitting the ball to make very
high bounces and being able to bounce over any mountain to access
any valley, given enough bounces.
As the temperature is made relatively colder, the ball cannot bounce so high,
and it also can settle to become trapped in relatively smaller ranges of
valleys.
.PP
We imagine that our mountain range is aptly described by a \*Qcost function.\*U
We define probability distributions of the two directional parameters, called
generating distributions since they generate possible
valleys or states we are to explore.
We define another distribution, called the acceptance distribution, which
depends on the difference of cost functions of the present generated valley
we are to explore and the last saved lowest valley.
The acceptance distribution decides probabilistically whether to stay
in a new lower valley or to bounce out of it.
All the generating and acceptance distributions depend on temperatures.
.PP
The ASA code was first developed in 1987 as Very Fast Simulated
Reannealing (VFSR) to deal with the necessity of performing adaptive
global optimization on multivariate nonlinear stochastic systems.
.[
%A L. Ingber
%T Very fast simulated re-annealing
%J Mathematical Computer Modelling
%V 12
%P 967-973
%D 1989
%O URL http://www.ingber.com/asa89_vfsr.pdf
.]
The first published use of VFSR for a complex systems was in combat
analysis, using a model of combat first developed in 1986, and then
applied to exercise and simulation data in a series of papers that
spanned 1988-1993.
.[
%A L. Ingber
%T Statistical mechanics of combat and extensions
%B Toward a Science of Command, Control, and Communications
%E C. Jones
%I American Institute of Aeronautics and Astronautics
%C Washington, D.C.
%D 1993
%P 117-149
%O ISBN 1-56347-068-3.  URL http://www.ingber.com/combat93_c3sci.pdf
.]
The first applications to combat analysis used code written in RATFOR
and converted into FORTRAN.  Other applications since then have used
new code written in C.  (The ASA\-NOTES file contains some comments on
interfacing ASA with FORTRAN codes.)
.PP
In November 1992, the VFSR C\-code was rewritten, e.g., changing to the
use of long descriptive names, and made publicly available as version
6.35 under a \*Qcopyleft\*U GNU General Public License (GPL),
.[
%A L. Ingber
%A B. Rosen
%R Global optimization C-code
%I University of Texas
%C San Antonio, TX
%T Very Fast Simulated Reannealing (VFSR)
%D 1992
%O URL ftp://ringer.cs.utsa.edu/pub/rosen/vfsr.tar.gz
.]
and copies were placed in NETLIB and STATLIB.
.PP
Beginning in January 93, many adaptive features were developed, largely
in response to users' requests, leading to this ASA code.  Until 1996,
ASA was located at http://www.alumni.caltech.edu/~ingber/.  Pointers
were placed in NETLIB and STATLIB to this location.  ASA versions 1.1
through 5.13 retained the GPL, but subsequent versions through this one
have incorporated a simpler ASA\-LICENSE, based in part on a University
of California license, that protects the integrity of the algorithm,
promotes widespread usage, and requires reference to current source
code.  As the archive grew, more room and maintenance was required,
and in February 1996 the site was moved to the present ingber.com
location.  Pointers were placed in the Caltech site to this location.
http://alumni.caltech.edu/~ingber is the mirror homepage for the ASA
site.  Beginning in January 2007, ASA also is listed at
http://asa-caltech.sourceforge.net (http://asa-caltech.sf.net).
.PP
ASA has been examined in the context of a review of methods of
simulated annealing using annealing versus quenching (faster
temperature schedules than permitted by basic heuristic proof of
ergodicity).
.[
%A L. Ingber
%T Simulated annealing: Practice versus theory
%J Mathematical Computer Modelling
%V 18
%D 1993
%P 29-57
%O URL http://www.ingber.com/asa93_sapvt.pdf
.]
A paper has indicated how this technique can be enhanced by combining
it with some other powerful algorithms, e.g., to produce an algorithm
for parallel computation.
.[
%A L. Ingber
%T Generic mesoscopic neural networks based on statistical mechanics
of neocortical interactions
%J Physical Review A
%V 45
%P R2183-R2186
%D 1992
%O URL http://www.ingber.com/smni92_mnn.pdf
.]
ASA is now used world\-wide across many disciplines,
.[
%A M. Wofsey
%T Technology: Shortcut tests validity of complicated formulas
%J The Wall Street Journal
%V CCXXII
%P B1
%D 24 September 1993
.]
.[
%A L. Ingber
%T Adaptive simulated annealing (ASA): Lessons learned
%J Control and Cybernetics
%V 25
%P 33-54
%D 1996
%O This was an invited paper to a special issue of the Polish journal
Control and Cybernetics on \*QSimulated Annealing Applied to Combinatorial
Optimization.\*U  URL http://www.ingber.com/asa96_lessons.pdf
.]
.[
%A L. Ingber
%T Data mining and knowledge discovery via statistical mechanics
in nonlinear stochastic systems
%J Mathl. Computer Modelling
%V 27
%P 9-31
%D 1998
%O URL http://www.ingber.com/path98_datamining.pdf
.]