populations.c

一个完整的C语言遗传程序包

/*
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!  ([e-mail])
*/

#ifndef lint
static char populations_c_rcsid[]="$Id: populations.c,v 2.8 1993/04/22 07:39:12 gpc-avc Exp gpc-avc $";
#endif

/*
 *
 * $Log: populations.c,v $
 * Revision 2.8  1993/04/22  07:39:12  gpc-avc
 * Removed old log messages
 *
 * Revision 2.7  1993/04/14  04:59:00  gpc-avc
 * Fixed bug of not initializing fraction inside the for loop
 *
 *
 */

#include <stdio.h>
#include <malloc.h>
#include <errno.h>
#include <values.h>
#include "gpc.h"



#ifdef ANSI_FUNC

VOID allocate_populations(
  int		numpops,
  pop_struct	*pop
  )
#else

VOID allocate_populations(numpops,pop)
  int 		numpops;
  pop_struct	*pop;
#endif
{
  int	p;

  for (p=0; p<numpops; p++) {
    pop[p].standardized_fitness =
      (float *) malloc(pop[p].population_size*sizeof(float));
    pop[p].adjusted_fitness = (float *) malloc(pop[p].population_size*sizeof(float));
    pop[p].normalized_fitness =
      (float *) malloc(pop[p].population_size*sizeof(float));
    pop[p].fitness_sort_index = (int *) malloc(pop[p].population_size*sizeof(int));
    pop[p].tournament_index = (int *) malloc(pop[p].tournament_K*sizeof(int));
    pop[p].population = (tree **) malloc(pop[p].population_size*sizeof(tree *));
    pop[p].new_population = (tree **) malloc(pop[p].population_size*sizeof(tree *));
    pop[p].best_of_generation = (tree *) NULL; 
    pop[p].best_of_run = (tree *) NULL;
    pop[p].best_of_gen_fitness = (MAXFLOAT);
    pop[p].best_of_run_fitness = (MAXFLOAT);
  }
}


#ifdef ANSI_FUNC

VOID setup_deme_grid(
  int 		numpops,
  int		demerows,
  int		demecols,	       
  pop_struct 	*pop,
  pop_struct    ***grid
  )
#else

VOID setup_deme_grid(numpops,demerows,demecols,pop,grid)
  int 		numpops;
  int		demerows;
  int		demecols;
  pop_struct 	*pop;
  pop_struct    ***grid;
#endif
{
  int	r, c;
  int	i, p, nperdeme;

  for (p=0;p<numpops;p++) {
    nperdeme = (pop[p].population_size/(demerows*demecols));
    for (r=0,i=0; r<demerows;r++) {
      for (c=0;c<demecols;c++,i+=nperdeme) {
	grid[r][c][p].my_row = r;
	grid[r][c][p].my_col = c;
	grid[r][c][p].population_size = nperdeme;
	grid[r][c][p].steady_state = pop[p].steady_state;
	grid[r][c][p].load_from_file = pop[p].load_from_file;
	grid[r][c][p].max_depth_for_new_trees =
	  pop[p].max_depth_for_new_trees;
	grid[r][c][p].max_depth_after_crossover =
	  pop[p].max_depth_after_crossover;
	grid[r][c][p].max_mutant_depth = pop[p].max_mutant_depth;
	grid[r][c][p].grow_method = pop[p].grow_method;
	grid[r][c][p].selection_method = pop[p].selection_method;
	grid[r][c][p].tournament_K = pop[p].tournament_K;
	grid[r][c][p].deme_search_radius_sigma =
	  pop[p].deme_search_radius_sigma;
	grid[r][c][p].tournament_index =
	  (int *) malloc(pop[p].tournament_K*sizeof(int));
	grid[r][c][p].crossover_func_pt_fraction =
	  pop[p].crossover_func_pt_fraction;
	grid[r][c][p].crossover_any_pt_fraction =
	  pop[p].crossover_any_pt_fraction;
	grid[r][c][p].fitness_prop_repro_fraction =
	  pop[p].fitness_prop_repro_fraction;
	grid[r][c][p].parsimony_factor = pop[p].parsimony_factor;
	grid[r][c][p].standardized_fitness =
	  &(pop[p].standardized_fitness[i]);
	grid[r][c][p].adjusted_fitness =
	  &(pop[p].adjusted_fitness[i]);
	grid[r][c][p].normalized_fitness =
	  &(pop[p].normalized_fitness[i]);
	grid[r][c][p].fitness_sort_index =
	  &(pop[p].fitness_sort_index[i]);
	grid[r][c][p].population = &(pop[p].population[i]);
	grid[r][c][p].new_population =
	  &(pop[p].new_population[i]);
	grid[r][c][p].best_of_generation = (tree *) NULL;
	grid[r][c][p].best_of_run = (tree *) NULL;
	grid[r][c][p].best_of_run_gen = -1;
	grid[r][c][p].best_of_gen_fitness = -1.0;
	grid[r][c][p].best_of_run_fitness = -1.0;
	grid[r][c][p].function_table = pop[p].function_table; 
	grid[r][c][p].terminal_table = pop[p].terminal_table;
	grid[r][c][p].function_table_size = pop[p].function_table_size;
	grid[r][c][p].terminal_table_size = pop[p].terminal_table_size;
      }
    }
  }
}

