/**********************************************************************  ga_select.c **********************************************************************  ga_select - Genetic algorithm selection operators.  Copyright ?2000-2004, Stewart Adcock <stewart@linux-domain.com>  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;