ga_select.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

/**********************************************************************
  ga_select.c
 **********************************************************************

  ga_select - Genetic algorithm selection operators.
  Copyright ©2000-2004, Stewart Adcock <[e-mail]>
  All rights reserved.

  The latest version of this program should be available at:
  http://gaul.sourceforge.net/

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.  Alternatively, if your project
  is incompatible with the GPL, I will probably agree to requests
  for permission to use the terms of any other license.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY WHATSOEVER.

  A full copy of the GNU General Public License should be in the file
  "COPYING" provided with this distribution; if not, see:
  http://www.gnu.org/

 **********************************************************************

  Synopsis:     Routines for performing GA selection operations.

		This selection routines return TRUE if the selection
		procedure has run to completion, otherwise they return
		FALSE.  They may potentially return NULL for the
		selected entities.  This is valid behaviour and doesn't
		necessarily indicate that the selection producedure is
		complete.

		On the first call to these routines in a given
		generation, pop->select_state is gauranteed to be set
		to zero.  These routines are then free to modify this
		value, for example, to store the number of selections
		performed in this generation.

		The ga_select_one_xxx() functions are intended for
		asexual selections.
		The ga_select_two_xxx() functions are intended for
		sexual selections.  Checking whether the mother and
		father are different entities is optional.

		The calling code is welcome to not use any of these
		functions.

		These functions return a pointer to the entity instead
		of an id because, potentially, the entities may come
		from a different population.

		It may be important to use the value held in the
		pop->orig_size field instead of the pop->size field
		because the population size is liable to increase
		between calls to these functions!  (Although, of course,
		you are free to use whichever value you like in
		user-defined functions.)

  To do:	Reimplement stochastic universal selection etc. using this callback mechanism.
		Reimplement probability ranges: mutation_prob = mutation_max - (mutation_max-mutation_min)*i/pop->orig_size;

 **********************************************************************/

#include "gaul/ga_core.h"

/**********************************************************************
  gaul_select_stats()
  synopsis:     Determine mean and standard deviation (and some other
                potentially useful junk) of the fitness scores.
  parameters:	population *pop
  return:	TRUE
  last updated: 30/04/01
 **********************************************************************/

static boolean gaul_select_stats( population *pop,
                             double *average, double *stddev, double *sum )
  {
  int           i;                      /* Loop over all entities. */
  double        fsum=0.0, fsumsq=0.0;   /* Sum and sum squared. */

#if 0
/*
 * Checks not needed for this static function unless used by
 * external code... which it isn't.
 */
  if (!pop) die("Null pointer to population structure passed.");
  if (pop->size < 1) die("Pointer to empty population structure passed.");
#endif

  for (i=0; i<pop->orig_size; i++)
    {
    fsum += pop->entity_iarray[i]->fitness;
    fsumsq += SQU(pop->entity_iarray[i]->fitness);
    }

  *sum = fsum;
  *average = fsum / pop->orig_size;
  *stddev = (fsumsq - fsum*fsum/pop->orig_size)/pop->orig_size;

  return TRUE;
  }


/**********************************************************************
  gaul_select_sum_fitness()
  synopsis:	Determine sum of entity fitnesses.
  parameters:	population *pop
  return:	double sum
  last updated: 11 Jun 2002
 **********************************************************************/

static double gaul_select_sum_fitness( population *pop )
  {
  int           i;		/* Loop over all entities. */
  double        sum=0.0;	/* Sum and sum squared. */

  for (i=0; i<pop->orig_size; i++)
    {
    sum += pop->entity_iarray[i]->fitness;
    }

  return sum;
  }


/**********************************************************************
  gaul_select_sum_sq_fitness()
  synopsis:	Determine sum of squared entity fitnesses.
  parameters:	population *pop
  return:	double sum
  last updated: 23 Mar 2004
 **********************************************************************/

static double gaul_select_sum_sq_fitness( population *pop )
  {
  int           i;		/* Loop over all entities. */
  double        sum=0.0;	/* Sum and sum squared. */

  for (i=0; i<pop->orig_size; i++)
    {
    sum += ( pop->entity_iarray[i]->fitness * pop->entity_iarray[i]->fitness );
    }

  return sum;
  }


/**********************************************************************
  ga_select_one_random()
  synopsis:	Select a single random entity.  Selection stops when
		(population size)*(mutation ratio)=(number selected)
  parameters:
  return:	
  last updated: 30/04/01
 **********************************************************************/

boolean ga_select_one_random(population *pop, entity **mother)
  {

  if (!pop) die("Null pointer to population structure passed.");

  if (pop->orig_size < 1)
    {
    *mother = NULL;
    return TRUE;
    }

  *mother = pop->entity_iarray[random_int(pop->orig_size)];

  pop->select_state++;

  return pop->select_state>(pop->orig_size*pop->mutation_ratio);
  }


/**********************************************************************
  ga_select_two_random()
  synopsis:	Select a pair of random entities.  Selection stops when
		(population size)*(crossover ratio)=(number selected)
  parameters:
  return:	
  last updated: 30/04/01
 **********************************************************************/

