generations.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 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_FUNC

VOID generations(
  int		numpops,
  int		numgens,
  int		start_gen,
  pop_struct	*pop,
  int		demes,
  pop_struct	***grid,
  int		demerows,
  int		demecols
  )
#else

VOID 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_FUNC
VOID dump_population(
  pop_struct 	*pop,
  int 		p
  )
#else
VOID 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_FUNC

VOID zero_fitness_of_populations(
  int		numpops,
  pop_struct	*pop,
  int		p				 
  )
#else

VOID 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_FUNC
static int fitness_compare(
  int *i,
  int *j
)
#else
static 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_FUNC
VOID sort_population_by_fitness(
  pop_struct	*pop,
  int 	p
  )
#else
VOID 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_FUNC
VOID add_parsimony_to_fitness(
  pop_struct 	*pop,
  int 		p
  )
#else
VOID 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_FUNC
VOID normalize_fitness_of_population(
  pop_struct	*pop,
  int 		p
)
#else
VOID 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_FUNC

VOID report_on_generation(
  int 		g,
  pop_struct	*pop,
  int 		p
  )
#else

VOID 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_FUNC
VOID report_on_run(
  int		numpops,
  pop_struct	*pop
  )
#else
VOID 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);
  }
}