1 /**********************************************************************
2 ga_de.c
3 **********************************************************************
4
5 ga_de - Differential Evolution.
6 Copyright ©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: Differential Evolution.
29
30 The DE algorithm was originally conceived by Rainer
31 Storn and Ken Price. The GAUL implementation is
32 based in part on their "de36.c" reference source code.
33 See http://www.icsi.berkeley.edu/~storn/code.html
34
35 You may notice that this code includes equivalents of
36 all of the original DE strategies along with a
37 selection of additional strateties.
38
39 **********************************************************************/
40
41 #include "gaul/ga_de.h"
42
43 /**********************************************************************
44 ga_population_set_differentialevolution_parameters()
45 synopsis: Sets the differential evolution parameters for a
46 population.
47 parameters: population *pop Population to set parameters of.
48 const GAcompare Callback to compare two entities.
49 return: none
50 last updated: 12 Apr 2005
51 **********************************************************************/
52
ga_population_set_differentialevolution_parameters(population * pop,const ga_de_strategy_type strategy,const ga_de_crossover_type crossover,const int num_perturbed,const double weighting_min,const double weighting_max,const double crossover_factor)53 void ga_population_set_differentialevolution_parameters( population *pop,
54 const ga_de_strategy_type strategy,
55 const ga_de_crossover_type crossover,
56 const int num_perturbed,
57 const double weighting_min,
58 const double weighting_max,
59 const double crossover_factor )
60 {
61
62 if ( !pop ) die("Null pointer to population structure passed.");
63
64 plog( LOG_VERBOSE, "Population's differential evolution parameters set" );
65
66 if (pop->de_params == NULL)
67 pop->de_params = s_malloc(sizeof(ga_de_t));
68
69 pop->de_params->strategy = strategy;
70 pop->de_params->crossover_method = crossover;
71 pop->de_params->num_perturbed = num_perturbed;
72 pop->de_params->weighting_min = weighting_min;
73 pop->de_params->weighting_max = weighting_max;
74 pop->de_params->crossover_factor = crossover_factor;
75
76 return;
77 }
78
79
80 /*
81 * Pick an number of random entities by moving their index to the
82 * beginning of the permutation array.
83 * This method is a lot more efficient than the original algorithm's
84 * approach - especially for small population sizes.
85 */
86
_gaul_pick_random_entities(int * permutation,int num,int size,int avoid)87 static void _gaul_pick_random_entities(int *permutation, int num, int size, int avoid)
88 {
89 int j; /* Loop variable over picked numbers. */
90 int pos, tmp; /* Current indices. */
91
92 for (j=0; j<num; j++)
93 {
94 do
95 {
96 pos = j+random_int(size-j);
97 } while (permutation[pos] == avoid);
98
99 tmp = permutation[j];
100 permutation[j] = permutation[pos];
101 permutation[pos] = tmp;
102 }
103
104 return;
105 }
106
107
108 /**********************************************************************
109 ga_differentialevolution()
110 synopsis: Performs differential evolution.
111 parameters:
112 return:
113 last updated: 12 Apr 2005
114 **********************************************************************/
115
ga_differentialevolution(population * pop,const int max_generations)116 int ga_differentialevolution( population *pop,
117 const int max_generations )
118 {
119 int generation=0; /* Current generation number. */
120 int i; /* Loop variable over entities. */
121 int best; /* Index of best entity. */
122 int *permutation; /* Permutation array for random selections. */
123 entity *tmpentity; /* New entity. */
124 int L, n; /* Allele indices. */
125 double weighting_factor; /* Weighting multiplier. */
126
127 /* Checks. */
128 if (!pop)
129 die("NULL pointer to population structure passed.");
130 if (!pop->de_params)
131 die("ga_population_set_differentialevolution_params(), or similar, must be used prior to ga_differentialevolution().");
132
133 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
134 if (!pop->rank) die("Population's ranking callback is undefined.");
135 if (pop->stable_size < 6) die("Population's stable size is too small. (Must be at least 6)");
136 if ( pop->de_params->crossover_factor < 0.0 ||
137 pop->de_params->crossover_factor > 1.0 )
138 die("Invalid crossover_factor.");
139
140 plog(LOG_VERBOSE, "The differential evolution has begun!");
141
142 pop->generation = 0;
143
144 /*
145 * Score the initial population members.
146 */
147 if (pop->size < pop->stable_size)
148 gaul_population_fill(pop, pop->stable_size - pop->size);
149
150 if (pop->entity_iarray[0]->fitness == GA_MIN_FITNESS)
151 pop->evaluate(pop, pop->entity_iarray[0]);
152
153 #pragma omp parallel for \
154 shared(pop) private(i) \
155 schedule(static)
156 for (i=0; i<pop->size; i++)
157 {
158 if (pop->entity_iarray[i]->fitness == GA_MIN_FITNESS)
159 pop->evaluate(pop, pop->entity_iarray[i]);
160 }
161
162 /*
163 * Prepare arrays to store permutations.
164 */
165 permutation = s_malloc(sizeof(int)*pop->size);
166 for (i=0; i<pop->size; i++)
167 permutation[i]=i;
168
169 /*
170 * Do all the generations:
171 *
172 * Stop when (a) max_generations reached, or
173 * (b) "pop->generation_hook" returns FALSE.
174 */
175 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
176 generation<max_generations )
177 {
178 generation++;
179 pop->generation = generation;
180 pop->orig_size = pop->size;
181
182 plog(LOG_VERBOSE,
183 "Population size is %d at start of generation %d",
184 pop->orig_size, generation );
185
186 /*
187 * Determine weighting factor.
188 */
189 if (pop->de_params->weighting_min == pop->de_params->weighting_max)
190 {
191 weighting_factor = pop->de_params->weighting_min;
192 }
193 else
194 {
195 weighting_factor = random_double_range(pop->de_params->weighting_min, pop->de_params->weighting_max);
196 }
197
198 /*
199 * Find best solution.
200 */
201 best = 0;
202
203 if (pop->rank == ga_rank_fitness)
204 {
205 for (i=1; i<pop->size; i++)
206 {
207 if (pop->entity_iarray[i]->fitness > pop->entity_iarray[best]->fitness)
208 best = i;
209 }
210 }
211 else
212 {
213 for (i=1; i<pop->size; i++)
214 {
215 if ( pop->rank(pop, pop->entity_iarray[i],
216 pop, pop->entity_iarray[best]) > 0 )
217 best = i;
218 }
219 }
220
221 plog(LOG_VERBOSE,
222 "Best fitness is %f at start of generation %d",
223 pop->entity_iarray[best]->fitness, generation );
224
225 #pragma omp parallel for \
226 if (GAUL_DETERMINISTIC_OPENMP==0) \
227 shared(pop) private(i) \
228 schedule(static)
229 for (i=0; i<pop->orig_size; i++)
230 {
231
232 tmpentity = ga_entity_clone(pop, pop->entity_iarray[i]);
233 n = random_int(pop->len_chromosomes);
234
235 /*
236 * Note that the following code may appear bloated due to excessive
237 * extraction of branches from loops.
238 * However, this yields much more efficient code (particularly for larger
239 * chromosomes) on less-than-cutting-edge compilers.
240 */
241
242 if (pop->de_params->crossover_method == GA_DE_CROSSOVER_BINOMIAL)
243 {
244 if (pop->de_params->strategy == GA_DE_STRATEGY_BEST)
245 {
246 if (pop->de_params->num_perturbed == 1)
247 { /* DE/best/1/bin */
248
249 _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);
250
251 ((double *)tmpentity->chromosome[0])[n] =
252 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
253 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
254 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
255
256 for (L=1; L<pop->len_chromosomes; L++)
257 {
258 if ( random_boolean() )
259 ((double *)tmpentity->chromosome[0])[n] =
260 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
261 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
262 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
263
264 n = (n+1)%pop->len_chromosomes;
265 }
266
267 }
268 else if (pop->de_params->num_perturbed == 2)
269 { /* DE/best/2/bin */
270
271 _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);
272
273 ((double *)tmpentity->chromosome[0])[n] =
274 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
275 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
276 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
277 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
278 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
279
280 for (L=1; L<pop->len_chromosomes; L++)
281 {
282 if ( random_boolean() )
283 ((double *)tmpentity->chromosome[0])[n] =
284 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
285 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
286 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
287 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
288 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
289
290 n = (n+1)%pop->len_chromosomes;
291 }
292
293 }
294 else if (pop->de_params->num_perturbed == 3)
295 { /* DE/best/3/exp */
296
297 _gaul_pick_random_entities(permutation, 6, pop->orig_size, i);
298
299 ((double *)tmpentity->chromosome[0])[n] =
300 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
301 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
302 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
303 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
304 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
305 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
306 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]);
307
308 for (L=1; L<pop->len_chromosomes; L++)
309 {
310 if ( random_boolean() )
311 ((double *)tmpentity->chromosome[0])[n] =
312 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
313 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
314 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
315 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
316 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
317 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
318 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]);
319
320
321 n = (n+1)%pop->len_chromosomes;
322 }
323
324 }
325 else
326 {
327 die("Invalid differential evolution selection number.");
328 }
329 }
330 else if (pop->de_params->strategy == GA_DE_STRATEGY_RAND)
331 {
332 if (pop->de_params->num_perturbed == 1)
333 { /* DE/rand/1/bin */
334 _gaul_pick_random_entities(permutation, 3, pop->orig_size, i);
335
336 ((double *)tmpentity->chromosome[0])[n] =
337 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
338 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
339 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]);
340
341 for (L=1; L<pop->len_chromosomes; L++)
342 {
343 if ( random_boolean() )
344 ((double *)tmpentity->chromosome[0])[n] =
345 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
346 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
347 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]);
348
349 n = (n+1)%pop->len_chromosomes;
350 }
351
352 }
353 else if (pop->de_params->num_perturbed == 2)
354 { /* DE/rand/2/bin */
355 _gaul_pick_random_entities(permutation, 5, pop->orig_size, i);
356
357 ((double *)tmpentity->chromosome[0])[n] =
358 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
359 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
360 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
361 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
362 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);
363
364 for (L=1; L<pop->len_chromosomes; L++)
365 {
366 if ( random_boolean() )
367 ((double *)tmpentity->chromosome[0])[n] =
368 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
369 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
370 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
371 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
372 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);
373
374 n = (n+1)%pop->len_chromosomes;
375 }
376
377 }
378 else if (pop->de_params->num_perturbed == 3)
379 { /* DE/rand/3/bin */
380 _gaul_pick_random_entities(permutation, 7, pop->orig_size, i);
381
382 ((double *)tmpentity->chromosome[0])[n] =
383 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
384 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
385 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
386 + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
387 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
388 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
389 - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);
390
391 for (L=1; L<pop->len_chromosomes; L++)
392 {
393 if ( random_boolean() )
394 ((double *)tmpentity->chromosome[0])[n] =
395 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
396 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
397 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
398 + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
399 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
400 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
401 - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);
402
403 n = (n+1)%pop->len_chromosomes;
404 }
405
406 }
407 else
408 {
409 die("Invalid differential evolution selection number.");
410 }
411 }
412 else if (pop->de_params->strategy == GA_DE_STRATEGY_RANDTOBEST)
413 {
414 if (pop->de_params->num_perturbed == 1)
415 { /* DE/rand-to-best/1/bin */
416 _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);
417
418 ((double *)tmpentity->chromosome[0])[n] +=
419 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
420 - ((double *)tmpentity->chromosome[0])[n]
421 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
422 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
423
424 for (L=1; L<pop->len_chromosomes; L++)
425 {
426 if ( random_boolean() )
427 ((double *)tmpentity->chromosome[0])[n] +=
428 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
429 - ((double *)tmpentity->chromosome[0])[n]
430 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
431 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
432
433 n = (n+1)%pop->len_chromosomes;
434 }
435
436 }
437 else if (pop->de_params->num_perturbed == 2)
438 { /* DE/rand-to-best/2/bin */
439 _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);
440
441 ((double *)tmpentity->chromosome[0])[n] +=
442 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
443 - ((double *)tmpentity->chromosome[0])[n]
444 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
445 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
446 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
447 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
448
449 for (L=1; L<pop->len_chromosomes; L++)
450 {
451 if ( random_boolean() )
452 ((double *)tmpentity->chromosome[0])[n] +=
453 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
454 - ((double *)tmpentity->chromosome[0])[n]
455 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
456 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
457 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
458 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
459
460 n = (n+1)%pop->len_chromosomes;
461 }
462
463 }
464 else
465 {
466 die("Invalid differential evolution selection number.");
467 }
468 }
469 else
470 {
471 die("Unknown differential evolution strategy.");
472 }
473
474 }
475 else
476 { /* pop->de_params->crossover_method == GA_DE_CROSSOVER_EXPONENTIAL */
477 if (pop->de_params->strategy == GA_DE_STRATEGY_BEST)
478 {
479 if (pop->de_params->num_perturbed == 1)
480 { /* DE/best/1/exp */
481
482 _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);
483
484 L = 0;
485 do
486 {
487 ((double *)tmpentity->chromosome[0])[n] =
488 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
489 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
490 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
491
492 n = (n+1)%pop->len_chromosomes;
493 L++;
494 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
495
496 }
497 else if (pop->de_params->num_perturbed == 2)
498 { /* DE/best/2/exp */
499
500 _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);
501
502 L = 0;
503 do
504 {
505 ((double *)tmpentity->chromosome[0])[n] =
506 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
507 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
508 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
509 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
510 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
511
512 n = (n+1)%pop->len_chromosomes;
513 L++;
514 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
515 }
516 else if (pop->de_params->num_perturbed == 3)
517 { /* DE/best/3/exp */
518
519 _gaul_pick_random_entities(permutation, 6, pop->orig_size, i);
520
521 L = 0;
522 do
523 {
524 ((double *)tmpentity->chromosome[0])[n] =
525 ((double *)pop->entity_iarray[best]->chromosome[0])[n]
526 + weighting_factor*(((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
527 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
528 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
529 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
530 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
531 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]);
532
533 n = (n+1)%pop->len_chromosomes;
534 L++;
535 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
536 }
537 else
538 {
539 die("Invalid differential evolution selection number.");
540 }
541
542 }
543 else if (pop->de_params->strategy == GA_DE_STRATEGY_RAND)
544 {
545 if (pop->de_params->num_perturbed == 1)
546 { /* DE/rand/1/exp (DE1) */
547
548 _gaul_pick_random_entities(permutation, 3, pop->orig_size, i);
549
550 L = 0;
551 do
552 {
553 ((double *)tmpentity->chromosome[0])[n] =
554 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
555 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
556 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]);
557
558 n = (n+1)%pop->len_chromosomes;
559 L++;
560 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
561
562 }
563 else if (pop->de_params->num_perturbed == 2)
564 { /* DE/rand/2/exp */
565
566 _gaul_pick_random_entities(permutation, 5, pop->orig_size, i);
567
568 L = 0;
569 do
570 {
571 ((double *)tmpentity->chromosome[0])[n] =
572 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
573 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
574 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
575 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
576 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]);
577
578 n = (n+1)%pop->len_chromosomes;
579 L++;
580 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
581
582 }
583 else if (pop->de_params->num_perturbed == 3)
584 { /* DE/rand/3/exp */
585
586 _gaul_pick_random_entities(permutation, 7, pop->orig_size, i);
587
588 L = 0;
589 do
590 {
591 ((double *)tmpentity->chromosome[0])[n] =
592 ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
593 + weighting_factor*(((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
594 + ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
595 + ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]
596 - ((double *)pop->entity_iarray[permutation[4]]->chromosome[0])[n]
597 - ((double *)pop->entity_iarray[permutation[5]]->chromosome[0])[n]
598 - ((double *)pop->entity_iarray[permutation[6]]->chromosome[0])[n]);
599
600 n = (n+1)%pop->len_chromosomes;
601 L++;
602 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
603
604 }
605 else
606 {
607 die("Invalid differential evolution selection number.");
608 }
609
610 }
611 else if (pop->de_params->strategy == GA_DE_STRATEGY_RANDTOBEST)
612 {
613 if (pop->de_params->num_perturbed == 1)
614 { /* DE/rand-to-best/1/exp */
615
616 _gaul_pick_random_entities(permutation, 2, pop->orig_size, i);
617
618 L = 0;
619 do
620 {
621 ((double *)tmpentity->chromosome[0])[n] +=
622 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
623 - ((double *)tmpentity->chromosome[0])[n]
624 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
625 - ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]);
626
627 n = (n+1)%pop->len_chromosomes;
628 L++;
629 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
630
631 }
632 else if (pop->de_params->num_perturbed == 2)
633 { /* DE/rand-to-best/2/exp */
634
635 _gaul_pick_random_entities(permutation, 4, pop->orig_size, i);
636
637 L = 0;
638 do
639 {
640 ((double *)tmpentity->chromosome[0])[n] +=
641 weighting_factor*(((double *)pop->entity_iarray[best]->chromosome[0])[n]
642 - ((double *)tmpentity->chromosome[0])[n]
643 + ((double *)pop->entity_iarray[permutation[0]]->chromosome[0])[n]
644 + ((double *)pop->entity_iarray[permutation[1]]->chromosome[0])[n]
645 - ((double *)pop->entity_iarray[permutation[2]]->chromosome[0])[n]
646 - ((double *)pop->entity_iarray[permutation[3]]->chromosome[0])[n]);
647
648 n = (n+1)%pop->len_chromosomes;
649 L++;
650 } while(random_boolean_prob(pop->de_params->crossover_factor) && (L < pop->len_chromosomes));
651
652 }
653 else
654 {
655 die("Invalid differential evolution selection number.");
656 }
657
658 }
659 else
660 {
661 die("Unknown differential evolution strategy.");
662 }
663
664 }
665
666 /*
667 * Evaluate new solution and restore the former chromosome values
668 * if this new solution is not an improvement.
669 */
670 if ( !pop->evaluate(pop, tmpentity) ||
671 ( pop->rank == ga_rank_fitness && pop->entity_iarray[i]->fitness > tmpentity->fitness ) ||
672 ( pop->rank != ga_rank_fitness && pop->rank(pop, tmpentity, pop, pop->entity_iarray[i]) < 0 ) )
673 {
674 /*printf("DEBUG: old = %f > new = %f\n", pop->entity_iarray[i]->fitness, tmpentity->fitness);*/
675 ga_entity_blank(pop, tmpentity);
676 ga_entity_copy(pop, tmpentity, pop->entity_iarray[i]);
677 }
678
679 }
680
681 /*
682 * Eliminate the original population members.
683 */
684 while (pop->orig_size > 0)
685 {
686 pop->orig_size--;
687 ga_entity_dereference_by_rank(pop, pop->orig_size);
688 }
689
690 /*
691 * End of generation.
692 */
693 plog(LOG_VERBOSE,
694 "After generation %d, population has fitness scores between %f and %f",
695 generation,
696 pop->entity_iarray[0]->fitness,
697 pop->entity_iarray[pop->size-1]->fitness );
698
699 } /* Generation loop. */
700
701 /*
702 * Ensure final ordering of population is correct.
703 */
704 sort_population(pop);
705
706 return generation;
707 }
708
709
710