1 /**********************************************************************
2 ga_sa.c
3 **********************************************************************
4
5 ga_sa - A simulated annealling algorithm for comparison and search.
6 Copyright ©2002-2005, Stewart Adcock <stewart@linux-domain.com>
7 All rights reserved.
8
9 The latest version of this program should be available at:
10 http://gaul.sourceforge.net/
11
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version. Alternatively, if your project
16 is incompatible with the GPL, I will probably agree to requests
17 for permission to use the terms of any other license.
18
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY WHATSOEVER.
21
22 A full copy of the GNU General Public License should be in the file
23 "COPYING" provided with this distribution; if not, see:
24 http://www.gnu.org/
25
26 **********************************************************************
27
28 Synopsis: A simulated annealling algorithm for comparison and search.
29
30 **********************************************************************/
31
32 #include "gaul/ga_sa.h"
33
34 /**********************************************************************
35 ga_sa_boltzmann_acceptance()
36 synopsis: Simulated annealling acceptance criterion.
37 parameters:
38 return:
39 last updated: 14 Oct 2002
40 **********************************************************************/
41
ga_sa_boltzmann_acceptance(population * pop,entity * original,entity * putative)42 boolean ga_sa_boltzmann_acceptance( population *pop,
43 entity *original,
44 entity *putative )
45 {
46
47 return ( original->fitness < putative->fitness ||
48 random_boolean_prob(exp((putative->fitness-original->fitness)
49 /(GA_BOLTZMANN_FACTOR*pop->sa_params->temperature))) );
50 }
51
52
53 /**********************************************************************
54 ga_sa_linear_acceptance()
55 synopsis: Simulated annealling acceptance criterion.
56 parameters:
57 return:
58 last updated: 14 Oct 2002
59 **********************************************************************/
60
ga_sa_linear_acceptance(population * pop,entity * original,entity * putative)61 boolean ga_sa_linear_acceptance( population *pop,
62 entity *original,
63 entity *putative )
64 {
65
66 return ( original->fitness < putative->fitness+pop->sa_params->temperature );
67 }
68
69
70 /**********************************************************************
71 ga_population_set_sa_temperature()
72 synopsis: Sets the simulated annealling temperature.
73 Valid only for use during callbacks from
74 ga_simulated_annealling().
75 parameters:
76 return:
77 last updated: 11 Oct 2002
78 **********************************************************************/
79
ga_population_set_sa_temperature(population * pop,const double temp)80 void ga_population_set_sa_temperature( population *pop,
81 const double temp )
82 {
83
84 if ( !pop ) die("Null pointer to population structure passed.");
85 if ( !pop->sa_params )
86 die("ga_population_set_sa_parameters() must be called prior to ga_population_set_sa_temperature()");
87
88 pop->sa_params->temperature = temp;
89
90 return;
91 }
92
93
94 /**********************************************************************
95 ga_population_get_sa_temperature()
96 synopsis: Returns the current simulated annealling temperature.
97 parameters:
98 return:
99 last updated: 11 Oct 2002
100 **********************************************************************/
101
ga_population_get_sa_temperature(population * pop)102 double ga_population_get_sa_temperature( population *pop )
103 {
104
105 if ( !pop ) die("Null pointer to population structure passed.");
106 if ( !pop->sa_params )
107 die("ga_population_set_sa_parameters() must be called prior to ga_population_get_sa_temperature()");
108
109 return pop->sa_params->temperature;
110 }
111
112
113 /**********************************************************************
114 ga_population_set_sa_parameters()
115 synopsis: Sets the simulated annealling parameters for a
116 population.
117 parameters:
118 return:
119 last updated: 11 Oct 2002
120 **********************************************************************/
121
ga_population_set_sa_parameters(population * pop,GAsa_accept sa_accept,const double initial_temp,const double final_temp,const double temp_step,const int temp_freq)122 void ga_population_set_sa_parameters( population *pop,
123 GAsa_accept sa_accept,
124 const double initial_temp,
125 const double final_temp,
126 const double temp_step,
127 const int temp_freq )
128 {
129
130 if ( !pop ) die("Null pointer to population structure passed.");
131 if ( !sa_accept ) die("Null pointer to GAsa_accept callback passed.");
132
133 plog( LOG_VERBOSE,
134 "Population's SA parameters: inital_temp = %f final_temp = %f temp_step = %f temp_freq = %d",
135 initial_temp, final_temp, temp_step, temp_freq );
136
137 if (pop->sa_params == NULL)
138 pop->sa_params = s_malloc(sizeof(ga_sa_t));
139
140 pop->sa_params->sa_accept = sa_accept;
141 pop->sa_params->initial_temp = initial_temp;
142 pop->sa_params->final_temp = final_temp;
143 pop->sa_params->temp_step = temp_step;
144 pop->sa_params->temp_freq = temp_freq;
145 pop->sa_params->temperature = 0.0; /* Current temperature. */
146
147 return;
148 }
149
150
151 /**********************************************************************
152 ga_sa()
153 synopsis: Performs optimisation on the passed entity by using a
154 simplistic simulated annealling protocol. The local
155 search and fitness evaluations are performed using the
156 standard mutation and evaluation callback mechanisms,
157 respectively.
158
159 The passed entity will have its data overwritten. The
160 remainder of the population will be let untouched. Note
161 that it is safe to pass a NULL initial structure, in
162 which case a random starting structure wil be generated,
163 however the final solution will not be available to the
164 caller in any obvious way.
165
166 Custom cooling schemes may be introduced by using
167 ga_population_set_sa_temperature() from within
168 an iteration_hook callback.
169 parameters:
170 return:
171 last updated: 18 Feb 2005
172 **********************************************************************/
173
ga_sa(population * pop,entity * initial,const int max_iterations)174 int ga_sa( population *pop,
175 entity *initial,
176 const int max_iterations )
177 {
178 int iteration=0; /* Current iteration number. */
179 entity *putative; /* Current solution. */
180 entity *best; /* Current solution. */
181 entity *tmp; /* Used to swap working solutions. */
182
183 /* Checks. */
184 if (!pop) die("NULL pointer to population structure passed.");
185 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
186 if (!pop->mutate) die("Population's mutation callback is undefined.");
187 if (!pop->sa_params) die("ga_population_set_sa_params(), or similar, must be used prior to ga_sa().");
188
189 /* Prepare working entities. */
190 putative = ga_get_free_entity(pop);
191 best = ga_get_free_entity(pop);
192
193 /* Do we need to generate a random starting solution? */
194 if (!initial)
195 {
196 plog(LOG_VERBOSE, "Will perform simulated annealling with random starting solution.");
197
198 initial = ga_get_free_entity(pop);
199 ga_entity_seed(pop, best);
200 }
201 else
202 {
203 plog(LOG_VERBOSE, "Will perform simulated annealling with specified starting solution.");
204 ga_entity_copy(pop, best, initial);
205 }
206
207 /*
208 * Ensure that initial solution is scored.
209 */
210 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
211
212 plog( LOG_VERBOSE,
213 "Prior to the first iteration, the current solution has fitness score of %f",
214 best->fitness );
215
216 /*
217 * Do all the iterations:
218 *
219 * Stop when (a) max_iterations reached, or
220 * (b) "pop->iteration_hook" returns FALSE.
221 */
222 pop->sa_params->temperature = pop->sa_params->initial_temp;
223
224 while ( (pop->iteration_hook?pop->iteration_hook(iteration, best):TRUE) &&
225 iteration<max_iterations )
226 {
227 iteration++;
228
229 if (pop->sa_params->temp_freq == -1)
230 {
231 pop->sa_params->temperature = pop->sa_params->initial_temp
232 + ((double)iteration/max_iterations)
233 * (pop->sa_params->final_temp-pop->sa_params->initial_temp);
234 }
235 else
236 {
237 if ( pop->sa_params->temperature > pop->sa_params->final_temp
238 && iteration%pop->sa_params->temp_freq == 0 )
239 {
240 pop->sa_params->temperature -= pop->sa_params->temp_step;
241 }
242 }
243
244 /*
245 * Generate and score a new solution.
246 */
247 pop->mutate(pop, best, putative);
248 pop->evaluate(pop, putative);
249
250 /*
251 * Use the acceptance criterion to decide whether this new solution should
252 * be selected or discarded.
253 */
254 if ( pop->sa_params->sa_accept(pop, best, putative) )
255 {
256 tmp = best;
257 best = putative;
258 putative = tmp;
259 }
260
261 /*
262 * Save the current best solution in the initial entity, if this
263 * is now the best found so far.
264 */
265 if ( initial->fitness<best->fitness )
266 {
267 ga_entity_blank(pop, initial);
268 ga_entity_copy(pop, initial, best);
269 }
270
271 /*
272 * Use the iteration callback.
273 */
274 plog( LOG_VERBOSE,
275 "After iteration %d, the current solution has fitness score of %f",
276 iteration,
277 best->fitness );
278
279 } /* Iteration loop. */
280
281 /*
282 * Cleanup.
283 */
284 ga_entity_dereference(pop, best);
285 ga_entity_dereference(pop, putative);
286
287 return iteration;
288 }
289
290
291