asa-readme+.txt

simulated annealing code ASA

     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.

          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 "toy" problems optimized
     using ASA, which  can  provide  immediate  examples  on  how  you  can
     optimize your own problem.

          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.

          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.

          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.,
        #if MY_TEMPLATE                 /* MY_TEMPLATE_asa_user */
          /* you can add your own set of #define here */
        #define ... TRUE
        #define ... 100
        #endif

          See  http://www.ingber.com/utils_file_formats.txt  for some links
     to information on gzip, PostScript, PDF, tar, and shar utilities.  The


                                      - 4 -





     Adaptive Simulated Annealing (ASA)                       Lester Ingber




     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.

     3.4.  Use of Documentation for Tuning

          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  "grey  box"  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.

          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.

          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 "toy" 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.

          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


                                      - 5 -





     Adaptive Simulated Annealing (ASA)                       Lester Ingber




     already has climbed this learning curve  and  whose  experience  might
     offer quick help.

     4.  Availability of ASA Code


     4.1.  ingber.com

          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.

          Interactively [brackets signify machine prompts]:
             [your_machine%] ftp ftp.ingber.com
             [Name (...):] anonymous
             [Password:] your_e-mail_address
             [ftp>] binary
             [ftp>] ls
             [ftp>] get file_of_interest
             [ftp>] quit

          The home page http://www.ingber.com/ under  WWW,  and  the  ASCII
     version 00index.txt, contain an index of the other files.

          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.

          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].

     4.2.  Electronic Mail

          If  you  do  not have WWW or FTP access, get the Guide to Offline
     Internet    Access,    returned    by    sending    an    e-mail    to
     [e-mail]     with     only     the     words     "send
     usenet/news.answers/internet-services/access-via-email" 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.

     5.  Background







                                      - 6 -





     Adaptive Simulated Annealing (ASA)                       Lester Ingber




     5.1.  Context

          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.

          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.

          It  helps  to  visualize  the  problems presented by such complex
     systems as a geographical terrain.  For example, consider  a  mountain
     range,   with  two  "parameters,"  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  "temperature,"  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.

          We  imagine that our mountain range is aptly described by a "cost
     function."  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.

          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[2].
     The  first  published  use of VFSR for a complex systems was in combat


                                      - 7 -





     Adaptive Simulated Annealing (ASA)                       Lester Ingber




     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[3].  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.)

          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 "copyleft" GNU General Public License (GPL)[4],
     and copies were placed in NETLIB and STATLIB.

          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).

          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)[5].   A  paper  has  indicated  how  this technique can be