-
Notifications
You must be signed in to change notification settings - Fork 2
/
README-orig.txt
224 lines (176 loc) · 9.23 KB
/
README-orig.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
Simulated Annealing Package
When one trys to estimate such things as the minimum, or the
least-squares optimal parameters of a nonlinear system, the
existence of multiple local minima can cause problems with the
determination of the global optimum. Techniques such as Newton's
method, the Simplex method and Least-squares Linear Taylor
Differential correction technique can be useful provided that
one is lucky enough to start sufficiently close to the global minimum.
All these methods suffer from the inability to distinguish a local
minimum from a global one because they follow the local gradients
towards the minimum. Simulated annealing is a technique for solving
such problems. It works by following local gradients, but occasionally
it will move against the gradient in order to escape a local extremum.
The attached code implements a straightforward Simulated
Annealing package. There are three versions of the package, one in
C, one in C++ and one in Ada. You will find each version in its own
subdirectory.
There are two sample driver programs for each package
(the first example program for the C and C++ versions can be compiled
for two different examples). The first example is finding the
global minimum of a function that has multiple local minima
(the second version of this example puts constraints on the range
that the search can be done over). The second example finds the
optimal fit to the function:
y = (1-(x/a)**2) exp( - (x/b)**2 )
Since this function is nonlinear, there is no closed form analytic least
squares solution. There are two input data sets that can be used
(data3n.dat and data3rn.dat each with different noise levels). The
actual parameters are a = 70.0, and b = 50.0 (note that because of the
squares of the parameters, the positive and negative values of these
parameters are equivalent).
The C and C++ code is initializes with a pointer to the
cost function and the number of parameters it contains. The Ada
code implements the library as a generic package and so the cost
function is bound to the library at compile time. The cost
function should take as parameters a vector of the parameters and
return a measure of how good the current estimate of the parameters
is (the smaller the better). Both versions of the first example are
one dimensional, the second example is two dimensional.
The routines:
SAInit() - (C, Ada)
Informs the library of the cost function to
apply and its dimension. (The C++ equivalent is
the constructor for the object). The Ada version
just accepts the number of dimensions of the system
as a parameter since the function to use is bound
to the library at compile time.
Returns a 0 if the initialization fails.
SAfree() - (C)
Releases internally allocated space for the
library. (The C++ equivalent is the destructor for
the object, there is no Ada equivalent).
SAinitial() - (C, Ada)
initial() - (C++)
Sets the initial guess values of the parameters
to be optimized.
SAcurrent() - (C, Ada)
current() - (C++)
Gets the current values of the parameters, after
the annealing is performed, this the near optimum
estimate of the parameters.
SAoptimum() - (C, Ada)
optimum() - (C++)
Gets the best values of the parameters found so
far. Because during the final annealing process
the iterations may have stopped during an upgradient
exploration, the current values of the parameters
may not be the best ones found (the more iterations
that are performed, the less likely that this will
be the case). As a hedge against this possibility,
the best values found are stored separately. This
routine returns this value.
SAMelt() - (C, Ada)
melt() - (C++)
This routine "heats" the system starting at the
current temperature, until a phase change is
detected. The phase change is determined by the
occurence by a large jump in the specific heat
for the system. This routine returns the melting
temperature for diagnostic purposes.
SAanneal() - (C, Ada)
This routine applies a Cauchy cooling schedule
to the system in order to perform the annealing
process. This routine returns the final temperature
of the system for diagnostic purposes.
The following routines are all QUERY/SET functions, they all
provide a means to query and/or set certain internal parameters.
In order to SET a value, just pass the desired quantity to the
function. To QUERY a value, in C pass the predefined quantity
NO_VALUE, in C++ and Ada just call the function with no parameters.
SABoltzmann() - (C, Ada)
Boltzmann() - (C++)
Set/Query the "Boltzmann" constant for this
problem. This constant is used as a scaling
factor in the calculation of the probabilities
for accepting upgradient changes in the parameters.
SAlearning_rate() - (C, Ada)
learning_rate() - (C++)
Set/Query the "learning rate". This parameter
determines how heavily to weight the temperature
when calculating the parameter jump sizes.
SAtemperature() - (C, Ada)
temperature() - (C++)
Set/Query the system "temperature". Ordinarily
this is not set by the application, although I
have often found it worthwhile to "heat" the
system a little above the melting point before
begining the annealing process.
SAjump() - (C, Ada)
jump() - (C++)
Set/Query the critical value of the jump in
the specific heat that is required for the system
to be considered to be melted. This value is
the minimum Specific_Heat/Old_Specific_Heat that
is to be used.
SAiterations() - (C, Ada)
iterations() - (C++)
Set/Query the number of iterations to be used
in the annealing process. This can be used to
set or query the default value that will be used
if it is not specified in the SAanneal() ( or
anneal() ) routine.
Extensions to the code:
The code is written to be as general as possible, trading off
optimization in favor of generality. There are almost certainly ways
to speed up the code if the structure of a specific problem is accounted
for.
A possible extension that would be easy to do, is to allow more
than one simulated annealing process to exist within a single program.
This can be readily done in the C and Ada code because all the data is
maintained within a hidden structure. All that would need to be done
is to have SAInit() create each structure dynamically and to return a
handle to that structure instead of a 1/0. All the other routines would
then need to be modified to have an additional parameter that is the
handle for the annealing object. The C++ code supports multiple objects
directly without the need for any modification.
The Random number generator:
I have provided a 31 or 16 bit implementation of the random number
generator known as R250. This generator not only has fairly good
statistical properties, but it is also fast. It compares about 15%
faster than other random number generators that I have tried. Its period
is 2^249, so the 16 bit version is actually practical to use, the
default compiler settings are for 31 bits.
Portability notes:
This code should port to different platforms readily. I
have run it on MS-DOS with Zortech C++ V3.0 and Borland C++ V3.0.
On Unix I have run it with the AT&T V2.1 C++ compiler on MIPS and
Silicon Graphics workstations and on the Linux operating system.
The system dependencies that I am aware of can be handled by the
macros within the Makefile.
The CPU timer function may need to be rewritten for some systems.
I have NOT provided an MS-DOS version. (I have a millisecond resolution
CPU timer for MS-DOS and can provide it to those that request it).
The Makefile was written for Unix systems. Some changes will be
necessary for using in on MS-DOS. The site dependent stuff is
all at the top of the Makefile, I have tried to make the changes
obvious (but since this package has not been beta tested, I
would appreciate any feedback).
The C library is written to directly provide for either an ANSI-C
compiler or the older style K&R compiler. If you have the older
compiler define the macro NO_PROTO (i.e. compile with -DNO_PROTO
in the compile command). The example programs are written for
ANSI-C, but following the example of the include file SA.H, you
should be able to hand edit the function prototypes so that it
will compile under a K&R compiler.
Intercomparison of packages:
To within roundoff differences, these packages will give
the same result regardless of the language being used. However
in order to make the comparison, the initial guess of the solution
should not be done using the random number generator. This is
because the differences in how the global random number routine
is handled in the procedural C code and the object oriented C++ code.
Everett (Skip) Carter Phone: 408-641-0645 FAX: 408-641-0647
Taygeta Scientific Inc. INTERNET: skip@taygeta.com
1340 Munras Ave., Suite 314 UUCP: ...!uunet!taygeta!skip
Monterey, CA. 93940 WWW: http://www.taygeta.com/skip.html