1 /**********************************************************************
2 ga_optim.c
3 **********************************************************************
4
5 ga_optim - Optimisation and evolution routines.
6 Copyright ©2000-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: Routines for optimisation and evolution.
29
30 Note that the temperatures in the simulated annealling
31 and MC functions do not exactly run from the initial
32 temperature to the final temperature. They are offset
33 slightly so that sequential calls to these functions
34 will have a linear temperature change. The SA and MC
35 code in this file is deprecated anyway - these routines
36 have been replaced with much more flexible alternatives
37 and will be removed in the near future.
38
39 To do: Finish rewriting parallel versions, ga_evolution_mp() in particular.
40 Write ga_evolution_pvm().
41 Need to fix elitism/crowding stuff.
42 Remove much duplicated code.
43 OpenMOSIX fix. See below.
44 gaul_adapt_and_evaluate_forked() and gaul_adapt_and_evaluate_threaded() are only parallelized for the case that no adaptation occurs.
45
46 **********************************************************************/
47
48 #include "gaul/ga_optim.h"
49
50 /*
51 * Here is a kludge.
52 *
53 * This constant, if defined, causes a 10 microsecond delay to be
54 * inserted after each fork() call. It shouldn't be needed, but
55 * apparently on OpenMOSIX lots of processes started at the same
56 * time cause all sorts of problems (mostly bus errors). This
57 * delay gives OpenMOSIX a chance to migrate some processes to
58 * other nodes before this becomes a problem (hopefully).
59 *
60 * A long-term fix fix will be to check the return value from the
61 * forked processes and repeat them if they died. This may be
62 * added... eventually.
63 *
64 * I don't think this is needed anymore for recent versions of
65 * OpenMOSIX.
66 */
67 #define NEED_MOSIX_FORK_HACK 1
68
69 #if HAVE_MPI == 1
70 /*
71 * Convenience wrappers around MPI functions:
72 *
73 * These are used in the *_mp() functions.
74 */
75 static int rank=-1; /* Current process's rank. */
76 static int size=0; /* Total number of processes. */
77 static int namelen; /* Length of processor name. */
78 static char node_name[MPI_MAX_PROCESSOR_NAME]; /* String containing processor name. */
79
80 /*
81 * MPI tags.
82 */
83 #define GA_TAG_SLAVE_NOTIFICATION 1001
84 #define GA_TAG_BUFFER_LEN 1002
85 #define GA_TAG_INSTRUCTION 1003
86 #define GA_TAG_FITNESS 1004
87 #define GA_TAG_CHROMOSOMES 1005
88
89 /**********************************************************************
90 mpi_init()
91 synopsis: Ensure that MPI is initialised and prepare some global
92 variables.
93 parameters:
94 return: TRUE if master process, FALSE otherwise.
95 last updated: 23 Sep 2003
96 **********************************************************************/
97
mpi_init(void)98 static void mpi_init(void)
99 {
100
101 if (rank==-1)
102 {
103 /*
104 * FIXME: Test for prior MPI_Init() call here.
105 */
106 MPI_Comm_size(MPI_COMM_WORLD, &size);
107 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
108 MPI_Get_processor_name(node_name, &namelen);
109 }
110
111 return;
112 }
113
114
115 /**********************************************************************
116 mpi_ismaster()
117 synopsis: Is this the master process?
118 parameters:
119 return: TRUE if master process, FALSE otherwise.
120 last updated: 03 Feb 2003
121 **********************************************************************/
122
mpi_ismaster(void)123 static boolean mpi_ismaster(void)
124 {
125 return (rank==0);
126 }
127
128
129 /**********************************************************************
130 mpi_get_num_processes()
131 synopsis: Return the total number of MPI processes.
132 parameters:
133 return: int number of processes.
134 last updated: 03 Feb 2003
135 **********************************************************************/
136
mpi_get_num_processes(void)137 static int mpi_get_num_processes(void)
138 {
139 return (size);
140 }
141
142
143 /**********************************************************************
144 mpi_get_rank()
145 synopsis: Return the rank of this process.
146 parameters:
147 return: int rank
148 last updated: 03 Feb 2003
149 **********************************************************************/
150
mpi_get_rank(void)151 static int mpi_get_rank(void)
152 {
153 return (rank);
154 }
155
156
157 /**********************************************************************
158 mpi_get_next_rank()
159 synopsis: Return the rank of the next node in a circular
160 topology.
161 parameters:
162 return: int rank
163 last updated: 03 Feb 2003
164 **********************************************************************/
165
mpi_get_next_rank(void)166 static int mpi_get_next_rank(void)
167 {
168 int next=rank+1; /* The rank of the next process */
169
170 if (next==size) next=0; /* Last process sends to first process */
171
172 return (next);
173 }
174
175
176 /**********************************************************************
177 mpi_get_prev_rank()
178 synopsis: Return the rank of the previous node in a circular
179 topology.
180 parameters:
181 return: int rank
182 last updated: 03 Feb 2003
183 **********************************************************************/
184
mpi_get_prev_rank(void)185 static int mpi_get_prev_rank(void)
186 {
187 int prev=rank; /* The rank of the previous process */
188
189 if (prev==0) prev=size; /* First process sends to last process */
190
191 return (prev-1);
192 }
193
194
195 /**********************************************************************
196 gaul_bond_slaves_mpi()
197 synopsis: Register, set up and synchronise slave processes.
198 parameters: population *pop
199 return: none
200 last updated: 10 May 2004
201 **********************************************************************/
202
gaul_bond_slaves_mpi(population * pop,int buffer_len,int buffer_max)203 static void gaul_bond_slaves_mpi(population *pop, int buffer_len, int buffer_max)
204 {
205 int i; /* Loop variable over slave processes. */
206 int mpi_rank; /* Rank of slave process. */
207 int mpi_size; /* Number of slave processes. */
208 MPI_Status status; /* MPI status structure. */
209 int two_int[2]; /* Send buffer. */
210
211 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
212
213 two_int[0] = buffer_len;
214 two_int[1] = buffer_max;
215
216 /*
217 * Listen for all slave processes.
218 */
219 for (i=1; i<mpi_size; i++)
220 {
221 MPI_Recv(&mpi_rank, 1, MPI_INT, MPI_ANY_SOURCE, GA_TAG_SLAVE_NOTIFICATION, MPI_COMM_WORLD, &status);
222 /* FIXME: Check status here. */
223
224 /*
225 * Send slave the buffer length that it will require.
226 */
227 MPI_Send(two_int, 2, MPI_INT, status.MPI_SOURCE, GA_TAG_BUFFER_LEN, MPI_COMM_WORLD);
228 }
229
230 return;
231 }
232
233
234 /**********************************************************************
235 gaul_debond_slaves_mpi()
236 synopsis: Release and synchronise slave processes.
237 parameters: population *pop
238 return: none
239 last updated: 10 May 2004
240 **********************************************************************/
241
gaul_debond_slaves_mpi(population * pop)242 static void gaul_debond_slaves_mpi(population *pop)
243 {
244 int i; /* Loop variable over slave processes. */
245 int instruction=1; /* New population instruction. */
246 int mpi_size; /* Number of slave processes. */
247
248 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
249
250 /*
251 * Send instructions to all slave processes.
252 */
253 for (i=1; i<mpi_size; i++)
254 {
255 /* printf("DEBUG: Sending debond instruction to %d\n", i);*/
256 MPI_Send(&instruction, 1, MPI_INT, i, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
257 }
258
259 return;
260 }
261
262 #endif
263
264
265 /**********************************************************************
266 ga_attach_mpi_slave()
267 synopsis: Slave MPI process routine.
268 parameters: none
269 return: none
270 last updated: 10 May 2004
271 **********************************************************************/
272
ga_attach_mpi_slave(population * pop)273 void ga_attach_mpi_slave( population *pop )
274 {
275 #if HAVE_MPI == 1
276 MPI_Status status; /* MPI status structure. */
277 int single_int; /* Receive buffer. */
278 byte *buffer=NULL; /* Receive buffer. */
279 byte *chromo=NULL; /* Chromosome. */
280 boolean finished=FALSE; /* Whether this slave is done. */
281 entity *entity, *adult; /* Received entity, adapted entity. */
282 int buffer_len=0; /* Length of buffer to receive. */
283 int buffer_max=0; /* Chromosome byte representation length. */
284 int mpi_rank; /* Rank of MPI process; should never be 0 here. */
285 int two_int[2]; /* Send buffer. */
286
287 /*
288 * Rank zero process is master. This handles evolution. Other processes are slaves
289 * which simply evaluate entities, and should be attached using ga_attach_slave().
290 */
291 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
292 if (mpi_rank == 0) die("ga_attach_mpi_slave() called by process with rank=0.");
293
294 /*
295 * Send notification to master.
296 */
297 /* printf("DEBUG: Process %d notifying master\n", mpi_rank);*/
298 MPI_Send(&mpi_rank, 1, MPI_INT, 0, GA_TAG_SLAVE_NOTIFICATION, MPI_COMM_WORLD);
299
300 /*
301 * Allocate chromosome transfer buffer.
302 */
303 MPI_Recv(two_int, 2, MPI_INT, 0, GA_TAG_BUFFER_LEN, MPI_COMM_WORLD, &status);
304 buffer_len = two_int[0];
305 buffer_max = two_int[1];
306 buffer = s_malloc(buffer_len*sizeof(byte));
307
308 /* printf("DEBUG: slave buffer len %d %d\n", buffer_len, buffer_max);*/
309
310 /*
311 * Enter task loop.
312 */
313 do
314 {
315 /*
316 * Recieve instruction packet.
317 */
318 MPI_Recv(&single_int, 1, MPI_INT, 0, GA_TAG_INSTRUCTION, MPI_COMM_WORLD, &status);
319
320 /* printf("DEBUG: slave %d recieved instruction %d\n", mpi_rank, single_int);*/
321
322 switch (single_int)
323 {
324 case 0:
325 /* No more jobs. */
326 /* printf("DEBUG: slave %d recieved detach instruction.\n", mpi_rank);*/
327 finished=TRUE;
328 break;
329 case 1:
330 /* Prepare for calculations with a new population. */
331 /* FIXME: Incomplete. */
332 MPI_Send(&mpi_rank, 1, MPI_INT, 0, GA_TAG_SLAVE_NOTIFICATION, MPI_COMM_WORLD);
333 MPI_Recv(two_int, 2, MPI_INT, 0, GA_TAG_BUFFER_LEN, MPI_COMM_WORLD, &status);
334 break;
335 case 2:
336 /* Evaluation required. */
337 entity = ga_get_free_entity(pop);
338 MPI_Recv(buffer, buffer_len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
339 pop->chromosome_from_bytes(pop, entity, buffer);
340 if ( pop->evaluate(pop, entity) == FALSE )
341 entity->fitness = GA_MIN_FITNESS;
342 MPI_Send(&(entity->fitness), 1, MPI_DOUBLE, 0, GA_TAG_FITNESS, MPI_COMM_WORLD);
343 ga_entity_dereference(pop, entity);
344 break;
345 case 3:
346 /* Baldwinian adaptation required. */
347 entity = ga_get_free_entity(pop);
348 MPI_Recv(buffer, buffer_len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
349 pop->chromosome_from_bytes(pop, entity, buffer);
350 adult = pop->adapt(pop, entity);
351 MPI_Send(&(adult->fitness), 1, MPI_DOUBLE, 0, GA_TAG_FITNESS, MPI_COMM_WORLD);
352 ga_entity_dereference(pop, entity);
353 ga_entity_dereference(pop, adult);
354 break;
355 case 4:
356 /* Lamarkian adaptation required. */
357 entity = ga_get_free_entity(pop);
358 MPI_Recv(buffer, buffer_len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
359 pop->chromosome_from_bytes(pop, entity, buffer);
360 adult = pop->adapt(pop, entity);
361 MPI_Send(&(adult->fitness), 1, MPI_DOUBLE, 0, GA_TAG_FITNESS, MPI_COMM_WORLD);
362 if (buffer_max==0)
363 {
364 pop->chromosome_to_bytes(pop, adult, &chromo, &buffer_max);
365 MPI_Send(chromo, buffer_len, MPI_CHAR, 0, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
366 }
367 else
368 {
369 pop->chromosome_to_bytes(pop, adult, &buffer, &buffer_len);
370 MPI_Send(buffer, buffer_len, MPI_CHAR, 0, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
371 }
372 ga_entity_dereference(pop, entity);
373 ga_entity_dereference(pop, adult);
374 break;
375 default:
376 dief("Unknown instruction type packet recieved (%d).", single_int);
377 }
378
379 } while (finished==FALSE);
380
381 /*
382 * Clean-up and exit.
383 */
384 if (buffer != NULL)
385 s_free(buffer);
386
387 #else
388 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
389 #endif
390
391 return;
392 }
393
394
395 /**********************************************************************
396 ga_detach_mpi_slaves()
397 synopsis: Allow all slave processes to continue past the
398 ga_attach_mpi_slave() routine.
399 parameters: none
400 return: none
401 last updated: 10 May 2004
402 **********************************************************************/
403
ga_detach_mpi_slaves(void)404 void ga_detach_mpi_slaves(void)
405 {
406 #if HAVE_MPI == 1
407 int i; /* Loop variable over slave processes. */
408 int instruction=0; /* Detach instruction. */
409 int mpi_size; /* Number of slave processes. */
410 int mpi_rank; /* Rank of MPI process; should never be 0 here. */
411 int two_int[2]={0,0}; /* Send buffer. */
412 MPI_Status status; /* MPI status structure. */
413
414 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
415 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
416
417 /*
418 * Listen for all slave processes.
419 * FIXME: This shouldn't be needed really.
420 */
421 for (i=1; i<mpi_size; i++)
422 {
423 MPI_Recv(&mpi_rank, 1, MPI_INT, MPI_ANY_SOURCE, GA_TAG_SLAVE_NOTIFICATION, MPI_COMM_WORLD, &status);
424
425 /*
426 * Send slave the buffer length that it will require.
427 */
428 MPI_Send(two_int, 2, MPI_INT, status.MPI_SOURCE, GA_TAG_BUFFER_LEN, MPI_COMM_WORLD);
429 }
430
431 for (i=1; i<mpi_size; i++)
432 {
433 /* printf("DEBUG: Sending detach instruction to %d\n", i);*/
434 MPI_Send(&instruction, 1, MPI_INT, i, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
435 }
436
437 #else
438 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
439 #endif
440
441 return;
442 }
443
444
445 /**********************************************************************
446 gaul_entity_swap_rank()
447 synopsis: Swap the ranks of a pair of entities.
448 parameters: population *pop
449 const int rank1
450 const int rank2
451 return: none
452 last updated: 11 Jun 2002
453 **********************************************************************/
454
gaul_entity_swap_rank(population * pop,const int rank1,const int rank2)455 static void gaul_entity_swap_rank(population *pop, const int rank1, const int rank2)
456 {
457 entity *tmp; /* Swapped entity. */
458
459 tmp = pop->entity_iarray[rank1];
460 pop->entity_iarray[rank1] = pop->entity_iarray[rank2];
461 pop->entity_iarray[rank2] = tmp;
462
463 return;
464 }
465
466
467 /**********************************************************************
468 gaul_migration()
469 synopsis: Migration cycle.
470 parameters: population *pop
471 return: none
472 last updated: 11 Jun 2002
473 **********************************************************************/
474
gaul_migration(const int num_pops,population ** pops)475 static void gaul_migration(const int num_pops, population **pops)
476 {
477 int pop0_osize; /* Required for correct migration. */
478 int current_island; /* Current current_island number. */
479 int i; /* Loop over members of population. */
480
481 plog( LOG_VERBOSE, "*** Migration Cycle ***" );
482
483 pop0_osize = pops[0]->size;
484 for(current_island=1; current_island<num_pops; current_island++)
485 {
486 for(i=0; i<pops[current_island]->size; i++)
487 {
488 if (random_boolean_prob(pops[current_island]->migration_ratio))
489 {
490 ga_entity_clone(pops[current_island-1], pops[current_island]->entity_iarray[i]);
491 /* printf("%d, %d: Cloned %d %f\n", mpi_get_rank(), current_island, i, pops[current_island]->entity_iarray[i]->fitness);*/
492 }
493 }
494 }
495
496 for(i=0; i<pop0_osize; i++)
497 {
498 if (random_boolean_prob(pops[0]->migration_ratio))
499 ga_entity_clone(pops[num_pops-1], pops[0]->entity_iarray[i]);
500 /* printf("%d, 0: Cloned %d %f\n", mpi_get_rank(), i, pops[current_island]->entity_iarray[i]->fitness);*/
501 }
502
503 /*
504 * Sort the individuals in each population.
505 * Need this to ensure that new immigrants are ranked correctly.
506 * FIXME: It would be more efficient to insert the immigrants correctly.
507 */
508 #pragma omp parallel for \
509 shared(pops,num_pops) private(current_island) \
510 schedule(static)
511 for(current_island=0; current_island<num_pops; current_island++)
512 {
513 sort_population(pops[current_island]);
514 }
515
516 return;
517 }
518
519
520 /**********************************************************************
521 gaul_crossover()
522 synopsis: Mating cycle. (i.e. Sexual reproduction).
523 parameters: population *pop
524 return: none
525 last updated: 11 Jun 2002
526 **********************************************************************/
527
gaul_crossover(population * pop)528 static void gaul_crossover(population *pop)
529 {
530 entity *mother, *father; /* Parent entities. */
531 entity *son, *daughter; /* Child entities. */
532
533 plog(LOG_VERBOSE, "*** Mating cycle ***");
534
535 if (pop->crossover_ratio <= 0.0) return;
536
537 pop->select_state = 0;
538
539 /* Select pairs of entities to mate via crossover. */
540 #pragma intel omp parallel taskq
541 while ( !(pop->select_two(pop, &mother, &father)) )
542 {
543
544 if (mother && father)
545 {
546 #pragma intel omp task \
547 private(son,daughter) captureprivate(mother,father)
548 {
549 plog(LOG_VERBOSE, "Crossover between %d (rank %d fitness %f) and %d (rank %d fitness %f)",
550 ga_get_entity_id(pop, mother),
551 ga_get_entity_rank(pop, mother), mother->fitness,
552 ga_get_entity_id(pop, father),
553 ga_get_entity_rank(pop, father), father->fitness);
554
555 son = ga_get_free_entity(pop);
556 daughter = ga_get_free_entity(pop);
557 pop->crossover(pop, mother, father, daughter, son);
558 }
559 }
560 else
561 {
562 plog( LOG_VERBOSE, "Crossover not performed." );
563 }
564 }
565
566 return;
567 }
568
569
570 /**********************************************************************
571 gaul_mutation()
572 synopsis: Mutation cycle. (i.e. Asexual reproduction)
573 parameters: population *pop
574 return: none
575 last updated: 11 Jun 2002
576 **********************************************************************/
577
gaul_mutation(population * pop)578 static void gaul_mutation(population *pop)
579 {
580 entity *mother; /* Parent entities. */
581 entity *daughter; /* Child entities. */
582
583 plog(LOG_VERBOSE, "*** Mutation cycle ***");
584
585 if (pop->mutation_ratio <= 0.0) return;
586
587 pop->select_state = 0;
588
589 /*
590 * Select entities to undergo asexual reproduction, in each case the child will
591 * have a genetic mutation of some type.
592 */
593 #pragma intel omp parallel taskq
594 while ( !(pop->select_one(pop, &mother)) )
595 {
596
597 if (mother)
598 {
599 #pragma intel omp task \
600 private(daughter) captureprivate(mother)
601 {
602 plog(LOG_VERBOSE, "Mutation of %d (rank %d fitness %f)",
603 ga_get_entity_id(pop, mother),
604 ga_get_entity_rank(pop, mother), mother->fitness );
605
606 daughter = ga_get_free_entity(pop);
607 pop->mutate(pop, mother, daughter);
608 }
609 }
610 else
611 {
612 plog( LOG_VERBOSE, "Mutation not performed." );
613 }
614 }
615
616 return;
617 }
618
619
620 /**********************************************************************
621 gaul_evaluation_slave_mp()
622 synopsis: Fitness evaluations and adaptations are performed here.
623 parameters: population *pop
624 return: none
625 last updated: 03 Feb 2003
626 **********************************************************************/
627
628 #if HAVE_MPI == 1
gaul_evaluation_slave_mp(population * pop)629 static void gaul_evaluation_slave_mp(population *pop)
630 {
631 MPI_Status status; /* MPI status structure. */
632 int single_int; /* Receive buffer. */
633 byte *buffer; /* Receive buffer. */
634 boolean finished=FALSE; /* Whether this slave is done. */
635 entity *entity, *adult; /* Received entity, adapted entity. */
636 int len=0; /* Length of buffer to receive. */
637
638 /*
639 * Allocate receive buffer.
640 * FIXME: This length data shouldn't be needed!
641 */
642 MPI_Recv(&len, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
643 buffer = s_malloc(len*sizeof(byte));
644
645 /*printf("DEBUG: slave %d recieved %d (len)\n", rank, len);*/
646
647 /*
648 * Instruction packet.
649 */
650 do
651 {
652 MPI_Recv(&single_int, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
653
654 /*printf("DEBUG: slave %d recieved %d (instruction)\n", rank, len);*/
655
656 switch (single_int)
657 {
658 case 0:
659 /* Evaluation required. */
660 entity = ga_get_free_entity(pop);
661 MPI_Recv(buffer, len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
662 pop->chromosome_from_bytes(pop, entity, buffer);
663 if ( pop->evaluate(pop, entity) == FALSE )
664 entity->fitness = GA_MIN_FITNESS;
665 MPI_Send(&(entity->fitness), 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
666 break;
667 case 1:
668 /* Baldwinian adaptation required. */
669 entity = ga_get_free_entity(pop);
670 MPI_Recv(buffer, len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
671 pop->chromosome_from_bytes(pop, entity, buffer);
672 adult = pop->adapt(pop, entity);
673 MPI_Send(&(adult->fitness), 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
674 break;
675 case 2:
676 /* Lamarkian adaptation required. */
677 entity = ga_get_free_entity(pop);
678 MPI_Recv(buffer, len, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
679 pop->chromosome_from_bytes(pop, entity, buffer);
680 adult = pop->adapt(pop, entity);
681 MPI_Send(&(adult->fitness), 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
682 pop->chromosome_to_bytes(pop, adult, &buffer, &len);
683 MPI_Send(buffer, len, MPI_CHAR, 0, 0, MPI_COMM_WORLD);
684 break;
685 case 3:
686 /* No more jobs. */
687 finished=TRUE;
688 break;
689 default:
690 die("Unknown instruction packet recieved");
691 }
692
693 } while (finished==FALSE);
694
695 /*
696 * Synchronise population on this process with that on the master process.
697 */
698 ga_genocide(pop,0);
699 ga_population_append_receive(pop, 0);
700
701 s_free(buffer);
702
703 return;
704 }
705 #endif
706
707
708 /**********************************************************************
709 gaul_ensure_evaluations()
710 synopsis: Fitness evaluations.
711 Evaluate all previously unevaluated entities.
712 No adaptation.
713 parameters: population *pop
714 return: none
715 last updated: 01 Jul 2004
716 **********************************************************************/
717
gaul_ensure_evaluations(population * pop)718 static void gaul_ensure_evaluations(population *pop)
719 {
720 int i; /* Loop variable over entity ranks. */
721
722 #pragma omp parallel for \
723 shared(pop) private(i) \
724 schedule(static)
725 for (i=0; i<pop->size; i++)
726 {
727 /*printf("DEBUG: gaul_ensure_evaluations() parallel for %d on %d/%d.\n", i, omp_get_thread_num(), omp_get_num_threads());*/
728 if (pop->entity_iarray[i]->fitness == GA_MIN_FITNESS)
729 {
730 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
731 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
732 }
733 }
734
735 return;
736 }
737
738
739 /**********************************************************************
740 gaul_ensure_evaluations_mp()
741 synopsis: Fitness evaluations.
742 Evaluate all previously unevaluated entities.
743 No adaptation.
744 parameters: population *pop
745 return: none
746 last updated: 03 Feb 2003
747 **********************************************************************/
748
749 #if HAVE_MPI == 1
gaul_ensure_evaluations_mp(population * pop)750 static void gaul_ensure_evaluations_mp(population *pop)
751 {
752 int i; /* Loop variable over entity ranks. */
753
754 plog(LOG_FIXME, "Need to parallelise this!");
755
756 for (i=0; i<pop->size; i++)
757 {
758 if (pop->entity_iarray[i]->fitness == GA_MIN_FITNESS)
759 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
760 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
761 }
762
763 return;
764 }
765 #endif
766
767
768 /**********************************************************************
769 gaul_ensure_evaluations_mpi()
770 synopsis: Fitness evaluations.
771 Evaluate all previously unevaluated entities.
772 No adaptation.
773 parameters: population *pop
774 return: none
775 last updated: 10 May 2004
776 **********************************************************************/
777
778 #if HAVE_MPI == 1
gaul_ensure_evaluations_mpi(population * pop,int * eid,byte * buffer,int buffer_len,int buffer_max)779 static void gaul_ensure_evaluations_mpi( population *pop, int *eid,
780 byte *buffer, int buffer_len, int buffer_max )
781 {
782 MPI_Status status; /* MPI status structure. */
783 double single_double; /* Recieve buffer. */
784 int instruction=2; /* Detach instruction. */
785 int mpi_size; /* Number of slave processes. */
786 int process_num; /* Number of remote processes running calculations. */
787 int eval_num; /* Id of entity being processed. */
788 byte *chromo=NULL; /* Chromosome in byte form. */
789
790 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
791
792 /*
793 * A process is notifed to begin each fitness evaluation until
794 * all processes are busy, at which point we wait for
795 * results before initiating more.
796 *
797 * Skip evaluations for entities that have been previously evaluated.
798 */
799 process_num = 0;
800 eval_num = 0;
801
802 /* Skip to the next entity which needs evaluating. */
803 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
804
805 while (process_num < mpi_size-1 && eval_num < pop->size)
806 {
807 eid[process_num] = eval_num;
808
809 /* Send instruction and required data. */
810 MPI_Send(&instruction, 1, MPI_INT, process_num+1, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
811 if (buffer_max==0)
812 {
813 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &chromo, &buffer_max);
814 MPI_Send(chromo, buffer_len, MPI_CHAR, process_num+1, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
815 }
816 else
817 {
818 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &buffer, &buffer_len);
819 MPI_Send(buffer, buffer_len, MPI_CHAR, process_num+1, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
820 }
821
822 process_num++;
823 eval_num++;
824
825 /* Skip to the next entity which needs evaluating. */
826 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
827 }
828
829 while (process_num > 0)
830 { /* Wait for a process to finish. */
831 MPI_Recv(&single_double, 1, MPI_DOUBLE, MPI_ANY_SOURCE, GA_TAG_FITNESS, MPI_COMM_WORLD, &status);
832 /* FIXME: Check status here. */
833
834 /* Find which entity this process was evaluating. */
835 if (eid[status.MPI_SOURCE-1] == -1) die("Internal error. eid is -1");
836
837 pop->entity_iarray[eid[status.MPI_SOURCE-1]]->fitness = single_double;
838
839 if (eval_num < pop->size)
840 {
841 eid[status.MPI_SOURCE-1] = eval_num;
842
843 MPI_Send(&instruction, 1, MPI_INT, status.MPI_SOURCE, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
844 if (buffer_max==0)
845 {
846 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &chromo, &buffer_max);
847 MPI_Send(chromo, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
848 }
849 else
850 {
851 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &buffer, &buffer_len);
852 MPI_Send(buffer, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
853 }
854
855 eval_num++;
856
857 /* Skip to the next entity which needs evaluating. */
858 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
859 }
860 else
861 {
862 eid[status.MPI_SOURCE-1] = -1;
863 process_num--;
864 }
865 }
866
867 return;
868 }
869 #endif
870
871
872 /**********************************************************************
873 gaul_ensure_evaluations_forked()
874 synopsis: Fitness evaluations.
875 Evaluate all previously unevaluated entities.
876 No adaptation.
877 parameters: population *pop
878 return: none
879 last updated: 30 Jun 2002
880 **********************************************************************/
881
882 #if W32_CRIPPLED != 1
gaul_ensure_evaluations_forked(population * pop,const int num_processes,int * eid,pid_t * pid,const int * evalpipe)883 static void gaul_ensure_evaluations_forked(population *pop, const int num_processes,
884 int *eid, pid_t *pid, const int *evalpipe)
885 {
886 int fork_num; /* Index of current forked process. */
887 int num_forks; /* Number of forked processes. */
888 int eval_num; /* Index of current entity. */
889 pid_t fpid; /* PID of completed child process. */
890
891 /*
892 * A forked process is started for each fitness evaluation upto
893 * a maximum of max_processes at which point we wait for
894 * results before forking more.
895 *
896 * Skip evaluations for entities that have been previously evaluated.
897 */
898 fork_num = 0;
899 eval_num = 0;
900
901 /* Fork initial processes. */
902 /* Skip to the next entity which needs evaluating. */
903 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
904
905 while (fork_num < num_processes && eval_num < pop->size)
906 {
907 eid[fork_num] = eval_num;
908 pid[fork_num] = fork();
909
910 if (pid[fork_num] < 0)
911 { /* Error in fork. */
912 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
913 }
914 else if (pid[fork_num] == 0)
915 { /* This is the child process. */
916 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
917 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
918
919 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
920
921 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
922 _exit(1);
923 }
924
925 fork_num++;
926 eval_num++;
927
928 /* Skip to the next entity which needs evaluating. */
929 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
930 #ifdef NEED_MOSIX_FORK_HACK
931 usleep(10);
932 #endif
933 }
934 num_forks = fork_num;
935
936 /* Wait for a forked process to finish and, if needed, fork another. */
937 while (num_forks > 0)
938 {
939 fpid = wait(NULL);
940
941 if (fpid == -1) die("Error in wait().");
942
943 /* Find which entity this forked process was evaluating. */
944 fork_num = 0;
945 while (fpid != pid[fork_num]) fork_num++;
946
947 if (eid[fork_num] == -1) die("Internal error. eid is -1");
948
949 read(evalpipe[2*fork_num], &(pop->entity_iarray[eid[fork_num]]->fitness), sizeof(double));
950
951 if (eval_num < pop->size)
952 { /* New fork. */
953 eid[fork_num] = eval_num;
954 pid[fork_num] = fork();
955
956 if (pid[fork_num] < 0)
957 { /* Error in fork. */
958 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
959 }
960 else if (pid[fork_num] == 0)
961 { /* This is the child process. */
962 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
963 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
964
965 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
966
967 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
968 _exit(1);
969 }
970
971 eval_num++;
972
973 /* Skip to the next entity which needs evaluating. */
974 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
975 }
976 else
977 {
978 pid[fork_num] = -1;
979 eid[fork_num] = -1;
980 num_forks--;
981 }
982 }
983
984 return;
985 }
986 #endif
987
988
989 /**********************************************************************
990 gaul_ensure_evaluations_threaded()
991 synopsis: Fitness evaluations.
992 Evaluate all previously unevaluated entities.
993 No adaptation.
994 Threaded processing version.
995 parameters: population *pop
996 return: none
997 last updated: 18 Sep 2002
998 **********************************************************************/
999
1000 #if HAVE_PTHREADS == 1
1001
1002 typedef struct threaddata_s
1003 {
1004 int thread_num;
1005 int eval_num;
1006 population *pop;
1007 pthread_t pid;
1008 } threaddata_t;
1009
1010 /*
1011 * This is the child thread code used by gaul_ensure_evaluations_threaded(),
1012 * gaul_adapt_and_evaluate_threaded() and gaul_survival_threaded() to evaluate entities.
1013 */
_evaluation_thread(void * data)1014 static void *_evaluation_thread( void *data )
1015 {
1016 int eval_num = ((threaddata_t *)data)->eval_num;
1017 population *pop = ((threaddata_t *)data)->pop;
1018
1019 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
1020 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
1021
1022 #if GA_DEBUG>2
1023 printf("DEBUG: Thread %d has evaluated entity %d\n", ((threaddata_t *)data)->thread_num, eval_num);
1024 #endif
1025
1026 ((threaddata_t *)data)->thread_num = -1; /* Signal that this thread is finished. */
1027
1028 pthread_exit(NULL);
1029
1030 return NULL; /* Keep Compaq's C/C++ compiler happy. */
1031 }
1032
gaul_ensure_evaluations_threaded(population * pop,const int max_threads,threaddata_t * threaddata)1033 static void gaul_ensure_evaluations_threaded( population *pop, const int max_threads, threaddata_t *threaddata )
1034 {
1035 int thread_num; /* Index of current thread. */
1036 int num_threads; /* Number of threads currently in use. */
1037 int eval_num; /* Index of current entity. */
1038
1039 /*
1040 * A thread is created for each fitness evaluation upto
1041 * a maximum of max_threads at which point we wait for
1042 * results before continuing.
1043 *
1044 * Skip evaluations for entities that have been previously evaluated.
1045 */
1046 thread_num = 0;
1047 eval_num = 0;
1048
1049 /* Skip to the next entity which needs evaluating. */
1050 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
1051
1052 while (thread_num < max_threads && eval_num < pop->size)
1053 {
1054 threaddata[thread_num].thread_num = thread_num;
1055 threaddata[thread_num].eval_num = eval_num;
1056
1057 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
1058 { /* Error in thread creation. */
1059 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1060 }
1061
1062 thread_num++;
1063 eval_num++;
1064
1065 /* Skip to the next entity which needs evaluating. */
1066 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
1067 eval_num++;
1068 }
1069
1070 num_threads = thread_num;
1071
1072 /* Wait for a thread to finish and, if needed, create another. */
1073 /* Also, find which entity this thread was evaluating. */
1074 thread_num=0;
1075 while (num_threads > 0)
1076 {
1077 while (threaddata[thread_num].thread_num >= 0)
1078 {
1079 thread_num++;
1080 if (thread_num==max_threads)
1081 {
1082 thread_num=0;
1083 /* FIXME: Insert short sleep here? */
1084 }
1085 }
1086
1087 #if GA_DEBUG>2
1088 printf("DEBUG: Thread %d finished. num_threads=%d eval_num=%d/%d\n", thread_num, num_threads, eval_num, pop->size);
1089 #endif
1090
1091 if ( pthread_join(threaddata[thread_num].pid, NULL) < 0 )
1092 {
1093 dief("Error %d in pthread_join. (%s)", errno, errno==ESRCH?"ESRCH":errno==EINVAL?"EINVAL":errno==EDEADLK?"EDEADLK":"unknown");
1094 }
1095
1096 if (eval_num < pop->size)
1097 { /* New thread. */
1098 threaddata[thread_num].thread_num = thread_num;
1099 threaddata[thread_num].eval_num = eval_num;
1100
1101 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
1102 { /* Error in thread creation. */
1103 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1104 }
1105
1106 eval_num++;
1107
1108 /* Skip to the next entity which needs evaluating. */
1109 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
1110 eval_num++;
1111 }
1112 else
1113 {
1114 threaddata[thread_num].thread_num = 0;
1115 threaddata[thread_num].eval_num = -1;
1116 num_threads--;
1117 }
1118 }
1119
1120 return;
1121 }
1122 #endif /* HAVE_PTHREADS */
1123
1124
1125 /**********************************************************************
1126 gaul_adapt_and_evaluate()
1127 synopsis: Fitness evaluations.
1128 Evaluate the new entities produced in the current
1129 generation, whilst performing any necessary adaptation.
1130 Simple sequential version.
1131 parameters: population *pop
1132 return: none
1133 last updated: 11 Jun 2002
1134 **********************************************************************/
1135
gaul_adapt_and_evaluate(population * pop)1136 static void gaul_adapt_and_evaluate(population *pop)
1137 {
1138 int i; /* Loop variable over entity ranks. */
1139 entity *adult=NULL; /* Adapted entity. */
1140 int adultrank; /* Rank of adapted entity. */
1141
1142 if (pop->scheme == GA_SCHEME_DARWIN)
1143 { /* This is pure Darwinian evolution. Simply assess fitness of all children. */
1144
1145 plog(LOG_VERBOSE, "*** Fitness Evaluations ***");
1146
1147 #pragma omp parallel for \
1148 shared(pop) private(i) \
1149 schedule(static)
1150 for (i=pop->orig_size; i<pop->size; i++)
1151 {
1152 /*printf("DEBUG: gaul_adapt_and_evaluate() parallel for %d on %d/%d.\n", i, omp_get_thread_num(), omp_get_num_threads());*/
1153 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
1154 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
1155 }
1156
1157 return;
1158 }
1159 else
1160 { /* Some kind of adaptation is required. First reevaluate parents, as needed, then children. */
1161
1162 plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
1163
1164 if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
1165 {
1166 #pragma omp parallel for \
1167 shared(pop) private(i,adult) \
1168 schedule(static)
1169 for (i=0; i<pop->orig_size; i++)
1170 {
1171 adult = pop->adapt(pop, pop->entity_iarray[i]);
1172 pop->entity_iarray[i]->fitness=adult->fitness;
1173 ga_entity_dereference(pop, adult);
1174 }
1175 }
1176 else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
1177 {
1178 #pragma omp parallel for \
1179 shared(pop) private(i,adult,adultrank) \
1180 schedule(static)
1181 for (i=0; i<pop->orig_size; i++)
1182 {
1183 adult = pop->adapt(pop, pop->entity_iarray[i]);
1184 adultrank = ga_get_entity_rank(pop, adult);
1185 gaul_entity_swap_rank(pop, i, adultrank);
1186 ga_entity_dereference_by_rank(pop, adultrank);
1187 }
1188 }
1189
1190 if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
1191 {
1192 #pragma omp parallel for \
1193 shared(pop) private(i,adult) \
1194 schedule(static)
1195 for (i=pop->orig_size; i<pop->size; i++)
1196 {
1197 adult = pop->adapt(pop, pop->entity_iarray[i]);
1198 pop->entity_iarray[i]->fitness=adult->fitness;
1199 ga_entity_dereference(pop, adult);
1200 }
1201 }
1202 else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
1203 {
1204 #pragma omp parallel for \
1205 shared(pop) private(i,adult,adultrank) \
1206 schedule(static)
1207 for (i=pop->orig_size; i<pop->size; i++)
1208 {
1209 adult = pop->adapt(pop, pop->entity_iarray[i]);
1210 adultrank = ga_get_entity_rank(pop, adult);
1211 gaul_entity_swap_rank(pop, i, adultrank);
1212 ga_entity_dereference_by_rank(pop, adultrank);
1213 }
1214 }
1215 }
1216
1217 return;
1218 }
1219
1220
1221 /**********************************************************************
1222 gaul_adapt_and_evaluate_mp()
1223 synopsis: Fitness evaluations.
1224 Evaluate the new entities produced in the current
1225 generation, whilst performing any necessary adaptation.
1226 MPI version.
1227 parameters: population *pop
1228 return: none
1229 last updated: 03 Feb 2003
1230 **********************************************************************/
1231
1232 #if HAVE_MPI == 1
gaul_adapt_and_evaluate_mp(population * pop)1233 static void gaul_adapt_and_evaluate_mp(population *pop)
1234 {
1235 int i; /* Loop variable over entity ranks. */
1236 entity *adult=NULL; /* Adapted entity. */
1237 int adultrank; /* Rank of adapted entity. */
1238
1239 plog(LOG_FIXME, "Need to parallelise this!");
1240
1241 if (pop->scheme == GA_SCHEME_DARWIN)
1242 { /* This is pure Darwinian evolution. Simply assess fitness of all children. */
1243
1244 plog(LOG_VERBOSE, "*** Fitness Evaluations ***");
1245
1246 #pragma omp parallel for \
1247 shared(pop) private(i) \
1248 schedule(static)
1249 for (i=pop->orig_size; i<pop->size; i++)
1250 {
1251 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
1252 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
1253 }
1254
1255 return;
1256 }
1257 else
1258 { /* Some kind of adaptation is required. First reevaluate parents, as needed, then children. */
1259
1260 plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
1261
1262 if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
1263 {
1264 #pragma omp parallel for \
1265 shared(pop) private(i,adult) \
1266 schedule(static)
1267 for (i=0; i<pop->orig_size; i++)
1268 {
1269 adult = pop->adapt(pop, pop->entity_iarray[i]);
1270 pop->entity_iarray[i]->fitness=adult->fitness;
1271 ga_entity_dereference(pop, adult);
1272 }
1273 }
1274 else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
1275 {
1276 #pragma omp parallel for \
1277 shared(pop) private(i,adult,adultrank) \
1278 schedule(static)
1279 for (i=0; i<pop->orig_size; i++)
1280 {
1281 adult = pop->adapt(pop, pop->entity_iarray[i]);
1282 adultrank = ga_get_entity_rank(pop, adult);
1283 gaul_entity_swap_rank(pop, i, adultrank);
1284 ga_entity_dereference_by_rank(pop, adultrank);
1285 }
1286 }
1287
1288 if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
1289 {
1290 #pragma omp parallel for \
1291 shared(pop) private(i,adult) \
1292 schedule(static)
1293 for (i=pop->orig_size; i<pop->size; i++)
1294 {
1295 adult = pop->adapt(pop, pop->entity_iarray[i]);
1296 pop->entity_iarray[i]->fitness=adult->fitness;
1297 ga_entity_dereference(pop, adult);
1298 }
1299 }
1300 else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
1301 {
1302 #pragma omp parallel for \
1303 shared(pop) private(i,adult,adultrank) \
1304 schedule(static)
1305 for (i=pop->orig_size; i<pop->size; i++)
1306 {
1307 adult = pop->adapt(pop, pop->entity_iarray[i]);
1308 adultrank = ga_get_entity_rank(pop, adult);
1309 gaul_entity_swap_rank(pop, i, adultrank);
1310 ga_entity_dereference_by_rank(pop, adultrank);
1311 }
1312 }
1313 }
1314
1315 return;
1316 }
1317 #endif
1318
1319
1320 /**********************************************************************
1321 gaul_adapt_and_evaluate_mpi()
1322 synopsis: Fitness evaluations.
1323 Evaluate the new entities produced in the current
1324 generation, whilst performing any necessary adaptation.
1325 MPI version.
1326 parameters: population *pop
1327 return: none
1328 last updated: 24 Jun 2004
1329 **********************************************************************/
1330
1331 #if HAVE_MPI == 1
gaul_adapt_and_evaluate_mpi(population * pop,int * eid,byte * buffer,int buffer_len,int buffer_max)1332 static void gaul_adapt_and_evaluate_mpi( population *pop, int *eid,
1333 byte *buffer, int buffer_len, int buffer_max )
1334 {
1335 int i; /* Loop variable over entity ranks. */
1336 entity *adult=NULL; /* Adapted entity. */
1337 int adultrank; /* Rank of adapted entity. */
1338 MPI_Status status; /* MPI status structure. */
1339 double single_double; /* Recieve buffer. */
1340 int instruction=2; /* Detach instruction. */
1341 int mpi_size; /* Number of slave processes. */
1342 int process_num; /* Number of remote processes running calculations. */
1343 int eval_num; /* Id of entity being processed. */
1344 byte *chromo=NULL; /* Chromosome in byte form. */
1345
1346 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
1347
1348 if (pop->scheme == GA_SCHEME_DARWIN)
1349 { /* This is pure Darwinian evolution. Simply assess fitness of all children. */
1350
1351 plog(LOG_VERBOSE, "*** Fitness Evaluations ***");
1352
1353 /*
1354 * A process is notifed to begin each fitness evaluation until
1355 * all processes are busy, at which point we wait for
1356 * results before initiating more.
1357 *
1358 * Skip evaluations for entities that have been previously evaluated.
1359 */
1360 process_num = 0;
1361 eval_num = pop->orig_size; /* These solutions must already be evaluated. */
1362
1363 /* Skip to the next entity which needs evaluating. */
1364 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
1365
1366 while (process_num < mpi_size-1 && eval_num < pop->size)
1367 {
1368 eid[process_num] = eval_num;
1369
1370 /* Send instruction and required data. */
1371 MPI_Send(&instruction, 1, MPI_INT, process_num+1, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
1372 if (buffer_max==0)
1373 {
1374 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &chromo, &buffer_max);
1375 MPI_Send(chromo, buffer_len, MPI_CHAR, process_num+1, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
1376 }
1377 else
1378 {
1379 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &buffer, &buffer_len);
1380 MPI_Send(buffer, buffer_len, MPI_CHAR, process_num+1, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
1381 }
1382
1383 process_num++;
1384 eval_num++;
1385
1386 /* Skip to the next entity which needs evaluating. */
1387 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
1388 }
1389
1390 while (process_num > 0)
1391 { /* Wait for a process to finish. */
1392 MPI_Recv(&single_double, 1, MPI_DOUBLE, MPI_ANY_SOURCE, GA_TAG_FITNESS, MPI_COMM_WORLD, &status);
1393 /* FIXME: Check status here. */
1394
1395 /* Find which entity this process was evaluating. */
1396 if (eid[status.MPI_SOURCE-1] == -1) die("Internal error. eid is -1");
1397
1398 pop->entity_iarray[eid[status.MPI_SOURCE-1]]->fitness = single_double;
1399
1400 if (eval_num < pop->size)
1401 {
1402 eid[status.MPI_SOURCE-1] = eval_num;
1403
1404 MPI_Send(&instruction, 1, MPI_INT, status.MPI_SOURCE, GA_TAG_INSTRUCTION, MPI_COMM_WORLD);
1405 if (buffer_max==0)
1406 {
1407 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &chromo, &buffer_max);
1408 MPI_Send(chromo, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
1409 }
1410 else
1411 {
1412 pop->chromosome_to_bytes(pop, pop->entity_iarray[eval_num], &buffer, &buffer_len);
1413 MPI_Send(buffer, buffer_len, MPI_CHAR, status.MPI_SOURCE, GA_TAG_CHROMOSOMES, MPI_COMM_WORLD);
1414 }
1415
1416 eval_num++;
1417
1418 /* Skip to the next entity which needs evaluating. */
1419 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
1420 }
1421 else
1422 {
1423 eid[status.MPI_SOURCE-1] = -1;
1424 process_num--;
1425 }
1426 }
1427
1428 return;
1429 }
1430 else
1431 { /* Some kind of adaptation is required. First reevaluate parents, as needed, then children. */
1432
1433 plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
1434 plog(LOG_FIXME, "Need to parallelise this!");
1435
1436 if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
1437 {
1438 #pragma omp parallel for \
1439 shared(pop) private(i,adult) \
1440 schedule(static)
1441 for (i=0; i<pop->orig_size; i++)
1442 {
1443 adult = pop->adapt(pop, pop->entity_iarray[i]);
1444 pop->entity_iarray[i]->fitness=adult->fitness;
1445 ga_entity_dereference(pop, adult);
1446 }
1447 }
1448 else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
1449 {
1450 #pragma omp parallel for \
1451 shared(pop) private(i,adult,adultrank) \
1452 schedule(static)
1453 for (i=0; i<pop->orig_size; i++)
1454 {
1455 adult = pop->adapt(pop, pop->entity_iarray[i]);
1456 adultrank = ga_get_entity_rank(pop, adult);
1457 gaul_entity_swap_rank(pop, i, adultrank);
1458 ga_entity_dereference_by_rank(pop, adultrank);
1459 }
1460 }
1461
1462 if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
1463 {
1464 #pragma omp parallel for \
1465 shared(pop) private(i,adult) \
1466 schedule(static)
1467 for (i=pop->orig_size; i<pop->size; i++)
1468 {
1469 adult = pop->adapt(pop, pop->entity_iarray[i]);
1470 pop->entity_iarray[i]->fitness=adult->fitness;
1471 ga_entity_dereference(pop, adult);
1472 }
1473 }
1474 else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
1475 {
1476 #pragma omp parallel for \
1477 shared(pop) private(i,adult,adultrank) \
1478 schedule(static)
1479 for (i=pop->orig_size; i<pop->size; i++)
1480 {
1481 adult = pop->adapt(pop, pop->entity_iarray[i]);
1482 adultrank = ga_get_entity_rank(pop, adult);
1483 gaul_entity_swap_rank(pop, i, adultrank);
1484 ga_entity_dereference_by_rank(pop, adultrank);
1485 }
1486 }
1487 }
1488
1489 return;
1490 }
1491 #endif
1492
1493
1494 /**********************************************************************
1495 gaul_adapt_and_evaluate_forked()
1496 synopsis: Fitness evaluations.
1497 Evaluate the new entities produced in the current
1498 generation, whilst performing any necessary adaptation.
1499 Forked processing version.
1500 parameters: population *pop
1501 return: none
1502 last updated: 11 Jun 2002
1503 **********************************************************************/
1504
1505 #if W32_CRIPPLED != 1
gaul_adapt_and_evaluate_forked(population * pop,const int num_processes,int * eid,pid_t * pid,const int * evalpipe)1506 static void gaul_adapt_and_evaluate_forked(population *pop,
1507 const int num_processes,
1508 int *eid, pid_t *pid, const int *evalpipe)
1509 {
1510 int i; /* Loop variable over entity ranks. */
1511 entity *adult=NULL; /* Adapted entity. */
1512 int adultrank; /* Rank of adapted entity. */
1513 int fork_num; /* Index of current forked process. */
1514 int num_forks; /* Number of forked processes. */
1515 int eval_num; /* Index of current entity. */
1516 pid_t fpid; /* PID of completed child process. */
1517
1518 if (pop->scheme == GA_SCHEME_DARWIN)
1519 { /* This is pure Darwinian evolution. Simply assess fitness of all children. */
1520
1521 plog(LOG_VERBOSE, "*** Fitness Evaluations ***");
1522
1523 /*
1524 * A forked process is started for each fitness evaluation upto
1525 * a maximum of max_processes at which point we wait for
1526 * results before forking more.
1527 *
1528 * FIXME: This lump of code is almost identical to that in
1529 * gaul_ensure_evaluations_forked() and shouldn't really be duplicated.
1530 */
1531 fork_num = 0;
1532 eval_num = pop->orig_size;
1533
1534 /* Fork initial processes. */
1535 while (fork_num < num_processes && eval_num < pop->size)
1536 {
1537 eid[fork_num] = eval_num;
1538 pid[fork_num] = fork();
1539
1540 if (pid[fork_num] < 0)
1541 { /* Error in fork. */
1542 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1543 }
1544 else if (pid[fork_num] == 0)
1545 { /* This is the child process. */
1546 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
1547 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
1548
1549 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
1550
1551 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
1552 _exit(1);
1553 }
1554 fork_num++;
1555 eval_num++;
1556 #ifdef NEED_MOSIX_FORK_HACK
1557 usleep(10);
1558 #endif
1559 }
1560 num_forks = fork_num;
1561
1562 /* Wait for a forked process to finish and, if needed, fork another. */
1563 while (num_forks > 0)
1564 {
1565 fpid = wait(NULL);
1566
1567 if (fpid == -1) die("Error in wait().");
1568
1569 /* Find which entity this forked process was evaluating. */
1570 fork_num = 0;
1571 while (fpid != pid[fork_num]) fork_num++;
1572
1573 if (eid[fork_num] == -1) die("Internal error. eid is -1");
1574
1575 read(evalpipe[2*fork_num], &(pop->entity_iarray[eid[fork_num]]->fitness), sizeof(double));
1576
1577 if (eval_num < pop->size)
1578 { /* New fork. */
1579 eid[fork_num] = eval_num;
1580 pid[fork_num] = fork();
1581
1582 if (pid[fork_num] < 0)
1583 { /* Error in fork. */
1584 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1585 }
1586 else if (pid[fork_num] == 0)
1587 { /* This is the child process. */
1588 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
1589 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
1590
1591 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
1592
1593 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
1594 _exit(1);
1595 }
1596
1597 eval_num++;
1598 }
1599 else
1600 {
1601 pid[fork_num] = -1;
1602 eid[fork_num] = -1;
1603 num_forks--;
1604 }
1605 }
1606
1607 return;
1608 }
1609 else
1610 { /* Some kind of adaptation is required. First reevaluate parents, as needed, then children. */
1611
1612 plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
1613
1614 if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
1615 {
1616 for (i=0; i<pop->orig_size; i++)
1617 {
1618 adult = pop->adapt(pop, pop->entity_iarray[i]);
1619 pop->entity_iarray[i]->fitness=adult->fitness;
1620 ga_entity_dereference(pop, adult);
1621 }
1622 }
1623 else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
1624 {
1625 for (i=0; i<pop->orig_size; i++)
1626 {
1627 adult = pop->adapt(pop, pop->entity_iarray[i]);
1628 adultrank = ga_get_entity_rank(pop, adult);
1629 gaul_entity_swap_rank(pop, i, adultrank);
1630 ga_entity_dereference_by_rank(pop, adultrank);
1631 }
1632 }
1633
1634 if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
1635 {
1636 for (i=pop->orig_size; i<pop->size; i++)
1637 {
1638 adult = pop->adapt(pop, pop->entity_iarray[i]);
1639 pop->entity_iarray[i]->fitness=adult->fitness;
1640 ga_entity_dereference(pop, adult);
1641 }
1642 }
1643 else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
1644 {
1645 for (i=pop->orig_size; i<pop->size; i++)
1646 {
1647 adult = pop->adapt(pop, pop->entity_iarray[i]);
1648 adultrank = ga_get_entity_rank(pop, adult);
1649 gaul_entity_swap_rank(pop, i, adultrank);
1650 ga_entity_dereference_by_rank(pop, adultrank);
1651 }
1652 }
1653 }
1654
1655 return;
1656 }
1657 #endif
1658
1659
1660 /**********************************************************************
1661 gaul_adapt_and_evaluate_threaded()
1662 synopsis: Fitness evaluations.
1663 Evaluate the new entities produced in the current
1664 generation, whilst performing any necessary adaptation.
1665 Threaded processing version.
1666 parameters: population *pop
1667 return: none
1668 last updated: 15 Apr 2004
1669 **********************************************************************/
1670
1671 #if HAVE_PTHREADS == 1
gaul_adapt_and_evaluate_threaded(population * pop,const int max_threads,threaddata_t * threaddata)1672 static void gaul_adapt_and_evaluate_threaded(population *pop,
1673 const int max_threads,
1674 threaddata_t *threaddata)
1675 {
1676 int i; /* Loop variable over entity ranks. */
1677 entity *adult=NULL; /* Adapted entity. */
1678 int adultrank; /* Rank of adapted entity. */
1679 int thread_num; /* Index of current thread. */
1680 int num_threads; /* Number of threads currently in use. */
1681 int eval_num; /* Index of current entity. */
1682
1683 if (pop->scheme == GA_SCHEME_DARWIN)
1684 { /* This is pure Darwinian evolution. Simply assess fitness of all children. */
1685
1686 plog(LOG_VERBOSE, "*** Fitness Evaluations ***");
1687
1688 /*
1689 * A thread is created for each fitness evaluation upto
1690 * a maximum of max_threads at which point we wait for
1691 * results before creating more.
1692 *
1693 * Skip evaluations for entities that have been previously evaluated.
1694 *
1695 * FIXME: This lump of code is almost identical to that in
1696 * gaul_ensure_evaluations_threaded() and shouldn't really be duplicated.
1697 */
1698 thread_num = 0;
1699 eval_num = 0;
1700
1701 /* Skip to the next entity which needs evaluating. */
1702 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS) eval_num++;
1703
1704 while (thread_num < max_threads && eval_num < pop->size)
1705 {
1706 threaddata[thread_num].thread_num = thread_num;
1707 threaddata[thread_num].eval_num = eval_num;
1708
1709 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
1710 { /* Error in thread creation. */
1711 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1712 }
1713
1714 thread_num++;
1715 eval_num++;
1716
1717 /* Skip to the next entity which needs evaluating. */
1718 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
1719 eval_num++;
1720 }
1721
1722 num_threads = thread_num;
1723
1724 /* Wait for a thread to finish and, if needed, create another. */
1725 /* Also, find which entity this thread was evaluating. */
1726 thread_num=0;
1727 while (num_threads > 0)
1728 {
1729 while (threaddata[thread_num].thread_num >= 0)
1730 {
1731 thread_num++;
1732 if (thread_num==max_threads)
1733 {
1734 thread_num=0;
1735 /* FIXME: Insert short sleep here? */
1736 }
1737 }
1738
1739 #if GA_DEBUG>2
1740 printf("DEBUG: Thread %d finished. num_threads=%d eval_num=%d/%d\n", thread_num, num_threads, eval_num, pop->size);
1741 #endif
1742
1743 if ( pthread_join(threaddata[thread_num].pid, NULL) < 0 )
1744 {
1745 dief("Error %d in pthread_join. (%s)", errno, errno==ESRCH?"ESRCH":errno==EINVAL?"EINVAL":errno==EDEADLK?"EDEADLK":"unknown");
1746 }
1747
1748 if (eval_num < pop->size)
1749 { /* New thread. */
1750 threaddata[thread_num].thread_num = thread_num;
1751 threaddata[thread_num].eval_num = eval_num;
1752
1753 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
1754 { /* Error in thread creation. */
1755 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
1756 }
1757
1758 eval_num++;
1759
1760 /* Skip to the next entity which needs evaluating. */
1761 while (eval_num < pop->size && pop->entity_iarray[eval_num]->fitness!=GA_MIN_FITNESS)
1762 eval_num++;
1763 }
1764 else
1765 {
1766 threaddata[thread_num].thread_num = 0;
1767 threaddata[thread_num].eval_num = -1;
1768 num_threads--;
1769 }
1770 }
1771
1772 return;
1773 }
1774 else
1775 { /* Some kind of adaptation is required. First reevaluate parents, as needed, then children. */
1776
1777 plog(LOG_VERBOSE, "*** Adaptation and Fitness Evaluations ***");
1778
1779 if ( (pop->scheme & GA_SCHEME_BALDWIN_PARENTS)!=0 )
1780 {
1781 for (i=0; i<pop->orig_size; i++)
1782 {
1783 adult = pop->adapt(pop, pop->entity_iarray[i]);
1784 pop->entity_iarray[i]->fitness=adult->fitness;
1785 ga_entity_dereference(pop, adult);
1786 }
1787 }
1788 else if ( (pop->scheme & GA_SCHEME_LAMARCK_PARENTS)!=0 )
1789 {
1790 for (i=0; i<pop->orig_size; i++)
1791 {
1792 adult = pop->adapt(pop, pop->entity_iarray[i]);
1793 adultrank = ga_get_entity_rank(pop, adult);
1794 gaul_entity_swap_rank(pop, i, adultrank);
1795 ga_entity_dereference_by_rank(pop, adultrank);
1796 }
1797 }
1798
1799 if ( (pop->scheme & GA_SCHEME_BALDWIN_CHILDREN)!=0 )
1800 {
1801 for (i=pop->orig_size; i<pop->size; i++)
1802 {
1803 adult = pop->adapt(pop, pop->entity_iarray[i]);
1804 pop->entity_iarray[i]->fitness=adult->fitness;
1805 ga_entity_dereference(pop, adult);
1806 }
1807 }
1808 else if ( (pop->scheme & GA_SCHEME_LAMARCK_CHILDREN)!=0 )
1809 {
1810 for (i=pop->orig_size; i<pop->size; i++)
1811 {
1812 adult = pop->adapt(pop, pop->entity_iarray[i]);
1813 adultrank = ga_get_entity_rank(pop, adult);
1814 gaul_entity_swap_rank(pop, i, adultrank);
1815 ga_entity_dereference_by_rank(pop, adultrank);
1816 }
1817 }
1818 }
1819
1820 return;
1821 }
1822 #endif
1823
1824
1825 /**********************************************************************
1826 gaul_survival()
1827 synopsis: Survival of the fittest.
1828 Enforce elitism, apply crowding operator, reduce
1829 population back to its stable size and rerank entities,
1830 as required.
1831
1832 *** FIXME: crowding analysis incomplete. ***
1833
1834 parameters: population *pop
1835 return: none
1836 last updated: 18 Mar 2003
1837 **********************************************************************/
1838
gaul_survival(population * pop)1839 static void gaul_survival(population *pop)
1840 {
1841 int i; /* Loop variable over entity ranks. */
1842
1843 plog(LOG_VERBOSE, "*** Survival of the fittest ***");
1844
1845 /*
1846 * Need to kill parents, or rescore parents?
1847 */
1848 if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
1849 {
1850 while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
1851 {
1852 pop->orig_size--;
1853 ga_entity_dereference_by_rank(pop, pop->orig_size);
1854 }
1855 }
1856 else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
1857 {
1858 plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
1859
1860 #pragma omp parallel for \
1861 shared(pop) private(i) \
1862 schedule(static)
1863 for (i=pop->orig_size; i<pop->size; i++)
1864 {
1865 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
1866 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
1867 }
1868 }
1869
1870 /*
1871 * Sort all population members by fitness.
1872 */
1873 sort_population(pop);
1874
1875 /*
1876 * Enforce the type of crowding desired.
1877 *
1878 * Rough crowding doesn't actual check whether two chromosomes are
1879 * identical - just assumes they are if they have identical
1880 * fitness. Exact elitism does make the full check.
1881 */
1882 #if 0
1883 if (pop->elitism == GA_ELITISM_EXACT || pop->elitism == GA_ELITISM_ROUGH)
1884 { /* Fatal version */
1885 i = 1;
1886
1887 while (i<pop->size && i<pop->stable_size)
1888 {
1889 if (pop->entity_iarray[i]->fitness==pop->entity_iarray[i-1]->fitness &&
1890 (pop->elitism != GA_ELITISM_EXACT ||
1891 ga_compare_genome(pop, pop->entity_iarray[i], pop->entity_iarray[i-1])) )
1892 {
1893 ga_entity_dereference_by_rank(pop, i);
1894 }
1895 else
1896 {
1897 i++;
1898 }
1899 }
1900 }
1901 else if (pop->elitism == GA_ELITISM_EXACT_COMP || pop->elitism == GA_ELITISM_ROUGH_COMP)
1902 { /* Increased competition version */
1903 i = MIN(pop->size, pop->stable_size);
1904 elitism_penalty = fabs(pop->entity_iarray[0]->fitness*GA_ELITISM_MULTIPLIER)
1905 + GA_ELITISM_CONSTANT;
1906
1907 while (i>0)
1908 {
1909 if (pop->entity_iarray[i]->fitness==pop->entity_iarray[i-1]->fitness &&
1910 (pop->elitism != GA_ELITISM_EXACT_COMP ||
1911 ga_compare_genome(pop, pop->entity_iarray[i], pop->entity_iarray[i-1])) )
1912 {
1913 pop->entity_iarray[i]->fitness -= elitism_penalty;
1914 }
1915 i--;
1916 }
1917
1918 plog(LOG_VERBOSE, "*** Sorting again ***");
1919
1920 sort_population(pop); /* FIXME: We could possibly (certianly) choose
1921 a more optimal sort algorithm here. */
1922 }
1923 #endif
1924
1925 /*
1926 * Least fit population members die to restore the
1927 * population size to its stable size.
1928 */
1929 ga_genocide(pop, pop->stable_size);
1930 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
1931
1932 return;
1933 }
1934
1935
1936 /**********************************************************************
1937 gaul_survival_mp()
1938 synopsis: Survival of the fittest.
1939 Enforce elitism, apply crowding operator, reduce
1940 population back to its stable size and rerank entities,
1941 as required.
1942
1943 *** FIXME: crowding analysis incomplete. ***
1944
1945 parameters: population *pop
1946 return: none
1947 last updated: 18 Mar 2003
1948 **********************************************************************/
1949
1950 #if HAVE_MPI == 1
gaul_survival_mp(population * pop)1951 static void gaul_survival_mp(population *pop)
1952 {
1953 int i; /* Loop variable over entity ranks. */
1954
1955 plog(LOG_FIXME, "Need to parallelise this!");
1956
1957 plog(LOG_VERBOSE, "*** Survival of the fittest ***");
1958
1959 /*
1960 * Need to kill parents, or rescore parents?
1961 */
1962 if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
1963 {
1964 while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
1965 {
1966 pop->orig_size--;
1967 ga_entity_dereference_by_rank(pop, pop->orig_size);
1968 }
1969 }
1970 else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
1971 {
1972 plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
1973
1974 #pragma omp parallel for \
1975 shared(pop) private(i) \
1976 schedule(static)
1977 for (i=pop->orig_size; i<pop->size; i++)
1978 {
1979 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
1980 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
1981 }
1982 }
1983
1984 /*
1985 * Sort all population members by fitness.
1986 */
1987 sort_population(pop);
1988
1989 /*
1990 * Enforce the type of crowding desired.
1991 *
1992 * Rough crowding doesn't actual check whether two chromosomes are
1993 * identical - just assumes they are if they have identical
1994 * fitness. Exact elitism does make the full check.
1995 *
1996 * FIXME: Crowding code missing!!!
1997 */
1998
1999 /*
2000 * Least fit population members die to restore the
2001 * population size to its stable size.
2002 */
2003 ga_genocide(pop, pop->stable_size);
2004 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2005
2006 return;
2007 }
2008 #endif
2009
2010
2011 /**********************************************************************
2012 gaul_survival_mpi()
2013 synopsis: Survival of the fittest.
2014 Enforce elitism, apply crowding operator, reduce
2015 population back to its stable size and rerank entities,
2016 as required.
2017
2018 *** FIXME: crowding analysis incomplete. ***
2019
2020 parameters: population *pop
2021 return: none
2022 last updated: 10 May 2004
2023 **********************************************************************/
2024
2025 #if HAVE_MPI == 1
gaul_survival_mpi(population * pop)2026 static void gaul_survival_mpi(population *pop)
2027 {
2028 int i; /* Loop variable over entity ranks. */
2029
2030 plog(LOG_VERBOSE, "*** Survival of the fittest ***");
2031
2032 /*
2033 * Need to kill parents, or rescore parents?
2034 */
2035 if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
2036 {
2037 while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
2038 {
2039 pop->orig_size--;
2040 ga_entity_dereference_by_rank(pop, pop->orig_size);
2041 }
2042 }
2043 else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
2044 {
2045 plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
2046 plog(LOG_FIXME, "Need to parallelise this!");
2047
2048 #pragma omp parallel for \
2049 shared(pop) private(i) \
2050 schedule(static)
2051 for (i=pop->orig_size; i<pop->size; i++)
2052 {
2053 if ( pop->evaluate(pop, pop->entity_iarray[i]) == FALSE )
2054 pop->entity_iarray[i]->fitness = GA_MIN_FITNESS;
2055 }
2056 }
2057
2058 /*
2059 * Sort all population members by fitness.
2060 */
2061 sort_population(pop);
2062
2063 /*
2064 * Enforce the type of crowding desired.
2065 *
2066 * Rough crowding doesn't actual check whether two chromosomes are
2067 * identical - just assumes they are if they have identical
2068 * fitness. Exact elitism does make the full check.
2069 *
2070 * FIXME: Crowding code missing!!!
2071 */
2072
2073 /*
2074 * Least fit population members die to restore the
2075 * population size to its stable size.
2076 */
2077 ga_genocide(pop, pop->stable_size);
2078 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2079
2080 return;
2081 }
2082 #endif
2083
2084
2085 /**********************************************************************
2086 gaul_survival_forked()
2087 synopsis: Survival of the fittest.
2088 Enforce elitism, apply crowding operator, reduce
2089 population back to its stable size and rerank entities,
2090 as required.
2091 Forked processing version.
2092
2093 *** FIXME: crowding analysis incomplete. ***
2094
2095 parameters: population *pop
2096 return: none
2097 last updated: 18 Mar 2003
2098 **********************************************************************/
2099
2100 #if W32_CRIPPLED != 1
gaul_survival_forked(population * pop,const int num_processes,int * eid,pid_t * pid,const int * evalpipe)2101 static void gaul_survival_forked(population *pop,
2102 const int num_processes,
2103 int *eid, pid_t *pid, const int *evalpipe)
2104 {
2105 int fork_num; /* Index of current forked process. */
2106 int num_forks; /* Number of forked processes. */
2107 int eval_num; /* Index of current entity. */
2108 pid_t fpid; /* PID of completed child process. */
2109
2110 plog(LOG_VERBOSE, "*** Survival of the fittest ***");
2111
2112 /*
2113 * Need to kill parents, or rescore parents?
2114 */
2115 if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
2116 {
2117 while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
2118 {
2119 pop->orig_size--;
2120 ga_entity_dereference_by_rank(pop, pop->orig_size);
2121 }
2122 }
2123 else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
2124 {
2125 plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
2126
2127 /*
2128 * A forked process is started for each fitness evaluation upto
2129 * a maximum of max_processes at which point we wait for
2130 * results before forking more.
2131 */
2132 fork_num = 0;
2133 eval_num = 0;
2134
2135 /* Fork initial processes. */
2136
2137 while (fork_num < num_processes && eval_num < pop->orig_size)
2138 {
2139 eid[fork_num] = eval_num;
2140 pid[fork_num] = fork();
2141
2142 if (pid[fork_num] < 0)
2143 { /* Error in fork. */
2144 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
2145 }
2146 else if (pid[fork_num] == 0)
2147 { /* This is the child process. */
2148 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
2149 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
2150
2151 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
2152
2153 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
2154 _exit(1);
2155 }
2156
2157 fork_num++;
2158 eval_num++;
2159
2160 #ifdef NEED_MOSIX_FORK_HACK
2161 usleep(10);
2162 #endif
2163 }
2164 num_forks = fork_num;
2165
2166 /* Wait for a forked process to finish and, if needed, fork another. */
2167 while (num_forks > 0)
2168 {
2169 fpid = wait(NULL);
2170
2171 if (fpid == -1) die("Error in wait().");
2172
2173 /* Find which entity this forked process was evaluating. */
2174 fork_num = 0;
2175 while (fpid != pid[fork_num]) fork_num++;
2176
2177 if (eid[fork_num] == -1) die("Internal error. eid is -1");
2178
2179 read(evalpipe[2*fork_num], &(pop->entity_iarray[eid[fork_num]]->fitness), sizeof(double));
2180
2181 if (eval_num < pop->size)
2182 { /* New fork. */
2183 eid[fork_num] = eval_num;
2184 pid[fork_num] = fork();
2185
2186 if (pid[fork_num] < 0)
2187 { /* Error in fork. */
2188 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
2189 }
2190 else if (pid[fork_num] == 0)
2191 { /* This is the child process. */
2192 if ( pop->evaluate(pop, pop->entity_iarray[eval_num]) == FALSE )
2193 pop->entity_iarray[eval_num]->fitness = GA_MIN_FITNESS;
2194
2195 write(evalpipe[2*fork_num+1], &(pop->entity_iarray[eval_num]->fitness), sizeof(double));
2196
2197 fsync(evalpipe[2*fork_num+1]); /* Ensure data is written to pipe. */
2198 _exit(1);
2199 }
2200
2201 eval_num++;
2202 }
2203 else
2204 {
2205 pid[fork_num] = -1;
2206 eid[fork_num] = -1;
2207 num_forks--;
2208 }
2209 }
2210 }
2211
2212 /*
2213 * Sort all population members by fitness.
2214 */
2215 sort_population(pop);
2216
2217 /*
2218 * Enforce the type of crowding desired.
2219 *
2220 * Rough crowding doesn't actual check whether two chromosomes are
2221 * identical - just assumes they are if they have identical
2222 * fitness. Exact elitism does make the full check.
2223 *
2224 * FIXME: Crowding code missing!!!
2225 */
2226
2227 /*
2228 * Least fit population members die to restore the
2229 * population size to its stable size.
2230 */
2231 ga_genocide(pop, pop->stable_size);
2232 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2233
2234 return;
2235 }
2236 #endif
2237
2238
2239 /**********************************************************************
2240 gaul_survival_threaded()
2241 synopsis: Survival of the fittest.
2242 Enforce elitism, apply crowding operator, reduce
2243 population back to its stable size and rerank entities,
2244 as required.
2245 Threaded processing version.
2246
2247 *** FIXME: crowding analysis incomplete. ***
2248
2249 parameters: population *pop
2250 return: none
2251 last updated: 18 Mar 2003
2252 **********************************************************************/
2253
2254 #if HAVE_PTHREADS == 1
gaul_survival_threaded(population * pop,const int max_threads,threaddata_t * threaddata)2255 static void gaul_survival_threaded(population *pop,
2256 const int max_threads,
2257 threaddata_t *threaddata)
2258 {
2259 int thread_num; /* Index of current thread. */
2260 int num_threads; /* Number of threads currently in use. */
2261 int eval_num; /* Index of current entity. */
2262
2263 plog(LOG_VERBOSE, "*** Survival of the fittest ***");
2264
2265 /*
2266 * Need to kill parents, or rescore parents?
2267 */
2268 if (pop->elitism == GA_ELITISM_PARENTS_DIE || pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES)
2269 {
2270 while (pop->orig_size>(pop->elitism == GA_ELITISM_ONE_PARENT_SURVIVES))
2271 {
2272 pop->orig_size--;
2273 ga_entity_dereference_by_rank(pop, pop->orig_size);
2274 }
2275 }
2276 else if (pop->elitism == GA_ELITISM_RESCORE_PARENTS)
2277 {
2278
2279 plog(LOG_VERBOSE, "*** Fitness Re-evaluations ***");
2280
2281 /*
2282 * A thread is created for each fitness evaluation upto
2283 * a maximum of max_threads at which point we wait for
2284 * results before continuing.
2285 *
2286 * Skip evaluations for entities that have been previously evaluated.
2287 */
2288 thread_num = 0;
2289 eval_num = 0;
2290
2291 while (thread_num < max_threads && eval_num < pop->orig_size)
2292 {
2293 threaddata[thread_num].thread_num = thread_num;
2294 threaddata[thread_num].eval_num = eval_num;
2295
2296 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
2297 { /* Error in thread creation. */
2298 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
2299 }
2300
2301 thread_num++;
2302 eval_num++;
2303 }
2304
2305 num_threads = thread_num;
2306
2307 /* Wait for a thread to finish and, if needed, create another. */
2308 /* Also, find which entity this thread was evaluating. */
2309 thread_num=0;
2310 while (num_threads > 0)
2311 {
2312 while (threaddata[thread_num].thread_num >= 0)
2313 {
2314 thread_num++;
2315 if (thread_num==max_threads)
2316 {
2317 thread_num=0;
2318 /* FIXME: Insert short sleep here? */
2319 }
2320 }
2321
2322 #if GA_DEBUG>2
2323 printf("DEBUG: Thread %d finished. num_threads=%d eval_num=%d/%d\n", thread_num, num_threads, eval_num, pop->size);
2324 #endif
2325
2326 if ( pthread_join(threaddata[thread_num].pid, NULL) < 0 )
2327 {
2328 dief("Error %d in pthread_join. (%s)", errno, errno==ESRCH?"ESRCH":errno==EINVAL?"EINVAL":errno==EDEADLK?"EDEADLK":"unknown");
2329 }
2330
2331 if (eval_num < pop->orig_size)
2332 { /* New thread. */
2333 threaddata[thread_num].thread_num = thread_num;
2334 threaddata[thread_num].eval_num = eval_num;
2335
2336 if (pthread_create(&(threaddata[thread_num].pid), NULL, _evaluation_thread, (void *)&(threaddata[thread_num])) < 0)
2337 { /* Error in thread creation. */
2338 dief("Error %d in pthread_create. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
2339 }
2340
2341 eval_num++;
2342 }
2343 else
2344 {
2345 threaddata[thread_num].thread_num = 0;
2346 threaddata[thread_num].eval_num = -1;
2347 num_threads--;
2348 }
2349 }
2350
2351 }
2352
2353 /*
2354 * Sort all population members by fitness.
2355 */
2356 sort_population(pop);
2357
2358 /*
2359 * Enforce the type of crowding desired.
2360 *
2361 * Rough crowding doesn't actual check whether two chromosomes are
2362 * identical - just assumes they are if they have identical
2363 * fitness. Exact elitism does make the full check.
2364 *
2365 * FIXME: Crowding code missing!!!
2366 */
2367
2368 /*
2369 * Least fit population members die to restore the
2370 * population size to its stable size.
2371 */
2372 ga_genocide(pop, pop->stable_size);
2373 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2374
2375 return;
2376 }
2377 #endif /* HAVE_PTHREADS */
2378
2379
2380 /**********************************************************************
2381 ga_evolution()
2382 synopsis: Main genetic algorithm routine. Performs GA-based
2383 optimisation on the given population.
2384 This is a generation-based GA.
2385 ga_genesis(), or equivalent, must be called prior to
2386 this function.
2387 parameters:
2388 return:
2389 last updated: 17 Feb 2005
2390 **********************************************************************/
2391
ga_evolution(population * pop,const int max_generations)2392 int ga_evolution( population *pop,
2393 const int max_generations )
2394 {
2395 int generation=0; /* Current generation number. */
2396
2397 /* Checks. */
2398 if (!pop) die("NULL pointer to population structure passed.");
2399 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
2400 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
2401 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
2402 if (!pop->mutate) die("Population's mutation callback is undefined.");
2403 if (!pop->crossover) die("Population's crossover callback is undefined.");
2404 if (!pop->rank) die("Population's ranking callback is undefined.");
2405 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
2406
2407 plog(LOG_VERBOSE, "The evolution has begun!");
2408
2409 pop->generation = 0;
2410
2411 /*
2412 * Score and sort the initial population members.
2413 */
2414 if (pop->size < pop->stable_size)
2415 gaul_population_fill(pop, pop->stable_size - pop->size);
2416 gaul_ensure_evaluations(pop);
2417 sort_population(pop);
2418 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2419
2420 plog( LOG_VERBOSE,
2421 "Prior to the first generation, population has fitness scores between %f and %f",
2422 pop->entity_iarray[0]->fitness,
2423 pop->entity_iarray[pop->size-1]->fitness );
2424
2425 /*
2426 * Do all the generations:
2427 *
2428 * Stop when (a) max_generations reached, or
2429 * (b) "pop->generation_hook" returns FALSE.
2430 */
2431 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
2432 generation<max_generations )
2433 {
2434 generation++;
2435 pop->generation = generation;
2436 pop->orig_size = pop->size;
2437
2438 plog(LOG_DEBUG,
2439 "Population size is %d at start of generation %d",
2440 pop->orig_size, generation );
2441
2442 /*
2443 * Crossover step.
2444 */
2445 gaul_crossover(pop);
2446
2447 /*
2448 * Mutation step.
2449 */
2450 gaul_mutation(pop);
2451
2452 /*
2453 * Apply environmental adaptations, score entities, sort entities, etc.
2454 */
2455 gaul_adapt_and_evaluate(pop);
2456
2457 /*
2458 * Survival of the fittest.
2459 */
2460 gaul_survival(pop);
2461
2462 /*
2463 * Use callback.
2464 */
2465 plog(LOG_VERBOSE,
2466 "After generation %d, population has fitness scores between %f and %f",
2467 generation,
2468 pop->entity_iarray[0]->fitness,
2469 pop->entity_iarray[pop->size-1]->fitness );
2470
2471 } /* Generation loop. */
2472
2473 return generation;
2474 }
2475
2476
2477 /**********************************************************************
2478 ga_evolution_forked()
2479 synopsis: Main genetic algorithm routine. Performs GA-based
2480 optimisation on the given population. This is a
2481 generation-based GA. ga_genesis(), or equivalent,
2482 must be called prior to this function.
2483
2484 This function is like ga_evolution(), except that all
2485 fitness evaluations will be performed in forked
2486 processes which is ideal for use on multiprocessor
2487 machines or Beowulf-style clusters with process
2488 migration e.g. Mosix ( http://www.mosix.org/ ) or
2489 openMosix ( http://openmosix.sourceforge.net/ )
2490
2491 Thanks go to Syrrx, Inc. who, in essence, funded
2492 development of this function.
2493
2494 parameters:
2495 return: Number of generations performed.
2496 last updated: 17 Feb 2005
2497 **********************************************************************/
2498
2499 #if W32_CRIPPLED != 1
ga_evolution_forked(population * pop,const int max_generations)2500 int ga_evolution_forked( population *pop,
2501 const int max_generations )
2502 {
2503 int generation=0; /* Current generation number. */
2504 int i; /* Loop over members of population or pipes. */
2505 int *evalpipe; /* Pipes for returning fitnesses. */
2506 pid_t *pid; /* Child PIDs. */
2507 int *eid; /* Entity which forked process is evaluating. */
2508 int max_processes=0; /* Maximum number of processes to fork at one time. */
2509 char *max_proc_str; /* Value of enviroment variable. */
2510
2511 /* Checks. */
2512 if (!pop) die("NULL pointer to population structure passed.");
2513 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
2514 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
2515 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
2516 if (!pop->mutate) die("Population's mutation callback is undefined.");
2517 if (!pop->crossover) die("Population's crossover callback is undefined.");
2518 if (!pop->rank) die("Population's ranking callback is undefined.");
2519 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
2520
2521 /*
2522 * Look at environment to find number of processes to fork.
2523 */
2524 max_proc_str = getenv(GA_NUM_PROCESSES_ENVVAR_STRING);
2525 if (max_proc_str) max_processes = atoi(max_proc_str);
2526 if (max_processes == 0) max_processes = GA_DEFAULT_NUM_PROCESSES;
2527
2528 plog(LOG_VERBOSE, "The evolution has begun! Upto %d processes will be fork'ed", max_processes);
2529
2530 pop->generation = 0;
2531
2532 /*
2533 * Allocate memory required for handling the forked processes.
2534 * Open pipes for reporting fitnesses.
2535 * Clear pid and eid arrays.
2536 */
2537 pid = s_malloc(max_processes*sizeof(pid_t));
2538 eid = s_malloc(max_processes*sizeof(int));
2539 evalpipe = s_malloc(2*max_processes*sizeof(int));
2540 for (i=0; i<max_processes; i++)
2541 {
2542 if (pipe(&evalpipe[2*i])==-1) die("Unable to open pipe");
2543 pid[i] = -1;
2544 eid[i] = -1;
2545 }
2546
2547 /*
2548 * Score and sort the initial population members.
2549 */
2550 if (pop->size < pop->stable_size)
2551 gaul_population_fill(pop, pop->stable_size - pop->size);
2552 gaul_ensure_evaluations_forked(pop, max_processes, eid, pid, evalpipe);
2553 sort_population(pop);
2554 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2555
2556 plog( LOG_VERBOSE,
2557 "Prior to the first generation, population has fitness scores between %f and %f",
2558 pop->entity_iarray[0]->fitness,
2559 pop->entity_iarray[pop->size-1]->fitness );
2560
2561 /*
2562 * Do all the generations:
2563 *
2564 * Stop when (a) max_generations reached, or
2565 * (b) "pop->generation_hook" returns FALSE.
2566 */
2567 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
2568 generation<max_generations )
2569 {
2570 generation++;
2571 pop->generation = generation;
2572 pop->orig_size = pop->size;
2573
2574 plog(LOG_DEBUG,
2575 "Population size is %d at start of generation %d",
2576 pop->orig_size, generation );
2577
2578 /*
2579 * Crossover step.
2580 */
2581 gaul_crossover(pop);
2582
2583 /*
2584 * Mutation step.
2585 */
2586 gaul_mutation(pop);
2587
2588 /*
2589 * Score all child entities from this generation.
2590 */
2591 gaul_adapt_and_evaluate_forked(pop, max_processes, eid, pid, evalpipe);
2592
2593 /*
2594 * Apply survival pressure.
2595 */
2596 gaul_survival_forked(pop, max_processes, eid, pid, evalpipe);
2597
2598 plog(LOG_VERBOSE,
2599 "After generation %d, population has fitness scores between %f and %f",
2600 generation,
2601 pop->entity_iarray[0]->fitness,
2602 pop->entity_iarray[pop->size-1]->fitness );
2603
2604 } /* Main generation loop. */
2605
2606 /*
2607 * Close the pipes and free memory.
2608 */
2609 for (i=0; i<max_processes; i++)
2610 {
2611 close(evalpipe[2*i]);
2612 close(evalpipe[2*i+1]);
2613 }
2614
2615 s_free(pid);
2616 s_free(eid);
2617 s_free(evalpipe);
2618
2619 return generation;
2620 }
2621 #else
ga_evolution_forked(population * pop,const int max_generations)2622 int ga_evolution_forked( population *pop,
2623 const int max_generations )
2624 {
2625 die("Sorry, the ga_evolution_forked() function isn't available for Windows.");
2626 return 0;
2627 }
2628 #endif
2629
2630
2631 /**********************************************************************
2632 ga_evolution_threaded()
2633 synopsis: Main genetic algorithm routine. Performs GA-based
2634 optimisation on the given population. This is a
2635 generation-based GA. ga_genesis(), or equivalent,
2636 must be called prior to this function.
2637
2638 This function is like ga_evolution(), except that all
2639 fitness evaluations will be performed in threads
2640 and is therefore ideal for use on SMP multiprocessor
2641 machines or multipipelined processors (e.g. the new
2642 Intel Xeons).
2643
2644 parameters:
2645 return: Number of generations performed.
2646 last updated: 17 Feb 2005
2647 **********************************************************************/
2648
2649 #if HAVE_PTHREADS == 1
ga_evolution_threaded(population * pop,const int max_generations)2650 int ga_evolution_threaded( population *pop,
2651 const int max_generations )
2652 {
2653 int generation=0; /* Current generation number. */
2654 int max_threads=0; /* Maximum number of threads to use at one time. */
2655 char *max_thread_str; /* Value of enviroment variable. */
2656 threaddata_t *threaddata; /* Used for passing data to threads. */
2657 int i; /* Loop over threaddata elements. */
2658
2659 /* Checks. */
2660 if (!pop) die("NULL pointer to population structure passed.");
2661 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
2662 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
2663 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
2664 if (!pop->mutate) die("Population's mutation callback is undefined.");
2665 if (!pop->crossover) die("Population's crossover callback is undefined.");
2666 if (!pop->rank) die("Population's ranking callback is undefined.");
2667 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
2668
2669 /*
2670 * Look at environment to find number of threads to use.
2671 */
2672 max_thread_str = getenv(GA_NUM_THREADS_ENVVAR_STRING);
2673 if (max_thread_str) max_threads = atoi(max_thread_str);
2674 if (max_threads == 0) max_threads = GA_DEFAULT_NUM_THREADS;
2675
2676 plog(LOG_VERBOSE, "The evolution has begun! Upto %d threads will be created", max_threads);
2677
2678 /*
2679 * Allocate memory required for handling the threads.
2680 */
2681 threaddata = s_malloc(sizeof(threaddata_t)*max_threads);
2682 for (i=0; i<max_threads; i++)
2683 threaddata[i].pop = pop;
2684
2685 pop->generation = 0;
2686
2687 /*
2688 * Score and sort the initial population members.
2689 */
2690 if (pop->size < pop->stable_size)
2691 gaul_population_fill(pop, pop->stable_size - pop->size);
2692 gaul_ensure_evaluations_threaded(pop, max_threads, threaddata);
2693 sort_population(pop);
2694 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2695
2696 plog( LOG_VERBOSE,
2697 "Prior to the first generation, population has fitness scores between %f and %f",
2698 pop->entity_iarray[0]->fitness,
2699 pop->entity_iarray[pop->size-1]->fitness );
2700
2701 /*
2702 * Do all the generations:
2703 *
2704 * Stop when (a) max_generations reached, or
2705 * (b) "pop->generation_hook" returns FALSE.
2706 */
2707 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
2708 generation<max_generations )
2709 {
2710 generation++;
2711 pop->generation = generation;
2712 pop->orig_size = pop->size;
2713
2714 plog(LOG_DEBUG,
2715 "Population size is %d at start of generation %d",
2716 pop->orig_size, generation );
2717
2718 /*
2719 * Crossover step.
2720 */
2721 gaul_crossover(pop);
2722
2723 /*
2724 * Mutation step.
2725 */
2726 gaul_mutation(pop);
2727
2728 /*
2729 * Score all child entities from this generation.
2730 */
2731 gaul_adapt_and_evaluate_threaded(pop, max_threads, threaddata);
2732
2733 /*
2734 * Apply survival pressure.
2735 */
2736 gaul_survival_threaded(pop, max_threads, threaddata);
2737
2738 plog(LOG_VERBOSE,
2739 "After generation %d, population has fitness scores between %f and %f",
2740 generation,
2741 pop->entity_iarray[0]->fitness,
2742 pop->entity_iarray[pop->size-1]->fitness );
2743
2744 } /* Main generation loop. */
2745
2746 /* Free memory used for storing thread information. */
2747 s_free(threaddata);
2748
2749 return generation;
2750 }
2751 #else
ga_evolution_threaded(population * pop,const int max_generations)2752 int ga_evolution_threaded( population *pop,
2753 const int max_generations )
2754 {
2755
2756 die("Support for ga_evolution_threaded() not compiled.");
2757
2758 return 0;
2759 }
2760 #endif /* HAVE_PTHREADS */
2761
2762
2763 /**********************************************************************
2764 ga_evolution_threaded()
2765 synopsis: Main genetic algorithm routine. Performs GA-based
2766 optimisation on the given population. This is a
2767 generation-based GA. ga_genesis(), or equivalent,
2768 must be called prior to this function.
2769
2770 This function is like ga_evolution(), except that all
2771 fitness evaluations will be performed in threads
2772 and is therefore ideal for use on SMP multiprocessor
2773 machines or multipipelined processors (e.g. the new
2774 Intel Xeons).
2775
2776 parameters:
2777 return: Number of generations performed.
2778 last updated: 17 Feb 2005
2779 **********************************************************************/
2780
2781 #if HAVE_PTHREADS == -2
2782 /* Old version of code. */
ga_evolution_threaded(population * pop,const int max_generations)2783 int ga_evolution_threaded( population *pop,
2784 const int max_generations )
2785 {
2786 int generation=0; /* Current generation number. */
2787 int i; /* Loop over members of population. */
2788 pthread_t *tid; /* Child thread IDs. */
2789 pthread_mutex_t *mid; /* Child mutex IDs. */
2790 pthread_cond_t *cid; /* Child condition variable IDs. */
2791 int *eid; /* Entity which forked process is evaluating. */
2792 int max_threads=0; /* Maximum number of evaluation threads to use at one time. */
2793 char *max_thread_str; /* Value of enviroment variable. */
2794
2795 /* Checks. */
2796 if (!pop) die("NULL pointer to population structure passed.");
2797 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
2798 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
2799 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
2800 if (!pop->mutate) die("Population's mutation callback is undefined.");
2801 if (!pop->crossover) die("Population's crossover callback is undefined.");
2802 if (!pop->rank) die("Population's ranking callback is undefined.");
2803 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
2804
2805 /*
2806 * Look at environment to find number of threads to create.
2807 */
2808 max_thread_str = getenv(GA_NUM_THREADS_ENVVAR_STRING);
2809 if (max_thread_str) max_threads = atoi(max_thread_str);
2810 if (max_threads == 0) max_threads = GA_DEFAULT_NUM_THREADS;
2811
2812 plog(LOG_VERBOSE, "The evolution has begun! Upto %d threads will be created", max_threads);
2813
2814 pop->generation = 0;
2815
2816 /*
2817 * Start with all threads locked.
2818 */
2819 THREAD_LOCK(global_thread_lock);
2820
2821 /*
2822 * Allocate memory required for handling the threads.
2823 * Initially use eid array to pass thread enumerations.
2824 */
2825 tid = s_malloc(max_threads*sizeof(pthread_t));
2826 mid = s_malloc(max_threads*sizeof(pthread_mutex_t));
2827 cid = s_malloc(max_threads*sizeof(pthread_cond_t));
2828 eid = s_malloc(max_threads*sizeof(int));
2829 for (i=0; i<max_threads; i++)
2830 {
2831 eid[i] = i;
2832 if ( !pthread_mutex_init(&(mid[i]), NULL) )
2833 die("Unable to initialize mutex variable.");
2834 if ( !pthread_cond_init(&(cid[i]), NULL) )
2835 die("Unable to initialize condition variable.");
2836 if ( !pthread_create(&(tid[i]), NULL, (void *(*)(void *)) worker_thread, (void *) &(eid[i])) )
2837 die("Unable to create thread.");
2838 }
2839
2840 /*
2841 * Clear eid array.
2842 */
2843 for (i=0; i<max_threads; i++)
2844 {
2845 pthread_mutex_lock(&(mid[i]));
2846 pthread_cond_wait(&(cid[i]), &(mid[i]));
2847 pthread_mutex_unlock(&(mid[i]));
2848 eid[i] = -1;
2849 }
2850
2851 /*
2852 * Score and sort the initial population members.
2853 */
2854 if (pop->size < pop->stable_size)
2855 gaul_population_fill(pop, pop->stable_size - pop->size);
2856 gaul_ensure_evaluations_threaded(pop, max_threads, eid, tid);
2857 sort_population(pop);
2858 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
2859
2860 plog( LOG_VERBOSE,
2861 "Prior to the first generation, population has fitness scores between %f and %f",
2862 pop->entity_iarray[0]->fitness,
2863 pop->entity_iarray[pop->size-1]->fitness );
2864
2865 /*
2866 * Do all the generations:
2867 *
2868 * Stop when (a) max_generations reached, or
2869 * (b) "pop->generation_hook" returns FALSE.
2870 */
2871 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
2872 generation<max_generations )
2873 {
2874 generation++;
2875 pop->generation = generation;
2876 pop->orig_size = pop->size;
2877
2878 plog(LOG_DEBUG,
2879 "Population size is %d at start of generation %d",
2880 pop->orig_size, generation );
2881
2882 /*
2883 * Crossover step.
2884 */
2885 gaul_crossover(pop);
2886
2887 /*
2888 * Mutation step.
2889 */
2890 gaul_mutation(pop);
2891
2892 /*
2893 * Score all child entities from this generation.
2894 */
2895 gaul_adapt_and_evaluate_threaded(pop, max_threads, eid, tid);
2896
2897 /*
2898 * Apply survival pressure.
2899 */
2900 gaul_survival_threaded(pop, max_threads, eid, tid);
2901
2902 plog(LOG_VERBOSE,
2903 "After generation %d, population has fitness scores between %f and %f",
2904 generation,
2905 pop->entity_iarray[0]->fitness,
2906 pop->entity_iarray[pop->size-1]->fitness );
2907
2908 } /* Main generation loop. */
2909
2910 /*
2911 * Clean-up threads.
2912 */
2913 for (i=0; i<max_threads; i++)
2914 {
2915 pthread_cancel(&(tid[i]));
2916 pthread_join(&(tid[i]));
2917 pthread_mutex_destroy(&(mid[i]));
2918 pthread_cond_destroy(&(cid[i]));
2919 }
2920
2921 /*
2922 * Free memory.
2923 */
2924 s_free(tid);
2925 s_free(mid);
2926 s_free(cid);
2927 s_free(eid);
2928
2929 return generation;
2930 }
2931 #endif
2932
2933
2934 /**********************************************************************
2935 ga_evolution_with_stats()
2936 synopsis: Main genetic algorithm routine. Performs GA-based
2937 optimisation on the given population.
2938 This is a generation-based GA.
2939 ga_genesis(), or equivalent, must be called prior to
2940 this function.
2941 This is almost identical to ga_evolution() except is
2942 modified to facilitate the collection of certain
2943 statistics.
2944
2945 *** Should be deprecated. ***
2946 parameters:
2947 return:
2948 last updated: 17 Feb 2005
2949 **********************************************************************/
2950
2951 #ifdef COMPILE_DEPRECATED_FUNCTIONS
2952
ga_evolution_with_stats(population * pop,const ga_elitism_type elitism,const int max_generations)2953 int ga_evolution_with_stats( population *pop,
2954 const ga_elitism_type elitism,
2955 const int max_generations )
2956 {
2957 int generation=0; /* Current generation number. */
2958 int i; /* Loop over members of population. */
2959 entity *mother, *father; /* Parent entities. */
2960 entity *son, *daughter; /* Child entities. */
2961 entity *adult; /* Temporary copy for gene optimisation. */
2962 boolean finished; /* Whether crossover/mutation rounds are complete. */
2963 int new_pop_size; /* Population size prior to adaptation. */
2964 FILE *STATS_OUT; /* Filehandle for stats log. */
2965 char stats_fname[80]; /* Filename for stats log. */
2966 int crossover_good, crossover_poor; /* Fornication statistics. */
2967 int mutation_good, mutation_poor; /* - " - */
2968 double crossover_gain, mutation_gain; /* - " - */
2969
2970 /* Checks. */
2971 if (!pop) die("NULL pointer to population structure passed.");
2972 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
2973 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
2974 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
2975 if (!pop->mutate) die("Population's mutation callback is undefined.");
2976 if (!pop->crossover) die("Population's crossover callback is undefined.");
2977 if (!pop->rank) die("Population's ranking callback is undefined.");
2978 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
2979
2980 plog(LOG_WARNING, "This is a deprecated function!");
2981
2982 plog(LOG_VERBOSE, "The evolution has begun!");
2983
2984 pop->generation = 0;
2985
2986 /*
2987 * Create name for statistics log file.
2988 * Write a simple header to that file.
2989 */
2990 sprintf(stats_fname, "ga_stats_%d.dat", (int) getpid());
2991 STATS_OUT = fopen(stats_fname, "a");
2992 fprintf(STATS_OUT, "gen crossover mutation\n");
2993 fclose(STATS_OUT);
2994
2995 /*
2996 * Score and sort the initial population members.
2997 */
2998 if (pop->size < pop->stable_size)
2999 gaul_population_fill(pop, pop->stable_size - pop->size);
3000 gaul_ensure_evaluations(pop);
3001 sort_population(pop);
3002 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
3003
3004 plog( LOG_VERBOSE,
3005 "Prior to the first generation, population has fitness scores between %f and %f",
3006 pop->entity_iarray[0]->fitness,
3007 pop->entity_iarray[pop->size-1]->fitness );
3008
3009 /* Do all the generations: */
3010 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
3011 generation<max_generations )
3012 {
3013 generation++;
3014 pop->generation = generation;
3015 pop->orig_size = pop->size;
3016
3017 plog(LOG_DEBUG,
3018 "Population size is %d at start of generation %d",
3019 pop->orig_size, generation );
3020
3021 /*
3022 * Zero statistics.
3023 */
3024 crossover_good=0;
3025 crossover_poor=0;
3026 mutation_good=0;
3027 mutation_poor=0;
3028
3029 crossover_gain=0.0;
3030 mutation_gain=0.0;
3031
3032 /*
3033 * Mating cycle.
3034 *
3035 * Select pairs of entities to mate via crossover. (Sexual reproduction).
3036 *
3037 * Score the new entities as we go.
3038 */
3039 plog(LOG_VERBOSE, "*** Mating cycle ***");
3040
3041 pop->select_state = 0;
3042
3043 finished = FALSE;
3044 while (!finished)
3045 {
3046 finished = pop->select_two(pop, &mother, &father);
3047
3048 if (mother && father)
3049 {
3050 plog(LOG_VERBOSE, "Crossover between %d (%d = %f) and %d (%d = %f)",
3051 ga_get_entity_id(pop, mother),
3052 ga_get_entity_rank(pop, mother), mother->fitness,
3053 ga_get_entity_id(pop, father),
3054 ga_get_entity_rank(pop, father), father->fitness);
3055
3056 son = ga_get_free_entity(pop);
3057 daughter = ga_get_free_entity(pop);
3058 pop->crossover(pop, mother, father, daughter, son);
3059 if ( pop->evaluate(pop, daughter) == FALSE )
3060 daughter->fitness = GA_MIN_FITNESS;
3061 if ( pop->evaluate(pop, son) == FALSE )
3062 son->fitness = GA_MIN_FITNESS;
3063
3064 /*
3065 * Collate stats.
3066 */
3067 if (son->fitness > father->fitness)
3068 crossover_good++;
3069 else
3070 crossover_poor++;
3071 if (daughter->fitness > father->fitness)
3072 crossover_good++;
3073 else
3074 crossover_poor++;
3075 if (son->fitness > mother->fitness)
3076 crossover_good++;
3077 else
3078 crossover_poor++;
3079 if (daughter->fitness > mother->fitness)
3080 crossover_good++;
3081 else
3082 crossover_poor++;
3083
3084 if (son->fitness > MAX(mother->fitness,father->fitness))
3085 crossover_gain += son->fitness-MAX(mother->fitness,father->fitness);
3086 if (daughter->fitness > MAX(mother->fitness,father->fitness))
3087 crossover_gain += daughter->fitness-MAX(mother->fitness,father->fitness);
3088 }
3089 else
3090 {
3091 plog( LOG_VERBOSE, "Crossover not performed." );
3092 }
3093 }
3094
3095 /*
3096 * Mutation cycle.
3097 *
3098 * Select entities to undergo asexual reproduction, in which case the child will
3099 * have a genetic mutation of some type.
3100 *
3101 * Score the new entities as we go.
3102 */
3103 plog(LOG_VERBOSE, "*** Mutation cycle ***");
3104
3105 pop->select_state = 0;
3106
3107 finished = FALSE;
3108 while (!finished)
3109 {
3110 finished = pop->select_one(pop, &mother);
3111
3112 if (mother)
3113 {
3114 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
3115 ga_get_entity_id(pop, mother),
3116 ga_get_entity_rank(pop, mother), mother->fitness );
3117
3118 daughter = ga_get_free_entity(pop);
3119 pop->mutate(pop, mother, daughter);
3120 if ( pop->evaluate(pop, daughter) == FALSE )
3121 daughter->fitness = GA_MIN_FITNESS;
3122
3123 /*
3124 * Collate stats.
3125 */
3126 if (daughter->fitness > mother->fitness)
3127 {
3128 mutation_good++;
3129 mutation_gain += daughter->fitness-mother->fitness;
3130 }
3131 else
3132 {
3133 mutation_poor++;
3134 }
3135
3136 }
3137 else
3138 {
3139 plog( LOG_VERBOSE, "Mutation not performed." );
3140 }
3141 }
3142
3143 /*
3144 * Environmental adaptation.
3145 *
3146 * Skipped in the case of Darwinian evolution.
3147 * Performed in the case of Baldwinian evolution.
3148 * Performed, and genes are modified, in the case of Lamarckian evolution.
3149 *
3150 * Maybe, could reoptimise all solutions at each generation. This would allow
3151 * a reduced optimisation protocol and only those solutions which are
3152 * reasonable would survive for further optimisation.
3153 */
3154 if (pop->scheme != GA_SCHEME_DARWIN)
3155 {
3156 plog(LOG_VERBOSE, "*** Adaptation round ***");
3157
3158 new_pop_size = pop->size;
3159
3160 switch (pop->scheme)
3161 {
3162 case (GA_SCHEME_BALDWIN_CHILDREN):
3163 /* Baldwinian evolution for children only. */
3164 for (i=pop->orig_size; i<new_pop_size; i++)
3165 {
3166 adult = pop->adapt(pop, pop->entity_iarray[i]);
3167 pop->entity_iarray[i]->fitness=adult->fitness;
3168 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3169 ga_entity_dereference_by_rank(pop, new_pop_size);
3170 }
3171 break;
3172 case (GA_SCHEME_BALDWIN_ALL):
3173 /* Baldwinian evolution for entire population. */
3174 /* I don't recommend this, but it is here for completeness. */
3175 for (i=0; i<new_pop_size; i++)
3176 {
3177 adult = pop->adapt(pop, pop->entity_iarray[i]);
3178 pop->entity_iarray[i]->fitness=adult->fitness;
3179 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3180 ga_entity_dereference_by_rank(pop, new_pop_size);
3181 }
3182 break;
3183 case (GA_SCHEME_LAMARCK_CHILDREN):
3184 /* Lamarckian evolution for children only. */
3185 while (new_pop_size>pop->orig_size)
3186 {
3187 new_pop_size--;
3188 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3189 ga_entity_dereference_by_rank(pop, new_pop_size);
3190 }
3191 break;
3192 case (GA_SCHEME_LAMARCK_ALL):
3193 /* Lamarckian evolution for entire population. */
3194 while (new_pop_size>0)
3195 {
3196 new_pop_size--;
3197 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3198 ga_entity_dereference_by_rank(pop, new_pop_size);
3199 }
3200 break;
3201 default:
3202 dief("Unknown evolutionary scheme %d.\n", pop->scheme);
3203 }
3204 }
3205
3206 /*
3207 * Least fit population members die to restore the
3208 * population size to the stable size.
3209 */
3210 gaul_survival(pop);
3211
3212 plog(LOG_VERBOSE,
3213 "After generation %d, population has fitness scores between %f and %f",
3214 generation,
3215 pop->entity_iarray[0]->fitness,
3216 pop->entity_iarray[pop->size-1]->fitness );
3217
3218 /*
3219 * Write statistics.
3220 */
3221 STATS_OUT = fopen(stats_fname, "a");
3222 fprintf(STATS_OUT, "%d: %d-%d %f %d-%d %f\n", generation,
3223 crossover_good, crossover_poor, crossover_gain,
3224 mutation_good, mutation_poor, mutation_gain);
3225 fclose(STATS_OUT);
3226 } /* Generation loop. */
3227
3228 return generation;
3229 }
3230 #endif
3231
3232
3233 /**********************************************************************
3234 ga_evolution_steady_state()
3235 synopsis: Main genetic algorithm routine. Performs GA-based
3236 optimisation on the given population.
3237 This is a steady-state GA.
3238 ga_genesis(), or equivalent, must be called prior to
3239 this function.
3240 parameters:
3241 return:
3242 last updated: 17 Feb 2005
3243 **********************************************************************/
3244
ga_evolution_steady_state(population * pop,const int max_iterations)3245 int ga_evolution_steady_state( population *pop,
3246 const int max_iterations )
3247 {
3248 int iteration=0; /* Current iteration count. */
3249 int i; /* Loop over members of population. */
3250 entity *mother, *father; /* Parent entities. */
3251 entity *son, *daughter, *child; /* Child entities. */
3252 entity *adult; /* Temporary copy for gene optimisation. */
3253 int new_pop_size; /* Population size prior to adaptation. */
3254
3255 /* Checks. */
3256 if (!pop) die("NULL pointer to population structure passed.");
3257 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
3258 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
3259 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
3260 if (!pop->mutate) die("Population's mutation callback is undefined.");
3261 if (!pop->crossover) die("Population's crossover callback is undefined.");
3262 if (!pop->replace) die("Population's replacement callback is undefined.");
3263 if (!pop->rank) die("Population's ranking callback is undefined.");
3264 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
3265
3266 plog(LOG_VERBOSE, "The evolution has begun!");
3267
3268 pop->generation = 0;
3269
3270 /*
3271 * Score and sort the initial population members.
3272 */
3273 if (pop->size < pop->stable_size)
3274 gaul_population_fill(pop, pop->stable_size - pop->size);
3275 gaul_ensure_evaluations(pop);
3276 sort_population(pop);
3277 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
3278
3279 plog( LOG_VERBOSE,
3280 "Prior to the first iteration, population has fitness scores between %f and %f",
3281 pop->entity_iarray[0]->fitness,
3282 pop->entity_iarray[pop->size-1]->fitness );
3283
3284 /* Do all the iterations: */
3285 while ( (pop->generation_hook?pop->generation_hook(iteration, pop):TRUE) &&
3286 iteration<max_iterations )
3287 {
3288 iteration++;
3289 pop->orig_size = pop->size;
3290
3291 son = NULL;
3292 daughter = NULL;
3293 child = NULL;
3294
3295 plog(LOG_DEBUG,
3296 "Population size is %d at start of iteration %d",
3297 pop->orig_size, iteration );
3298
3299 /*
3300 * Mating cycle.
3301 *
3302 * Select pairs of entities to mate via crossover. (Sexual reproduction).
3303 *
3304 * Score the new entities as we go.
3305 */
3306 plog(LOG_VERBOSE, "*** Mating ***");
3307
3308 pop->select_state = 0;
3309
3310 pop->select_two(pop, &mother, &father);
3311
3312 if (mother && father)
3313 {
3314 plog(LOG_VERBOSE, "Crossover between %d (%d = %f) and %d (%d = %f)",
3315 ga_get_entity_id(pop, mother),
3316 ga_get_entity_rank(pop, mother), mother->fitness,
3317 ga_get_entity_id(pop, father),
3318 ga_get_entity_rank(pop, father), father->fitness);
3319
3320 son = ga_get_free_entity(pop);
3321 daughter = ga_get_free_entity(pop);
3322 pop->crossover(pop, mother, father, daughter, son);
3323 if ( pop->evaluate(pop, daughter) == FALSE )
3324 {
3325 ga_entity_dereference(pop, daughter);
3326 daughter = NULL;
3327 }
3328 if ( pop->evaluate(pop, son) == FALSE )
3329 {
3330 ga_entity_dereference(pop, son);
3331 son = NULL;
3332 }
3333 }
3334 else
3335 {
3336 plog( LOG_VERBOSE, "Crossover not performed." );
3337 }
3338
3339 /*
3340 * Mutation cycle.
3341 *
3342 * Select entities to undergo asexual reproduction, in which case the child will
3343 * have a genetic mutation of some type.
3344 *
3345 * Score the new entities as we go.
3346 */
3347 plog(LOG_VERBOSE, "*** Mutation ***");
3348
3349 pop->select_state = 0;
3350
3351 pop->select_one(pop, &mother);
3352
3353 if (mother)
3354 {
3355 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
3356 ga_get_entity_id(pop, mother),
3357 ga_get_entity_rank(pop, mother), mother->fitness );
3358
3359 child = ga_get_free_entity(pop);
3360 pop->mutate(pop, mother, child);
3361 if ( pop->evaluate(pop, child) == FALSE )
3362 {
3363 ga_entity_dereference(pop, child);
3364 child = NULL;
3365 }
3366 }
3367 else
3368 {
3369 plog( LOG_VERBOSE, "Mutation not performed." );
3370 }
3371
3372 /*
3373 * Environmental adaptation.
3374 *
3375 * Skipped in the case of Darwinian evolution.
3376 * Performed in the case of Baldwinian evolution.
3377 * Performed, and genes are modified, in the case of Lamarckian evolution.
3378 *
3379 * Maybe, could reoptimise all solutions at each generation. This would allow
3380 * a reduced optimisation protocol and only those solutions which are
3381 * reasonable would survive for further optimisation.
3382 *
3383 * FIXME: This is wrong for GA_SCHEME_BALDWIN, GA_SCHEME_LAMARCK and may be
3384 * optimised for GA_SCHEME_BALDWIN_ALL, GA_SCHEME_LAMARCK_ALL.
3385 */
3386 if (pop->scheme != GA_SCHEME_DARWIN)
3387 {
3388 plog(LOG_VERBOSE, "*** Adaptation ***");
3389
3390 new_pop_size = pop->size;
3391
3392 switch (pop->scheme)
3393 {
3394 case (GA_SCHEME_BALDWIN_CHILDREN):
3395 /* Baldwinian evolution for children only. */
3396 for (i=pop->orig_size; i<new_pop_size; i++)
3397 {
3398 adult = pop->adapt(pop, pop->entity_iarray[i]);
3399 pop->entity_iarray[i]->fitness=adult->fitness;
3400 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3401 ga_entity_dereference_by_rank(pop, new_pop_size);
3402 }
3403 break;
3404 case (GA_SCHEME_BALDWIN_ALL):
3405 /* Baldwinian evolution for entire population. */
3406 /* I don't recommend this, but it is here for completeness. */
3407 for (i=0; i<new_pop_size; i++)
3408 {
3409 adult = pop->adapt(pop, pop->entity_iarray[i]);
3410 pop->entity_iarray[i]->fitness=adult->fitness;
3411 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3412 ga_entity_dereference_by_rank(pop, new_pop_size);
3413 }
3414 break;
3415 case (GA_SCHEME_LAMARCK_CHILDREN):
3416 /* Lamarckian evolution for children only. */
3417 while (new_pop_size>pop->orig_size)
3418 {
3419 new_pop_size--;
3420 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3421 ga_entity_dereference_by_rank(pop, new_pop_size);
3422 }
3423 break;
3424 case (GA_SCHEME_LAMARCK_ALL):
3425 /* Lamarckian evolution for entire population. */
3426 while (new_pop_size>0)
3427 {
3428 new_pop_size--;
3429 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3430 ga_entity_dereference_by_rank(pop, new_pop_size);
3431 }
3432 break;
3433 default:
3434 dief("Unknown evolutionary scheme %d.\n", pop->scheme);
3435 }
3436 }
3437
3438 /*
3439 * Insert new entities into population.
3440 */
3441 if (son) pop->replace(pop, son);
3442 if (daughter) pop->replace(pop, daughter);
3443 if (child) pop->replace(pop, child);
3444
3445 /*
3446 * Use callback.
3447 */
3448 plog(LOG_VERBOSE, "*** Analysis ***");
3449
3450 plog(LOG_VERBOSE,
3451 "After iteration %d, population has fitness scores between %f and %f",
3452 iteration,
3453 pop->entity_iarray[0]->fitness,
3454 pop->entity_iarray[pop->size-1]->fitness );
3455
3456 } /* Iteration loop. */
3457
3458 return (iteration<max_iterations);
3459 }
3460
3461
3462 /**********************************************************************
3463 ga_evolution_steady_state_with_stats()
3464 synopsis: Main genetic algorithm routine. Performs GA-based
3465 optimisation on the given population.
3466 This is a steady-state GA.
3467 ga_genesis(), or equivalent, must be called prior to
3468 this function.
3469 parameters:
3470 return:
3471 last updated: 17 Feb 2005
3472 **********************************************************************/
3473
3474 #ifdef COMPILE_DEPRECATED_FUNCTIONS
3475
ga_evolution_steady_state_with_stats(population * pop,const int max_iterations)3476 int ga_evolution_steady_state_with_stats( population *pop,
3477 const int max_iterations )
3478 {
3479 int iteration=0; /* Current iteration count. */
3480 int i; /* Loop over members of population. */
3481 entity *mother, *father; /* Parent entities. */
3482 entity *son, *daughter, *child; /* Child entities. */
3483 entity *adult; /* Temporary copy for gene optimisation. */
3484 int new_pop_size; /* Population size prior to adaptation. */
3485 FILE *STATS_OUT; /* Filehandle for stats log. */
3486 char stats_fname[80]; /* Filename for stats log. */
3487 int crossover_good, crossover_poor; /* Fornication statistics. */
3488 int mutation_good, mutation_poor; /* - " - */
3489 double crossover_gain, mutation_gain; /* - " - */
3490
3491 /* Checks. */
3492 if (!pop) die("NULL pointer to population structure passed.");
3493 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
3494 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
3495 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
3496 if (!pop->mutate) die("Population's mutation callback is undefined.");
3497 if (!pop->crossover) die("Population's crossover callback is undefined.");
3498 if (!pop->replace) die("Population's replacement callback is undefined.");
3499 if (!pop->rank) die("Population's ranking callback is undefined.");
3500 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
3501
3502 plog(LOG_WARNING, "This is a deprecated function!");
3503
3504 plog(LOG_VERBOSE, "The evolution has begun!");
3505
3506 pop->generation = 0;
3507
3508 /*
3509 * Create name for statistics log file.
3510 * Write a simple header to that file.
3511 */
3512 sprintf(stats_fname, "ga_stats_%d.dat", (int) getpid());
3513 STATS_OUT = fopen(stats_fname, "a");
3514 fprintf(STATS_OUT, "gen crossover mutation\n");
3515 fclose(STATS_OUT);
3516
3517 /*
3518 * Score and sort the initial population members.
3519 */
3520 if (pop->size < pop->stable_size)
3521 gaul_population_fill(pop, pop->stable_size - pop->size);
3522 gaul_ensure_evaluations(pop);
3523 sort_population(pop);
3524 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
3525
3526 plog( LOG_VERBOSE,
3527 "Prior to the first iteration, population has fitness scores between %f and %f",
3528 pop->entity_iarray[0]->fitness,
3529 pop->entity_iarray[pop->size-1]->fitness );
3530
3531 /* Do all the iterations: */
3532 while ( (pop->generation_hook?pop->generation_hook(iteration, pop):TRUE) &&
3533 iteration<max_iterations )
3534 {
3535 iteration++;
3536 pop->orig_size = pop->size;
3537
3538 son = NULL;
3539 daughter = NULL;
3540 child = NULL;
3541
3542 plog(LOG_DEBUG,
3543 "Population size is %d at start of iteration %d",
3544 pop->orig_size, iteration );
3545
3546 /*
3547 * Zero statistics.
3548 */
3549 crossover_good=0;
3550 crossover_poor=0;
3551 mutation_good=0;
3552 mutation_poor=0;
3553
3554 crossover_gain=0.0;
3555 mutation_gain=0.0;
3556
3557 /*
3558 * Mating cycle.
3559 *
3560 * Select pairs of entities to mate via crossover. (Sexual reproduction).
3561 *
3562 * Score the new entities as we go.
3563 */
3564 plog(LOG_VERBOSE, "*** Mating ***");
3565
3566 pop->select_state = 0;
3567
3568 pop->select_two(pop, &mother, &father);
3569
3570 if (mother && father)
3571 {
3572 plog(LOG_VERBOSE, "Crossover between %d (%d = %f) and %d (%d = %f)",
3573 ga_get_entity_id(pop, mother),
3574 ga_get_entity_rank(pop, mother), mother->fitness,
3575 ga_get_entity_id(pop, father),
3576 ga_get_entity_rank(pop, father), father->fitness);
3577
3578 son = ga_get_free_entity(pop);
3579 daughter = ga_get_free_entity(pop);
3580 pop->crossover(pop, mother, father, daughter, son);
3581 if ( pop->evaluate(pop, daughter) == FALSE )
3582 daughter->fitness = GA_MIN_FITNESS;
3583 if ( pop->evaluate(pop, son) == FALSE )
3584 son->fitness = GA_MIN_FITNESS;
3585
3586 /*
3587 * Collate stats.
3588 */
3589 if (son->fitness > father->fitness)
3590 crossover_good++;
3591 else
3592 crossover_poor++;
3593 if (daughter->fitness > father->fitness)
3594 crossover_good++;
3595 else
3596 crossover_poor++;
3597 if (son->fitness > mother->fitness)
3598 crossover_good++;
3599 else
3600 crossover_poor++;
3601 if (daughter->fitness > mother->fitness)
3602 crossover_good++;
3603 else
3604 crossover_poor++;
3605
3606 if (son->fitness > MAX(mother->fitness,father->fitness))
3607 crossover_gain += son->fitness-MAX(mother->fitness,father->fitness);
3608 if (daughter->fitness > MAX(mother->fitness,father->fitness))
3609 crossover_gain += daughter->fitness-MAX(mother->fitness,father->fitness);
3610
3611 }
3612 else
3613 {
3614 plog( LOG_VERBOSE, "Crossover not performed." );
3615 }
3616
3617 /*
3618 * Mutation cycle.
3619 *
3620 * Select entities to undergo asexual reproduction, in which case the child will
3621 * have a genetic mutation of some type.
3622 *
3623 * Score the new entities as we go.
3624 */
3625 plog(LOG_VERBOSE, "*** Mutation ***");
3626
3627 pop->select_state = 0;
3628
3629 pop->select_one(pop, &mother);
3630
3631 if (mother)
3632 {
3633 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
3634 ga_get_entity_id(pop, mother),
3635 ga_get_entity_rank(pop, mother), mother->fitness );
3636
3637 child = ga_get_free_entity(pop);
3638 pop->mutate(pop, mother, child);
3639 if ( pop->evaluate(pop, child) == FALSE )
3640 child->fitness = GA_MIN_FITNESS;
3641
3642 /*
3643 * Collate stats.
3644 */
3645 if (child->fitness > mother->fitness)
3646 {
3647 mutation_good++;
3648 mutation_gain += child->fitness-mother->fitness;
3649 }
3650 else
3651 {
3652 mutation_poor++;
3653 }
3654
3655 }
3656 else
3657 {
3658 plog( LOG_VERBOSE, "Mutation not performed." );
3659 }
3660
3661 /*
3662 * Environmental adaptation.
3663 *
3664 * Skipped in the case of Darwinian evolution.
3665 * Performed in the case of Baldwinian evolution.
3666 * Performed, and genes are modified, in the case of Lamarckian evolution.
3667 *
3668 * Maybe, could reoptimise all solutions at each generation. This would allow
3669 * a reduced optimisation protocol and only those solutions which are
3670 * reasonable would survive for further optimisation.
3671 *
3672 * FIXME: This is wrong for GA_SCHEME_BALDWIN, GA_SCHEME_LAMARCK and may be
3673 * optimised for GA_SCHEME_BALDWIN_ALL, GA_SCHEME_LAMARCK_ALL.
3674 */
3675 if (pop->scheme != GA_SCHEME_DARWIN)
3676 {
3677 plog(LOG_VERBOSE, "*** Adaptation ***");
3678
3679 new_pop_size = pop->size;
3680
3681 switch (pop->scheme)
3682 {
3683 case (GA_SCHEME_BALDWIN_CHILDREN):
3684 /* Baldwinian evolution for children only. */
3685 for (i=pop->orig_size; i<new_pop_size; i++)
3686 {
3687 adult = pop->adapt(pop, pop->entity_iarray[i]);
3688 pop->entity_iarray[i]->fitness=adult->fitness;
3689 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3690 ga_entity_dereference_by_rank(pop, new_pop_size);
3691 }
3692 break;
3693 case (GA_SCHEME_BALDWIN_ALL):
3694 /* Baldwinian evolution for entire population. */
3695 /* I don't recommend this, but it is here for completeness. */
3696 for (i=0; i<new_pop_size; i++)
3697 {
3698 adult = pop->adapt(pop, pop->entity_iarray[i]);
3699 pop->entity_iarray[i]->fitness=adult->fitness;
3700 /* check. */ s_assert(ga_get_entity_rank(pop, adult) == new_pop_size);
3701 ga_entity_dereference_by_rank(pop, new_pop_size);
3702 }
3703 break;
3704 case (GA_SCHEME_LAMARCK_CHILDREN):
3705 /* Lamarckian evolution for children only. */
3706 while (new_pop_size>pop->orig_size)
3707 {
3708 new_pop_size--;
3709 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3710 ga_entity_dereference_by_rank(pop, new_pop_size);
3711 }
3712 break;
3713 case (GA_SCHEME_LAMARCK_ALL):
3714 /* Lamarckian evolution for entire population. */
3715 while (new_pop_size>0)
3716 {
3717 new_pop_size--;
3718 adult = pop->adapt(pop, pop->entity_iarray[new_pop_size]);
3719 ga_entity_dereference_by_rank(pop, new_pop_size);
3720 }
3721 break;
3722 default:
3723 dief("Unknown evolutionary scheme %d.\n", pop->scheme);
3724 }
3725 }
3726
3727 /*
3728 * Insert new entities into population.
3729 */
3730 if (son) pop->replace(pop, son);
3731 if (daughter) pop->replace(pop, daughter);
3732 if (child) pop->replace(pop, child);
3733
3734 /*
3735 * Use callback.
3736 */
3737 plog(LOG_VERBOSE, "*** Analysis ***");
3738
3739 plog(LOG_VERBOSE,
3740 "After iteration %d, population has fitness scores between %f and %f",
3741 iteration,
3742 pop->entity_iarray[0]->fitness,
3743 pop->entity_iarray[pop->size-1]->fitness );
3744
3745 /*
3746 * Write statistics.
3747 */
3748 STATS_OUT = fopen(stats_fname, "a");
3749 fprintf(STATS_OUT, "%d: %d-%d %f %d-%d %f\n", iteration,
3750 crossover_good, crossover_poor, crossover_gain,
3751 mutation_good, mutation_poor, mutation_gain);
3752 fclose(STATS_OUT);
3753
3754 } /* Iteration loop. */
3755
3756 return (iteration<max_iterations);
3757 }
3758 #endif
3759
3760
3761 /**********************************************************************
3762 ga_random_mutation_hill_climbing()
3763 synopsis: Perform equivalent to zero temperature metropolis
3764 optimisation. If initial solution is NULL, then a
3765 random initial solution is generated.
3766 The original entity will not be munged.
3767
3768 -- This function is deprecated! --
3769 parameters:
3770 return: Best solution found.
3771 last updated: 18/12/00
3772 **********************************************************************/
3773
3774 #ifdef COMPILE_DEPRECATED_FUNCTIONS
3775
ga_random_mutation_hill_climbing(population * pop,entity * initial,const int max_iterations)3776 entity *ga_random_mutation_hill_climbing( population *pop,
3777 entity *initial,
3778 const int max_iterations)
3779 {
3780 int iteration=0; /* Current iteration number. */
3781 entity *current, *best, *new, *temp; /* The solutions. */
3782 #if GA_WRITE_STATS==TRUE
3783 FILE *STATS_OUT; /* Filehandle for stats log. */
3784 char stats_fname[80]; /* Filename for stats log. */
3785 #endif
3786
3787 /* Checks. */
3788 if ( !pop ) die("NULL pointer to population structure passed.");
3789 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
3790 if (!pop->mutate) die("Population's mutation callback is undefined.");
3791
3792 plog(LOG_WARNING, "This is a deprecated function!");
3793
3794 current = ga_get_free_entity(pop); /* The 'working' solution. */
3795 best = ga_get_free_entity(pop); /* The best solution so far. */
3796
3797 /* Do we need to generate a random starting solution? */
3798 if (!initial)
3799 {
3800 plog(LOG_VERBOSE, "Will perform RMHC optimisation with random starting solution.");
3801
3802 ga_entity_seed(pop, best);
3803 }
3804 else
3805 {
3806 plog(LOG_VERBOSE, "Will perform RMHC optimisation with specified starting solution.");
3807 ga_entity_copy(pop, best, initial);
3808 }
3809
3810 /*
3811 * Create name for statistics log file.
3812 * Write a simple header to that file.
3813 */
3814 #if GA_WRITE_STATS==TRUE
3815 sprintf(stats_fname, "rmhc_stats_%d.dat", (int) getpid());
3816 STATS_OUT = fopen(stats_fname, "a");
3817 fprintf(STATS_OUT, "Random Mutation Hill Climbing\n");
3818 fclose(STATS_OUT);
3819 #endif
3820
3821 /*
3822 * Score the initial solution.
3823 */
3824 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
3825 plog(LOG_DEBUG,
3826 "Prior to the scoring, the solution has fitness score of %f",
3827 best->fitness );
3828
3829 /*
3830 * Copy best solution found over current solution.
3831 */
3832 ga_entity_copy(pop, current, best);
3833 new = ga_get_free_entity(pop);
3834
3835 /* Do all the iterations: */
3836 while ( (pop->iteration_hook?pop->iteration_hook(iteration, current):TRUE) &&
3837 iteration<max_iterations )
3838 {
3839 iteration++;
3840
3841 plog( LOG_VERBOSE,
3842 "Prior to the iteration %d, the solution has fitness score of %f",
3843 iteration, current->fitness );
3844
3845 /*
3846 * Perform random mutation.
3847 */
3848 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
3849 ga_get_entity_id(pop, current),
3850 ga_get_entity_rank(pop, current), current->fitness );
3851
3852 pop->mutate(pop, current, new);
3853
3854 temp = current;
3855 current = new;
3856 new = temp;
3857
3858 pop->evaluate(pop, current);
3859
3860 if (best->fitness < current->fitness)
3861 {
3862 /* plog(LOG_DEBUG, "Selecting new solution.");*/
3863 ga_entity_blank(pop, best);
3864 ga_entity_copy(pop, best, current);
3865 }
3866 else
3867 {
3868 ga_entity_blank(pop, current);
3869 ga_entity_copy(pop, current, best);
3870 }
3871
3872 ga_entity_blank(pop, new);
3873
3874 /*
3875 * Write statistics.
3876 */
3877 #if GA_WRITE_STATS==TRUE
3878 STATS_OUT = fopen(stats_fname, "a");
3879 fprintf(STATS_OUT, "%d: %f\n", iteration, best->fitness);
3880 fclose(STATS_OUT);
3881 #endif
3882 }
3883
3884 plog( LOG_VERBOSE,
3885 "After final iteration, the solution has fitness score of %f",
3886 current->fitness );
3887
3888 /*
3889 * Current no longer needed. It is upto the caller to dereference the
3890 * optimum solution found.
3891 */
3892 ga_entity_dereference(pop, current);
3893
3894 return best;
3895 }
3896 #endif
3897
3898
3899 /**********************************************************************
3900 ga_next_ascent_hill_climbing()
3901 synopsis: Perform systematic ascent hill climbing optimisation.
3902 (Needn't nessecarily use next allele each time, but
3903 this was the simplist to implement.)
3904 If initial solution is NULL, then a randomly generated
3905 initial solution is generated.
3906 The original entity will not be munged.
3907 NOTE: Needs to be passed an 'extended' mutation
3908 function.
3909 max_iterations refers to the number of _complete_
3910 cycles.
3911 parameters:
3912 return: Best solution found.
3913 last updated: 21/12/00
3914 **********************************************************************/
3915
3916 #ifdef COMPILE_DEPRECATED_FUNCTIONS
3917
old_ga_next_ascent_hill_climbing(population * pop,entity * initial,const int max_iterations,GAspecificmutate mutationfunc)3918 entity *old_ga_next_ascent_hill_climbing( population *pop,
3919 entity *initial,
3920 const int max_iterations,
3921 GAspecificmutate mutationfunc)
3922 {
3923 int iteration=0; /* Current iteration number. */
3924 entity *current, *best; /* The solutions. */
3925 int chromo=0, point=0; /* Mutation locus. */
3926 #if GA_WRITE_STATS==TRUE
3927 FILE *STATS_OUT; /* Filehandle for stats log. */
3928 char stats_fname[80]; /* Filename for stats log. */
3929 #endif
3930
3931 plog(LOG_WARNING, "This is a deprecated function!");
3932
3933 /* Checks. */
3934 if ( !pop ) die("NULL pointer to population structure passed.");
3935 if ( !pop->evaluate ) die("Population's evaluation callback is undefined.");
3936 if ( !mutationfunc ) die("Mutation callback is undefined.");
3937
3938 current = ga_get_free_entity(pop); /* The 'working' solution. */
3939 best = ga_get_free_entity(pop); /* The best solution so far. */
3940
3941 plog(LOG_FIXME, "NAHC algorithm is not parallelised.");
3942
3943 /* Do we need to generate a random starting solution? */
3944 if (!initial)
3945 {
3946 plog(LOG_VERBOSE, "Will perform NAHC optimisation with random starting solution.");
3947
3948 ga_entity_seed(pop, best);
3949 }
3950 else
3951 {
3952 plog(LOG_VERBOSE, "Will perform NAHC optimisation with specified starting solution.");
3953 ga_entity_copy(pop, best, initial);
3954 }
3955
3956 /*
3957 * Create name for statistics log file.
3958 * Write a simple header to that file.
3959 */
3960 #if GA_WRITE_STATS==TRUE
3961 sprintf(stats_fname, "nahc_stats_%d.dat", (int) getpid());
3962 STATS_OUT = fopen(stats_fname, "a");
3963 fprintf(STATS_OUT, "Next Ascent Hill Climbing\n");
3964 fclose(STATS_OUT);
3965 #endif
3966
3967 /*
3968 * Score the initial solution.
3969 */
3970 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
3971 plog(LOG_DEBUG, "Prior to the scoring, the solution has fitness score of %f", best->fitness );
3972
3973 /*
3974 * Copy best solution found over current solution.
3975 */
3976 ga_entity_copy(pop, current, best);
3977
3978 /* Do all the iterations: */
3979 while ( (pop->iteration_hook?pop->iteration_hook(iteration, current):TRUE) &&
3980 iteration<max_iterations )
3981 {
3982
3983 plog( LOG_VERBOSE,
3984 "Iteration %d chromosome %d, point %d, solution has fitness score of %f",
3985 iteration, chromo, point,
3986 current->fitness );
3987
3988 mutationfunc(chromo, point, current->chromosome[chromo]);
3989
3990 ga_entity_clear_data(pop, current, chromo); /* Required to force regeneration of structural data. */
3991 pop->evaluate(pop, current);
3992
3993 /*
3994 * Is current better than best?
3995 */
3996 if (best->fitness < current->fitness)
3997 {
3998 /* plog(LOG_DEBUG, "Selecting new solution.");*/
3999 ga_entity_blank(pop, best);
4000 ga_entity_copy(pop, best, current);
4001 }
4002 else
4003 {
4004 ga_entity_blank(pop, current);
4005 ga_entity_copy(pop, current, best);
4006 }
4007
4008 /*
4009 * Write statistics.
4010 */
4011 #if GA_WRITE_STATS==TRUE
4012 STATS_OUT = fopen(stats_fname, "a");
4013 fprintf(STATS_OUT, "%d: %f (%d %d)\n", iteration, best->fitness, chromo, point);
4014 fclose(STATS_OUT);
4015 #endif
4016
4017 /*
4018 * Choose next nucleotide to mutate/optimise.
4019 */
4020 point++;
4021 if (point == pop->len_chromosomes)
4022 {
4023 point = 0;
4024 chromo++;
4025 if (chromo == pop->num_chromosomes)
4026 {
4027 chromo=0;
4028 iteration++;
4029 }
4030 }
4031 }
4032
4033 plog( LOG_VERBOSE,
4034 "After final iteration, the solution has fitness score of %f",
4035 current->fitness );
4036
4037 /*
4038 * Current no longer needed. It is upto the caller to dereference the
4039 * optimum solution found.
4040 */
4041 ga_entity_dereference(pop, current);
4042
4043 return best;
4044 }
4045 #endif
4046
4047
4048 /**********************************************************************
4049 ga_metropolis_mutation()
4050 synopsis: Perform arbitrary temperature metropolis optimisation.
4051 If initial solution is NULL, then random solution is
4052 generated. Syncs with other processors every iteration
4053 and grabs the overall best solution if better than
4054 this processors current solution is worse than the best
4055 plus the temperature.
4056 The original entity will not be munged.
4057 parameters:
4058 return: Best solution found.
4059 last updated: 19/01/01
4060 **********************************************************************/
4061
4062 #ifdef COMPILE_DEPRECATED_FUNCTIONS
4063
ga_metropolis_mutation(population * pop,entity * initial,const int max_iterations,const int temperature)4064 entity *ga_metropolis_mutation( population *pop,
4065 entity *initial,
4066 const int max_iterations,
4067 const int temperature)
4068 {
4069 int iteration=0; /* Current iteration number. */
4070 entity *current, *best, *fresh; /* The solutions. */
4071 entity *temp=NULL; /* Used for swapping current and new. */
4072 #if GA_WRITE_STATS==TRUE
4073 FILE *STATS_OUT; /* Filehandle for stats log. */
4074 char stats_fname[80]; /* Filename for stats log. */
4075 #endif
4076
4077 plog(LOG_NORMAL, "This function is deprecated!");
4078
4079 /* Checks. */
4080 if ( !pop ) die("NULL pointer to population structure passed.");
4081 if ( !pop->evaluate ) die("Population's evaluation callback is undefined.");
4082 if ( !pop->mutate ) die("Population's mutation callback is undefined.");
4083
4084 current = ga_get_free_entity(pop); /* The 'working' solution. */
4085 best = ga_get_free_entity(pop); /* The best solution so far. */
4086
4087 plog(LOG_FIXME, "Metropolis algorithm is not parallelised.");
4088
4089 /* Do we need to generate a random starting solution? */
4090 if (!initial)
4091 {
4092 plog(LOG_VERBOSE, "Will perform metropolis optimisation at %d degrees with random starting solution.", temperature);
4093
4094 ga_entity_seed(pop, best);
4095 }
4096 else
4097 {
4098 plog(LOG_VERBOSE, "Will perform metropolis optimisation at %d degrees.");
4099 ga_entity_copy(pop, best, initial);
4100 }
4101
4102 /*
4103 * Create name for statistics log file.
4104 * Write a simple header to that file.
4105 */
4106 #if GA_WRITE_STATS==TRUE
4107 sprintf(stats_fname, "mstats_%d.dat", (int) getpid());
4108 STATS_OUT = fopen(stats_fname, "a");
4109 fprintf(STATS_OUT, "Metropolis optimisation at %d degrees.\n", temperature);
4110 fclose(STATS_OUT);
4111 #endif
4112
4113 /*
4114 * Score the initial solution.
4115 */
4116 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
4117 plog(LOG_DEBUG, "Prior to the scoring, the solution has fitness score of %f", best->fitness );
4118
4119 /*
4120 * Copy best solution found over current solution.
4121 */
4122 ga_entity_copy(pop, current, best);
4123 fresh = ga_get_free_entity(pop);
4124
4125 /* Do all the iterations: */
4126 while ( (pop->iteration_hook?pop->iteration_hook(iteration, current):TRUE) &&
4127 iteration<max_iterations )
4128 {
4129 iteration++;
4130
4131 plog(LOG_VERBOSE,
4132 "Prior to iteration %d, solution has fitness score of %f",
4133 iteration, current->fitness );
4134
4135 /*
4136 * Perform random mutation.
4137 */
4138 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
4139 ga_get_entity_id(pop, current),
4140 ga_get_entity_rank(pop, current), current->fitness );
4141
4142 pop->mutate(pop, current, fresh);
4143
4144 temp = current;
4145 current = fresh;
4146 fresh = temp;
4147
4148 pop->evaluate(pop, current);
4149
4150 /*
4151 * Should we keep this solution?
4152 */
4153 if ( best->fitness < current->fitness ||
4154 random_boolean_prob(exp((current->fitness-best->fitness)
4155 /(GA_BOLTZMANN_FACTOR*temperature))) )
4156 {
4157 /* plog(LOG_DEBUG, "Selecting fresh solution."); */
4158 ga_entity_blank(pop, best);
4159 ga_entity_copy(pop, best, current);
4160 }
4161 else
4162 {
4163 /* plog(LOG_DEBUG, "Rejecting fresh solution."); */
4164 ga_entity_blank(pop, current);
4165 ga_entity_copy(pop, current, best);
4166 }
4167
4168 ga_entity_blank(pop, fresh);
4169
4170 /*
4171 * Write statistics.
4172 */
4173 #if GA_WRITE_STATS==TRUE
4174 STATS_OUT = fopen(stats_fname, "a");
4175 fprintf(STATS_OUT, "%d: %f\n", iteration, best->fitness);
4176 fclose(STATS_OUT);
4177 #endif
4178 }
4179
4180 plog( LOG_VERBOSE,
4181 "After final iteration, solution has fitness score of %f",
4182 best->fitness );
4183
4184 /*
4185 * Current no longer needed. It is upto the caller to dereference the
4186 * optimum solution found.
4187 */
4188 ga_entity_dereference(pop, current);
4189 ga_entity_dereference(pop, temp);
4190
4191 return best;
4192 }
4193 #endif
4194
4195
4196 /**********************************************************************
4197 ga_simulated_annealling_mutation()
4198 synopsis: Perform mutation/SA (GA mutation/Simulated Annealling).
4199 If initial solution is NULL, then random solution is
4200 generated. Syncs with other processors every iteration
4201 and grabs the overall best solution if better than
4202 this processors current solution is worse than the best
4203 plus the temperature.
4204 The original entity will not be munged.
4205 parameters:
4206 return: Best solution found.
4207 last updated: 21/02/01
4208 **********************************************************************/
4209
4210 #ifdef COMPILE_DEPRECATED_FUNCTIONS
4211
ga_simulated_annealling_mutation(population * pop,entity * initial,const int max_iterations,const int initial_temperature,const int final_temperature)4212 entity *ga_simulated_annealling_mutation(population *pop,
4213 entity *initial,
4214 const int max_iterations,
4215 const int initial_temperature,
4216 const int final_temperature)
4217 {
4218 int iteration=0; /* Current iteration number. */
4219 entity *current, *best, *fresh; /* The solutions. */
4220 entity *temp=NULL; /* Used for swapping current and new solutions. */
4221 int temperature; /* Current temperature. */
4222 #if GA_WRITE_STATS==TRUE
4223 FILE *STATS_OUT; /* Filehandle for stats log. */
4224 char stats_fname[80]; /* Filename for stats log. */
4225 #endif
4226
4227 plog(LOG_NORMAL, "This function is deprecated!");
4228
4229 /* Checks. */
4230 if ( !pop ) die("NULL pointer to population structure passed.");
4231 if ( !pop->evaluate ) die("Population's evaluation callback is undefined.");
4232 if ( !pop->mutate ) die("Population's mutation callback is undefined.");
4233
4234 current = ga_get_free_entity(pop); /* The 'working' solution. */
4235 best = ga_get_free_entity(pop); /* The best solution so far. */
4236
4237 plog(LOG_FIXME, "Simulated annealling algorithm is not parallelised.");
4238
4239 /* Do we need to generate a random starting solution? */
4240 if (!initial)
4241 {
4242 plog(LOG_VERBOSE, "Will perform %d steps of MC/SA optimisation between %d and %d degrees with random starting solution.", max_iterations, initial_temperature, final_temperature);
4243
4244 ga_entity_seed(pop, best);
4245 }
4246 else
4247 {
4248 plog(LOG_VERBOSE, "Will perform %d steps of MC/SA optimisation between %d and %d degrees.", max_iterations, initial_temperature, final_temperature);
4249
4250 ga_entity_copy(pop, best, initial);
4251 }
4252
4253 /*
4254 * Create name for statistics log file.
4255 * Write a simple header to that file.
4256 */
4257 #if GA_WRITE_STATS==TRUE
4258 sprintf(stats_fname, "sastats_%d.dat", (int) getpid());
4259 STATS_OUT = fopen(stats_fname, "a");
4260 fprintf(STATS_OUT, "MC/SA optimisation at %d to %d degrees.\n",
4261 initial_temperature, final_temperature);
4262 fclose(STATS_OUT);
4263 #endif
4264
4265 /*
4266 * Score the initial solution.
4267 */
4268 if (best->fitness==GA_MIN_FITNESS) pop->evaluate(pop, best);
4269 plog(LOG_DEBUG, "Prior to the scoring, the solution has fitness score of %f", best->fitness );
4270
4271 /*
4272 * Copy best solution over current solution.
4273 */
4274 ga_entity_copy(pop, current, best);
4275 fresh = ga_get_free_entity(pop);
4276
4277 /* Do all the iterations: */
4278 while ( (pop->iteration_hook?pop->iteration_hook(iteration, current):TRUE) &&
4279 iteration<max_iterations )
4280 {
4281 temperature = initial_temperature + ((double)iteration/max_iterations)*(final_temperature-initial_temperature);
4282 iteration++;
4283
4284 plog( LOG_VERBOSE,
4285 "Prior to iteration %d temperature %d, solution has fitness score of %f",
4286 iteration, temperature, current->fitness );
4287
4288 /*
4289 * Perform random mutation.
4290 */
4291 plog(LOG_VERBOSE, "Mutation of %d (%d = %f)",
4292 ga_get_entity_id(pop, current),
4293 ga_get_entity_rank(pop, current), current->fitness );
4294
4295 pop->mutate(pop, current, fresh);
4296
4297 temp = current;
4298 current = fresh;
4299 fresh = temp;
4300
4301 pop->evaluate(pop, current);
4302
4303 /*
4304 * Should we keep this solution?
4305 if ( best->fitness < current->fitness ||
4306 random_boolean_prob(exp((current->fitness-best->fitness)
4307 /(GA_BOLTZMANN_FACTOR*temperature))) )
4308 */
4309 if ( best->fitness < current->fitness+temperature )
4310 { /* Copy this solution best solution. */
4311 /* plog(LOG_DEBUG, "Selecting fresh solution.");*/
4312 ga_entity_blank(pop, best);
4313 ga_entity_copy(pop, best, current);
4314 }
4315 else
4316 { /* Copy best solution over current solution. */
4317 /* plog(LOG_DEBUG, "Rejecting fresh solution.");*/
4318 ga_entity_blank(pop, current);
4319 ga_entity_copy(pop, current, best);
4320 }
4321
4322 ga_entity_blank(pop, fresh);
4323
4324 /*
4325 * Write statistics.
4326 */
4327 #if GA_WRITE_STATS==TRUE
4328 STATS_OUT = fopen(stats_fname, "a");
4329 fprintf(STATS_OUT, "%d: (%d degrees) %f\n",
4330 iteration, temperature, best->fitness);
4331 fclose(STATS_OUT);
4332 #endif
4333 }
4334
4335 plog(LOG_VERBOSE,
4336 "After final iteration, the solution has fitness score of %f",
4337 best->fitness );
4338
4339 /*
4340 * Current no longer needed. It is upto the caller to dereference the
4341 * optimum solution found.
4342 */
4343 ga_entity_dereference(pop, current);
4344 ga_entity_dereference(pop, temp);
4345
4346 return best;
4347 }
4348 #endif
4349
4350
4351 /**********************************************************************
4352 ga_evolution_archipelago()
4353 synopsis: Main genetic algorithm routine. Performs GA-based
4354 optimisation on the given populations using a simple
4355 current_island model. Migration occurs around a cyclic
4356 topology only. Migration causes a duplication of the
4357 respective entities. This is a generation-based GA.
4358 ga_genesis(), or equivalent, must be called prior to
4359 this function.
4360 parameters: const int num_pops
4361 population **pops
4362 const int max_generations
4363 return: number of generation performed
4364 last updated: 17 Feb 2005
4365 **********************************************************************/
4366
ga_evolution_archipelago(const int num_pops,population ** pops,const int max_generations)4367 int ga_evolution_archipelago( const int num_pops,
4368 population **pops,
4369 const int max_generations )
4370 {
4371 int generation=0; /* Current generation number. */
4372 int current_island; /* Current current_island number. */
4373 population *pop=NULL; /* Current population. */
4374 boolean complete=FALSE; /* Whether evolution is terminated. */
4375
4376 /* Checks. */
4377 if (!pops)
4378 die("NULL pointer to array of population structures passed.");
4379 if (num_pops<2)
4380 die("Need at least two populations for the current_island model.");
4381
4382 for (current_island=0; current_island<num_pops; current_island++)
4383 {
4384 pop = pops[current_island];
4385
4386 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
4387 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
4388 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
4389 if (!pop->mutate) die("Population's mutation callback is undefined.");
4390 if (!pop->crossover) die("Population's crossover callback is undefined.");
4391 if (!pop->rank) die("Population's ranking callback is undefined.");
4392 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
4393
4394 /* Set current_island property. */
4395 pop->island = current_island;
4396 }
4397
4398 plog(LOG_VERBOSE, "The evolution has begun on %d islands!", num_pops);
4399
4400 pop->generation = 0;
4401
4402 for (current_island=0; current_island<num_pops; current_island++)
4403 {
4404 pop = pops[current_island];
4405
4406 /*
4407 * Score and sort the initial population members.
4408 */
4409 if (pop->size < pop->stable_size)
4410 gaul_population_fill(pop, pop->stable_size - pop->size);
4411 gaul_ensure_evaluations(pop);
4412 sort_population(pop);
4413 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
4414
4415 plog( LOG_VERBOSE,
4416 "Prior to the first generation, population on current_island %d has fitness scores between %f and %f",
4417 current_island,
4418 pop->entity_iarray[0]->fitness,
4419 pop->entity_iarray[pop->size-1]->fitness );
4420 }
4421
4422 /* Do all the generations: */
4423 while ( generation<max_generations && complete==FALSE)
4424 {
4425 generation++;
4426 pop->generation = generation;
4427
4428 /*
4429 * Migration step.
4430 */
4431 gaul_migration(num_pops, pops);
4432
4433 for(current_island=0; current_island<num_pops; current_island++)
4434 {
4435 pop = pops[current_island];
4436
4437 plog( LOG_VERBOSE, "*** Evolution on current_island %d ***", current_island );
4438
4439 if (pop->generation_hook?pop->generation_hook(generation, pop):TRUE)
4440 {
4441 pop->orig_size = pop->size;
4442
4443 plog( LOG_DEBUG,
4444 "Population %d size is %d at start of generation %d",
4445 current_island, pop->orig_size, generation );
4446
4447 /*
4448 * Crossover step.
4449 */
4450 gaul_crossover(pop); /* FIXME: Need to pass current_island for messages. */
4451
4452 /*
4453 * Mutation step.
4454 */
4455 gaul_mutation(pop); /* FIXME: Need to pass current_island for messages. */
4456
4457 /*
4458 * Apply environmental adaptations, score entities, sort entities, etc.
4459 */
4460 gaul_adapt_and_evaluate(pop);
4461
4462 /*
4463 * Survival of the fittest.
4464 */
4465 gaul_survival(pop);
4466
4467 }
4468 else
4469 {
4470 complete = TRUE;
4471 }
4472 }
4473
4474 plog(LOG_VERBOSE,
4475 "After generation %d, population %d has fitness scores between %f and %f",
4476 generation,
4477 current_island,
4478 pop->entity_iarray[0]->fitness,
4479 pop->entity_iarray[pop->size-1]->fitness );
4480
4481 } /* Generation loop. */
4482
4483 return generation;
4484 }
4485
4486
4487 /**********************************************************************
4488 ga_evolution_archipelago_mpi()
4489 synopsis: Main genetic algorithm routine. Performs GA-based
4490 optimisation on the given populations using a simple
4491 current_island model. Migration occurs around a cyclic
4492 topology only. Migration causes a duplication of the
4493 respective entities. This is a generation-based GA.
4494 ga_genesis(), or equivalent, must be called prior to
4495 this function.
4496 parameters: const int num_pops
4497 population **pops
4498 const int max_generations
4499 return: number of generation performed
4500 last updated: 21 Feb 2005
4501 **********************************************************************/
4502
ga_evolution_archipelago_mpi(const int num_pops,population ** pops,const int max_generations)4503 int ga_evolution_archipelago_mpi( const int num_pops,
4504 population **pops,
4505 const int max_generations )
4506 {
4507 #if HAVE_MPI==1
4508 int current_island; /* Current current_island number. */
4509 population *pop=NULL; /* Current population. */
4510 boolean complete=FALSE; /* Whether evolution is terminated. */
4511 int generation=0; /* Current generation number. */
4512 int mpi_rank; /* Rank of MPI process; should always by 0 here. */
4513 int mpi_size; /* Number of MPI processes. */
4514 byte *buffer=NULL; /* Send buffer. */
4515 int buffer_len=0; /* Length of send buffer. */
4516 int buffer_max=0; /* Length of send buffer. */
4517 int *eid; /* Sorage of entity ids being processed. */
4518
4519 /* Checks. */
4520 if (!pops)
4521 die("NULL pointer to array of population structures passed.");
4522 if (num_pops<2)
4523 die("Need at least two populations for the current_island model.");
4524
4525 for (current_island=0; current_island<num_pops; current_island++)
4526 {
4527 pop = pops[current_island];
4528
4529 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
4530 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
4531 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
4532 if (!pop->mutate) die("Population's mutation callback is undefined.");
4533 if (!pop->crossover) die("Population's crossover callback is undefined.");
4534 if (!pop->rank) die("Population's ranking callback is undefined.");
4535 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
4536
4537 /* Set current_island property. */
4538 pop->island = current_island;
4539 }
4540
4541 for (current_island=0; current_island<num_pops; current_island++)
4542 {
4543 pop = pops[current_island];
4544
4545 /*
4546 * Seed initial entities.
4547 * This is required prior to determining the size of the send buffer.
4548 */
4549 if (pop->size < pop->stable_size)
4550 gaul_population_fill(pop, pop->stable_size - pop->size);
4551 }
4552
4553 /*
4554 * Rank zero process is master. This handles evolution. Other processes are slaves
4555 * which simply evaluate entities, and should be attached using ga_attach_slave().
4556 */
4557 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
4558 if (mpi_rank != 0)
4559 die("ga_evolution_archipelago_mpi() called by process other than rank=0.");
4560
4561 /*
4562 * Allocate a send buffer of the required length and an array to store
4563 * entity ids.
4564 */
4565 buffer_len = pop->chromosome_to_bytes(pop, pop->entity_iarray[0], &buffer, &buffer_max);
4566 if (buffer_max == 0)
4567 buffer = s_malloc(buffer_len*sizeof(byte));
4568
4569 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
4570 eid = s_malloc(mpi_size*sizeof(int));
4571
4572 /*
4573 * Register, set up and synchronise slave processes.
4574 */
4575 gaul_bond_slaves_mpi(pop, buffer_len, buffer_max);
4576
4577 plog(LOG_VERBOSE, "The evolution has begun on %d islands (on %d processors)!", num_pops, mpi_size);
4578
4579 pop->generation = 0;
4580
4581 for (current_island=0; current_island<num_pops; current_island++)
4582 {
4583 pop = pops[current_island];
4584
4585 /*
4586 * Score and sort the initial population members.
4587 */
4588 gaul_ensure_evaluations_mpi(pop, eid, buffer, buffer_len, buffer_max);
4589 sort_population(pop);
4590 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
4591
4592 plog( LOG_VERBOSE,
4593 "Prior to the first generation, population on current_island %d has fitness scores between %f and %f",
4594 current_island,
4595 pop->entity_iarray[0]->fitness,
4596 pop->entity_iarray[pop->size-1]->fitness );
4597 }
4598
4599 /* Do all the generations: */
4600 while ( generation<max_generations && complete==FALSE)
4601 {
4602 generation++;
4603 pop->generation = generation;
4604
4605 /*
4606 * Migration step.
4607 */
4608 gaul_migration(num_pops, pops);
4609
4610 for(current_island=0; current_island<num_pops; current_island++)
4611 {
4612 pop = pops[current_island];
4613
4614 plog( LOG_VERBOSE, "*** Evolution on current_island %d ***", current_island );
4615
4616 if (pop->generation_hook?pop->generation_hook(generation, pop):TRUE)
4617 {
4618 pop->orig_size = pop->size;
4619
4620 plog( LOG_DEBUG,
4621 "Population %d size is %d at start of generation %d",
4622 current_island, pop->orig_size, generation );
4623
4624 /*
4625 * Crossover step.
4626 */
4627 gaul_crossover(pop); /* FIXME: Need to pass current_island for messages. */
4628
4629 /*
4630 * Mutation step.
4631 */
4632 gaul_mutation(pop); /* FIXME: Need to pass current_island for messages. */
4633
4634 /*
4635 * Apply environmental adaptations, score entities, sort entities, etc.
4636 */
4637 gaul_adapt_and_evaluate_mpi(pop, eid, buffer, buffer_len, buffer_max);
4638
4639 /*
4640 * Survival of the fittest.
4641 */
4642 gaul_survival_mpi(pop);
4643
4644 }
4645 else
4646 {
4647 complete = TRUE;
4648 }
4649 }
4650
4651 plog(LOG_VERBOSE,
4652 "After generation %d, population %d has fitness scores between %f and %f",
4653 generation,
4654 current_island,
4655 pop->entity_iarray[0]->fitness,
4656 pop->entity_iarray[pop->size-1]->fitness );
4657
4658 /*
4659 * Use callback.
4660 */
4661 plog( LOG_VERBOSE,
4662 "After generation %d, population has fitness scores between %f and %f",
4663 generation,
4664 pop->entity_iarray[0]->fitness,
4665 pop->entity_iarray[pop->size-1]->fitness );
4666
4667 } /* Generation loop. */
4668
4669 /*
4670 * Register, set up and synchronise slave processes.
4671 */
4672 gaul_debond_slaves_mpi(pop);
4673
4674 /*
4675 * Deallocate send buffer and entity id array.
4676 */
4677 s_free(buffer);
4678 s_free(eid);
4679
4680 return generation;
4681 #else
4682 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
4683
4684 return 0;
4685 #endif
4686 }
4687
4688
4689 /**********************************************************************
4690 ga_evolution_archipelago_threaded()
4691 synopsis: Main genetic algorithm routine. Performs GA-based
4692 optimisation on the given populations using a simple
4693 current_island model. Migration occurs around a cyclic
4694 topology only. Migration causes a duplication of the
4695 respective entities. This is a generation-based GA.
4696 ga_genesis(), or equivalent, must be called prior to
4697 this function.
4698 This is a multiprocess version, using a thread
4699 for each current_island.
4700 FIXME: There is scope for further optimisation in here.
4701 parameters: const int num_pops
4702 population **pops
4703 const int max_generations
4704 return: number of generation performed
4705 last updated: 18 Feb 2005
4706 **********************************************************************/
4707
4708 #if HAVE_PTHREADS == 1
ga_evolution_archipelago_threaded(const int num_pops,population ** pops,const int max_generations)4709 int ga_evolution_archipelago_threaded( const int num_pops,
4710 population **pops,
4711 const int max_generations )
4712 {
4713 int generation=0; /* Current generation number. */
4714 int current_island; /* Current current_island number. */
4715 population *pop=NULL; /* Current population. */
4716 boolean complete=FALSE; /* Whether evolution is terminated. */
4717 int max_threads=0; /* Maximum number of threads to use at one time. */
4718 char *max_thread_str; /* Value of enviroment variable. */
4719 threaddata_t *threaddata; /* Used for passing data to threads. */
4720 int i; /* Loop over threaddata elements. */
4721
4722 /* Checks. */
4723 if (!pops)
4724 die("NULL pointer to array of population structures passed.");
4725 if (num_pops<2)
4726 die("Need at least two populations for the current_island model.");
4727
4728 for (current_island=0; current_island<num_pops; current_island++)
4729 {
4730 pop = pops[current_island];
4731
4732 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
4733 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
4734 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
4735 if (!pop->mutate) die("Population's mutation callback is undefined.");
4736 if (!pop->crossover) die("Population's crossover callback is undefined.");
4737 if (!pop->rank) die("Population's ranking callback is undefined.");
4738 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
4739
4740 /* Set current_island property. */
4741 pop->island = current_island;
4742 }
4743
4744 plog(LOG_VERBOSE, "The evolution has begun on %d islands!", num_pops);
4745
4746 /*
4747 * Look at environment to find number of threads to use.
4748 */
4749 max_thread_str = getenv(GA_NUM_THREADS_ENVVAR_STRING);
4750 if (max_thread_str) max_threads = atoi(max_thread_str);
4751 if (max_threads == 0) max_threads = GA_DEFAULT_NUM_THREADS;
4752
4753 plog(LOG_VERBOSE, "During evolution upto %d threads will be created", max_threads);
4754
4755 /*
4756 * Allocate memory required for handling the threads.
4757 */
4758 threaddata = s_malloc(sizeof(threaddata_t)*max_threads);
4759 pop->generation = 0;
4760
4761 for (current_island=0; current_island<num_pops; current_island++)
4762 {
4763 pop = pops[current_island];
4764
4765 for (i=0; i<max_threads; i++)
4766 threaddata[i].pop = pop;
4767
4768 /*
4769 * Score and sort the initial population members.
4770 */
4771 if (pop->size < pop->stable_size)
4772 gaul_population_fill(pop, pop->stable_size - pop->size);
4773 gaul_ensure_evaluations_threaded(pop, max_threads, threaddata);
4774 sort_population(pop);
4775 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
4776
4777 plog( LOG_VERBOSE,
4778 "Prior to the first generation, population on current_island %d has fitness scores between %f and %f",
4779 current_island,
4780 pop->entity_iarray[0]->fitness,
4781 pop->entity_iarray[pop->size-1]->fitness );
4782 }
4783
4784 /* Do all the generations: */
4785 while ( generation<max_generations && complete==FALSE)
4786 {
4787 generation++;
4788 pop->generation = generation;
4789
4790 /*
4791 * Migration step.
4792 */
4793 gaul_migration(num_pops, pops);
4794
4795 for(current_island=0; current_island<num_pops; current_island++)
4796 {
4797 pop = pops[current_island];
4798
4799 plog( LOG_VERBOSE, "*** Evolution on current_island %d ***", current_island );
4800
4801 for (i=0; i<max_threads; i++)
4802 threaddata[i].pop = pop;
4803
4804 if (pop->generation_hook?pop->generation_hook(generation, pop):TRUE)
4805 {
4806 pop->orig_size = pop->size;
4807
4808 plog( LOG_DEBUG,
4809 "Population %d size is %d at start of generation %d",
4810 current_island, pop->orig_size, generation );
4811
4812 /*
4813 * Crossover step.
4814 */
4815 gaul_crossover(pop); /* FIXME: Need to pass current_island for messages. */
4816
4817 /*
4818 * Mutation step.
4819 */
4820 gaul_mutation(pop); /* FIXME: Need to pass current_island for messages. */
4821
4822 /*
4823 * Apply environmental adaptations, score entities, sort entities, etc.
4824 */
4825 gaul_adapt_and_evaluate_threaded(pop, max_threads, threaddata);
4826
4827 /*
4828 * Survival of the fittest.
4829 */
4830 gaul_survival_threaded(pop, max_threads, threaddata);
4831
4832 }
4833 else
4834 {
4835 complete = TRUE;
4836 }
4837 }
4838
4839 plog(LOG_VERBOSE,
4840 "After generation %d, population %d has fitness scores between %f and %f",
4841 generation,
4842 current_island,
4843 pop->entity_iarray[0]->fitness,
4844 pop->entity_iarray[pop->size-1]->fitness );
4845
4846 } /* Generation loop. */
4847
4848 /* Free memory used for storing thread information. */
4849 s_free(threaddata);
4850
4851 return generation;
4852 }
4853 #else
ga_evolution_archipelago_threaded(const int num_pops,population ** pops,const int max_generations)4854 int ga_evolution_archipelago_threaded( const int num_pops,
4855 population **pops,
4856 const int max_generations )
4857 {
4858 die("Support for ga_evolution_archipelago_threaded() not compiled.");
4859 return 0;
4860 }
4861 #endif
4862
4863
4864 /**********************************************************************
4865 ga_evolution_archipelago_forked()
4866 synopsis: Main genetic algorithm routine. Performs GA-based
4867 optimisation on the given populations using a simple
4868 current_island model. Migration occurs around a cyclic
4869 topology only. Migration causes a duplication of the
4870 respective entities. This is a generation-based GA.
4871 ga_genesis(), or equivalent, must be called prior to
4872 this function.
4873 This is a multiprocess version, using a forked process
4874 for each current_island.
4875 parameters: const int num_pops
4876 population **pops
4877 const int max_generations
4878 return: number of generation performed
4879 last updated: 17 Feb 2005
4880 **********************************************************************/
4881
4882 #if W32_CRIPPLED != 1
ga_evolution_archipelago_forked(const int num_pops,population ** pops,const int max_generations)4883 int ga_evolution_archipelago_forked( const int num_pops,
4884 population **pops,
4885 const int max_generations )
4886 {
4887 int generation=0; /* Current generation number. */
4888
4889 plog(LOG_FIXME, "Code incomplete.");
4890
4891 #if 0
4892 int current_island; /* Current current_island number. */
4893 population *pop=NULL; /* Current population. */
4894 boolean complete=FALSE; /* Whether evolution is terminated. */
4895 int i; /* Loop over members of population. */
4896 int *evalpipe; /* Pipes for returning fitnesses. */
4897 pid_t *pid; /* Child PIDs. */
4898 int *eid; /* Entity which forked process is evaluating. */
4899 int fork_num; /* Index of current forked process. */
4900 int num_forks; /* Number of forked processes. */
4901 int eval_num; /* Index of current entity. */
4902 pid_t fpid; /* PID of completed child process. */
4903
4904 /* Checks. */
4905 if (!pops)
4906 die("NULL pointer to array of population structures passed.");
4907 if (num_pops<2)
4908 die("Need at least two populations for the current_island model.");
4909
4910 pop->generation = 0;
4911
4912 for (current_island=0; current_island<num_pops; current_island++)
4913 {
4914 pop = pops[current_island];
4915
4916 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
4917 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
4918 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
4919 if (!pop->mutate) die("Population's mutation callback is undefined.");
4920 if (!pop->crossover) die("Population's crossover callback is undefined.");
4921 if (!pop->rank) die("Population's ranking callback is undefined.");
4922 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
4923
4924 /* Set current_island property. */
4925 pop->island = current_island;
4926 }
4927
4928 plog(LOG_VERBOSE, "The evolution has begun on %d islands!", num_pops);
4929
4930 /*
4931 * Allocate memory.
4932 * Open pipes for reporting fitnesses.
4933 * Clear pid and eid arrays.
4934 */
4935 pid = s_malloc(max_processes*sizeof(pid_t));
4936 eid = s_malloc(max_processes*sizeof(int));
4937 evalpipe = s_malloc(2*max_processes*sizeof(int));
4938 for (i=0; i<max_processes; i++)
4939 {
4940 if (pipe(&evalpipe[2*i])==-1) die("Unable to open pipe");
4941 pid[i] = -1;
4942 eid[i] = -1;
4943 }
4944
4945 for (current_island=0; current_island<num_pops; current_island++)
4946 {
4947 pop = pops[current_island];
4948
4949 if (pid[fork_num] < 0)
4950 { /* Error in fork. */
4951 dief("Error %d in fork. (%s)", errno, errno==EAGAIN?"EAGAIN":errno==ENOMEM?"ENOMEM":"unknown");
4952 }
4953 else if (pid[fork_num] == 0)
4954 { /* This is the child process. */
4955
4956 /*
4957 * Score and sort the initial population members.
4958 */
4959 if (pop->size < pop->stable_size)
4960 gaul_population_fill(pop, pop->stable_size - pop->size);
4961 gaul_ensure_evaluations(pop);
4962 sort_population(pop);
4963 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
4964
4965 plog( LOG_VERBOSE,
4966 "Prior to the first generation, population on current_island %d has fitness scores between %f and %f",
4967 current_island,
4968 pop->entity_iarray[0]->fitness,
4969 pop->entity_iarray[pop->size-1]->fitness );
4970 }
4971
4972 /* Do all the generations: */
4973 while ( generation<max_generations && complete==FALSE)
4974 {
4975 generation++;
4976 pop->generation = generation;
4977
4978 /*
4979 * Migration and synchronisation step.
4980 */
4981 FIXME.
4982
4983 plog( LOG_VERBOSE, "*** Evolution on current_island %d ***", current_island );
4984
4985 if ( pop->generation_hook?pop->generation_hook(generation, pop):TRUE &&
4986 complete == FALSE )
4987 {
4988 pop->orig_size = pop->size;
4989
4990 plog( LOG_DEBUG,
4991 "Population %d size is %d at start of generation %d",
4992 current_island, pop->orig_size, generation );
4993
4994 /*
4995 * Crossover step.
4996 */
4997 gaul_crossover(pop); /* FIXME: Need to pass current_island for messages. */
4998
4999 /*
5000 * Mutation step.
5001 */
5002 gaul_mutation(pop); /* FIXME: Need to pass current_island for messages. */
5003
5004 /*
5005 * Apply environmental adaptations, score entities, sort entities, etc.
5006 */
5007 gaul_adapt_and_evaluate(pop);
5008
5009 /*
5010 * Survival of the fittest.
5011 */
5012 gaul_survival(pop);
5013
5014 }
5015 else
5016 {
5017 complete = TRUE;
5018 }
5019
5020 plog(LOG_VERBOSE,
5021 "After generation %d, population %d has fitness scores between %f and %f",
5022 generation,
5023 current_island,
5024 pop->entity_iarray[0]->fitness,
5025 pop->entity_iarray[pop->size-1]->fitness );
5026
5027 } /* Generation loop. */
5028
5029 _exit((int) complete);
5030 }
5031
5032 /*
5033 * Parent waits for children.
5034 * Synchronise children at the beginning of each generation, and
5035 * tell them to die if necessary.
5036 */
5037 FIXME.
5038
5039 /*
5040 * Collate final entities.
5041 */
5042 FIXME.
5043
5044 /*
5045 * Close the pipes and free memory.
5046 */
5047 for (i=0; i<max_processes; i++)
5048 {
5049 close(evalpipe[2*i]);
5050 close(evalpipe[2*i+1]);
5051 }
5052
5053 s_free(pid);
5054 s_free(eid);
5055 s_free(evalpipe);
5056 #endif
5057
5058 return generation;
5059 }
5060 #else
ga_evolution_archipelago_forked(const int num_pops,population ** pops,const int max_generations)5061 int ga_evolution_archipelago_forked( const int num_pops,
5062 population **pops,
5063 const int max_generations )
5064 {
5065 die("Sorry, the ga_evolution_archipelago_forked() function isn't available for Windows.");
5066 return 0;
5067 }
5068 #endif
5069
5070
5071 /**********************************************************************
5072 ga_evolution_archipelago_mp()
5073 synopsis: Main genetic algorithm routine. Performs GA-based
5074 optimisation on the given populations using a simple
5075 current_island model. Migration occurs around a cyclic
5076 topology only. Migration causes a duplication of the
5077 respective entities. This is a generation-based GA.
5078 This is a multi-processor version with uses one
5079 processor for one or more current_islands. Note that the
5080 populations must be pre-distributed. The number of
5081 populations on each processor and the properties (e.g.
5082 size) of those populations need not be equal - but be
5083 careful of load-balancing issues in this case. Safe
5084 to call (but slightly inefficient) in single processor
5085 case.
5086 ga_genesis(), or equivalent, must be called prior to
5087 this function.
5088 parameters: const int num_pops
5089 population **pops
5090 const int max_generations
5091 return: number of generation performed
5092 last updated: 11 Jun 2002
5093 **********************************************************************/
5094
ga_evolution_archipelago_mp(const int num_pops,population ** pops,const int max_generations)5095 int ga_evolution_archipelago_mp( const int num_pops,
5096 population **pops,
5097 const int max_generations )
5098 {
5099 #if HAVE_MPI == 1
5100 int generation=0; /* Current generation number. */
5101 int current_island; /* Current current_island number. */
5102 int i; /* Loop over members of population. */
5103 population *pop=NULL; /* Current population. */
5104 boolean complete=FALSE; /* Whether evolution is terminated. */
5105 int pop0_osize; /* Required for correct migration. */
5106 boolean *send_mask; /* Whether particular entities need to be sent. */
5107 int send_count; /* Number of entities to send. */
5108 int max_size=0; /* Largest maximum size of populations. */
5109
5110 /* Checks. */
5111 if (!pops)
5112 die("NULL pointer to array of population structures passed.");
5113
5114 for (current_island=0; current_island<num_pops; current_island++)
5115 {
5116 pop = pops[current_island];
5117
5118 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
5119 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
5120 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
5121 if (!pop->mutate) die("Population's mutation callback is undefined.");
5122 if (!pop->crossover) die("Population's crossover callback is undefined.");
5123 if (!pop->rank) die("Population's ranking callback is undefined.");
5124 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
5125
5126 /* Set current_island property. */
5127 pop->island = current_island;
5128 }
5129
5130 plog(LOG_VERBOSE, "The evolution has begun on %d current_islands on node %d!", num_pops, mpi_get_rank());
5131
5132 mpi_init();
5133
5134 for (current_island=0; current_island<num_pops; current_island++)
5135 {
5136 pop = pops[current_island];
5137
5138 /*
5139 * Score and sort the initial population members.
5140 */
5141 if (pop->size < pop->stable_size)
5142 gaul_population_fill(pop, pop->stable_size - pop->size);
5143 gaul_ensure_evaluations(pop);
5144 sort_population(pop);
5145 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
5146
5147 plog( LOG_VERBOSE,
5148 "Prior to the first generation, population on current_island %d (process %d) has fitness scores between %f and %f",
5149 current_island, mpi_get_rank(),
5150 pop->entity_iarray[0]->fitness,
5151 pop->entity_iarray[pop->size-1]->fitness );
5152
5153 max_size = max(max_size, pop->max_size);
5154 }
5155
5156 /* Allocate send_mask array. */
5157 send_mask = s_malloc(max_size*sizeof(boolean));
5158
5159 /* Do all the generations: */
5160 while ( generation<max_generations && complete==FALSE)
5161 {
5162 generation++;
5163
5164 /*
5165 * Migration Cycle.
5166 * 1) Migration that doesn't require inter-process communication.
5167 * 2) Migration that requires migration from 'even' processes.
5168 * 3) Migration that requires migration from 'odd' processes.
5169 * (Special case due to odd number of nodes is okay)
5170 */
5171 plog( LOG_VERBOSE, "*** Migration Cycle ***" );
5172 pop0_osize = pops[0]->size;
5173 for(current_island=1; current_island<num_pops; current_island++)
5174 {
5175 for(i=0; i<pops[current_island]->size; i++)
5176 {
5177 if (random_boolean_prob(pops[current_island]->migration_ratio))
5178 {
5179 ga_entity_clone(pops[current_island-1], pops[current_island]->entity_iarray[i]);
5180 /* printf("%d, %d: Cloned %d %f\n", mpi_get_rank(), current_island, i, pops[current_island]->entity_iarray[i]->fitness);*/
5181 }
5182 }
5183 }
5184
5185 if (mpi_get_num_processes()<2)
5186 { /* No parallel stuff initialized, or only 1 processor. */
5187 if (num_pops>1)
5188 { /* There is more than one current_island. */
5189 for(i=0; i<pop0_osize; i++)
5190 {
5191 if (random_boolean_prob(pops[0]->migration_ratio))
5192 {
5193 ga_entity_clone(pops[num_pops-1], pops[0]->entity_iarray[i]);
5194 /* printf("%d, %d: Cloned %d %f\n", mpi_get_rank(), 0, i, pops[0]->entity_iarray[i]->fitness);*/
5195 }
5196 }
5197 }
5198 }
5199 else
5200 {
5201 if (ISEVEN(mpi_get_rank()))
5202 { /* Send then Recieve. */
5203 send_count = 0;
5204 for(i=0; i<pop0_osize; i++)
5205 {
5206 send_mask[i] = random_boolean_prob(pops[0]->migration_ratio);
5207 send_count += send_mask[i];
5208 /* if (send_mask[i]) printf("%d, 0: Cloned %d %f\n", mpi_get_rank(), i, pops[num_pops-1]->entity_iarray[i]->fitness);*/
5209 }
5210
5211 ga_population_send_by_mask(pops[0], mpi_get_prev_rank(), send_count, send_mask);
5212
5213 ga_population_append_receive(pops[num_pops-1], mpi_get_next_rank());
5214 }
5215 else
5216 { /* Recieve then Send. */
5217 ga_population_append_receive(pops[num_pops-1], mpi_get_next_rank());
5218
5219 send_count = 0;
5220 for(i=0; i<pop0_osize; i++)
5221 {
5222 send_mask[i] = random_boolean_prob(pops[0]->migration_ratio);
5223 send_count += send_mask[i];
5224 /* if (send_mask[i]) printf("%d, 0: Cloned %d %f\n", mpi_get_rank(), i, pops[num_pops-1]->entity_iarray[i]->fitness);*/
5225 }
5226
5227 ga_population_send_by_mask(pops[0], mpi_get_prev_rank(), send_count, send_mask);
5228 }
5229 }
5230
5231 for(current_island=0; current_island<num_pops; current_island++)
5232 {
5233 pop = pops[current_island];
5234
5235 plog( LOG_VERBOSE, "*** Evolution on current_island %d ***", current_island );
5236
5237 /*
5238 * Sort the individuals in each population.
5239 * Need this to ensure that new immigrants are ranked correctly.
5240 * ga_population_score_and_sort(pop) is needed if scores may change during migration.
5241 */
5242 sort_population(pop);
5243 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
5244
5245 if (pop->generation_hook?pop->generation_hook(generation, pop):TRUE)
5246 {
5247 pop->orig_size = pop->size;
5248
5249 plog( LOG_DEBUG,
5250 "Population %d size is %d at start of generation %d",
5251 current_island, pop->orig_size, generation );
5252
5253 /*
5254 * Crossover step.
5255 */
5256 gaul_crossover(pop); /* FIXME: Need to pass current_island for messages. */
5257
5258 /*
5259 * Mutation step.
5260 */
5261 gaul_mutation(pop); /* FIXME: Need to pass current_island for messages. */
5262
5263 /*
5264 * Apply environmental adaptations, score entities, sort entities, etc.
5265 */
5266 gaul_adapt_and_evaluate(pop);
5267
5268 /*
5269 * Survival of the fittest.
5270 */
5271 gaul_survival(pop);
5272
5273 }
5274 else
5275 {
5276 complete = TRUE;
5277 }
5278 }
5279
5280 plog(LOG_VERBOSE,
5281 "After generation %d, population %d has fitness scores between %f and %f",
5282 generation,
5283 current_island,
5284 pop->entity_iarray[0]->fitness,
5285 pop->entity_iarray[pop->size-1]->fitness );
5286
5287 } /* Generation loop. */
5288
5289 /* Free the send_mask array. */
5290 s_free(send_mask);
5291
5292 return generation;
5293 #else
5294 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
5295
5296 return 0;
5297 #endif
5298 }
5299
5300
5301 /**********************************************************************
5302 ga_evolution_mp()
5303 synopsis: Main genetic algorithm routine. Performs GA-based
5304 optimisation on the given population.
5305 This is a generation-based GA.
5306 ga_genesis(), or equivalent, must be called prior to
5307 this function.
5308 parameters:
5309 return:
5310 last updated: 17 Feb 2005
5311 **********************************************************************/
5312
ga_evolution_mp(population * pop,const int max_generations)5313 int ga_evolution_mp( population *pop,
5314 const int max_generations )
5315 {
5316 #if HAVE_MPI==1
5317 int generation=0; /* Current generation number. */
5318
5319 /* Checks. */
5320 if (!pop) die("NULL pointer to population structure passed.");
5321 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
5322 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
5323 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
5324 if (!pop->mutate) die("Population's mutation callback is undefined.");
5325 if (!pop->crossover) die("Population's crossover callback is undefined.");
5326 if (!pop->rank) die("Population's ranking callback is undefined.");
5327 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
5328
5329 plog(LOG_VERBOSE, "The evolution has begun!");
5330
5331 mpi_init();
5332
5333 pop->generation = 0;
5334
5335 /*
5336 * Rank zero process is master. This handles evolution. Other processes are slaves
5337 * which simply evaluate entities.
5338 */
5339 if (mpi_ismaster())
5340 {
5341
5342 /*
5343 * Score and sort the initial population members.
5344 */
5345 if (pop->size < pop->stable_size)
5346 gaul_population_fill(pop, pop->stable_size - pop->size);
5347 gaul_ensure_evaluations_mp(pop);
5348 sort_population(pop);
5349 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
5350
5351 plog( LOG_VERBOSE,
5352 "Prior to the first generation, population has fitness scores between %f and %f",
5353 pop->entity_iarray[0]->fitness,
5354 pop->entity_iarray[pop->size-1]->fitness );
5355
5356 /*
5357 * Do all the generations:
5358 *
5359 * Stop when (a) max_generations reached, or
5360 * (b) "pop->generation_hook" returns FALSE.
5361 */
5362 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
5363 generation<max_generations )
5364 {
5365 generation++;
5366 pop->generation = generation;
5367 pop->orig_size = pop->size;
5368
5369 plog(LOG_DEBUG,
5370 "Population size is %d at start of generation %d",
5371 pop->orig_size, generation );
5372
5373 /*
5374 * Crossover step.
5375 */
5376 gaul_crossover(pop);
5377
5378 /*
5379 * Mutation step.
5380 */
5381 gaul_mutation(pop);
5382
5383 /*
5384 * Apply environmental adaptations, score entities, sort entities, etc.
5385 */
5386 gaul_adapt_and_evaluate_mp(pop);
5387
5388 /*
5389 * Survival of the fittest.
5390 */
5391 gaul_survival_mp(pop);
5392
5393 /*
5394 * Use callback.
5395 */
5396 plog(LOG_VERBOSE,
5397 "After generation %d, population has fitness scores between %f and %f",
5398 generation,
5399 pop->entity_iarray[0]->fitness,
5400 pop->entity_iarray[pop->size-1]->fitness );
5401
5402 } /* Generation loop. */
5403
5404 /*
5405 * Synchronise the population structures held across the processors.
5406 */
5407 /*gaul_broadcast_population_mp(pop);*/
5408 ga_population_send_every(pop, -1);
5409 }
5410 else
5411 {
5412 gaul_evaluation_slave_mp(pop);
5413 }
5414
5415 return generation;
5416 #else
5417 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
5418
5419 return 0;
5420 #endif
5421 }
5422
5423
5424 /**********************************************************************
5425 ga_evolution_mpi()
5426 synopsis: Main genetic algorithm routine. Performs GA-based
5427 optimisation on the given population.
5428 This is a generation-based GA which utilizes MPI
5429 processes.
5430 parameters:
5431 return:
5432 last updated: 17 Feb 2005
5433 **********************************************************************/
5434
ga_evolution_mpi(population * pop,const int max_generations)5435 int ga_evolution_mpi( population *pop,
5436 const int max_generations )
5437 {
5438 #if HAVE_MPI==1
5439 int generation=0; /* Current generation number. */
5440 int mpi_rank; /* Rank of MPI process; should always by 0 here. */
5441 int mpi_size; /* Number of MPI processes. */
5442 byte *buffer=NULL; /* Send buffer. */
5443 int buffer_len=0; /* Length of send buffer. */
5444 int buffer_max=0; /* Length of send buffer. */
5445 int *eid; /* Sorage of entity ids being processed. */
5446
5447 /* Checks. */
5448 if (!pop) die("NULL pointer to population structure passed.");
5449 if (!pop->evaluate) die("Population's evaluation callback is undefined.");
5450 if (!pop->select_one) die("Population's asexual selection callback is undefined.");
5451 if (!pop->select_two) die("Population's sexual selection callback is undefined.");
5452 if (!pop->mutate) die("Population's mutation callback is undefined.");
5453 if (!pop->crossover) die("Population's crossover callback is undefined.");
5454 if (!pop->rank) die("Population's ranking callback is undefined.");
5455 if (pop->scheme != GA_SCHEME_DARWIN && !pop->adapt) die("Population's adaption callback is undefined.");
5456
5457 /*
5458 * Rank zero process is master. This handles evolution. Other processes are slaves
5459 * which simply evaluate entities, and should be attached using ga_attach_slave().
5460 */
5461 MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank);
5462 if (mpi_rank != 0) die("ga_evolution_mpi() called by process other than rank=0.");
5463
5464 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
5465
5466 plog(LOG_VERBOSE, "The evolution has begun (on %d processors)!", mpi_size);
5467
5468 /*
5469 * Seed initial entities.
5470 * This is required prior to determining the size of the send buffer.
5471 */
5472 if (pop->size < pop->stable_size)
5473 gaul_population_fill(pop, pop->stable_size - pop->size);
5474
5475 /*
5476 * Allocate a send buffer of the required length and an array to store
5477 * entity ids.
5478 */
5479 buffer_len = pop->chromosome_to_bytes(pop, pop->entity_iarray[0], &buffer, &buffer_max);
5480 if (buffer_max == 0)
5481 buffer = s_malloc(buffer_len*sizeof(byte));
5482
5483 eid = s_malloc(mpi_size*sizeof(int));
5484
5485 /*
5486 * Register, set up and synchronise slave processes.
5487 */
5488 gaul_bond_slaves_mpi(pop, buffer_len, buffer_max);
5489
5490 pop->generation = 0;
5491
5492 /*
5493 * Score and sort the initial population members.
5494 */
5495 gaul_ensure_evaluations_mpi(pop, eid, buffer, buffer_len, buffer_max);
5496 sort_population(pop);
5497 ga_genocide_by_fitness(pop, GA_MIN_FITNESS);
5498
5499 plog( LOG_VERBOSE,
5500 "Prior to the first generation, population has fitness scores between %f and %f",
5501 pop->entity_iarray[0]->fitness,
5502 pop->entity_iarray[pop->size-1]->fitness );
5503
5504 /*
5505 * Do all the generations:
5506 *
5507 * Stop when (a) max_generations reached, or
5508 * (b) "pop->generation_hook" returns FALSE.
5509 */
5510 while ( (pop->generation_hook?pop->generation_hook(generation, pop):TRUE) &&
5511 generation<max_generations )
5512 {
5513 generation++;
5514 pop->generation = generation;
5515 pop->orig_size = pop->size;
5516
5517 plog(LOG_DEBUG,
5518 "Population size is %d at start of generation %d",
5519 pop->orig_size, generation );
5520
5521 /*
5522 * Crossover step.
5523 */
5524 gaul_crossover(pop);
5525
5526 /*
5527 * Mutation step.
5528 */
5529 gaul_mutation(pop);
5530
5531 /*
5532 * Apply environmental adaptations, score entities, sort entities, etc.
5533 */
5534 gaul_adapt_and_evaluate_mpi(pop, eid, buffer, buffer_len, buffer_max);
5535
5536 /*
5537 * Survival of the fittest.
5538 */
5539 gaul_survival_mpi(pop);
5540
5541 /*
5542 * Use callback.
5543 */
5544 plog( LOG_VERBOSE,
5545 "After generation %d, population has fitness scores between %f and %f",
5546 generation,
5547 pop->entity_iarray[0]->fitness,
5548 pop->entity_iarray[pop->size-1]->fitness );
5549
5550 } /* Generation loop. */
5551
5552 /*
5553 * Register, set up and synchronise slave processes.
5554 */
5555 gaul_debond_slaves_mpi(pop);
5556
5557 /*
5558 * Deallocate send buffer and entity id array.
5559 */
5560 s_free(buffer);
5561 s_free(eid);
5562
5563 return generation;
5564 #else
5565 plog(LOG_WARNING, "Attempt to use parallel function without compiled support.");
5566
5567 return 0;
5568 #endif
5569 }
5570
5571
5572