~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina6/tina-libs/tina/math/mathNum_genalg.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**********
  2  *
  3  * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
  4  * University of Manchester, UK.  All rights reserved.
  5  *
  6  * Redistribution and use in source and binary forms, with or without modification,
  7  * are permitted provided that the following conditions are met:
  8  *
  9  *   . Redistributions of source code must retain the above copyright notice,
 10  *     this list of conditions and the following disclaimer.
 11  *
 12  *   . Redistributions in binary form must reproduce the above copyright notice,
 13  *     this list of conditions and the following disclaimer in the documentation 
 14  *     and/or other materials provided with the distribution.
 15  *
 16  *   . Neither the name of the University of Manchester nor the names of its
 17  *     contributors may be used to endorse or promote products derived from this
 18  *     software without specific prior written permission.
 19  * 
 20  *
 21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 25  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 31  * POSSIBILITY OF SUCH DAMAGE.
 32  *
 33  **********
 34  *
 35  * Program :    TINA
 36  * File    :
 37  * Date    :
 38  * Version :
 39  * CVS Id  :
 40  *
 41  * Author  :  paul.bromiley@man.ac.uk
 42  *
 43  * Notes : TINA genetic algorithm optimiser.
 44  *
 45  *********
 46 */
 47 /**
 48  *  @file
 49  *  @brief  Multi-objective genetic algorithm code:
 50  *   top level routines. PAB 5 / 9 / 2002. This version
 51  *   has specific alterations for the octants optimisation
 52  *   (in the point generation area).
 53  *
 54  *
 55 */
 56 
 57 #include "mathNum_genalg.h"
 58 
 59 #if HAVE_CONFIG_H
 60 #include <config.h>
 61 #endif
 62 
 63 #include <math.h>
 64 #include <float.h>
 65 #include <time.h>
 66 #include <stdio.h>
 67 #include <stdlib.h>
 68 #include <string.h>
 69 #include <tina/sys/sysDef.h>
 70 #include <tina/sys/sysPro.h>
 71 #include <tina/math/math_NumPro.h>
 72 #include <tina/math/math_UtilPro.h>
 73 
 74 
 75 static int population_size = 0;                 /* The number of soultions in the population */
 76 static int soln_no_points = 0;                  /* The number of points in a solution */
 77 static int dim = 0;                             /* The dimensionality of the space  */
 78 static int no_objectives = 0;                   /* The no of objective functions that will be used */
 79 static int no_mutators = 0;                     /* The number of items in the mutation probabilities vector */
 80 static int no_monitors = 0;                     /* The number of items in the monitor vector */
 81 static double *init_mutation_probs=NULL;        /* Initialisation vector for the mutation probabilities */
 82 static double **space_limits=NULL;              /* The upper and lower limits of each spatial dimension */
 83 static double spatial_acc = 0;                  /* Spatial resoultion rerquired */
 84 
 85 /* Globals for program state and testing */
 86 
 87 static int breeding_flag=0;                     /* 0=crossover, 1=cloning, 2=plauge (replace both parents with randoms  */
 88 static int reattempt_flag=0;                    /* 1 if reattempting cloning after unsuccessful crossover               */
 89 static int patricide_flag=0;                    /* 0=none, 1=on first attempt, 2=on second attempt                      */
 90 static int cost_test_flag=0;
 91 
 92 /* Global pointers to functions: hooks to allow code to be recycled for different problems                              */
 93 
 94 /* static int (*label_assign_func)(double *point); */                                           /* Label assignment function for random points  */
 95 static void (*cost_evaluation_func)(Genome *genome);                                                    /* Manager for objective function calls         */
 96 static void (*selection_manager_func)(List *genome_list, void **breeding_pair);                         /* Selects the breeding pair                    */
 97 static void **(*breeding_manager_func)(void **breeding_pair);                                           /* Crossover function                           */
 98 static void **(*crossover_backend_func)(void **breeding_pair);                                          /* Crossover backend function                   */
 99 static void (*mutation_manager_func)(Genome *genome);                                                   /* Mutation function                            */
