Very Fast Simulated Reannealing code available for beta testing

Lester Ingber ingber at alumni.cco.caltech.edu
Sun Nov 22 23:46:07 EST 1992


           VERY FAST SIMULATED REANNEALING (VFSR) (C)

             Lester Ingber ingber at alumni.caltech.edu
                               and
              Bruce Rosen rosen at ringer.cs.utsa.edu

1.  License and Availability


1.1.  GNU Copyleft License

     This  Very  Fast  Simulated Reannealing (VFSR) code is being
made available under a GNU COPYING-LIB "copyleft" license, and is
owned  jointly  by Lester Ingber and Bruce Rosen[1].  Please read
the copy of this license contained in this directory.

1.2.  NETLIB Electronic Availability of VFSR

     You can obtain our code  from  NETLIB.   This  can  be  done
interactively, or you can obtain it by electronic mail request.

1.2.1.  Interactive

     From your local machine login to research.att.com:
        local% ftp research.att.com
        Name (research.att.com:your_login_name): netlib
        Password: [type in your_login_name or anything]
        ftp> cd opt
        ftp> binary
        ftp> get vfsr.Z
        ftp> quit
After  `uncompress  vfsr.Z'  read  the  header of vfsr for simple
directions on obtaining your source files.  For example, on  most
machines, after `sh vfsr' they will reside in a VFSR directory.

1.2.2.  Electronic Mail Request

     Send the following one-line electronic mail request
        send vfsr from opt
        [For general NETLIB info, just use: send index]
to one of the NETLIB sites:
        netlib at research.att.com (AT&T Bell Labs, NJ, USA)
		[most recent version]
        netlib at ornl.gov         (Oak Ridge Natl Lab, TN, USA)
        netlib at ukc.ac.uk        (U Kent, UK)
        netlib at nac.no           (Oslo, Norway)
        netlib at cs.uow.edu.au    (U Wollongong, NSW, Australia)

2.  Background and Context

     VFSR  was  developed  in  1987 to deal with the necessity of
performing adaptive global optimization on multivariate nonlinear
stochastic  systems[2].   VFSR was recoded and applied to several
complex systems, in combat analysis[3],  finance[4],  and  neuro-
science[5].   A  comparison  has  shown  VFSR to be superior to a
standard genetic algorithm simulation on a suite of standard test
problems[6],  and  VFSR  has  been  examined  in the context of a
review of methods of simulated annealing[7].  A project comparing
standard  Boltzmann  annealing  with "fast" Cauchy annealing with
VFSR has concluded that VFSR is a superior algorithm[8].  A paper
has  indicated how this technique can be enhanced by combining it
with some other powerful algorithms[9].

2.1.  Efficiency Versus Necessity

     VFSR is not necessarily an "efficient" code.   For  example,
if  you know that your cost function to be optimized is something
close to a parabola, then a simple gradient Newton search  method
most  likely  would  be faster than VFSR.  VFSR is believed to be
faster and more robust than other simulated annealing  techniques
for  most  complex problems with multiple local optima; again, be
careful to note that some problems  are  best  treated  by  other
algorithms.   If you do not know much about the structure of your
system, and especially if it has  complex  constraints,  and  you
need  to  search for a global optimum, then we heartily recommend
our VFSR code to you.

2.2.  Outline of Use

     Set up the VFSR interface: Your program  should  be  divided
into two basic modules.  (1) The user calling procedure, contain-
ing the cost function to be minimized (or  its  negative  if  you
require  a  global  maximum),  here  is  contained  in user.c and
user.h.  (2) The VFSR optimization procedure, here  is  contained
in  vfsr.c  and  vfsr.h.   Furthermore, there are some options to
explore in the Makefile.  We assume there will  be  no  confusion
over  the standard uses of the term "parameter" in different con-
texts, e.g., as an element passed by a subroutine or as a  physi-
cal coefficient in a cost function.

     In VFSR/TESTS we have included some user_out files from some
sample runs, containing timed runs  on  a  Sun4c/4.1.3  (SPARC-2)
using    compilers    cc,   acc   and   gcc-2.3.1,   and   on   a
Dec5100/Ultrix-4.2 using compilers cc and gcc-2.2.2.  No  attempt
was  made  to optimize the use of any of these compilers, so that
the runs do not really signify any testing of these compilers  or
architectures;  rather  they  are  meant to be used as a guide to
determine what you might expect on your own machine.