#ifdef ANSI_FUNC

VOID initialize_populations(
  int		numpops,
  pop_struct	*pop
  )
#else

VOID initialize_populations(numpops,pop)
  int		numpops;
  pop_struct	*pop;
#endif
{
  int	p;
  int	i;
  int	min_depth_for_new_trees = 1;
  int 	full_cycle;
  int 	grow;
  int	size;
  FILE	*f;
  tree	*temp;

  for (p=0; p<numpops; p++) {
    full_cycle = 0;
    for (i=0; i<pop[p].population_size; i++) {
      switch (pop[p].grow_method) {
      case FULL:
	size = pop[p].max_depth_for_new_trees;
	grow = 1;
	break;
      case GROW:
	size = pop[p].max_depth_for_new_trees;
	grow = 0;
	break;
      case RAMPED:
	size = (min_depth_for_new_trees +
		(i % (pop[p].max_depth_for_new_trees-min_depth_for_new_trees)));
	if (pop[p].max_depth_for_new_trees != min_depth_for_new_trees)
	  if (!(i % (pop[p].max_depth_for_new_trees-min_depth_for_new_trees)))
	    full_cycle = (!full_cycle);
	grow = (full_cycle);
	break;
      default:
	fprintf(stderr,"Error in initialize_populations(): Method %d must be %d %d or %d\n",
		pop[p].grow_method, FULL, GROW, RAMPED);
      }
      pop[p].population[i] = create_random_tree(pop, p, size, 1, grow);
    }
    /* replace the first members of population with those to be read
       from a file, if filename is not null */
    if (pop[p].load_from_file[0] != '\0') {
      f = fopen(pop[p].load_from_file,"r");
      for (i=0; (((int)(temp=read_tree(pop,p,f))) != EOF) &&
	   (i<pop[p].population_size); i++) {
	free_tree(pop[p].population[i]);
	pop[p].population[i] = temp;
      }
    }
  }
}

#ifdef ANSI_FUNC

VOID breed_new_population(
  pop_struct	*pop,
  int 		p,
  int 		demes,
  int 		nrows,
  int 		ncols,
  int		steady_state			  
  )
#else

VOID breed_new_population(pop,p,demes,nrows,ncols,steady_state)
  pop_struct *pop;
  int		p;
  int 		demes;
  int 		nrows;
  int 		ncols;
  int		steady_state;
