selection.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 selection_c_rcsid[]="$Id: selection.c,v 2.7 1993/05/29 22:59:21 gpc-avc Exp gpc-avc $";
#endif

/*
 *
 * $Log: selection.c,v $
 * Revision 2.7  1993/05/29  22:59:21  gpc-avc
 * use M_PI from math.h instead of PI from gpc.h
 *
 * Revision 2.6  1993/04/22  07:39:12  gpc-avc
 * Removed old log messages
 *
 * Revision 2.5  1993/04/14  04:50:16  gpc-avc
 * just a change of the revision number
 *
 *
 */

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


#ifdef ANSI_FUNC

tree *find_tree(
  pop_struct 	*pop,
  int 		p,
  int 		demes,
  int 		nrows,
  int 		ncols,
  int		*worst,
  int		*best
  )
#else

tree *find_tree(pop,p,demes,nrows,ncols,worst,best)
  pop_struct	*pop;
  int		p;
  int 		demes;
  int 		nrows;
  int 		ncols;
  int		*worst;
  int		*best;
#endif
{
  if (demes) {
    return find_tree_using_demes(pop,p,nrows,ncols,worst,best);
  } else {
    switch (pop[p].selection_method) {
    case TOURNAMENT:
      return find_tree_using_tournament(pop,p,worst,best);
    case OVERSELECT:
      return 
	find_tree_using_fitnessprop(pop,p,random_float_with_overselect(pop,p));
    case FITNESSPROP:
      return find_tree_using_fitnessprop(pop,p,random_float(1.0));
    default:
      fprintf(stderr,"Invalid selection method %d\n",pop[p].selection_method);
      return (NULL);
    }
  }
}

#ifdef ANSI_FUNC

tree *find_tree_using_demes(
  pop_struct 	*pop,
  int 		p,
  int 		nrows,
  int 		ncols,
  int		*worst,
  int		*best
  )
#else

tree *find_tree_using_demes(pop,p,nrows,ncols,worst,best)
  pop_struct	*pop;
  int		p;
  int 		nrows;
  int 		ncols;
  int		*worst;
  int		*best;
#endif
{
  int   i,row,col;
  int	best_index, best_i, worst_index;

  /* Select tournament_K individuals */
  for (i = 0; i < pop[p].tournament_K; i++) {
    pop[p].tournament_index[i] =
      cannonical_select(pop,p,nrows,ncols);
#if DBDEMES == 1
    printf(" %d (LID=%d, SF=%f)\n", i, pop[p].tournament_index[i],
	   POP[p].standardized_fitness[pop[p].tournament_index[i]]);
#endif
  }

  /* Find fitest individual */
  best_index = worst_index = pop[p].tournament_index[best_i=0];
  for (i = 1; i < pop[p].tournament_K; i++) {
    if (POP[p].standardized_fitness[pop[p].tournament_index[i]] <
	POP[p].standardized_fitness[best_index]) {
      best_index = pop[p].tournament_index[i];
      best_i = i;
    }
    if (POP[p].standardized_fitness[pop[p].tournament_index[i]] >=
	POP[p].standardized_fitness[worst_index]) {
      worst_index = pop[p].tournament_index[i];
    }
  }
#if DBDEMES == 1
  printf(" %d WON (linear id=%d)\n", best_i, best_index);
#endif
  *best = best_index;
  *worst = worst_index;
  return POP[p].population[best_index];
}

#ifdef ANSI_FUNC
int cannonical_select (
  pop_struct 	*pop,
  int 		p,
  int 		nrows,
  int 		ncols
  )
#else
int cannonical_select(pop,p,nrows,ncols)
  pop_struct	*pop;
  int		p;
  int 		nrows;
  int 		ncols;
#endif
{
  float		azimuth, range, x, y;
  int		row,col,individual_id;

  azimuth = random_float(2.0*M_PI);
  range = gaussian_noise(0.0, pop[p].deme_search_radius_sigma);

  x = (0.5+(float)(pop[p].my_col)) + range * (float) cos((double)azimuth);
  y = (0.5+(float)(pop[p].my_row)) + range * (float) sin((double)azimuth);

  if (x<0.0) x+= (float) ncols;
  if (y<0.0) y+= (float) nrows;

  col = ((int) x)%ncols;
  row = ((int) y)%nrows;
  individual_id = random_int(pop[p].population_size);
#if DBDEMES == 1
  printf("select id %d from row %d col %d for tournament slot",
	 individual_id, row, col);
#endif
  return ((row*ncols) + col)*pop[p].population_size + individual_id;
}

#ifdef ANSI_FUNC
float random_float_with_overselect(
  pop_struct 	*pop,
  int 		p
  )
#else
float random_float_with_overselect(pop,p)
  pop_struct	*pop;
  int		p;
#endif
{
  float	boundary;

  if (pop[p].population_size < 1000) {
    fprintf(stderr,"population size %d is too small for overselection\n",
	    pop[p].population_size);
    exit(-1);
  }

  boundary = 320.0 / (float) (pop[p].population_size);
  if (random_float(1.0) < 0.8) {
    return random_float(1.0);
  } else {
    return (boundary + random_float(1.0-boundary));
  }
}

#ifdef ANSI_FUNC
tree *find_tree_using_tournament_2(
  pop_struct	*pop,
  int 		p
  )
#else
tree *find_tree_using_tournament_2(pop,p)
  pop_struct 	*pop;
  int		p;
#endif
{
  int	index1, index2;

  index1 = random_int(pop[p].population_size);
  index2 = random_int(pop[p].population_size);
  if (pop[p].standardized_fitness[index1] <
      pop[p].standardized_fitness[index2])
    return pop[p].population[index1];
  else
    return pop[p].population[index2];
}


#ifdef ANSI_FUNC

tree *find_tree_using_tournament(
  pop_struct 	*pop,
  int 		p,
  int		*worst,
  int		*best
  )
#else

tree *find_tree_using_tournament(pop,p,worst,best)
  pop_struct	*pop;
  int		p;
  int		*worst;
  int		*best;
#endif
{
  int   i;
  int	best_fitness_index;
  int	worst_fitness_index;

  /* Select tournament_K individuals */
  for (i = 0; i < pop[p].tournament_K; i++) {
    pop[p].tournament_index[i] = random_int(pop[p].population_size);
  }
  /* Find fitest individual */
  best_fitness_index = worst_fitness_index = pop[p].tournament_index[0];
  for (i = 1; i < pop[p].tournament_K; i++) {
    if (pop[p].standardized_fitness[pop[p].tournament_index[i]] <
	pop[p].standardized_fitness[best_fitness_index]) {
      best_fitness_index = pop[p].tournament_index[i];
    }
    if (pop[p].standardized_fitness[pop[p].tournament_index[i]] >=
	pop[p].standardized_fitness[worst_fitness_index]) {
      worst_fitness_index = pop[p].tournament_index[i];
    }
  }
  *best = best_fitness_index;
  *worst = worst_fitness_index;
  return pop[p].population[best_fitness_index];
}

#ifdef ANSI_FUNC
tree *find_tree_using_fitnessprop(
  pop_struct 	*pop,
  int 		p,
  float 	thresh
  )
#else
tree *find_tree_using_fitnessprop(pop, p, thresh)
  pop_struct	*pop;
  int		p;
  float		thresh;
#endif
{
  int	i;
  float	sum;
  int	worst_index;

  for (i=0, sum=0.0;
       ((i<pop[p].population_size) && (sum < thresh));
       sum += pop[p].normalized_fitness[pop[p].fitness_sort_index[i]], i++);
  return pop[p].population[pop[p].fitness_sort_index[i-1]];
}