3.  Makefile

     This file was generated using `make doc'.  The Makefile con-
tains  some options for formatting this file differently, includ-
ing the PostScript version README.ps and the text version README.

     Since  complex  problems  by  their  nature  are often quite
unique, it is unlikely that our default parameters are just right
for  your problem.  However, our experience has shown that if you
a priori do not have any reason to determine your own parameters,
then  you might do just fine using our defaults, and we recommend
using them as a first-order guess.  Most of our defaults  can  be
changed  simply  by uncommenting lines in the Makefile.  Remember
to recompile the entire code every time you change  any  options.
Depending  on  how you integrate VFSR into your own user modules,
you may wish to modify this Makefile or  at  least  use  some  of
these options in your own compilation procedures.

     Read  through  all the options in the Makefile.  As the com-
ments therein suggest, it may be necessary to change some of them
on  some  systems.   Here are just a couple of examples you might
consider:

3.1.  SMALL_FLOAT

     For example, on one  convex  running  our  test  problem  in
user.c  the  SMALL_FLOAT  default  was  too  small  and  the code
crashed.  A larger value was found to give reasonable results.

     The reason is that the fat tail  of  VFSR,  associated  with
high  parameter temperatures, is very important for searching the
breadth of the ranges especially in the initial stages of search.
However,  the  parameter temperatures require small values at the
final stages of the search to  converge  to  the  best  solution,
albeit  this is reached very quickly given the exponential sched-
ule proven in the referenced publications to be permissible  with
VFSR.   Note  that  our  test problem in user.c is a particularly
nasty one, with 1E20 local minima and requiring  VFSR  to  search
over  many  orders  of magnitude of the cost function before cor-
rectly finding the global minimum.

     In VFSR/TESTS We  have  included  vfsr_out  files  comparing
results   using   SMALL_FLOAT=1.0E-16,  SMALL_FLOAT=1.0E-18  (the
default),  and  SMALL_FLOAT=1.0E-20.   Although  the  same  final
results were achieved, the intermediate calculations differ some-
what.

3.2.  HAVE_ANSI

     As another example, setting HAVE_ANSI=FALSE will permit  you
to  use  an older K&R C compiler.  This option can be used if you
do  not  have  an   ANSI   compiler,   overriding   the   default
HAVE_ANSI=TRUE.

4.  User Module

     We  have  set  up this module as user.c and user.h.  You may
wish to combine them into one file, or you may wish  to  use  our
VFSR  module  as  one component of a library required for a large
project.

4.1.  int main(int argc, char **argv)

     In main, set up your initializations and calling  statements
to vfsr.  In the files user.c and user.h, we have provided a sam-
ple program, as well as a sample cost function  for  your  conve-
nience.   If you do not intend to pass parameters into main, then
you can just declare it as main() without the argc and argv argu-
ments.

4.2.  void user_initialize_parameters()

     Before calling vfsr, the user must allocate storage and ini-
tialize some of the passed parameters.   A  sample  procedure  is
provided  as a template.  In this procedure the user should allo-
cate storage for the passed arrays and  define  the  minimum  and
maximum  values.   Below, we detail all the parameters which must
be initialized.  If your arrays are of size 1, still use them  as
arrays as described in user.c.

4.3.  double user_cost_function(double *x, int *valid_flag)

     You  can  give any name to user_cost_function as long as you
pass this name to vfsr.  x (or whatever name you pass to vfsr) is
an array of doubles representing a set of parameters to evaluate,
and valid_flag (or whatever name you pass to vfsr) is the address
of  an integer.  In user_cost_function, *valid_flag should be set
to FALSE (0) if the parameters violate a set of user defined con-
straints  (e.g.,  as  defined by a set of boundary conditions) or
TRUE  (1)  if  the  parameters  represent  a  valid  state.    If
*valid_flag is FALSE, no acceptance test will be attempted, and a
new set of trial parameters  will  be  generated.   The  function
returns a real value which VFSR will minimize.

4.4.  double user_random_generator()

     A  random number generator function must be passed next.  It
may be as simple as one of  the  UNIX  random  number  generators
(e.g.  drand48),  or  may be user defined, but it should return a
real value within [0,1) and not take  any  parameters.   We  have
provided  a good random number generator, randflt, and its auxil-
iary routines with the code in the file user module.

4.5.  void initialize_rng()

     Most random number generators should be "warmed-up" by call-
ing a set of dummy random numbers.

4.6.  void print_time(char *message)

     As  a convenience, we have included this subroutine, and its
auxiliary routine aux_print_time, to keep track of the time spent
during  optimization.   It  takes  as its only parameter a string
which  will  be  printed.   We   have   given   an   example   in
user_cost_function  to  illustrate  how  print_time may be called
periodically   every   set   number   of   calls   by    defining
PRINT_FREQUENCY in user.h.

4.7.
vfsr(
     user_cost_function,
     user_random_generator,
     number_parameters,
     parameter_type,
     parameter_initial_final,
     final_cost,
     parameter_minimum,
     parameter_maximum,
     tangents,
     curvature);

     This is the form of the call to vfsr from user.c.

4.8.
void vfsr(
     double (*user_cost_function) (),
     double (*user_random_generator) (),
     int number_parameters,
     int *parameter_type,
     double *parameter_initial_final,
     double final_cost,
     double *parameter_minimum,
     double *parameter_maximum,
     double *tangents,
     double *curvature)

     This is how vfsr is defined in the VFSR module, contained in
vfsr.c and vfsr.h.  Each parameter is described below as it  must
be passed to this module from the user module.

4.8.1.  double (*user_cost_function) ()

     The  parameter (*user_cost_function*) () is a pointer to the
cost function that you defined in your user module.

4.8.2.  double (*user_random_generator) ()

     As discussed above, a pointer to the random number generator
function, defined in the user module, must be passed next.

4.8.3.  int number_parameters

     An  integer containing the dimensionality of the state space
is passed next.  Each of the arrays that follow are to be of  the
size number_parameters.

4.8.4.  int *parameter_type

     This  integer  array  is  passed next.  Each element of this
array (each flag) is either REAL_TYPE (0) (indicating the parame-
ter  is a real value) or INTEGER_TY


More information about the Comp-bio mailing list