100 static void (*constraint_evaluation_func)(void **child_pair);                                           /* Detects invalid ("lethal") children          */
101 static void (*patricide_func)(void **parents, void **children);                                         /* Patricide function                           */
102 static double *(*labelled_point_generator)(void);                                                       /* External random point generator function     */
103 static List *(*labelled_point_list_generator)(void);                                                    /* External labelled point list generator       */
104 static int (*solution_comparator_func)(Genome *genome, List *genome_list);                              /* Compare genome to genomes in list for distance       */
105 static List *(*solution_comparator_2_func)(Genome *genome, List *genome_list);                          /* Compares a genome to genomes in list for cost        */
106 static double (*solution_distance_func)(List *point_list_1, List *point_list_2);                        /* Relative dist between pointlists             */
107 static double (*solution_dotp_func)(List *point_1, List *point_2, List *point_3);                       /* Dot product of vectors 1->2 and 1->3         */
108 static void (*mon_func)(List *genome_list, List *es_list);                                              /* Hook for external population monitor func    */
109 static List *(*es_manager_func)(void **breeding_pair,  List *genome_list, List *extracted_set_list);    /* Manages entry into the extracted set         */
110 static void (*backup_func)(List *pop_list, List *es_list, int algorithm_time);                          /* Hook for external backup function            */
111 
112 /* Globals associated with the extracted set and with timing */
113 
114 static int current_extracted_set_length = 0;    /* Current no of elements in the extracted set list                     */
115 static int max_extracted_set_length = 0;        /* Max no of elements allowed in the extracted set list                 */
116 static int extraction_age = 0;                  /* No. of breeding cycles before a genome is extracted                  */
117 static int alg_time=0;                          /* The time, in cycles, since the start of the algorithm                */
118 static int backup_freq=0;                       /* Time in cycles between calls of the backup function                  */
119 static int init_alg_time=0;                     /* Time offset for alg time                                             */
120 
121 
122 /* Globals for file input/output */
123 
124 static char *input_pathname=NULL, *output_pathname=NULL, *backup_pathname=NULL;
125 
126 
127 double pab_rand(void)
128 {
129         /* Returns a double precision random number between 0 and 1 but not exactly 1 */
130 
131         return rand_unif(0.0, 1.0);
132 }
133 
134 
135 /* Note: there is a danger in sloppy use of the random generator functions: you must ensure that each random solution   */
136 /* has a full set of labels, otherwise the crossover function will not work                                             */
137 
138 
139 void genome_header_copy(Genome *parent, Genome *child)
140 {
141         /* Copy the part of the genome which is not the point list from the parent to the child                         */
142         /* Note that this does not copy certain critical fields, such as the search direction, which are undefined at   */
143         /* this stage                                                                                                   */
144 
145         int i, *search_direction=NULL;
146         double *parent_mut_vec = NULL, *child_mut_vec=NULL, *cost_vec=NULL;
147 
148         child->no_points = parent->no_points;
149         child->age = 0;
150         child->extraction_point = 0;
151 
152         parent_mut_vec = (double *)parent->mutation_prob_vector;
153         child_mut_vec = dvector_alloc(0, no_mutators);
154         for(i=0; i<no_mutators; i++)
155         {
156                 child_mut_vec[i] = parent_mut_vec[i];
157         }
158         child->mutation_prob_vector = child_mut_vec;
159 
160         cost_vec = dvector_alloc(0, no_objectives);
161         search_direction = ivector_alloc(0, no_objectives);
162         for(i=0; i<no_objectives; i++)
163         {
164                 cost_vec[i] = 0.0;
165                 search_direction[i] = 0;
166         }
167         child->cost_vec = cost_vec;
168         child->search_direction=search_direction;
169 
170         child->monitor_vector = ivector_alloc(0, no_monitors);
171         for(i=0; i<no_monitors; i++)
172         {
173                 child->monitor_vector[i] = 0;
174         }
175 }
176 
177 
178 void closest_genome_header_init(Genome *genome, List *genome_list)
179 {
180         /* Initialise the header of a new genome with the header information from the closest genome in the population  */
181 
182         Genome *list_genome=NULL, *min_genome=NULL;
183         List *point_list_1=NULL, *point_list_2=NULL, *plist=NULL;
184         double dist=0, min_dist=FLT_MAX;
185 
186         point_list_1 = genome->point_list;
187         for(plist = genome_list; plist!=NULL; plist=plist->next)
188         {
189                 list_genome = (Genome *)plist->to;
190                 point_list_2 = (List *)list_genome->point_list;
191                 dist = solution_distance_func(point_list_1, point_list_2);
192                 if(dist<min_dist)
193                 {       
194                         min_genome = list_genome;
195                         min_dist = dist;
196                 }       
197         }
198         genome_header_copy(min_genome, genome);
199 }
200 
201 
202 void genome_header_generator(Genome *genome, int no_points, List *genome_list)
203 {
204         /* Alloc a genome and fill the fields which are not the point list: common to both genome generator functions   */
205         /* The point list must be generated first if the headers are to be filled with those of the nearest genome in   */
206         /* the population. The nearest genome header information will only be used if genome_list is not NULL           */
207         
208         int i;
209 
210         genome->no_points = no_points; 
211         genome->age = 0;
212         genome->parent_age = 0;
213         genome->extraction_point=0;
214         genome->mutation_prob_vector = dvector_alloc(0, no_mutators);
215 
216         /* Multiple possibilities for header assignment: random, initialised, or copy of closest genome                 */
217         
218         if(alg_time!=init_alg_time&&genome_list!=NULL)
219         {
220                 closest_genome_header_init(genome, genome_list);
221         }
222         else
223         {
224                 for(i=0; i<no_mutators; i++)
225                 {
226                         genome->mutation_prob_vector[i] = init_mutation_probs[i];
227                         /* genome->mutation_prob_vector[i] = pab_rand(); */
228                 }
229         }
230 
231         genome->cost_vec = dvector_alloc(0, no_objectives);
232         genome->search_direction = ivector_alloc(0, no_objectives);     
233         
234         for(i=0; i<no_objectives; i++)
235         {       
236                 genome->cost_vec[i] = 0;
237                 genome->search_direction[i]=0;
238         }
239 
240         genome->monitor_vector = ivector_alloc(0, no_monitors);
241         for(i=0; i<no_monitors; i++)
242         {
243                 genome->monitor_vector[i] = 0;
244         }
245 }
246 
247 
248 Genome *labelled_solution_generator(int no_points, List *genome_list)
249 {
250         /* Generates a genome such that the points have a full
251            set of labels, as needed by the crossover routine */
252 
253         Genome *genome=NULL;
254 
255         genome = talloc(Genome);
256         genome->point_list = labelled_point_list_generator();
257         genome_header_generator(genome, no_points, genome_list);
258         cost_evaluation_func(genome);
259 
260         return genome;
261 }
262 
263 
264 List *labelled_population_generator(int no_genomes, int no_points)
265 {
266         /* Generates an entire random population of no_genomes genomes, each having                                     */
267         /* no_points points                                                                                             */
268 
269         List *genome_list=NULL;
270         Genome *genome=NULL;
271         int i;
272         
273         for(i=0; i<no_genomes; i++)
274         {
275                 genome = labelled_solution_generator(no_points, NULL);
276                 genome_list = link_addtostart(genome_list, link_alloc(genome, 1002));
277         }
278         return genome_list;
279 }
280 
281 
282 Genome *genome_copy(Genome *genome)
283 {
284         /* Copy function for the genome: assign a new genome, copy in the old genome and return the new one             */
285 
286         Genome *new_genome = NULL;
287         int i, *search_direction=NULL, *new_search_direction=NULL;
288         double *mut_vec = NULL, *new_mut_vec = NULL, *cost_vec=NULL, *new_cost_vec=NULL;
289         double *point=NULL, *new_point=NULL;
290         Match *nptr=NULL, *new_nptr=NULL;
291         List *plist = NULL, *new_point_list = NULL;
292 
293         new_genome = talloc(Genome);
294 
295         /* Copy the header */
296 
297         new_genome->no_points = genome->no_points;
298         new_genome->age = genome->age;
299         new_genome->extraction_point = 0;
300 
301         mut_vec = (double *)genome->mutation_prob_vector;
302         new_mut_vec = dvector_alloc(0, no_mutators);
303         for(i=0; i<no_mutators; i++)
304         {
305                 new_mut_vec[i] = mut_vec[i];
306         }
307         new_genome->mutation_prob_vector = new_mut_vec;
308         
309         search_direction = (int *)genome->search_direction;
310         cost_vec = (double *)genome->cost_vec;
311         new_cost_vec = dvector_alloc(0, no_objectives);
312         new_search_direction = ivector_alloc(0, no_objectives);
313         for(i=0; i<no_objectives; i++)
314         {
315                 new_cost_vec[i] = cost_vec[i];
316                 new_search_direction[i] = search_direction[i];
317         }
318         new_genome->cost_vec = new_cost_vec;
319         new_genome->search_direction = new_search_direction;
320 
321         new_genome->monitor_vector = ivector_alloc(0, no_monitors);
322         for(i=0; i<no_monitors; i++)
323         {
324                 new_genome->monitor_vector[i] = genome->monitor_vector[i];
325         }
326 
327 
328         /* Copy the point list */
329 
330         for(plist=genome->point_list; plist!=NULL; plist=plist->next)
331         {
332                 nptr = (Match *)plist->to;
333                 point = (double *)nptr->to1;
334                 new_point = dvector_alloc(0, (dim+1));
335                 new_nptr = match_alloc(1001);
336         
337                 for(i=0; i<(dim+1); i++)
338                 {
339                         new_point[i] = point[i];
340                 }
341                 
342                 new_nptr->to1 = new_point;
343                 new_nptr->to2 = fvector_alloc(0, 2);
344                 new_nptr->weight = 0.0;
345                 new_point_list = list_addtoend(new_point_list, link_alloc(new_nptr, 1002));
346         }
347         new_genome->point_list = new_point_list;
348         return new_genome;
349 }
350 
351 
352 Genome *genome_free(Genome *genome)
353 {
354         /* Free function for the genome structure: this assumes that the to1 and to2 pointers in each match structure   */
355         /* in the points list will point only to fvectors                                                               */
356 
357         List *plist=NULL, *next=NULL;
358         Match *nptr=NULL;
359         double *point=NULL, *costs=NULL, *mutators = NULL;
360         float *weights=NULL;
361         int *search_direction=NULL, *monitor_vector = NULL;
362 
363         for(plist=genome->point_list; plist!=NULL; plist=next)
364         {
365                 next = plist->next;
366                 nptr = (Match *)plist->to;
367                 point = (double *)nptr->to1;
368                 weights = (float *)nptr->to2;
369                 if(point!=NULL) 
370                 {
371                         dvector_free(point, 0);
372                         point=NULL;
373                         nptr->to1=NULL;
374                 }
375                 if(weights!=NULL) 
376                 {
377                         fvector_free(weights, 0);
378                         weights=NULL;
379                         nptr->to2=NULL;
380                 }
381                 match_free(nptr);
382                 rfree((void *)plist);
383         }       
384 
385         costs = (double *)genome->cost_vec;
386         mutators = (double *)genome->mutation_prob_vector;
387         search_direction = (int *)genome->search_direction;
388         monitor_vector = (int *)genome->monitor_vector;
389         dvector_free(costs, 0);
390         dvector_free(mutators, 0);
391         ivector_free(search_direction, 0);
392         ivector_free(monitor_vector, 0);
393         rfree((void *) genome); 
394 
395         return NULL;
396 }
397 
398 
399 List *genome_list_free(List *genome_list)
400 {
401         /* Free function to free a list of genome structures, such as the population list, the                          */
402         /* extracted set list etc.                                                                                      */
403 
404         List *plist = NULL;
405 
406         for(plist = genome_list; plist!=NULL; plist=plist->next)
407         {
408                 plist->to = genome_free((Genome *)plist->to);
409         }
410 
411         plist = genome_list;
412 
413         while(plist!=NULL) plist = link_rm_el(plist);
414 
415         return NULL;
416 }
417 
418 
419 void genome_backup(List *genome_list)
420 {
421         /* Top level genome list backup writer */
422 
423         FILE *f_back_ptr=NULL;
424 
425         if ((f_back_ptr=fopen(backup_pathname, "w"))==NULL)
426         {
427                 error("Cannot open backup file", warning);
428                 return;
429         }
430 
431         init_io_coords(dim, no_objectives, no_mutators, no_monitors);
432         genome_list_writer(genome_list, f_back_ptr);
433         fclose(f_back_ptr);
434 }
435 
436 
437 void genome_output(List *genome_list)
438 {
439         /* Top level genome_list_writer                                                                                 */
440 
441         FILE *f_out_ptr=NULL;
442 
443         if ((f_out_ptr=fopen(output_pathname, "w"))==NULL)
444         {
445                 error("Cannot open output file", warning);
446                 return;
447         }
448 
449         init_io_coords(dim, no_objectives, no_mutators, no_monitors);
450         genome_list_writer(genome_list, f_out_ptr);
451         fclose(f_out_ptr);
452 }
453 
454 
455 List *genome_input(void)
456 {
457         /* Top level genome_list_reader                                                                                 */
458 
459         FILE *f_in_ptr=NULL;
460         List *genome_list=NULL;
461 
462         if ((f_in_ptr=fopen(input_pathname, "r"))==NULL)
463         {
464                 error("Cannot open input file", warning);
465                 return NULL;
466         }
467 
468         init_io_coords(dim, no_objectives, no_mutators, no_monitors);
469         genome_list = genome_list_reader(genome_list, f_in_ptr);
470         fclose(f_in_ptr);
471         return genome_list;
472 }
473 
474 
475 List *random_list_select(List *list)
476 {
477         /* Randomly select a genome from the genome list */
478 
479         List *plist=NULL;
480         int i, int_rand_no, length_of_list=0;
481 
482         for(plist = list; plist!=NULL; plist=plist->next)
483         {
484                 length_of_list++;
485         }
486 
487         int_rand_no = (int)(length_of_list*pab_rand());
488 
489         plist = list;
490         for(i=0; i<int_rand_no; i++)
491         {
492                 plist = plist->next;
493         }
494         return plist;
495 }
496 
497 
498 void selection_manager_listsort(List *genome_list, void **breeding_pair)
499 {
500         /* Randomly select a genome, then randomly select one of the closest
501         n for breeding */
502 
503         Genome *genome_1=NULL, *genome_2=NULL;
504         void **min_genome;
505         List *plist_1 = NULL, *point_list_1=NULL, *point_list_2=NULL, *plist_2=NULL;
506         Match *nptr=NULL, *lptr=NULL;
507         double dist=0, neighbour_dist=FLT_MAX;
508         int neighbours, i;
509         
510         neighbours=12;
511         min_genome = pvector_alloc(0, neighbours);
512 
513         plist_1 = random_list_select(genome_list);
514         genome_1 = (Genome *)plist_1->to;
515         point_list_1 = genome_1->point_list;
516 
517         for(plist_2 = genome_list; plist_2 !=NULL; plist_2 = plist_2->next)
518         {
519                 genome_2 = (Genome *)plist_2->to;
520                 point_list_2 = genome_2->point_list;
521                 dist = solution_distance_func(point_list_1, point_list_2);
522 
523                 if (dist < neighbour_dist)
524                 {
525                         nptr = NULL;
526                         nptr = match_alloc(1001); 
527                         nptr->to1 = plist_2;
528                         nptr->weight = dist;
529                         for (i=0; i<neighbours; i++)
530                         {
531                                 lptr = (Match *)min_genome[i];
532                                 if (nptr!=NULL && (lptr ==NULL || dist < lptr->weight))
533                                 {
534                                         min_genome[i] = (void *)nptr;
535                                         if ((nptr!=NULL)&&(i==neighbours-1))
536                                                 neighbour_dist = nptr->weight;
537                                         nptr = lptr;
538                                 }
539                         }
540                         if (nptr!=NULL) rfree(nptr);
541                 }
542         }
543 
544         nptr = (Match *)min_genome[((int)(pab_rand()*neighbours))];
545         plist_2 = (List *)nptr->to1;
546         
547         for (i=0; i<neighbours; i++) rfree((void *)(min_genome[i]));
548         pvector_free(min_genome, 0);
549 
550         breeding_pair[0] = (void *)plist_1;
551         breeding_pair[1] = (void *)plist_2;
552 }
553 
554 
555 void selection_manager_voronoid(List *genome_list, void **breeding_pair)
556 {
557         /* Randomly select a genome, then randomly select one of the voronoid
558         neighbours in parameter space for breeding */
559 
560         Genome *genome_1=NULL, *genome_2=NULL, *genome_3=NULL;
561         void **min_genome;
562         List *plist_1 = NULL, *point_list_1=NULL, *point_list_2=NULL;
563         List *plist_2=NULL, *plist_3=NULL, *point_list_3=NULL;
564         double magnitude, dot_product, voronoid_dist;
565         int min_pos=0, int_rand_no, voronoid_flag;
566 
567         min_genome = pvector_alloc(0, population_size);
568 
569         /* Randomly select a genome */
570 
571         plist_1 = random_list_select(genome_list);
572         genome_1 = (Genome *)plist_1->to;
573         point_list_1 = genome_1->point_list;
574 
575         /* Find the neighbouring Voronoid cells */
576 
577         for(plist_2 = genome_list; plist_2!=NULL; plist_2 = plist_2->next)
578         {
579                 if(plist_2!=plist_1)
580                 {
581                         genome_2 = (Genome *)plist_2->to;
582                         point_list_2 = (List *)genome_2->point_list;
583 
584                         voronoid_flag=0;
585                         for(plist_3=genome_list; plist_3!=NULL; plist_3=plist_3->next)
586                         {
587                                 if(plist_3!=plist_2&&plist_3!=plist_1)
588                                 {
589                                         genome_3 = (Genome *)plist_3->to;
590                                         point_list_3 = (List *)genome_3->point_list;
591 
592                                         magnitude = solution_distance_func(point_list_1, point_list_3);
593                                         dot_product = solution_dotp_func(point_list_1, point_list_2, point_list_3);
594                                         voronoid_dist = sqr(magnitude)/dot_product;
595 
596                                         if(voronoid_dist<0.99&&voronoid_dist>0)
597                                         {
598                                                 /* 0.99 instead of 1 to avoid problems when there are two identical points in the space */
599 
600                                                 voronoid_flag=1;
601                                                 break;
602                                         }
603                                 }
604                         }
605                         if(voronoid_flag==0)
606                         {
607                                 min_genome[min_pos] = (void *)plist_2;
608                                 min_pos++;
609                         }
610                 }
611         }
612 
613         /* Randomly select one of the Voronoid neighbours and tidy up */
614 
615         int_rand_no = (int)(pab_rand()*min_pos);
616 
617         plist_2 = (List *)min_genome[int_rand_no];
618         pvector_free(min_genome, 0);
619 
620         /* Test: try adding a little random selection aswell */
621         /*
622         random_no = pab_rand();
623         if(random_no<0.1)
624         {
625                 plist_2 = plist_1;
626                 while(plist_2==plist_1)
627                 {
628                         plist_2 = random_list_select(genome_list);
629                 }
630         }
631         */
632         breeding_pair[0] = (void *)plist_1;
633         breeding_pair[1] = (void *)plist_2;
634 }
635 
636 
637 void selection_manager_random(List *genome_list, void **breeding_pair)
638 {
639 
640         /* Randomly select a pair of genomes from the population for breeding */
641 
642         List *plist=NULL;
643         int i, j, int_rand_no, int_rand_no_old;
644 
645         int_rand_no_old = -1;
646         for(i=0; i<2; i++)
647         {
648                 do
649                 {
650                         int_rand_no = (int)(population_size*pab_rand());
651                 }
652                 while(int_rand_no==int_rand_no_old);
653 
654                 plist = genome_list;
655                 for(j=0; j<int_rand_no; j++)
656                 {
657                         plist = plist->next;
658                 }
659                 breeding_pair[i] = (void *)plist;
660                 int_rand_no_old = int_rand_no;
661         }
662 }
663 
664 
665 void **cloner(void **breeding_pair)
666 {
667         /* Similar to crossover, but allows parents to breed with no crossover, producing clones of themselves for      */
668         /* children.  Don't worry about the later patricide comparison: it was written so that children equal to their  */
669         /* parents still enter the genome, so the path cloning->mutation in header will still result in children that   */
670         /* replace their parents                                                                                        */
671 
672         Genome *child1=NULL, *child2=NULL, *parent1=NULL, *parent2=NULL;
673         List *plist=NULL;
674         void **child_pair=NULL;
675 
676         plist = (List *)breeding_pair[0];
677         parent1 = (Genome *)plist->to;
678         plist = (List *)breeding_pair[1];
679         parent2 = (Genome *)plist->to;
680 
681         child1 = genome_copy(parent1);
682         child2 = genome_copy(parent2);
683 
684         child1->age = 0;
685         child2->age = 0;
686 
687         child_pair = pvector_alloc(0, 2);
688         child_pair[0] = (void *)child1;
689         child_pair[1] = (void *)child2;
690 
691         /* Alter child mutation vector to promote breeding by crossover */
692         /*
693         for(i=0; i<2; i++)
694         {
695                 child = (Genome *)child_pair[i];
696                 mut_vec = (double *)child->mutation_prob_vector;
697                 mut_vec[0] +=mut_vec[4];
698                 if(mut_vec[0]>1) mut_vec[0]=1;
699         }
700         */
701 
702         return child_pair;
703 }
704 
705 
706 Match *point_list_el_copy(Match *point_list_el)
707 {
708         /* Copy one element of the point list of a genome: return the copy */
709 
710         Match *point_copy=NULL;
711         double *point = NULL, *new_point=NULL;
712         int i;
713 
714         point = (double *)point_list_el->to1;
715 
716         point_copy = match_alloc(0);
717         new_point = dvector_alloc(0, (dim+1));
718 
719         for(i=0; i<(dim+1); i++)
720         {
721                 new_point[i] = point[i];
722         }
723 
724         point_copy->to1 = new_point;
725         point_copy->to2 = fvector_alloc(0, 2);
726         point_copy->weight = 0.0;
727 
728         return point_copy;
729 }
730 
731 
732 void **crossover(void **breeding_pair)
733 {
734         /* Take in a pvector of parents, breed, return a pvector of children.                                           */
735         /* Note that the parent pvector points to list elements from the population list (needed                        */
736         /* later at the patricide stage) whereas the child pvector points to the genomes.                               */
737         /* The arguments for the function should be pvectors with two elements each: this                               */
738         /* allows easy looping over the elements in patricide functions                                                 */
739 
740         Match *nptr = NULL, *mptr = NULL;
741         List *plist=NULL, *rlist=NULL;
742         Genome *child1=NULL, *child2=NULL, *parent1=NULL, *parent2=NULL;
743         double rand_no, *point=NULL;
744         float priority;
745         int split_point, i, j, tag_flag=0, child1_index = 0, child2_index = 0;
746         void **child1_temp_vector=NULL, **child2_temp_vector=NULL, **child_pair=NULL;
747 
748         plist = (List *)breeding_pair[0];
749         parent1 = (Genome *)plist->to;
750         plist = (List *)breeding_pair[1];
751         parent2 = (Genome *)plist->to;
752 
753         child1_temp_vector = pvector_alloc(0, (parent1->no_points));
754         child2_temp_vector = pvector_alloc(0, (parent1->no_points));
755 
756         child1 = talloc(Genome);
757         child2 = talloc(Genome);
758         child_pair = pvector_alloc(0, 2);
759         child_pair[0] = (void *)child1;
760         child_pair[1] = (void *)child2;
761 
762         genome_header_copy(parent1, child1);
763         genome_header_copy(parent2, child2);
764 
765         /* Fill the headers of the children, and alter the mutation vector to promote breeding by crossover             */
766         /*
767         for(i=0; i<2; i++)
768         {
769                 child = (Genome *)child_pair[i];
770                 mut_vec = (double *)child->mutation_prob_vector;
771                 mut_vec[0] -=mut_vec[4];
772                 if(mut_vec[0]<0) mut_vec[0]=0;
773         }
774         */
775         /* Find the crossover position and perform crossover                                                            */
776 
777         rand_no = pab_rand();
778         split_point = (int)(rand_no*((float)(parent1->no_points)));
779         if(split_point==0) split_point++;
780 
781         priority = ((float)split_point) / ((float)parent1->no_points);
782         if(priority<0.5) split_point = (parent1->no_points)-split_point;
783 
784         plist = parent1->point_list;
785 
786         for(i=0; i<split_point; i++)
787         {
788                 nptr = (Match *)plist->to;
789                 mptr = point_list_el_copy(nptr);
790                 child1_temp_vector[i] = (void *)(link_alloc(mptr, 1001));
791                 plist = plist->next;
792         }
793         for(i = split_point; i<(parent1->no_points); i++)
794         {
795                 nptr = plist->to;
796                 mptr = point_list_el_copy(nptr);
797                 child2_temp_vector[i] = (void *)(link_alloc(mptr, 1001));
798                 plist = plist->next;
799         }
800         child1_index = split_point;
801         child2_index = 0;
802 
803         /* Assign the points from parent 2 to get a complete set of tags in both children.                              */
804         /* This assumes that the tag values range from 1 to no_points and that both parents                             */
805         /* have the same no_points: any more complex set of tags will need a new version of                             */
806         /* this function                                                                                                */
807 
808         for(i=1; i<(parent1->no_points+1); i++)
809         {
810                 tag_flag=0;
811 
812                 /* Find the point with tag i in parent2                                                                 */
813 
814                 for(plist = (parent2->point_list); plist!=NULL; plist=plist->next)
815                 {
816                         nptr = (Match *)plist->to;
817                         point = (double *)nptr->to1;
818                         if((point[dim])==i) break;
819                 }
820 
821                 /* Find out whether the point with tag i from parent1 is already in child1                              */
822 
823                 for(j=0; j<(parent1->no_points); j++)
824                 {
825                         rlist = (List *)child1_temp_vector[j];
826                         if(rlist!=NULL)
827                         {
828                                 mptr = (Match *)rlist->to;
829                                 point = (double *)mptr->to1;
830                                 if((point[dim])==i) tag_flag=1;
831                         }
832                 }
833 
834                 if(tag_flag==1)
835                 {
836                         /* If child 1 had this point, put parent2's version in child2                                   */
837 
838                         mptr = point_list_el_copy(nptr);
839                         child2_temp_vector[child2_index] = (void *)link_alloc(mptr, 1001);
840                         child2_index++;
841                 }
842                 else
843                 {
844                         /* Else put it in child1                                                                        */
845 
846                         mptr = point_list_el_copy(nptr);
847                         child1_temp_vector[child1_index] = (void *)link_alloc(mptr, 1001);
848                         child1_index++;
849                 }
850         }
851 
852         /* Now the two child_temp_vectors are filled, copy them into the child point_lists                              */
853 
854         for(i=0; i<(parent1->no_points); i++)
855         {
856                 child1->point_list = list_addtoend((child1->point_list), (List *)(child1_temp_vector[i]));
857                 child2->point_list = list_addtoend((child2->point_list), (List *)(child2_temp_vector[i]));
858         }
859         pvector_free(child1_temp_vector, 0);
860         pvector_free(child2_temp_vector, 0);
861         return child_pair;
862 }
863 
864 
865 void **realval_crossover(void **breeding_pair)
866 {
867         /* Take in a pvector of parents, breed, return a pvector of children.                                           */
868         /* Note that the parent pvector points to list elements from the population list (needed                        */
869         /* later at the patricide stage) whereas the child pvector points to the genomes.                               */
870         /* The arguments for the function should be pvectors with two elements each: this                               */
871         /* allows easy looping over the elements in patricide functions                                                 */
872         /* This version is for parents which encode a single real valued point: it puts the children down randomly in   */
873         /* the hypercube defined by the parents                                                                         */
874 
875         Match *nptr=NULL;
876         List *plist=NULL;
877         Genome *child1=NULL, *child2=NULL, *parent1=NULL, *parent2=NULL;
878         double *parent1_point=NULL, *parent2_point=NULL, *child1_point=NULL, *child2_point=NULL;
879         int i;
880         void **child_pair=NULL;
881 
882         if(soln_no_points!=1)
883         {
884                 format("Warning: wrong crossover function\n");
885         }
886 
887         plist = (List *)breeding_pair[0];
888         parent1 = (Genome *)plist->to;
889         plist = (List *)breeding_pair[1];
890         parent2 = (Genome *)plist->to;
891 
892         plist = (List *)parent1->point_list;
893         nptr = (Match *)plist->to;
894         parent1_point = (double *)nptr->to1;
895 
896         plist = (List *)parent2->point_list;
897         nptr = (Match *)plist->to;
898         parent2_point = (double *)nptr->to1;
899 
900         child1 = talloc(Genome);
901         child2 = talloc(Genome);
902         child_pair = pvector_alloc(0, 2);
903         child_pair[0] = (void *)child1;
904         child_pair[1] = (void *)child2;
905 
906         genome_header_copy(parent1, child1);
907         genome_header_copy(parent2, child2);
908 
909         child1_point = dvector_alloc(0, (dim+1));
910         child2_point = dvector_alloc(0, (dim+1));
911 
912         child1_point[dim] = 1;
913         child2_point[dim] = 1;
914 
915         for(i=0; i<dim; i++)
916         {
917                 child1_point[i] = parent1_point[i] + pab_rand()*(parent2_point[i] - parent1_point[i]);
918                 child2_point[i] = parent1_point[i] + pab_rand()*(parent2_point[i] - parent1_point[i]);
919         }
920 
921         nptr = match_alloc(0);
922         nptr->to1 = child1_point;
923         child1->point_list = list_addtoend(((List *)child1->point_list), link_alloc(nptr, 1001));
924 
925         nptr = match_alloc(0);
926         nptr->to1 = child2_point;
927         child2->point_list = list_addtoend(((List *)child2->point_list), link_alloc(nptr, 1001));
928 
929         return child_pair;
930 }
931 
932 
933 void **breeding_manager(void **breeding_pair)
934 {
935         /* Decide whether to crossover or clone the parents */
936 
937         List *plist = NULL;
938         Genome *genome = NULL;
939         double rand_no, *mut_prob = NULL;
940         void **child_pair=NULL;
941 
942         rand_no = pab_rand();
943 
944         plist = (List *)breeding_pair[0];
945         genome = (Genome *)plist->to;
946         mut_prob = (double *)genome->mutation_prob_vector;
947 
948         if(rand_no>(mut_prob[1]))
949         {
950                 child_pair = crossover_backend_func(breeding_pair);
951         }
952         else
953         {
954                 /* If cloning of the parents occurs, mutation of coordinates must also occur */
955 
956                 child_pair = cloner(breeding_pair);
957                 breeding_flag=1;
958         }
959 
960         return child_pair;
961 }
962 
963 
964 void mutation_coordinate(Genome *genome)
965 {
966         List *plist=NULL;
967         Match *nptr;
968         double *point=NULL, *mut_vector=NULL;
969         float point_factor;
970         int no_coords, mut_pos, i, point_no, coord_no;
971 
972         /* Mutate a coordinate                                                                                  */
973 
974         mut_vector = genome->mutation_prob_vector;
975         no_coords = (genome->no_points) * dim;
976         mut_pos = (int)((double)no_coords * pab_rand());
977 
978         point_no = (int)((float)mut_pos / dim);
979         coord_no = mut_pos - (point_no*dim);
980 
981         plist = genome->point_list;
982         for(i=0; i<point_no; i++)
983         {
984                 plist = plist->next;
985         }
986         nptr = (Match *)plist->to;
987         point = (double *)nptr->to1;
988 
989         point_factor = mut_vector[3] * pab_rand() * (space_limits[coord_no][1]-space_limits[coord_no][0]);
990         if((pab_rand())<0.5)
991         {
992                 point[coord_no] -= point_factor;
993                 if(point[coord_no]<space_limits[coord_no][0]) point[coord_no] = space_limits[coord_no][0];
994         }
995         else
996         {
997                 point[coord_no] += point_factor;
998                 if(point[coord_no]>space_limits[coord_no][1]) point[coord_no] = space_limits[coord_no][1];
999         }
1000 }
1001 
1002 
1003 void mutation_header(Genome *genome)
1004 {
1005         double rand_no, *mut_vector=NULL;
1006         int mut_pos;
1007 
1008         /* Mutate a component of the header */
1009 
1010         mut_vector = genome->mutation_prob_vector;
1011         mut_pos = (int)(pab_rand()*no_mutators);
1012         rand_no = pab_rand();
1013         if(rand_no>0.5)
1014         {
1015                 mut_vector[mut_pos] += pab_rand()*mut_vector[4];
1016                 if(mut_vector[mut_pos]>1.0) mut_vector[mut_pos] = 1.0;
1017         }
1018         else
1019         {
1020                 mut_vector[mut_pos] -= pab_rand()*mut_vector[4];
1021                 if(mut_vector[mut_pos]<0.0) mut_vector[mut_pos] = 0.0;
1022         }
1023 }
1024 
1025 
1026 void mutation_manager(Genome *genome)
1027 {
1028         double *mut_vector=NULL;
1029         int *monitor_vector=NULL;
1030 
1031         /* Mutate a genome according to the probabilities held in its mutation probability vector: these are assumed    */
1032         /* to be :      element 0 probability that breeding involves crossover                                          */
1033         /*              element 1 probability of a coordinate mutation                                                  */
1034         /*              element 2 probability of a header mutation                                                      */
1035         /*              element 3 distance by which a coordinate is shifted if mutated                                  */
1036         /*              element 4 distance by which a header is shifted is mutated                                      */
1037         /*                                                                                                              */
1038         /* Things that can mutate: points, elements of mutation vector. Any deviation will require a new version.       */
1039 
1040         /* Caller for the actual mutation functions */
1041 
1042         mut_vector=(double *)genome->mutation_prob_vector;
1043         monitor_vector = (int *)genome->monitor_vector;
1044 
1045         if(pab_rand()<mut_vector[1]||breeding_flag==1)
1046         {
1047                 mutation_coordinate(genome);
1048                 monitor_vector[2] = 1;
1049         }
1050         if(pab_rand()<mut_vector[2])
1051         {
1052                 mutation_header(genome);
1053                 monitor_vector[2] = 2;
1054         }
1055 }
1056 
1057 
1058 void evaluate_constraints(void **child_pair)
1059 {
1060         /* Dummy function: no constraints for my problem, but others may have them      */
1061         /* If a child fails ths constraints for your problem, free it and set the       */ 
1062         /* pointer in the child pair to NULL                                            */
1063 
1064         ;
1065 }
1066 
1067 
1068 List *list_point_rm(List *at, List *list)
1069 {
1070         /* Remove the point "at" from the list "list", and join the list back together  */
1071         /* Do not free any of the list elements                                         */      
1072 
1073         List *last=NULL, *next=NULL;
1074 
1075         last = at->last;
1076         next = at->next;
1077 
1078         if(last==NULL&&next==NULL) return NULL;
1079 
1080         if(last==NULL)
1081         {
1082                 at->next=NULL;
1083                 next->last=NULL;
1084                 list = next;
1085         }
1086         else if(next==NULL)
1087         {
1088                 at->last=NULL;
1089                 last->next=NULL;
1090         }
1091         else
1092         {
1093                 at->last = NULL;
1094                 at->next = NULL;
1095                 last->next = next;
1096                 next->last = last;
1097         }
1098         return list;
1099 }
1100 
1101 
1102 double point_distance_func(double *point1, double *point2)
1103 {
1104         double distance;
1105         int i;
1106 
1107         distance = 0;
1108         for(i=0; i<dim; i++)
1109         {
1110                 distance += sqr( point1[i] - point2[i] );
1111         }
1112 
1113         return sqrt(distance);
1114 }
1115 
1116 
1117 void genome_point_list_sorter(Genome *genome)
1118 {
1119         /* Takes in a genome, looks at the point list, finds the two closest points and makes them adjacent     */
1120         
1121         List *point_list = NULL, *plist = NULL, *rlist = NULL, *min_plist = NULL, *min_rlist = NULL, *new_point_list = NULL;
1122         Match *nptr=NULL;
1123         double *point1 = NULL, *point2 = NULL, distance, min_distance=FLT_MAX;
1124         
1125         point_list = genome->point_list;
1126 
1127         for(plist=point_list; plist!=NULL; plist=plist->next)
1128         {
1129                 for(rlist = point_list; rlist!=NULL; rlist = rlist->next)
1130                 {
1131                         if(plist!=rlist)
1132                         {       
1133                                 nptr = (Match *)plist->to;
1134                                 point1 = (double *)nptr->to1;
1135                                 nptr = (Match *)rlist->to;
1136                                 point2 = (double *)nptr->to1;
1137 
1138                                 distance = point_distance_func(point1, point2);
1139                                 if(distance<min_distance)
1140                                 {
1141                                         min_distance = distance;
1142                                         min_plist = plist;
1143                                         min_rlist = rlist;
1144                                 }
1145                         }
1146                 }
1147         }
1148 
1149         if(min_rlist!=(min_plist->next)&&min_plist!=NULL&&min_rlist!=NULL)
1150         {
1151                 new_point_list = list_point_rm(min_rlist, point_list);
1152                 link_addafter(min_plist, min_rlist);
1153                 genome->point_list = new_point_list;
1154         }
1155 }
1156 
1157 
1158 int patricide_comparator(Genome *parent, Genome *child)
1159 {
1160         /* Compare the cost vectors of the child to the parent: return 1 if the child is better */
1161         /* than the parent on the parents search direciton (if any).                            */
1162 
1163         int i, *search_direction=NULL, search_sum=0, flag;
1164         double *child_cost=NULL, *parent_cost=NULL;
1165 
1166         if(parent==NULL||child==NULL) return 0;
1167 
1168         search_direction = (int *)parent->search_direction;
1169         parent_cost = (double *)parent->cost_vec;
1170         child_cost = (double *)child->cost_vec;
1171 
1172         for(i=0; i<no_objectives; i++)
1173         {
1174                 search_sum +=search_direction[i];
1175         }
1176         
1177         if(search_sum>0)
1178         {
1179                 /* Parent has a defined search direciton: child must improve in this direction 
1180                 and gets a copy of the parent's search direction */
1181 
1182                 flag = 1;
1183 
1184                 for(i=0; i<no_objectives; i++)
1185                 {       
1186                         if( (search_direction[i])!=0 && child_cost[i]>=parent_cost[i])
1187                         {
1188                                 flag=0;
1189                                 break;
1190                         }
1191                 }
1192         }
1193         else
1194         {
1195                 /* Parent had no defined search direction: child can improve in any direction, 
1196                 and gets its search direction set up */
1197 
1198                 flag = 0;
1199         
1200                 for(i=0; i<no_objectives; i++)
1201                 {       
1202                         if(child_cost[i]<parent_cost[i])
1203                         {
1204                                 flag=1;
1205                                 break;
1206                         }
1207                 }
1208         }
1209         return flag;
1210 }
1211 
1212 
1213 void patricide_direction_assign(Genome *parent, Genome *child)
1214 {
1215         /* Fill in the search direction of the child */
1216 
1217         int i, *search_direction=NULL, search_sum=0, *child_search_direction = NULL;
1218         double *child_cost=NULL, *parent_cost=NULL;
1219 
1220         search_direction = (int *)parent->search_direction;
1221         child_search_direction = (int *)child->search_direction;
1222         parent_cost = (double *)parent->cost_vec;
1223         child_cost = (double *)child->cost_vec;
1224 
1225         for(i=0; i<no_objectives; i++)
1226         { 
1227                 search_sum += search_direction[i];
1228         }
1229         
1230         if(search_sum>0)
1231         {
1232                 /* Parent has an assigned serach direction: copy this to the child      */
1233                 for(i=0; i<no_objectives; i++)
1234                 {
1235                         child_search_direction[i] = search_direction[i];
1236                 }
1237         }
1238         else
1239         {
1240                 /* Parent has no assigned search direction: assign new one for child    */
1241                 for(i=0; i<no_objectives; i++)
1242                 {
1243                         if(parent_cost[i]>child_cost[i])
1244                         {
1245                                 child_search_direction[i] = 1;
1246                         }       
1247                         else
1248                         {
1249                                 child_search_direction[i] = 0;
1250                         }
1251                 }
1252         }
1253 }
1254 
1255 
1256 void simple_patricide(void **breeding_pair, void **child_pair)
1257 {
1258         /* The parents and children should have valid cost function results at this stage       */
1259         /* Repalce parents with children on a first come first served basis                     */
1260         /* The arguments for the function should be pvectors with two elements each: this       */
1261         /* allows easy looping over the elements in patricide functions                         */
1262         /* Must be prepared for possibility that one or more children are NULL enetering this   */
1263         /* subroutine, due to failing constraints                                               */
1264 
1265         Genome *parent=NULL, *child=NULL;
1266         List *plist;
1267         int i, j, *monitor_vector=NULL;
1268 
1269         for(i=0; i<2; i++)
1270         {
1271                 plist = (List *)breeding_pair[i];
1272                 parent = (Genome *)plist->to;
1273 
1274                 for(j=0; j<2; j++)
1275                 {
1276                         child = (Genome *)child_pair[j];
1277                         if(parent!=NULL&&child!=NULL)
1278                         {
1279                                 if(patricide_comparator(parent, child)==1)
1280                                 {
1281                                         patricide_flag=1;                               
1282 
1283                                         /* Fill in the child's monitor vector */
1284                                         
1285                                         monitor_vector=child->monitor_vector;
1286                                         monitor_vector[0] = parent->age;
1287                                         monitor_vector[1] = breeding_flag++;
1288                                         monitor_vector[3] = reattempt_flag++;
1289                                         
1290                                         patricide_direction_assign(parent, child);
1291                                         
1292                                         /*****
1293 
1294                                         genome_point_list_sorter(child);
1295 
1296                                         *****/
1297 
1298                                         plist->to = child;
1299                                         genome_free(parent);
1300                                         parent=NULL;
1301                                         child=NULL;
1302                                         child_pair[j]=NULL;
1303                                 }
1304                         }
1305                 }
1306         }
1307 
1308         /* Now free up any remaining children and the pvector                                   */
1309 
1310         for(i=0; i<2; i++)
1311         {
1312                 child = (Genome *)child_pair[i];
1313                 if(child!=NULL)
1314                 {
1315                         genome_free(child);
1316                         child=NULL;
1317                 }
1318         }
1319 }
1320 
1321 
1322 void patricide_manager(void **breeding_pair, void **child_pair)
1323 {
1324         /* This function calls the patricide routine, and then checks whether any of the children       */
1325         /* were successful.  If the children were generated by crossover and neither was successful,    */
1326         /* it tries again with cloning, mutation and a repeat of crossover                              */
1327 
1328         Genome *child=NULL;
1329         int i;
1330 
1331         simple_patricide(breeding_pair, child_pair);
1332         
1333         if(patricide_flag==0&&breeding_flag==0)
1334         {
1335                 /* Crossover has failed to produce good children: have a go at cloning and mutation */
1336 
1337                 pvector_free(child_pair, 0);
1338                 child_pair = cloner(breeding_pair);
1339                 breeding_flag=1;
1340                 reattempt_flag=1;
1341 
1342                 for(i=0; i<2; i++)
1343                 {
1344                         child = (Genome *)child_pair[i];
1345                         mutation_manager(child);
1346                         cost_evaluation_func(child);
1347                 }
1348                 constraint_evaluation_func(child_pair);
1349                 simple_patricide(breeding_pair, child_pair);
1350                 if(patricide_flag==1) patricide_flag=2;
1351         }
1352         
1353         pvector_free(child_pair, 0);
1354 }
1355 
1356 
1357 List *so_extracted_set_manager(void **breeding_pair,  List *genome_list,
1358                                 List *extracted_set_list)
1359 {
1360         /* Subroutine to manage the extraction of the extracted set from the population         */
1361         /* The top level of the genome list must not change: if an individual is extracted, put */
1362         /* a new random genome in that list element.  The extracted set list can change, and    */
1363         /* the pointer to the start of the list is what gets returned                           */
1364         /* This subroutine should handle all aspects of measuring time within the algorithm     */
1365 
1366         Genome *genome = NULL, *list_genome = NULL, *new_genome=NULL;
1367         List *plist = NULL, *rlist=NULL, *qlist=NULL;
1368         int i, j, age, no_points, cost_flag;
1369         double *new_cost_vec = NULL, *list_cost_vec = NULL;
1370         
1371         for(i=0; i<2; i++)
1372         {
1373                 plist = (List *)breeding_pair[i];
1374                 genome = (Genome *)plist->to;
1375                 age = genome->age;
1376 
1377                 if(age<extraction_age)
1378                 {
1379                         (genome->age)++;
1380                 }
1381                 else if((solution_comparator_func(genome, extracted_set_list))==1)
1382                 {
1383                         no_points = genome->no_points;
1384                         new_genome = labelled_solution_generator(no_points, genome_list);
1385                         plist->to = new_genome;
1386                         genome = genome_free(genome);
1387                 }
1388                 else if((qlist=solution_comparator_2_func(genome, extracted_set_list))!=NULL)
1389                 {                                                                                       
1390 
1391                         genome->extraction_point=alg_time;
1392                         new_cost_vec = (double *)genome->cost_vec;
1393                         no_points = genome->no_points;
1394                         new_cost_vec = genome->cost_vec;
1395 
1396                         new_genome = labelled_solution_generator(no_points, genome_list);
1397                         plist->to = new_genome;                 
1398 
1399                         list_genome = (Genome *)qlist->to;
1400                         list_cost_vec = list_genome->cost_vec;
1401 
1402                         if(list_cost_vec[0]>new_cost_vec[0])
1403                         {
1404                                 qlist->to = genome;
1405                                 list_genome = genome_free(list_genome);
1406                         }
1407                         else
1408                         {
1409                                 genome = genome_free(genome);
1410                         }
1411                 }
1412                 else
1413                 {
1414                         genome->extraction_point=alg_time;
1415                         no_points = genome->no_points;
1416                         new_cost_vec = (double *)genome->cost_vec;
1417 
1418                         new_genome = labelled_solution_generator(no_points, genome_list);
1419                         plist->to = new_genome;
1420 
1421                         for(plist = extracted_set_list; plist!=NULL; plist = plist->next)
1422                         {
1423                                 /* Slot the new genome into the list at the point it is non-dominated */
1424 
1425                                 list_genome = (Genome *)plist->to;
1426                                 list_cost_vec = (double *)list_genome->cost_vec;
1427                                 cost_flag=0;
1428 
1429                                 for(j=0; j<no_objectives; j++)
1430                                 {
1431                                         if(list_cost_vec[j]<new_cost_vec[j]) cost_flag++;
1432                                 }
1433                                 if(cost_flag<no_objectives)
1434                                 {
1435                                         plist->to = genome;
1436                                         plist = plist->last;
1437                                         link_addafter(plist, link_alloc(list_genome, 1002));
1438                                         genome = NULL;
1439                                         current_extracted_set_length++;
1440                                         break;
1441                                 }
1442                         }
1443 
1444                         /* At this point one of three things need to be done */
1445 
1446                         if(current_extracted_set_length<max_extracted_set_length&&genome!=NULL)
1447                         {
1448 
1449                                 /* If there is still room and the genome had not yet been added, add it to the end of the list */
1450 
1451                                 extracted_set_list = list_addtoend(extracted_set_list, link_alloc(genome, 1002));
1452                                 current_extracted_set_length++;
1453                         }
1454                         else if(current_extracted_set_length>max_extracted_set_length)
1455                         {
1456 
1457                                 /* If adding the genome has made the list too long, free the last element */
1458 
1459                                 for(plist = extracted_set_list; plist!=NULL; plist=plist->next)
1460                                 {
1461                                         if(plist->next->next==NULL) break;
1462                                 }
1463                                 rlist = plist->next;
1464                                 list_genome = (Genome *)rlist->to;
1465                                 genome_free(list_genome);
1466                                 current_extracted_set_length--;
1467 
1468                                 plist->next = NULL;
1469                                 rfree((void *)rlist);
1470                         }
1471                         else if(genome!=NULL)
1472                         {
1473 
1474                                 /* If you still have the element at this stage, free it */
1475 
1476                                 genome = genome_free(genome);
1477                         }
1478                 }
1479         }
1480 
1481         alg_time++;
1482         return extracted_set_list;
1483 }
1484 
1485 
1486 List *mo_extracted_set_manager(void **breeding_pair,  List *genome_list,
1487                         List *extracted_set_list)
1488 {
1489         /* Subroutine to manage the extraction of the extracted set from the population         */
1490         /* The top level of the genome list must not change: if an individual is extracted, put */
1491         /* a new random genome in that list element.  The extracted set list can change, and    */
1492         /* the pointer to the start of the list is what gets returned                           */
1493         /* This subroutine should handle all aspects of measuring time within the algorithm     */
1494 
1495         Genome *genome = NULL, *list_genome = NULL, *new_genome=NULL;
1496         List *plist = NULL, *rlist=NULL, *next=NULL;
1497         int i, j, age, no_points, cost_flag, add_flag, pareto_flag, objectives_that_count;
1498         double *new_cost_vec = NULL, *list_cost_vec = NULL;
1499 
1500         for(i=0; i<2; i++)
1501         {
1502                 plist = (List *)breeding_pair[i];
1503                 genome = (Genome *)plist->to;
1504                 age = genome->age;
1505 
1506                 if(age<extraction_age)
1507                 {
1508                         (genome->age)++;
1509                 }
1510                 else if((solution_comparator_func(genome, extracted_set_list))==1)
1511                 {
1512                         no_points = genome->no_points;
1513                         new_genome = labelled_solution_generator(no_points, genome_list);
1514                         plist->to = new_genome;
1515                         genome = genome_free(genome);
1516                 }
1517                 else
1518                 {
1519                         genome->extraction_point=alg_time;
1520                         no_points = genome->no_points;
1521                         new_cost_vec = (double *)genome->cost_vec;
1522                         new_genome = labelled_solution_generator(no_points, genome_list);
1523                         plist->to = new_genome;
1524 
1525                         add_flag = 0;
1526                         pareto_flag=1;
1527                         plist=extracted_set_list;
1528 
1529                         while(plist!=NULL)
1530                         {
1531                                 list_genome = (Genome *)plist->to;
1532                                 list_cost_vec = (double *)list_genome->cost_vec;
1533                                 cost_flag=0;
1534                                 next=plist->next;
1535                                 objectives_that_count=no_objectives;
1536 
1537                                 for(j=0; j<no_objectives; j++)
1538                                 {
1539                                         if(list_cost_vec[j]<new_cost_vec[j]) cost_flag++;
1540                                         if(list_cost_vec[j]==new_cost_vec[j]) objectives_that_count--;
1541                                 }
1542                                 if(cost_flag==0)
1543                                 {
1544                                         /* If the new genome dominates one in the list, remove the list one and remember to     */
1545                                         /* add the new one to the list later                                                    */
1546 
1547                                         extracted_set_list = list_point_rm(plist, extracted_set_list);
1548                                         current_extracted_set_length--;
1549                                         list_genome = genome_free(list_genome);
1550                                         rfree((void *)plist);
1551                                         add_flag=1;
1552                                 }       
1553                                 if(cost_flag==objectives_that_count)
1554                                 {
1555                                         /* If the new genome is not dominated by anything in the list, add it. Objectives that count is needed  */
1556                                         /* for very specific test problems e.g. Van Veldhuizen MOP 6, where over part of the space one cost     */
1557                                         /* does not change, so costs are equal over distances larger than the spatial accuracy                  */
1558 
1559                                         pareto_flag=0;
1560                                 }       
1561                                 plist=next;
1562                         }
1563 
1564                         if(extracted_set_list==NULL||add_flag==1||pareto_flag==1)
1565                         {
1566                                 extracted_set_list = list_addtoend(extracted_set_list, link_alloc(genome, 1002));
1567                                 current_extracted_set_length++;
1568                         }
1569                         else if(current_extracted_set_length>max_extracted_set_length)
1570                         {
1571                                 /* If adding the genome has made the list too long, free the last element */
1572 
1573                                 for(plist = extracted_set_list; plist!=NULL; plist=plist->next)
1574                                 {
1575                                         if(plist->next->next==NULL) break;
1576                                 }       
1577                                 rlist = plist->next;
1578                                 list_genome = (Genome *)rlist->to;
1579                                 genome_free(list_genome);
1580                                 current_extracted_set_length--;
1581                 
1582                                 plist->next = NULL;
1583                                 rfree((void *)rlist);
1584                         }
1585                         else if(genome!=NULL)
1586                         {
1587                         
1588                                 /* If you still have the element at this stage, free it */
1589 
1590                                 genome = genome_free(genome);
1591                         }
1592                 }
1593         }
1594 
1595         alg_time++;
1596         return extracted_set_list;
1597 }
1598 
1599 
1600 List *choice_extracted_set_manager(void **breeding_pair, List *genome_list, List *extracted_set_list)
1601 {
1602 
1603         if(no_objectives==1)
1604         {
1605                 extracted_set_list = so_extracted_set_manager(breeding_pair, genome_list, extracted_set_list);
1606         }
1607         else
1608         {
1609                 extracted_set_list = mo_extracted_set_manager(breeding_pair, genome_list, extracted_set_list);
1610         }
1611         return extracted_set_list;
1612 }
1613 
1614 /***** Initialisation functions *****/
1615 
1616 
1617 void ga_init_coords(    int pop_size,                           /* The number of solutions in the population            */
1618                         int no_points,                          /* The number of points in each solution                */
1619                         int dimensionality,                     /* The dimensionality of the space                      */
1620                         int no_objective_functions,             /* The number of objective functions                    */
1621                         int no_mutation_probabilities,          /* The number of elements in the mutation prob vector   */
1622                         double *init_mutation_probabilities,    /* Init version of the mutation prob vector             */
1623                         double **coords_array,                  /* Array of spatial limits for this problem             */
1624                         int max_es_length,                      /* Maximum size of the extracted set                    */
1625                         int ext_age,                            /* No of breeding cycles before extraction              */
1626                         int no_mons,                            /* no of items in the monitor vector                    */
1627                         double spatial_accuracy,                /* Spatial resolution required                          */
1628                         int backup_iterations,                  /* No of iterations between population backups          */
1629                         int initialise_alg_time                 /* Start time offset                                    */
1630                 )
1631 {
1632         /* Init the numeric constants associated with the problem: the dimensionality of the space etc.         */
1633 
1634         population_size = pop_size;
1635         soln_no_points = no_points;
1636         space_limits = coords_array;
1637         dim = dimensionality;
1638         no_mutators = no_mutation_probabilities;
1639         no_objectives = no_objective_functions;
1640         init_mutation_probs = init_mutation_probabilities;
1641         max_extracted_set_length = max_es_length;
1642         extraction_age = ext_age;
1643         no_monitors = no_mons;
1644         spatial_acc = spatial_accuracy;
1645         backup_freq = backup_iterations;
1646         alg_time = initialise_alg_time;
1647         init_alg_time = initialise_alg_time;
1648 }
1649 
1650 
1651 void ga_init_pathnames( char *input_path,       /* The pathname for the input file                                      */
1652                         char *output_path,      /* The pathname for the output file                                     */
1653                         char *backup_path       /* The pathname for the backup file                                     */
1654                    )
1655 {
1656 
1657         /* Init the pathnames for the input, output and backup files                                                    */
1658 
1659         input_pathname = input_path;
1660         backup_pathname = backup_path;
1661         output_pathname = output_path;
1662 }
1663 
1664 
1665 void ga_init_functions( void (*p_cost_evaluation_func)(),               /* manager for objective function calls                                 */
1666                         void (*p_selection_manager_func)(),             /* Function to select the breeding pair                                 */
1667                         void **(*p_breeding_manager_func)(),            /* Breeding manager function                                            */
1668                         void **(*p_crossover_backend_func)(),           /* Crossover backend function                                           */
1669                         void (*p_mutation_manager_func)(),              /* Mutation manager function                                            */
1670                         void (*p_constraint_evaluation_func)(),         /* Detects invalid ("lethal") children                                  */
1671                         void (*p_patricide_func)(),                     /* Patricide function                                                   */
1672                         double *(*p_labelled_point_generator)(),        /* External random point generator function                             */
1673                         List *(*p_labelled_point_list_generator)(),     /* External generator for whole labelled point lists                    */
1674                         int (*p_solution_comparator_func)(),            /* Compares a genome to those in the extracted set for distance         */
1675                         List *(*p_solution_comparator_2_func)(),        /* Compares genome to genomes in list for cost func shape               */
1676                         double (*p_solution_distance_func)(),           /* Gives a (relative) measure of the distance between two pointlists    */
1677                         double (*p_dotp)(),                             /* Dot product of vectors 1->2 and 1->3                                 */
1678                         void (*p_mon_func)(),                           /* Hook for external population monitor function                        */
1679                         List *(*p_es_manager_func)(),                   /* Manages entry into the extracted list                                */
1680                         void (*p_backup_func)()                         /* Function for auto backup of populations                              */
1681                    )
1682 {
1683         /* Init the functions to be used in the problem: for label assign, constraint evaluation, etc                   */
1684         /* All of these must be non-NULL but can point to functions in this file through the genetic algorithm header   */
1685         /* file                                                                                                         */
1686 
1687         cost_evaluation_func = p_cost_evaluation_func;
1688         selection_manager_func = p_selection_manager_func;
1689         breeding_manager_func = p_breeding_manager_func;
1690         crossover_backend_func = p_crossover_backend_func;
1691         mutation_manager_func = p_mutation_manager_func;
1692         constraint_evaluation_func = p_constraint_evaluation_func;
1693         patricide_func = p_patricide_func;
1694         labelled_point_generator = p_labelled_point_generator;
1695         labelled_point_list_generator = p_labelled_point_list_generator;
1696         solution_comparator_func = p_solution_comparator_func;
1697         solution_comparator_2_func = p_solution_comparator_2_func;
1698         solution_distance_func = p_solution_distance_func;
1699         solution_dotp_func = p_dotp;
1700         mon_func = p_mon_func;
1701         es_manager_func = p_es_manager_func;
1702         backup_func = p_backup_func;
1703 }
1704 
1705 
1706 /***** Top level functions *****/
1707 
1708 
1709 List *exhaustive_search_1D(void)
1710 {
1711         /* Exhaustively search the space at the resolution given by spatial_acc, returning a list like unto the extracted set list      */
1712 
1713         Genome *genome=NULL;
1714         List *point_list=NULL, *plist=NULL, *optimal_list=NULL;
1715         Match *nptr=NULL;
1716         double pos_x=0, *point=NULL;
1717         void **breeding_pair=NULL;
1718         int i;
1719 
1720         breeding_pair = pvector_alloc(0, 2);
1721         srand(time(NULL));      /* Seed the random number generator with the current time */
1722 
1723         for(pos_x=space_limits[0][0]; pos_x<space_limits[0][1]; pos_x=pos_x+spatial_acc)
1724         {
1725                 for(i=0; i<2; i++)
1726                 {
1727                         genome = labelled_solution_generator(soln_no_points, NULL);
1728                         point_list = (List *)genome->point_list;
1729                         for(plist = point_list; plist!=NULL; plist = plist->next)
1730                         {
1731                                 nptr = (Match *)plist->to;
1732                                 point = (double *)nptr->to1;
1733                                 point[0] = pos_x;
1734                         }
1735                         genome->age = extraction_age+1;
1736                         cost_evaluation_func(genome);
1737                         breeding_pair[i] = (void *)link_alloc(genome, 1001);
1738                 }
1739 
1740                 optimal_list = es_manager_func(breeding_pair, NULL, optimal_list);
1741 
1742                 for(i=0; i<2; i++)
1743                 {
1744                         plist = (List *)breeding_pair[i];
1745                         genome = (Genome *)plist->to;
1746                         genome = genome_free(genome);
1747                         rfree((void *)plist);
1748                         breeding_pair[i]=NULL;
1749                 }
1750         }
1751         pvector_free(breeding_pair, 0);
1752         breeding_pair=NULL;
1753         return optimal_list;
1754 }
1755 
1756 
1757 
1758 List *exhaustive_search_2D(void)
1759 {
1760         /* Exhaustively search the space at the resolution given by spatial_acc, returning a list like unto the extracted set list      */
1761 
1762         Genome *genome=NULL;
1763         List *point_list=NULL, *plist=NULL, *optimal_list=NULL;
1764         Match *nptr=NULL;
1765         double pos_x=0, pos_y, *point=NULL;
1766         void **breeding_pair=NULL;
1767         int i;
1768 
1769         breeding_pair = pvector_alloc(0, 2);
1770         srand(time(NULL));      /* Seed the random number generator with the current time */
1771 
1772         for(pos_y=space_limits[1][0]; pos_y<space_limits[1][1]; pos_y=pos_y+spatial_acc)
1773         {
1774                 for(pos_x=space_limits[0][0]; pos_x<space_limits[0][1]; pos_x=pos_x+spatial_acc)
1775                 {
1776                         for(i=0; i<2; i++)
1777                         {
1778                                 genome = labelled_solution_generator(soln_no_points, NULL);
1779                                 point_list = (List *)genome->point_list;
1780                                 for(plist = point_list; plist!=NULL; plist = plist->next)
1781                                 {
1782                                         nptr = (Match *)plist->to;
1783                                         point = (double *)nptr->to1;
1784                                         point[0] = pos_x;
1785                                         point[1] = pos_y;
1786                                 }
1787                                 genome->age = extraction_age+1;
1788                                 cost_evaluation_func(genome);
1789                                 breeding_pair[i] = (void *)link_alloc(genome, 1001);
1790                         }
1791 
1792                         optimal_list = es_manager_func(breeding_pair, NULL, optimal_list);
1793 
1794                         for(i=0; i<2; i++)
1795                         {
1796                                 plist = (List *)breeding_pair[i];
1797                                 genome = (Genome *)plist->to;
1798                                 genome = genome_free(genome);
1799                                 rfree((void *)plist);
1800                                 breeding_pair[i]=NULL;
1801                         }
1802                 }
1803         }
1804         pvector_free(breeding_pair, 0);
1805         breeding_pair=NULL;
1806         return optimal_list;
1807 }
1808 
1809 
1810 List *exhaustive_search_3D(void)
1811 {
1812         /* Exhaustively search the space at the resolution given by spatial_acc, returning a list like unto the extracted set list      */
1813 
1814         Genome *genome=NULL;
1815         List *point_list=NULL, *plist=NULL, *optimal_list=NULL;
1816         Match *nptr=NULL;
1817         double pos_x=0, pos_y=0, pos_z=0, *point=NULL;
1818         void **breeding_pair=NULL;
1819         int i;
1820 
1821         breeding_pair = pvector_alloc(0, 2);
1822         srand(time(NULL));      /* Seed the random number generator with the current time */
1823 
1824         for(pos_z=space_limits[2][0]; pos_z<space_limits[2][1]; pos_z=pos_z+spatial_acc)
1825         {
1826                 for(pos_y=space_limits[1][0]; pos_y<space_limits[1][1]; pos_y=pos_y+spatial_acc)
1827                 {
1828                         for(pos_x=space_limits[0][0]; pos_x<space_limits[0][1]; pos_x=pos_x+spatial_acc)
1829                         {
1830                                 for(i=0; i<2; i++)
1831                                 {
1832                                         genome = labelled_solution_generator(soln_no_points, NULL);
1833                                         point_list = (List *)genome->point_list;
1834                                         for(plist = point_list; plist!=NULL; plist = plist->next)
1835                                         {
1836                                                 nptr = (Match *)plist->to;
1837                                                 point = (double *)nptr->to1;
1838                                                 point[0] = pos_x;
1839                                                 point[1] = pos_y;
1840                                                 point[2] = pos_z;
1841                                         }
1842                                         genome->age = extraction_age+1;
1843                                         cost_evaluation_func(genome);
1844                                         breeding_pair[i] = (void *)link_alloc(genome, 1001);
1845                                 }
1846 
1847                                 optimal_list = es_manager_func(breeding_pair, NULL, optimal_list);
1848 
1849                                 for(i=0; i<2; i++)
1850                                 {
1851                                         plist = (List *)breeding_pair[i];
1852                                         genome = (Genome *)plist->to;
1853                                         genome = genome_free(genome);
1854                                         rfree((void *)plist);
1855                                         breeding_pair[i]=NULL;
1856                                 }
1857                         }
1858                 }
1859         }
1860         pvector_free(breeding_pair, 0);
1861         breeding_pair=NULL;
1862         return optimal_list;
1863 }
1864 
1865 
1866 Match  *genetic_algorithm(List *pop_list_in, List *ext_list_in, int no_iterations)
1867 {
1868         /* Top level genetic algorithm routine */
1869 
1870         List *global_population_list=NULL;
1871         List *global_extracted_set_list=NULL;
1872 
1873         Genome *genome = NULL;
1874         Match *list_match=NULL;
1875         List *plist=NULL;
1876         void **breeding_pair=NULL, **child_pair=NULL;
1877         int i, k, backup_ticker=0;
1878 
1879         srand(time(NULL));      /* Seed the random number generator with the current time */
1880         cost_test_flag=0;
1881 
1882         /* Set up genome lists and their lengths */
1883 
1884         if(pop_list_in==NULL)
1885         {
1886                 for(i=0; i<population_size; i++)
1887                 {
1888                         genome = labelled_solution_generator(soln_no_points, NULL);
1889                         pop_list_in = link_addtostart(pop_list_in, link_alloc(genome, 1002));
1890                 }
1891                 backup_func(pop_list_in, NULL, alg_time);
1892         }
1893         else
1894         {
1895                 population_size=0;
1896                 for(plist = pop_list_in; plist!=NULL; plist=plist->next) population_size++;
1897         }
1898         global_population_list = pop_list_in;
1899         pop_list_in=NULL;       /* For testing */
1900 
1901         if(ext_list_in!=NULL)
1902         {
1903                 current_extracted_set_length=0;
1904                 for(plist = ext_list_in; plist!=NULL; plist=plist->next) current_extracted_set_length++;
1905         }
1906         global_extracted_set_list = ext_list_in;
1907         ext_list_in = NULL;     /* For testing */
1908 
1909         /* At this stage there are just two pointers to the population lists, global_population_list and global_extracted_set_list,     */
1910         /* both of which are global                                                                                                     */
1911 
1912         breeding_pair = pvector_alloc(0, 2);
1913 
1914         /* Main breeding loop */
1915 
1916         for(k=0; k<no_iterations; k++)
1917         {
1918                 /* Set program state flags for the new loop                             */
1919 
1920                 breeding_flag=0;
1921                 reattempt_flag=0;
1922                 patricide_flag=0;
1923 
1924                 /* Randomly select two individuals in the genome list for breeding      */
1925 
1926                 selection_manager_func(global_population_list, breeding_pair);
1927 
1928                 /* Breed or clone, and produce child pair                               */
1929 
1930                 child_pair = breeding_manager_func(breeding_pair);
1931 
1932                 /* Mutate */
1933 
1934                 for(i=0; i<2; i++)
1935                 {
1936                         genome = (Genome *)child_pair[i];
1937                         mutation_manager_func(genome);
1938                 }
1939 
1940                 /* Evaluate constraints and objectives, and perform patricide */
1941 
1942                 constraint_evaluation_func(child_pair);
1943 
1944                 for(i=0; i<2; i++)
1945                 {
1946                         genome = (Genome *)child_pair[i];
1947                         if(genome!=NULL) cost_evaluation_func(genome);
1948                 }
1949 
1950                 patricide_func(breeding_pair, child_pair);
1951 
1952                 /* Now do extractions, convergence checks and backups */
1953 
1954                 global_extracted_set_list = es_manager_func(breeding_pair, global_population_list, global_extracted_set_list);
1955 
1956                 mon_func(global_population_list, global_extracted_set_list);
1957                 if(backup_ticker==backup_freq&&backup_freq!=0)
1958                 {
1959                         backup_ticker=0;
1960                         backup_func(global_population_list, global_extracted_set_list, alg_time);
1961                 }
1962                 backup_ticker++;
1963         }
1964 
1965         pvector_free(breeding_pair, 0);
1966         breeding_pair=NULL;
1967         list_match = match_alloc(1003);
1968         list_match->to1 = global_population_list;
1969         list_match->to2 = global_extracted_set_list;
1970 
1971         return list_match;
1972 }
1973 
1974 
1975 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.