/*SGPC: Simple Genetic Programming in C(c) 1993 by Walter Alden Tackett and Aviram Carmi  This code and documentation is copyrighted and is not in the public domain. All rights reserved.   - This notice may not be removed or altered.  - You may not try to make money by distributing the package or by using the   process that the code creates.  - You may not distribute modified versions without clearly documenting your   changes and notifying the principal author.  - The origin of this software must not be misrepresented, either by   explicit claim or by omission.  Since few users ever read sources,   credits must appear in the documentation.  - Altered versions must be plainly marked as such, and must not be   misrepresented as being the original software.  Since few users ever read   sources, credits must appear in the documentation.  - The authors are not responsible for the consequences of use of this    software, no matter how awful, even if they arise from flaws in it. If you make changes to the code, or have suggestions for changes,let us know!  (gpc@ipld01.hac.com)*/#ifndef lintstatic char generations_c_rcsid[]="$Id: generations.c,v 2.13 1993/04/22 07:39:12 gpc-avc Exp gpc-avc $";#endif/* * * $Log: generations.c,v $ * Revision 2.13  1993/04/22  07:39:12  gpc-avc * Removed old log messages * * Revision 2.12  1993/04/15  09:10:10  gpc-avc * Added bsd_qsort() * * */#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <errno.h>#include "gpc.h"#ifdef ANSI_FUNCVOID generations(  int		numpops,  int		numgens,  int		start_gen,  pop_struct	*pop,  int		demes,  pop_struct	***grid,  int		demerows,  int		demecols  )#elseVOID generations(numpops,numgens,start_gen,pop,demes,grid,demerows,demecols)  int		numpops;  int		numgens;  int		start_gen;  pop_struct	*pop;  int		demes;  pop_struct	***grid;  int		demerows;  int		demecols;#endif{  int	g, p, i, j;  float valperf;  for (g=start_gen; g<numgens; g++) {    if (g) {      for (p = 0; p<numpops; p++) {	if (demes) {	  for (i=0;i<demerows;i++) {	    for (j=0;j<demecols;j++) {	      if (pop[p].steady_state) {		/* not strictly necessary, really, but removes what		   i think would otherwise be a trend for the upper		   left hand of the grid to have much lower fitness		   than the lower right */		breed_new_population(grid[random_int(demerows)]				         [random_int(demecols)],				     p,demes,demerows,demecols,				     pop[p].steady_state);	      } else  {		breed_new_population(grid[i][j],p,demes,demerows,demecols,				   pop[p].steady_state);	      }	    }	  }	} else {	  breed_new_population(pop,p,0,0,0,pop[p].steady_state);	}	if (!(pop[p].steady_state)) {	  free_population(pop,p);	  load_new_population(pop,p);	}      }    } else {      /* generation 0 is random */      initialize_populations(numpops,pop);      for (p = 0; p<numpops; p++) {	if (pop[p].steady_state) {	  evaluate_fitness_of_populations(numpops,numgens,pop,p);	  if (pop[p].parsimony_factor > 0.0) add_parsimony_to_fitness(pop,p);	}      }    }    /* NOTE that we breed ALL populations before we evaluate their fitness       (except in the case of steady-state).  This is done to support       co-evolution where there are multiple interacting populations       who are co-evaluated at each generation */    for (p = 0; p<numpops; p++) {      if (!(pop[p].steady_state)) {	zero_fitness_of_populations(numpops,pop,p);	evaluate_fitness_of_populations(numpops,numgens,pop,p);	if (pop[p].parsimony_factor > 0.0) add_parsimony_to_fitness(pop,p);      }      normalize_fitness_of_population(pop,p);      sort_population_by_fitness(pop,p);      pop[p].best_of_gen_fitness =	pop[p].standardized_fitness[pop[p].fitness_sort_index[0]];      pop[p].best_of_generation =	copy_tree(pop[p].population[pop[p].fitness_sort_index[0]]);#if REP_ON_GEN == 1      report_on_generation(g,pop,p);#endif#if ((DEBUG == 1)||(DBSS == 1))      dump_population(pop,p);#endif      #if ((DBDEMES == 1)||(DBSS == 1))      if (demes) { /* this should alway be true, but still.... */	for (i=0;i<demerows;i++) {	  for (j=0;j<demecols;j++) {	    printf("\nDUMPING DEME row=%d col=%d\n",i,j);	    dump_population(grid[i][j],p);	  }	}      }#endif      valperf =	validate_fitness_of_tree(numpops, numgens, pop, p,				 pop[p].population[pop[p].fitness_sort_index[0]]);#if REP_ON_GEN == 1      printf("\nValidation Fitness= %f\n", valperf);#endif      if (!g) {	pop[p].best_of_run_fitness = valperf;	pop[p].best_of_run = copy_tree(pop[p].population[pop[p].fitness_sort_index[0]]);	pop[p].best_of_run_gen = 0;      }      else if (valperf < pop[p].best_of_run_fitness) {	pop[p].best_of_run_fitness = valperf;	free((char *)pop[p].best_of_run);	pop[p].best_of_run = copy_tree(pop[p].best_of_generation);	pop[p].best_of_run_gen = g;      }            free_tree(pop[p].best_of_generation);    }    if (CHECKPOINT_FREQUENCY) {      if (g && !(g % CHECKPOINT_FREQUENCY)) {	checkpoint(numpops, numgens, demes, demerows, demecols, pop, g);      }    }    if (terminate_early(numpops,numgens,pop)) break;  }  /* checkpoint the last generation, if it was not just saved */  if (CHECKPOINT_FREQUENCY) {    if ((numgens-1) % CHECKPOINT_FREQUENCY) {      checkpoint(numpops,numgens,demes,demerows,demecols,pop,numgens-1);    }  }}#ifdef ANSI_FUNCVOID dump_population(  pop_struct 	*pop,  int 		p  )#elseVOID dump_population(pop,p)  pop_struct	*pop;  int		p;#endif{  int	i, index;  for (i=0; i<pop[p].population_size; i++) {    index = (DEMES? i : pop[p].fitness_sort_index[i]);    printf("pop= %d standardized = %f, adjusted = %f, norm = %f\n",	   p,	   pop[p].standardized_fitness[index],	   pop[p].adjusted_fitness[index],	   pop[p].normalized_fitness[index]);    write_tree(pop,pop[p].population[index],pop[p].ckpt_format,stdout);  }}#ifdef ANSI_FUNCVOID zero_fitness_of_populations(  int		numpops,  pop_struct	*pop,  int		p				   )#elseVOID zero_fitness_of_populations(numpops,pop,p)  int		numpops;  pop_struct	*pop;  int		p;#endif{  int	i;  for (i=0; i<pop[p].population_size; i++) {    pop[p].standardized_fitness[i] 	= 0.0;    pop[p].adjusted_fitness[i] 		= 0.0;    pop[p].normalized_fitness[i] 	= 0.0;  }}int	global_p;#ifdef ANSI_FUNCstatic int fitness_compare(  int *i,  int *j)#elsestatic int fitness_compare(i,j)  int	*i;  int	*j;#endif{  pop_struct *pop = POP;  if (pop[global_p].normalized_fitness[*j] > pop[global_p].normalized_fitness[*i]) {    return 1;  } else if (pop[global_p].normalized_fitness[*j] < pop[global_p].normalized_fitness[*i]) {    return -1;  } else return 0;}    #ifdef ANSI_FUNCVOID sort_population_by_fitness(  pop_struct	*pop,  int 	p  )#elseVOID sort_population_by_fitness(pop,p)  pop_struct	*pop;  int		p;#endif{  int	i;  global_p = p; /* kludge for fitness_compare */  for (i=0; i<pop[p].population_size; i++) {    pop[p].fitness_sort_index[i] = i;  }#ifdef STD_QSORT  qsort(pop[p].fitness_sort_index, pop[p].population_size, sizeof(int),	fitness_compare);#else  bsd_qsort(pop[p].fitness_sort_index, pop[p].population_size, sizeof(int),	fitness_compare);#endif}#ifdef ANSI_FUNCVOID add_parsimony_to_fitness(  pop_struct 	*pop,  int 		p  )#elseVOID add_parsimony_to_fitness(pop,p)  pop_struct 	*pop;  int		p;#endif{  int	i;  for (i=0; i<pop[p].population_size; i++) {    pop[p].standardized_fitness[i] +=       ((float) count_crossover_pts(pop[p].population[i]))*pop[p].parsimony_factor;  }}#ifdef ANSI_FUNCVOID normalize_fitness_of_population(  pop_struct	*pop,  int 		p)#elseVOID normalize_fitness_of_population(pop,p)  pop_struct	*pop;  int	       	p;#endif{  float	sum = 0.0;  int	i;  for (i=0; i<pop[p].population_size; i++) {    sum += (pop[p].adjusted_fitness[i] = 1.0/(1.0 + pop[p].standardized_fitness[i]));  }  for (i=0; i<pop[p].population_size; i++) {    pop[p].normalized_fitness[i] = (pop[p].adjusted_fitness[i]/sum);  }}#ifdef ANSI_FUNCVOID report_on_generation(  int 		g,  pop_struct	*pop,  int 		p  )#elseVOID report_on_generation(g,pop,p)  int		g;  pop_struct	*pop;  int		p;#endif{  int	i;  float	sum = 0.0;  sum = 0.0;  for (i=0; i<pop[p].population_size; i++) {    sum += pop[p].standardized_fitness[i];  }    printf("\nGeneration %d Population %d   Avg Std Fitness: %f\n",	 g, p, sum/(float)pop[p].population_size);  printf("Best-of-gen fitness: %f\nBest-of-gen tree:\n",	 pop[p].best_of_gen_fitness);  write_tree(pop,pop[p].best_of_generation,pop[p].format,stdout);}#ifdef ANSI_FUNCVOID report_on_run(  int		numpops,  pop_struct	*pop  )#elseVOID report_on_run(numpops,pop)  int		numpops;  pop_struct	*pop;#endif{  int	p;  for (p=0; p<numpops; p++) {    printf("Best tree for pop#%d found on gen %d, VALIDATED fitness = %f:\n",	   p, pop[p].best_of_run_gen, pop[p].best_of_run_fitness);    write_tree(pop, pop[p].best_of_run, pop[p].format, stdout);  }}