asa-readme.ms

simulated annealing code ASA

.[
%A L. Ingber
%T Adaptive Simulated Annealing (ASA) and Path-Integral
(PATHINT) Algorithms: Generic Tools for Complex Systems
%R ASA-PATHINT Lecture Plates
%I Lester Ingber Research
%D 2001
%O Invited talk U Calgary, Canada, April 2001.
URL http://www.ingber.com/asa01_lecture.pdf
.]
including specific disciplines such as finance,
.[
%A L. Ingber
%T Statistical mechanical aids to calculating term structure models
%J Physical Review A
%V 42
%D 1990
%P 7057-7064
%O URL http://www.ingber.com/markets90_interest.pdf
.]
.[
%A L. Ingber
%T Statistical mechanics of nonlinear nonequilibrium financial markets:
Applications to optimized trading
%J Mathematical Computer Modelling
%V 23
%P 101-121
%D 1996
%O URL http://www.ingber.com/markets96_trading.pdf
.]
.[
%A L. Ingber
%T Canonical momenta indicators of financial markets and neocortical EEG
%B Progress in Neural Information Processing
%E S.-I. Amari
%E L. Xu
%E I. King
%E K.-S. Leung
%I Springer
%C New York
%P 777-784
%D 1996
%O Invited paper to the 1996 International Conference on Neural Information
Processing (ICONIP'96), Hong Kong, 24-27 September 1996.
ISBN 981 3083-05-0.  URL http://www.ingber.com/markets96_momenta.pdf
.]
.[
%A L. Ingber
%A R.P. Mondescu
%T Optimization of Trading Physics Models of Markets
%D 2001
%V 12
%N 4
%P 776-790
%J IEEE Trans. Neural Networks
%O Invited paper for special issue on Neural Networks in
Financial Engineering. URL http://www.ingber.com/markets01_optim_trading.pdf
.]
.[
%A L. Ingber
%A R.P. Mondescu
%B Intelligent Internet-Based Information Processing Systems
%T Automated internet trading based on optimized physics models
of markets
%E R.J. Howlett
%E N.S. Ichalkaranje
%E L.C. Jain
%E G. Tonfoni
%I World Scientific
%C Singapore
%D 2003
%P 305-356
%O Invited paper. URL http://www.ingber.com/markets03_automated.pdf
.]
.[
%A L. Ingber
%T Statistical Mechanics of Financial Markets (SMFM):
Applications to Trading Indicators and Options
%R SMFM Lecture Plates
%I Lester Ingber Research
%D 2001
%O Invited talk U Calgary, Canada, April 2001. Invited talk U
Florida, Gainesville, April 2002. Invited talk Tulane U, New
Orleans, January 2003. URL http://www.ingber.com/markets01_lecture.pdf
.]
neuroscience,
.[
%A L. Ingber
%T Statistical mechanics of neocortical interactions:
A scaling paradigm applied to electroencephalography
%J Physical Review A
%V 44
%P 4017-4060
%D 1991
%O URL http://www.ingber.com/smni91_eeg.pdf
.]
.[
%A L. Ingber
%T Statistical mechanics of neocortical interactions:
Canonical momenta indicators of EEG
%J Physical Review E
%V 55
%P 4578-4593
%D 1997
%O URL http://www.ingber.com/smni97_cmi.pdf
.]
.[
%A L. Ingber
%T Statistical mechanics of neocortical interactions:
Training and testing canonical momenta indicators of EEG
%J Mathl. Computer Modelling
%V 27
%P 33-64
%D 1998
%O URL http://www.ingber.com/smni98_cmi_test.pdf
.]
.[
%A L. Ingber
%T Statistical Mechanics of Neocortical Interactions (SMNI):
Multiple Scales of Short-Term Memory and EEG Phenomena
%R SMNI Lecture Plates
%I Lester Ingber Research
%D 2001
%O Invited talk U Calgary, Canada, April 2001.
URL http://www.ingber.com/smni01_lecture.pdf
.]
and combat analyses.
.[
%A L. Ingber
%A H. Fujio
%A M.F. Wehner
%T Mathematical comparison of combat computer models to
exercise data
%J Mathematical Computer Modelling
%V 15
%N 1
%P 65-90
%D 1991
%O URL http://www.ingber.com/combat91_data.pdf
.]
.[
%A L. Ingber
%A D.D. Sworder
%T Statistical mechanics of combat with human factors
%J Mathematical Computer Modelling
%V 15
%N 11
%D 1991
%P 99-127
%O URL http://www.ingber.com/combat91_human.pdf
.]
.[
%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
.]
.[
%A M. Bowman
%A L. Ingber
%T Canonical momenta of nonlinear combat
%B Proceedings of the 1997 Simulation Multi-Conference, 6-10 April 1997,
Atlanta, GA
%I Society for Computer Simulation
%C San Diego, CA
%D 1997
%O URL http://www.ingber.com/combat97_cmi.pdf
.]
.[
%A L. Ingber
%T Statistical Mechanics of Combat (SMC): Mathematical
Comparison of Computer Models to Exercise Data
%R SMC Lecture Plates
%I Lester Ingber Research
%D 2001
%O URL http://www.ingber.com/combat01_lecture.pdf
.]
Some papers illustrate the combined use of ASA for optimization and
sampling.
.[
%A L. Ingber
%T Ideas by Statistical Mechanics (ISM)
%R Report 2006:ISM
%D 2006
%I Lester Ingber Research
%C Ashland, OR
%O URL http://www.ingber.com/smni06_ism.pdf
.]
The http://www.ingber.com/asa_papers.html file in the ASA archive
contains references to some patents and papers using ASA and VFSR.
.in 0
.\"             Equations set only in PostScript\(rg ([g]troff)
.if t \{\
.EQ
delim $$
gsize 11
.EN
.\}
.NH 2
Outline of ASA Algorithm
.XS
\*(SN 		Outline of ASA Algorithm
.XE
.PP
Details of the ASA algorithm are best obtained from the published
papers.  There are three parts to its basic structure.
.NH 3
Generating Probability Density Function
.XS
\*(SN 			Generating Probability Density Function
.XE
.PP
In a
.if t $D$-dimensional
.if n D\-dimensional
parameter space with parameters
.if t $p sup i$
.if n p^i
having ranges
.if t $[ A sub i ,~ B sub i ]$,
.if n [A_i, B_i],
about the
.if t $k$'th
.if n k'th
last saved point (e.g, a local optima),
.if t $p sub k sup i$,
.if n p_k^i,
a new point is generated using a distribution defined by the product
of distributions for each parameter,
.if t $g sup i ( y sup i ;^ T sub i )$
.if n g^i(y^i; T_i),
in terms of random variables
.if t $y sup i \(mo [ -1 ,~ 1]$,
.if n y^i in [-1, 1],
where
.if t $p sub k+1 sup i$ = $p sub k sup i + y sup i ( B sub i - A sub i )$,
.if n p_k+1^i = p_k^i + y^i(B_i - A_i),
and \*Qtemperatures\*U
.if t $T sub i$,
.if n T_i,
.ie t \{\
.EQ I
g sup i ( y sup i ;^ T sub i ) = 1 over { 2 ( | y sup i | + T sub i )
ln ( 1 + 1 / T sub i ) } ~.
.EN
.\}
.el \{\
.in +8n
g^i(y^i; T_i) = 1/[2(|y^i| + T_i)(1 + 1/T_i)].
.in 0
.\}
The DEFINE_OPTIONS USER_GENERATING_FUNCTION permits using an
alternative to this ASA distribution function.
.NH 3
Acceptance Probability Density Function
.XS
\*(SN 			Acceptance Probability Density Function
.XE
.PP
The cost functions,
.if t $C ( p sub k+1 ) - C ( p sub k )$,
.if n C(p_k+1) - C(p_k),
are compared using a uniform random generator,
.if t $U \(mo [ 0 ,~ 1 )$,
.if n U in [0, 1),
in a \*QBoltzmann\*U test: If
.ie t \{\
.EQ I
exp [ - fat ( C (p sub k+1 )  - C ( p sub k ) fat ) /
T sub {roman cost} ] > U ~,
.EN
.\}
.el \{\
.in +8n
exp[-(C(p_k+1) - C(p_k))/T_cost] > U,
.in 0
.\}
where
.if t $T sub {roman cost}$
.if n T_cost
is the \*Qtemperature\*U used for this test, then the new point is
accepted as the new saved point for the next iteration.  Otherwise, the
last saved point is retained.  The DEFINE_OPTIONS USER_ACCEPT_ASYMP_EXP
or USER_ACCEPT_THRESHOLD permit using alternatives to this Boltzmann
distribution function.
.NH 3
Reannealing Temperature Schedule
.XS
\*(SN 			Reannealing Temperature Schedule
.XE
.PP
The annealing schedule for each parameter temperature,
.if t $T sub i$
.if n T_i,
from a starting temperature
.if t $T sub i0$,
.if n T_i0,
is
.ie t \{\
.EQ I
T sub i ( k sub i ) = T sub 0i exp ( - c sub i k sub i sup 1/D ) ~.
.EN
.\}
.el \{\
.in +8n
T_i(k_i) = T_0i exp(-c_i k_i^(1/D)).
.in 0
.\}
This is discussed further below.
.PP
The annealing schedule for the cost temperature is developed similarly
to the parameter temperatures.  However, the index for reannealing the
cost function,
.if t $k sub {roman cost}$,
.if n k_cost,
is determined by the number of accepted points, instead of the number
of generated points as used for the parameters.  This choice was made
because the Boltzmann acceptance criteria uses an exponential
distribution which is not as fat\-tailed as the ASA distribution used
for the parameters.  This schedule can be modified using several
OPTIONS.  In particular, the Pre\-Compile DEFINE_OPTIONS
USER_COST_SCHEDULE permits quite arbitrary functional modifications for
this annealing schedule, and the Pre\-Compile DEFINE_OPTIONS
.PP
As determined by the Program Options selected, the parameter
\*Qtemperatures\*U may be periodically adaptively reannealed, or
increased relative to their previous values, using their relative first
derivatives with respect to the cost function, to guide the search
\*Qfairly\*U among the parameters.
.PP
As determined by the Program Options selected,
the reannealing of the cost temperature resets the scale of the
the annealing of the cost acceptance criteria as
.ie t \{\
.EQ I
T sub {roman cost} ( k sub {roman cost} ) = T sub {0 ~ roman cost}
exp ( - c sub {roman cost} k sub {roman cost} sup 1/D ) ~.
.EN
.\}
.el \{\
.in +8n
T_cost(k_cost) = T_0cost exp(-c_cost k_cost^(1/D)).
.in 0
.\}