1 /**********************************************************************
2 ga_deterministiccrowding.c
3 **********************************************************************
4
5 ga_deterministiccrowding - Deterministic crowding.
6 Copyright ©2003-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: Deterministic crowding.
29
30 **********************************************************************/
31
32 #include "gaul/ga_deterministiccrowding.h"
33
34 /**********************************************************************
35 ga_population_set_deterministiccrowding_parameters()
36 synopsis: Sets the deterministic crowding parameters for a
37 population.
38 parameters: population *pop Population to set parameters of.
39 const GAcompare Callback to compare two entities.
40 return: none
41 last updated: 20 May 2003
42 **********************************************************************/
43
ga_population_set_deterministiccrowding_parameters(population * pop,const GAcompare compare)44 void ga_population_set_deterministiccrowding_parameters( population *pop,
45 const GAcompare compare )
46 {
47
48 if ( !pop ) die("Null pointer to population structure passed.");
49 if ( !compare ) die("Null pointer to GAcompare callback passed.");
50
51 plog( LOG_VERBOSE, "Population's deterministic crowding parameters set" );
52
53 if (pop->dc_params == NULL)
54 pop->dc_params = s_malloc(sizeof(ga_dc_t));
55
56 pop->dc_params->compare = compare;
57
58 return;
59 }
60
61
62 /**********************************************************************
63 ga_deterministiccrowding()
64 synopsis: Performs optimisation of the given population by a
65 method known as determinstic crowding.
66 ga_genesis(), or equivalent, must be called prior to
67 this function.
68 This approach is useful when you desire a
69 significant amount of diversity in the resulting
70 population.
71 This was designed as a niching algorithm rather than
72 an optimisation algorithm.
73 During a generation, children potentially replace
74 their parents as soon as they are created, rather
75 than replacing them at the end of the generation.
76 This differs slightly from the canonical
77 deterministic crowding algorithm.
78 parameters:
79 return:
80 last updated: 18 Feb 2005
81 **********************************************************************/
82
ga_deterministiccrowding(population * pop,const int max_generations)83 int ga_deterministiccrowding( population *pop,
84 const int max_generations )
85 {
86 int generation=0; /* Current generation number. */
87 int *permutation, *ordered; /* Arrays of entities. */
88 entity *mother, *father; /* Current entities. */
89 entity *son, *daughter, *entity; /* Current entities. */
90 int i; /* Loop variable over entities. */
91 double dist1, dist2; /* Genetic or phenomic distances. */
92 int rank; /* Rank of entity in population. */
93
94 /* Checks. */
95 if (!pop)
96 die("NULL pointer to population structure passed.");
97 if (!pop->dc_params)
98 die("ga_population_set_deterministiccrowding_params(), or similar, must be used prior to ga_deterministiccrowding().");
99
100 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
101 if (!pop->mutate) die("Population's mutation callback is undefined.");
102 if (!pop->crossover) die("Population's crossover callback is undefined.");
103
104 if (!pop->dc_params->compare) die("Population's comparison callback is undefined.");
105
106 plog(LOG_VERBOSE, "The evolution by deterministic crowding has begun!");
107
108 pop->generation = 0;
109
110 /*
111 * Score the initial population members.
112 */
113 if (pop->size < pop->stable_size)
114 gaul_population_fill(pop, pop->stable_size - pop->size);
115
116 for (i=0; i<pop->size; i++)
117 {
118 if (pop->entity_iarray[i]->fitness == GA_MIN_FITNESS)
119 pop->evaluate(pop, pop->entity_iarray[i]);
120 }
121
122 sort_population(pop);
123 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
124
125
126 /*
127 * Prepare arrays to store permutations.
128 */
129 permutation = s_malloc(sizeof(int)*pop->size);
130 ordered = s_malloc(sizeof(int)*pop->size);
131 for (i=0; i<pop->size;i++)
132 ordered[i]=i;
133
134 plog( LOG_VERBOSE,
135 "Prior to the first generation, population has fitness scores between %f and %f",
136 pop->entity_iarray[0]->fitness,
137 pop->entity_iarray[pop->size-1]->fitness );
138
139 /*
140 * Do all the generations:
141 *
142 * Stop when (a) max_generations reached, or
143 * (b) "pop->generation_hook" returns FALSE.
144 */
145 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
146 generation<max_generations )
147 {
148 generation++;
149 pop->generation = generation;
150 pop->orig_size = pop->size;
151
152 plog(LOG_DEBUG,
153 "Population size is %d at start of generation %d",
154 pop->orig_size, generation );
155
156 sort_population(pop);
157
158 random_int_permutation(pop->orig_size, ordered, permutation);
159
160 for ( i=0; i<pop->orig_size; i++ )
161 {
162 mother = pop->entity_iarray[i];
163 father = pop->entity_iarray[permutation[i]];
164
165 /*
166 * Crossover step.
167 */
168 plog(LOG_VERBOSE, "Crossover between %d (rank %d fitness %f) and %d (rank %d fitness %f)",
169 ga_get_entity_id(pop, mother),
170 ga_get_entity_rank(pop, mother), mother->fitness,
171 ga_get_entity_id(pop, father),
172 ga_get_entity_rank(pop, father), father->fitness);
173
174 son = ga_get_free_entity(pop);
175 daughter = ga_get_free_entity(pop);
176 pop->crossover(pop, mother, father, daughter, son);
177
178 /*
179 * Mutation step.
180 */
181 if (random_boolean_prob(pop->mutation_ratio))
182 {
183 plog(LOG_VERBOSE, "Mutation of %d (rank %d)",
184 ga_get_entity_id(pop, daughter),
185 ga_get_entity_rank(pop, daughter) );
186
187 entity = ga_get_free_entity(pop);
188 pop->mutate(pop, daughter, entity);
189 ga_entity_dereference(pop, daughter);
190 daughter = entity;
191 }
192
193 if (random_boolean_prob(pop->mutation_ratio))
194 {
195 plog(LOG_VERBOSE, "Mutation of %d (rank %d)",
196 ga_get_entity_id(pop, son),
197 ga_get_entity_rank(pop, son) );
198
199 entity = ga_get_free_entity(pop);
200 pop->mutate(pop, son, entity);
201 ga_entity_dereference(pop, son);
202 son = entity;
203 }
204
205 /*
206 * Apply environmental adaptations, score entities, sort entities, etc.
207 * FIXME: Currently no adaptation.
208 */
209 pop->evaluate(pop, daughter);
210 pop->evaluate(pop, son);
211
212 /*
213 * Evaluate similarities.
214 */
215 dist1 = pop->dc_params->compare(pop, mother, daughter) + pop->dc_params->compare(pop, father, son);
216 dist2 = pop->dc_params->compare(pop, mother, son) + pop->dc_params->compare(pop, father, daughter);
217
218 /*
219 * Determine which entities will survive, and kill the others.
220 */
221 if (dist1 < dist2)
222 {
223 rank = ga_get_entity_rank(pop, daughter);
224 if (daughter->fitness < mother->fitness)
225 {
226 entity = pop->entity_iarray[i];
227 pop->entity_iarray[i] = pop->entity_iarray[rank];
228 pop->entity_iarray[rank] = entity;
229 }
230 ga_entity_dereference_by_rank(pop, rank);
231
232 rank = ga_get_entity_rank(pop, son);
233 if (son->fitness < father->fitness)
234 {
235 entity = pop->entity_iarray[permutation[i]];
236 pop->entity_iarray[permutation[i]] = pop->entity_iarray[rank];
237 pop->entity_iarray[rank] = entity;
238 }
239 ga_entity_dereference_by_rank(pop, rank);
240 }
241 else
242 {
243 rank = ga_get_entity_rank(pop, son);
244 if (son->fitness < mother->fitness)
245 {
246 entity = pop->entity_iarray[i];
247 pop->entity_iarray[i] = pop->entity_iarray[rank];
248 pop->entity_iarray[rank] = entity;
249 }
250 ga_entity_dereference_by_rank(pop, rank);
251
252 rank = ga_get_entity_rank(pop, daughter);
253 if (daughter->fitness < father->fitness)
254 {
255 entity = pop->entity_iarray[permutation[i]];
256 pop->entity_iarray[permutation[i]] = pop->entity_iarray[rank];
257 pop->entity_iarray[rank] = entity;
258 }
259 ga_entity_dereference_by_rank(pop, rank);
260 }
261 }
262
263 /*
264 * Use callback.
265 */
266 plog(LOG_VERBOSE,
267 "After generation %d, population has fitness scores between %f and %f",
268 generation,
269 pop->entity_iarray[0]->fitness,
270 pop->entity_iarray[pop->size-1]->fitness );
271
272 } /* Generation loop. */
273
274 /*
275 * Ensure final ordering of population is correct.
276 */
277 sort_population(pop);
278
279 return generation;
280 }
281
282
283