boolean ga_select_two_random(population *pop, entity **mother, entity **father)
  {

  if (!pop) die("Null pointer to population structure passed.");

  if (pop->orig_size < 2)
    {
    *mother = NULL;
    *father = NULL;
    return TRUE;
    }

  *mother = pop->entity_iarray[random_int(pop->orig_size)];
  do 
    {
    *father = pop->entity_iarray[random_int(pop->orig_size)];
    } while (*mother == *father);

  pop->select_state++;

  return pop->select_state>(pop->orig_size*pop->crossover_ratio);
  }


/**********************************************************************
  ga_select_one_every()
  synopsis:	Select every entity.
  parameters:
  return:	
  last updated: 23/04/01
 **********************************************************************/

boolean ga_select_one_every(population *pop, entity **mother)
  {

  if (!pop) die("Null pointer to population structure passed.");

  *mother = NULL;

  if ( pop->orig_size <= pop->select_state )
    {
    return TRUE;
    }

  *mother = pop->entity_iarray[pop->select_state];

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_two_every()
  synopsis:	Select every possible pair of parents.
  parameters:
  return:	
  last updated: 23/04/01
 **********************************************************************/

boolean ga_select_two_every(population *pop, entity **mother, entity **father)
  {

  if (!pop) die("Null pointer to population structure passed.");

  *mother = NULL;
  *father = NULL;

  if ( SQU(pop->orig_size) <= pop->select_state )
    {
    return TRUE;
    }

  *mother = pop->entity_iarray[pop->select_state%pop->orig_size];
  *father = pop->entity_iarray[pop->select_state/pop->orig_size];

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_one_randomrank()
  synopsis:	Select a single entity by my rank-based method.
  parameters:
  return:	
  last updated: 23/04/01
 **********************************************************************/

boolean ga_select_one_randomrank(population *pop, entity **mother)
  {

  if (!pop) die("Null pointer to population structure passed.");

  pop->select_state++;

  *mother = NULL;

  if ( pop->orig_size < pop->select_state )
    {
    return TRUE;
    }

  if ( random_boolean_prob(pop->mutation_ratio) )
    {
    *mother = pop->entity_iarray[random_int(pop->select_state)];
    }

  return FALSE;
  }


/**********************************************************************
  ga_select_two_randomrank()
  synopsis:	Select a pair of entities by my rank-based method.
		Basically, I loop through all entities, and each is
		paired with a random, fitter, partner.
  parameters:
  return:	
  last updated: 23/04/01
 **********************************************************************/

boolean ga_select_two_randomrank(population *pop, entity **mother, entity **father)
  {

  if (!pop) die("Null pointer to population structure passed.");

  pop->select_state++;

  *mother = NULL;
  *father = NULL;

  if ( pop->orig_size < pop->select_state )
    {
    return TRUE;
    }

  if ( random_boolean_prob(pop->crossover_ratio) )
    {
    *mother = pop->entity_iarray[random_int(pop->select_state)];
    *father = pop->entity_iarray[pop->select_state];
    }

  return FALSE;
  }


/**********************************************************************
  ga_select_one_bestof3()
  synopsis:	Kind of tournament selection.  Choose three random
		entities, return the best as the selection.  Selection
		stops when
		(population size)*(mutation ratio)=(number selected)
  parameters:
  return:	
  last updated: 25 May 2004
 **********************************************************************/

boolean ga_select_one_bestof3(population *pop, entity **mother)
  {
  entity	*mother2, *mother3;	/* Random competitors. */

  if (!pop) die("Null pointer to population structure passed.");

  if (pop->orig_size < 1)
    {
    *mother = NULL;
    return TRUE;
    }

  *mother = pop->entity_iarray[random_int(pop->orig_size)];
  mother2 = pop->entity_iarray[random_int(pop->orig_size)];
  mother3 = pop->entity_iarray[random_int(pop->orig_size)];

  if (mother2->fitness > (*mother)->fitness)
    *mother = mother2;
  if (mother3->fitness > (*mother)->fitness)
    *mother = mother3;

  pop->select_state++;

  return pop->select_state>(pop->orig_size*pop->mutation_ratio);
  }


/**********************************************************************
  ga_select_two_bestof2()
  synopsis:	Kind of tournament selection.  For each parent, choose
		three random entities, return the best as the
		selection.
		The two parents will be different.  Selection
		stops when
		(population size)*(crossover ratio)=(number selected)
  parameters:
  return:	
  last updated: 25 May 2004
 **********************************************************************/

boolean ga_select_two_bestof3(population *pop, entity **mother, entity **father)
  {
  entity	*challenger1, *challenger2;	/* Random competitors. */

  if (!pop) die("Null pointer to population structure passed.");

  if (pop->orig_size < 2)
    {
    *mother = NULL;
    *father = NULL;
    return TRUE;
    }

  *mother = pop->entity_iarray[random_int(pop->orig_size)];
  challenger1 = pop->entity_iarray[random_int(pop->orig_size)];
  challenger2 = pop->entity_iarray[random_int(pop->orig_size)];

  if (challenger1->fitness > (*mother)->fitness)
    *mother = challenger1;
  if (challenger2->fitness > (*mother)->fitness)
    *mother = challenger2;