1 /**********************************************************************
2 ga_systematicsearch.c
3 **********************************************************************
4
5 ga_systematicsearch - Systematic 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 systematic search algorithm for comparison and local
29 search.
30
31 **********************************************************************/
32
33 #include "gaul/ga_systematicsearch.h"
34
35 /**********************************************************************
36 ga_population_set_search_parameters()
37 synopsis: Sets the systematic search parameters for a population.
38 parameters:
39 return:
40 last updated: 08 Nov 2002
41 **********************************************************************/
42
ga_population_set_search_parameters(population * pop,GAscan_chromosome scan_chromosome)43 void ga_population_set_search_parameters( population *pop,
44 GAscan_chromosome scan_chromosome)
45 {
46
47 if ( !pop ) die("Null pointer to population structure passed.");
48 if ( !scan_chromosome ) die("Null pointer to GAscan_chromosome callback passed.");
49
50 if (pop->search_params == NULL)
51 pop->search_params = s_malloc(sizeof(ga_search_t));
52
53 pop->search_params->scan_chromosome = scan_chromosome;
54 pop->search_params->chromosome_state = 0;
55 pop->search_params->allele_state = 0;
56
57 return;
58 }
59
60
61 /**********************************************************************
62 ga_search()
63 synopsis: Performs a systematic search procedure.
64 The passed entity will have its data overwritten. The
65 remainder of the population will be let untouched.
66 Note that it is safe to pass a NULL initial structure,
67 however the final solution will not be
68 available to the caller in any obvious way.
69 parameters:
70 return:
71 last updated: 18 Feb 2005
72 **********************************************************************/
73
ga_search(population * pop,entity * best)74 int ga_search( population *pop,
75 entity *best)
76 {
77 int iteration=0; /* Current iteration number. */
78 entity *putative; /* Current solution. */
79 entity *tmp; /* Used to swap entities. */
80 int enumeration=0; /* Enumeration index. */
81 boolean finished=FALSE; /* Whether search is complete. */
82
83 /* Checks. */
84 if (!pop) die("NULL pointer to population structure passed.");
85 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
86 if (!pop->search_params) die("ga_population_set_search_params(), or similar, must be used prior to ga_search().");
87 if (!pop->search_params->scan_chromosome) die("Population's chromosome scan callback is undefined.");
88
89 /* Prepare working entity. */
90 putative = ga_get_free_entity(pop);
91
92 plog(LOG_VERBOSE, "Will perform systematic search.");
93
94 /* Do we need to allocate starting solution? */
95 if (!best)
96 {
97 best = ga_get_free_entity(pop);
98 ga_entity_seed(pop, best);
99 }
100
101 /*
102 * Ensure that initial solution is scored.
103 */
104 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
105
106 /*
107 * Prepare internal data for the enumeration algorithm.
108 */
109 pop->search_params->chromosome_state = 0;
110 pop->search_params->allele_state = 0;
111
112 /*
113 * Do all the iterations:
114 *
115 * Stop when (a) All enumerations performed or
116 * (b) "pop->iteration_hook" returns FALSE.
117 */
118 while ( (pop->iteration_hook?pop->iteration_hook(iteration, best):TRUE) &&
119 finished == FALSE )
120 {
121 iteration++;
122
123 /*
124 * Generate and score a new solution.
125 */
126 ga_entity_blank(pop, putative);
127 finished = pop->search_params->scan_chromosome(pop, putative, enumeration);
128 pop->evaluate(pop, putative);
129
130 /*
131 * Decide whether this new solution should be selected or discarded based
132 * on the relative fitnesses.
133 */
134 if ( putative->fitness > best->fitness )
135 {
136 tmp = best;
137 best = putative;
138 putative = tmp;
139 }
140
141 /*
142 * Use the iteration callback.
143 */
144 plog( LOG_VERBOSE,
145 "After iteration %d, the current solution has fitness score of %f",
146 iteration,
147 best->fitness );
148
149 } /* Iteration loop. */
150
151 /*
152 * Cleanup.
153 */
154 ga_entity_dereference(pop, putative);
155
156 return iteration;
157 }
158
159
160