#endif
{
  int	i, j, incr;
  float fraction = 0.0;
  tree	*parent1, *parent2, *offspring1, *offspring2, *pptr;
  int	worst_index1, worst_index2, best_index1, best_index2;

#if DBSS == 1
    if (demes) {
      printf(" Steady state breeding in deme (%d,%d) \n",
	     pop[p].my_row, pop[p].my_col);
    }
#endif
  if (steady_state && ((pop[p].selection_method == OVERSELECT) ||
		      (pop[p].selection_method == FITNESSPROP))) {
    printf("SORRY: steady_state population requires either DEMES or \n \
            selection_method = TOURNAMENT");
    exit (1);
  }
  for (i = 0, fraction = random_float(1.0); 
       i < pop[p].population_size;
       i += incr, fraction = random_float(1.0)) {

    parent1 = find_tree(pop,p,demes,nrows,ncols,&worst_index1,&best_index1);
    while (steady_state && (POP[p].population[worst_index1] == parent1))
      parent1 = find_tree(pop,p,demes,nrows,ncols,&worst_index1,&best_index1);
#if DBSS == 1
    printf("Parent 1: selected POP[%d] to breed. Fitness = %f\n \
            \tselected POP[%d] to replace. Fitness = %f\n",
	   best_index1, POP[p].standardized_fitness[best_index1],
	   worst_index1, POP[p].standardized_fitness[worst_index1]);
#endif
    if ((i < (pop[p].population_size-1)) &&
	(fraction <
	 (pop[p].crossover_func_pt_fraction+pop[p].crossover_any_pt_fraction))) {
      parent2 = find_tree(pop,p,demes,nrows,ncols,&worst_index2,&best_index2);
      while (steady_state && ((worst_index1 == worst_index2) ||
			      (POP[p].population[worst_index2] == parent2) ||
			      (POP[p].population[worst_index2] == parent1) ||
			      (POP[p].population[worst_index1] == parent2)))
	parent2 = find_tree(pop,p,demes,nrows,ncols,&worst_index2,&best_index2);
#if DBSS == 1
      printf("Parent 2: selected POP[%d] to breed. Fitness = %f\n \
            \tselected POP[%d] to replace. Fitness = %f\n",
	     best_index2, POP[p].standardized_fitness[best_index2],
	     worst_index2, POP[p].standardized_fitness[worst_index2]);
#endif

      if (fraction < pop[p].crossover_func_pt_fraction) {
	crossover_at_func_pt(pop, parent1, parent2, &offspring1, &offspring2);
      } else {
	crossover_at_any_pt(pop, parent1, parent2, &offspring1, &offspring2);
      }
      if (steady_state) {
	free_tree(POP[p].population[worst_index1]);
	free_tree(POP[p].population[worst_index2]);
	POP[p].population[worst_index1] = offspring1;
	POP[p].population[worst_index2] = offspring2;
	POP[p].standardized_fitness[worst_index1] =
	  evaluate_fitness_of_individual(POP,p,
					 POP[p].population[worst_index1],
					 worst_index1) +
          ((float) count_crossover_pts(POP[p].population[worst_index1]))*
	    pop[p].parsimony_factor;

	POP[p].standardized_fitness[worst_index2] =
	  evaluate_fitness_of_individual(POP,p,
					 POP[p].population[worst_index2],
					 worst_index2) +
          ((float) count_crossover_pts(POP[p].population[worst_index2]))*
	    pop[p].parsimony_factor;
      } else {
	pop[p].new_population[i] = offspring1;
	pop[p].new_population[i+1] = offspring2;
      }
      incr = 2;
    } else if (fraction <
	 (pop[p].crossover_func_pt_fraction
	  + pop[p].crossover_any_pt_fraction
	  + pop[p].fitness_prop_repro_fraction)) {
      if (steady_state) {
#if DBSS == 1
	printf("performing straight copy of parent 1\n");
#endif
	free_tree(POP[p].population[worst_index1]);
	POP[p].population[worst_index1] = copy_tree(parent1);
	/* kind of a waste - you should really set fitess-prop-repro-frac
	   to zero for the steady-state elitist model... */
	POP[p].standardized_fitness[worst_index1] =
	  evaluate_fitness_of_individual(POP,p,
					 POP[p].population[worst_index1],
					 worst_index1) +
            ((float) count_crossover_pts(POP[p].population[worst_index1]))*
	      pop[p].parsimony_factor;
      } else {
	pop[p].new_population[i] = copy_tree(parent1);
      }
      incr = 1;
    } else {
      if (steady_state) {
#if DBSS == 1
	printf("performing mutation of parent 1\n");
#endif
	free_tree(POP[p].population[worst_index1]);
	POP[p].population[worst_index1] = mutate(pop,copy_tree(parent1));
	POP[p].standardized_fitness[worst_index1] =
	  evaluate_fitness_of_individual(POP,p,
					 POP[p].population[worst_index1],
					 worst_index1) +
            ((float) count_crossover_pts(POP[p].population[worst_index1]))*
	      pop[p].parsimony_factor;
      } else {
	pop[p].new_population[i] = mutate(pop,copy_tree(parent1));
      }
      incr = 1;
    }
  }
}
     
#ifdef ANSI_FUNC

VOID free_population(
  pop_struct	*pop,
  int 	p
  )
#else

VOID free_population(pop,p)
  pop_struct	*pop;
  int		p;
#endif
{
  int	i;

  for (i=0; i<pop[p].population_size; i++) {
    free_tree(pop[p].population[i]);
  }
}

#ifdef ANSI_FUNC

VOID load_new_population(
  pop_struct	*pop,
  int p
  )
#else

VOID load_new_population(pop,p)
  pop_struct	*pop;
  int		p;
#endif
{
  int	i;

  for (i=0; i<pop[p].population_size; i++) {
    pop[p].population[i] = pop[p].new_population[i];
  }
}