Very Fast Simulated Reannealing code available for beta testing
Lester Ingber
ingber at alumni.cco.caltech.edu
Sun Nov 22 23:33:27 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_TYPE (1) (indicating the parame-
ter can take on only integer values).
4.8.5. double *parameter_initial_final
Next, an array of doubles is passed. Initially, this array
holds the set of starting parameters which should satisfy any
constraints or boundary conditions. Upon return from the VFSR
procedure, the array will contain the best set of parameters
found by vfsr to minimize the user's cost function. Experience
shows that any guesses within the acceptable ranges should suf-
fice, since initially the system is at high annealing temperature
and VFSR samples the breadth of the ranges.
4.8.6. double final_cost
This double should be defined in the calling program. Upon
return from the vfsr call, it will be the minimum cost value
found by vfsr.
4.8.7. double *parameter_minimum
4.8.8. double *parameter_maximum
These two arrays of doubles should also be passed. Since
VFSR works only on bounded search spaces, these arrays should
contain the minimum and maximum values each parameter can attain.
If you aren't sure, try a factor of 10 or 100 times any reason-
able values. The exponential temperature annealing schedule
should quickly sharpen the search down to the most important
region.
4.8.9. double *tangents
4.8.10. double *curvature
These two arrays of doubles should be passed last. On
return from vfsr, for real parameters, they contain the first and
second derivatives of the cost function with respect to its
parameters. These can be useful for determining the value of
your fit. In this implementation of VFSR, the tangents are used
to determine the relative reannealing among parameters.
5. Bug Reports
While we do not have time to help you solve your own appli-
cations, we do want VFSR to be helpful to a large community.
Therefore, we welcome your bug reports and constructive critiques
regarding our code. "Flames" will be rapidly quenched.
References
1. L. Ingber and B. Rosen, "vfsr," Very Fast Simulated Rean-
nealing (VFSR) Source Code, NETLIB Electronic Ftp Archive,
netlib at research.att.com (1992).
2. L. Ingber, "Very fast simulated re-annealing," Mathl. Com-
put. Modelling, 8, 12, pp. 967-973 (1989).
3. L. Ingber, H. Fujio, and M.F. Wehner, "Mathematical compari-
son of combat computer models to exercise data," Mathl. Com-
put. Modelling, 1, 15, pp. 65-90 (1991).
4. L. Ingber, "Statistical mechanical aids to calculating term
structure models," Phys. Rev. A, 12, 42, pp. 7057-7064
(1990).
5. L. Ingber, "Statistical mechanics of neocortical interac-
tions: A scaling paradigm applied to electroencephalogra-
phy," Phys. Rev. A, 6, 44, pp. 4017-4060 (1991).
6. L. Ingber and B. Rosen, "Genetic algorithms and very fast
simulated reannealing: A comparison," Mathl. Comput. Mod-
elling, 11, 16, pp. 87-100 (1992).
7. L. Ingber, "Simulated annealing: Practice versus theory,"
Statistics Comput., p. (to be published) (1993).
8. B. Rosen, "Function optimization based on advanced simulated
annealing," Report, University of Texas, San Antonio, TX
(1992).
9. L. Ingber, "Generic mesoscopic neural networks based on sta-
tistical mechanics of neocortical interactions," Phys. Rev.
A, 4, 45, pp. R2183-R2186 (1992).
[*] Some (p)reprints can be obtained via anonymous ftp from
ftp.umiacs.umd.edu [128.8.120.23] in the pub/ingber direc-
tory.
| Prof. Lester Ingber ingber at alumni.caltech.edu #
| P.O. Box 857 #
| McLean, VA 22101 703-848-1859 = [10ATT]0-700-L-INGBER #
More information about the Connectionists
mailing list