1 /**********************************************************************
2 ga_tabu.c
3 **********************************************************************
4
5 ga_tabu - A tabu-search algorithm for comparison and local 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 tabu-search algorithm for comparison and local search.
29
30 A novel population-based tabu-search is also provided.
31 (Or at least it will be!)
32
33 **********************************************************************/
34
35 #include "gaul/ga_tabu.h"
36
37 /**********************************************************************
38 ga_tabu_check_integer()
39 synopsis: Compares two solutions with integer chromosomes and
40 returns TRUE if, and only if, they are exactly
41 identical.
42 parameters:
43 return:
44 last updated: 10 Oct 2002
45 **********************************************************************/
46
ga_tabu_check_integer(population * pop,entity * putative,entity * tabu)47 boolean ga_tabu_check_integer( population *pop,
48 entity *putative,
49 entity *tabu)
50 {
51 int i; /* Loop variable over chromosomes. */
52 int j; /* Loop variable over alleles. */
53 int *a, *b; /* Comparison integer arrays. */
54
55 /* Checks. */
56 if ( !pop ) die("Null pointer to population structure passed.");
57 if ( !putative || !tabu ) die("Null pointer to entity structure passed.");
58
59 for (i=0; i<pop->num_chromosomes; i++)
60 {
61 a = (int*)(putative->chromosome[i]);
62 b = (int*)(tabu->chromosome[i]);
63
64 for (j=0; j<pop->len_chromosomes; j++)
65 if (a[j] != b[j]) return FALSE;
66 }
67
68 return TRUE;
69 }
70
71
72 /**********************************************************************
73 ga_tabu_check_char()
74 synopsis: Compares two solutions with character chromosomes and
75 returns TRUE if, and only if, they are exactly
76 identical.
77 parameters:
78 return:
79 last updated: 14 Oct 2002
80 **********************************************************************/
81
ga_tabu_check_char(population * pop,entity * putative,entity * tabu)82 boolean ga_tabu_check_char( population *pop,
83 entity *putative,
84 entity *tabu)
85 {
86 int i; /* Loop variable over chromosomes. */
87 int j; /* Loop variable over alleles. */
88 char *a, *b; /* Comparison char arrays. */
89
90 /* Checks. */
91 if ( !pop ) die("Null pointer to population structure passed.");
92 if ( !putative || !tabu ) die("Null pointer to entity structure passed.");
93
94 for (i=0; i<pop->num_chromosomes; i++)
95 {
96 a = (char*)(putative->chromosome[i]);
97 b = (char*)(tabu->chromosome[i]);
98
99 for (j=0; j<pop->len_chromosomes; j++)
100 if (a[j] != b[j]) return FALSE;
101 }
102
103 return TRUE;
104 }
105
106
107 /**********************************************************************
108 ga_tabu_check_boolean()
109 synopsis: Compares two solutions with boolean chromosomes and
110 returns TRUE if, and only if, they are exactly
111 identical.
112 parameters:
113 return:
114 last updated: 14 Oct 2002
115 **********************************************************************/
116
ga_tabu_check_boolean(population * pop,entity * putative,entity * tabu)117 boolean ga_tabu_check_boolean( population *pop,
118 entity *putative,
119 entity *tabu)
120 {
121 int i; /* Loop variable over chromosomes. */
122 int j; /* Loop variable over alleles. */
123 boolean *a, *b; /* Comparison boolean arrays. */
124
125 /* Checks. */
126 if ( !pop ) die("Null pointer to population structure passed.");
127 if ( !putative || !tabu ) die("Null pointer to entity structure passed.");
128
129 for (i=0; i<pop->num_chromosomes; i++)
130 {
131 a = (boolean*)(putative->chromosome[i]);
132 b = (boolean*)(tabu->chromosome[i]);
133
134 for (j=0; j<pop->len_chromosomes; j++)
135 if (a[j] != b[j]) return FALSE;
136 }
137
138 return TRUE;
139 }
140
141
142 /**********************************************************************
143 ga_tabu_check_double()
144 synopsis: Compares two solutions with double chromosomes and
145 returns TRUE if, and only if, allele pair difference
146 is less than TINY.
147 parameters:
148 return:
149 last updated: 14 Oct 2002
150 **********************************************************************/
151
ga_tabu_check_double(population * pop,entity * putative,entity * tabu)152 boolean ga_tabu_check_double( population *pop,
153 entity *putative,
154 entity *tabu)
155 {
156 int i; /* Loop variable over chromosomes. */
157 int j; /* Loop variable over alleles. */
158 double *a, *b; /* Comparison double arrays. */
159
160 /* Checks. */
161 if ( !pop ) die("Null pointer to population structure passed.");
162 if ( !putative || !tabu ) die("Null pointer to entity structure passed.");
163
164 for (i=0; i<pop->num_chromosomes; i++)
165 {
166 a = (double*)(putative->chromosome[i]);
167 b = (double*)(tabu->chromosome[i]);
168
169 for (j=0; j<pop->len_chromosomes; j++)
170 if (a[j] < b[j]-TINY || a[j] > b[j]+TINY) return FALSE;
171 }
172
173 return TRUE;
174 }
175
176
177 /**********************************************************************
178 ga_tabu_check_bitstring()
179 synopsis: Compares two solutions with bitstring chromosomes and
180 returns TRUE if, and only if, all alleles are exactly
181 the same.
182 parameters:
183 return:
184 last updated: 14 Oct 2002
185 **********************************************************************/
186
ga_tabu_check_bitstring(population * pop,entity * putative,entity * tabu)187 boolean ga_tabu_check_bitstring( population *pop,
188 entity *putative,
189 entity *tabu)
190 {
191 int i; /* Loop variable over chromosomes. */
192 int j; /* Loop variable over alleles. */
193 byte *a, *b; /* Comparison bitstrings. */
194
195 /* Checks. */
196 if ( !pop ) die("Null pointer to population structure passed.");
197 if ( !putative || !tabu ) die("Null pointer to entity structure passed.");
198
199 for (i=0; i<pop->num_chromosomes; i++)
200 {
201 a = (byte*)(putative->chromosome[i]);
202 b = (byte*)(tabu->chromosome[i]);
203
204 for (j=0; j<pop->len_chromosomes; j++)
205 if (ga_bit_get( a, i ) != ga_bit_get( b, i )) return FALSE;
206 }
207
208 return TRUE;
209 }
210
211
212 /**********************************************************************
213 gaul_check_tabu_list()
214 synopsis: Checks the tabu list verses the putative solutions and
215 chooses an acceptable solution. Returns -1 if all
216 putative solutions are tabu.
217 parameters:
218 return:
219 last updated: 14 Oct 2002
220 **********************************************************************/
221
gaul_check_tabu_list(population * pop,entity ** putative,entity ** tabu)222 static int gaul_check_tabu_list( population *pop,
223 entity **putative,
224 entity **tabu)
225 {
226 int i; /* Loop variable over putative solutions. */
227 int j; /* Loop variable over tabu list. */
228 boolean is_tabu; /* Whether current solution is tabu. */
229
230 for (i=0; i<pop->tabu_params->search_count; i++)
231 {
232 is_tabu = FALSE;
233 for (j=0; j<pop->tabu_params->list_length && tabu[j]!=NULL && is_tabu==FALSE; j++)
234 {
235 is_tabu = pop->tabu_params->tabu_accept(pop,putative[i],tabu[j]);
236 }
237 if (is_tabu==FALSE)
238 { /* This solution is not tabu. */
239 return i;
240 }
241 }
242
243 /* All solutions are tabu. */
244 return -1;
245 }
246
247
248 /**********************************************************************
249 ga_population_set_tabu_parameters()
250 synopsis: Sets the tabu-search parameters for a population.
251 parameters:
252 return:
253 last updated: 09 Oct 2002
254 **********************************************************************/
255
ga_population_set_tabu_parameters(population * pop,GAtabu_accept tabu_accept,const int list_length,const int search_count)256 void ga_population_set_tabu_parameters( population *pop,
257 GAtabu_accept tabu_accept,
258 const int list_length,
259 const int search_count)
260 {
261
262 if ( !pop ) die("Null pointer to population structure passed.");
263 if ( !tabu_accept ) die("Null pointer to GAtabu_accept callback passed.");
264
265 plog( LOG_VERBOSE,
266 "Population's tabu-search parameters: list_length = %d search_count = %d",
267 list_length, search_count );
268
269 if (pop->tabu_params == NULL)
270 pop->tabu_params = s_malloc(sizeof(ga_tabu_t));
271
272 pop->tabu_params->tabu_accept = tabu_accept;
273 pop->tabu_params->list_length = list_length;
274 pop->tabu_params->search_count = search_count;
275
276 return;
277 }
278
279
280 /**********************************************************************
281 ga_tabu()
282 synopsis: Performs optimisation on the passed entity by using a
283 simplistic tabu-search. The local search and fitness
284 evaluations are performed using the standard mutation
285 and evaluation callback mechanisms, respectively.
286 The passed entity will have its data overwritten. The
287 remainder of the population will be let untouched.
288 Note that it is safe to pass a NULL initial structure,
289 in which case a random starting structure wil be
290 generated, however the final solution will not be
291 available to the caller in any obvious way.
292 parameters:
293 return:
294 last updated: 18 Feb 2005
295 **********************************************************************/
296
ga_tabu(population * pop,entity * initial,const int max_iterations)297 int ga_tabu( population *pop,
298 entity *initial,
299 const int max_iterations )
300 {
301 int iteration=0; /* Current iteration number. */
302 int i, j; /* Index into putative solution array. */
303 entity *best; /* Current best solution. */
304 entity **putative; /* Current working solutions. */
305 entity *tmp; /* Used to swap working solutions. */
306 entity **tabu_list; /* Tabu list. */
307 int tabu_list_pos=0; /* Index into the tabu list. */
308
309 /* Checks. */
310 if (!pop) die("NULL pointer to population structure passed.");
311 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
312 if (!pop->mutate) die("Population's mutation callback is undefined.");
313 if (!pop->rank) die("Population's ranking callback is undefined.");
314 if (!pop->tabu_params) die("ga_population_set_tabu_params(), or similar, must be used prior to ga_tabu().");
315 if (!pop->tabu_params->tabu_accept) die("Population's tabu acceptance callback is undefined.");
316
317 /* Prepare working entities. */
318 best = ga_get_free_entity(pop); /* The best solution so far. */
319 putative = s_malloc(sizeof(entity *)*pop->tabu_params->search_count);
320
321 for (i=0; i<pop->tabu_params->search_count; i++)
322 {
323 putative[i] = ga_get_free_entity(pop); /* The 'working' solutions. */
324 }
325
326 /* Allocate and clear an array for the tabu list. */
327 tabu_list = s_malloc(sizeof(vpointer)*pop->tabu_params->list_length);
328
329 for (i=0; i<pop->tabu_params->list_length; i++)
330 {
331 tabu_list[i] = NULL;
332 }
333
334 /* Do we need to generate a random starting solution? */
335 if (!initial)
336 {
337 plog(LOG_VERBOSE, "Will perform tabu-search with random starting solution.");
338
339 initial = ga_get_free_entity(pop);
340 ga_entity_seed(pop, best);
341 }
342 else
343 {
344 plog(LOG_VERBOSE, "Will perform tabu-search with specified starting solution.");
345 ga_entity_copy(pop, best, initial);
346 }
347
348 /*
349 * Ensure that initial solution is scored.
350 */
351 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
352
353 plog( LOG_VERBOSE,
354 "Prior to the first iteration, the current solution has fitness score of %f",
355 best->fitness );
356
357 /*
358 * Do all the iterations:
359 *
360 * Stop when (a) max_iterations reached, or
361 * (b) "pop->iteration_hook" returns FALSE.
362 */
363 while ( (pop->iteration_hook?pop->iteration_hook(iteration, best):TRUE) &&
364 iteration<max_iterations )
365 {
366 iteration++;
367
368 /*
369 * Generate and score new solutions.
370 */
371 for (i=0; i<pop->tabu_params->search_count; i++)
372 {
373 pop->mutate(pop, best, putative[i]);
374 pop->evaluate(pop, putative[i]);
375 }
376
377 /*
378 * Sort new solutions (putative[0] will have highest rank).
379 * We assume that there are only a small(ish) number of
380 * solutions and, therefore, a simple bubble sort is adequate.
381 */
382 for (i=1; i<pop->tabu_params->search_count; i++)
383 {
384 for (j=pop->tabu_params->search_count-1; j>=i; j--)
385 {
386 if ( pop->rank(pop, putative[j], pop, putative[j-1]) > 0 )
387 { /* Perform a swap. */
388 tmp = putative[j];
389 putative[j] = putative[j-1];
390 putative[j-1] = tmp;
391 }
392 }
393 }
394
395 /*
396 * Save best solution if it is an improvement, otherwise
397 * select the best non-tabu solution (if any).
398 * If appropriate, update the tabu list.
399 */
400 if ( pop->rank(pop, putative[0], pop, best) > 0 )
401 {
402 tmp = best;
403 best = putative[0];
404 putative[0] = tmp;
405 if (tabu_list[tabu_list_pos] == NULL)
406 {
407 tabu_list[tabu_list_pos] = ga_entity_clone(pop, best);
408 }
409 else
410 {
411 ga_entity_blank(pop, tabu_list[tabu_list_pos]);
412 ga_entity_copy(pop, tabu_list[tabu_list_pos], best);
413 }
414 tabu_list_pos++;
415 if (tabu_list_pos >= pop->tabu_params->list_length)
416 tabu_list_pos=0;
417 }
418 else
419 {
420 if ( -1 < (j = gaul_check_tabu_list(pop, putative, tabu_list)) )
421 {
422 tmp = best;
423 best = putative[j];
424 putative[j] = tmp;
425 if (tabu_list[tabu_list_pos] == NULL)
426 {
427 tabu_list[tabu_list_pos] = ga_entity_clone(pop, best);
428 }
429 else
430 {
431 ga_entity_blank(pop, tabu_list[tabu_list_pos]);
432 ga_entity_copy(pop, tabu_list[tabu_list_pos], best);
433 }
434 tabu_list_pos++;
435 if (tabu_list_pos >= pop->tabu_params->list_length)
436 tabu_list_pos=0;
437 }
438 }
439
440 /*
441 * Save the current best solution in the initial entity, if this
442 * is now the best found so far.
443 */
444 if ( pop->rank(pop, best, pop, initial) > 0 )
445 {
446 ga_entity_blank(pop, initial);
447 ga_entity_copy(pop, initial, best);
448 }
449
450 /*
451 * Use the iteration callback.
452 */
453 plog( LOG_VERBOSE,
454 "After iteration %d, the current solution has fitness score of %f",
455 iteration,
456 best->fitness );
457
458 } /* Iteration loop. */
459
460 /*
461 * Cleanup.
462 */
463 ga_entity_dereference(pop, best);
464
465 for (i=0; i<pop->tabu_params->search_count; i++)
466 {
467 ga_entity_dereference(pop, putative[i]);
468 }
469
470 for (i=0; i<pop->tabu_params->list_length; i++)
471 {
472 if (tabu_list[i] != NULL)
473 ga_entity_dereference(pop, tabu_list[i]);
474 }
475
476 s_free(putative);
477 s_free(tabu_list);
478
479 return iteration;
480 }
481
482
483