ga_select.c

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

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

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

  if (challenger1 != *mother && challenger1->fitness > (*father)->fitness)
    *father = challenger1;

  if (challenger2 != *mother && challenger2->fitness > (*father)->fitness)
    *father = challenger2;

  pop->select_state++;

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


/**********************************************************************
  ga_select_one_bestof2()
  synopsis:	Kind of tournament selection.  Choose two random
		entities, return the best as the selection.  Selection
		stops when
		(population size)*(mutation ratio)=(number selected)
  parameters:
  return:	
  last updated: 30/04/01
 **********************************************************************/

boolean ga_select_one_bestof2(population *pop, entity **mother)
  {
  entity	*mother2;	/* Random competitor. */

  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)];

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

  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
		two 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_bestof2(population *pop, entity **mother, entity **father)
  {
  entity	*challenger;	/* Random competitor. */

  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)];
  challenger = pop->entity_iarray[random_int(pop->orig_size)];

  if (challenger->fitness > (*mother)->fitness)
    *mother = challenger;

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

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

  if (challenger != *mother && challenger->fitness > (*father)->fitness)
    *father = challenger;

  pop->select_state++;

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


/**********************************************************************
  ga_select_one_roulette()
  synopsis:	Fitness-proportionate roulette wheel selection.
		If pop->mutation_ratio is 1.0, the wheel will be spun
		pop->orig_size times, which matches Holland's original
		implementation.
		This version is for fitness values where 0.0 is bad and
		large positive values are good.  Negative values will
		severely mess-up the algorithm.
  parameters:
  return:	
  last updated: 28 Jun 2004
 **********************************************************************/

boolean ga_select_one_roulette(population *pop, entity **mother)
  {
  double	selectval;		/* Select when this reaches zero. */

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

  *mother = NULL;

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

  if (pop->select_state == 0)
    { /* First call of this generation. */
    gaul_select_stats(pop, &(pop->selectdata.mean), &(pop->selectdata.stddev), &(pop->selectdata.sum));
    pop->selectdata.current_expval = pop->selectdata.sum/pop->selectdata.mean;
    pop->selectdata.marker = random_int(pop->orig_size);
    }

  selectval = random_double(pop->selectdata.current_expval)*pop->selectdata.mean;

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= pop->entity_iarray[pop->selectdata.marker]->fitness;

    } while (selectval>0.0);

  pop->select_state++;

  *mother = pop->entity_iarray[pop->selectdata.marker];

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


/**********************************************************************
  ga_select_one_roulette_rebased()
  synopsis:	Fitness-proportionate roulette wheel selection.
		If pop->mutation_ratio is 1.0, the wheel will be spun
		pop->orig_size times, which matches Holland's original
		implementation.
		This version can cope with a mixture of positive and
		negative fitness scores.  The single least fit entity
		will never be selected, but this is not considered a
		problem.
  parameters:
  return:	
  last updated: 28 Jun 2004
 **********************************************************************/

boolean ga_select_one_roulette_rebased(population *pop, entity **mother)
  {
  double	selectval;		/* Select when this reaches zero. */

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

  *mother = NULL;

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

  if (pop->select_state == 0)
    { /* First call of this generation. */
    gaul_select_stats(pop, &(pop->selectdata.mean), &(pop->selectdata.stddev), &(pop->selectdata.sum));
    pop->selectdata.marker = random_int(pop->orig_size);
    pop->selectdata.minval = pop->entity_iarray[pop->orig_size-1]->fitness;
    pop->selectdata.mean -= pop->selectdata.minval;
    if (ISTINY(pop->selectdata.mean)) die("Degenerate population?");
    pop->selectdata.current_expval = (pop->selectdata.sum-pop->selectdata.minval*pop->orig_size)/pop->selectdata.mean;
    }

  selectval = random_double(pop->selectdata.current_expval);

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= (pop->entity_iarray[pop->selectdata.marker]->fitness-pop->selectdata.minval)/pop->selectdata.mean;

    } while (selectval>0.0);

  pop->select_state++;

  *mother = pop->entity_iarray[pop->selectdata.marker];

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


/**********************************************************************
  ga_select_two_roulette()
  synopsis:	Fitness-proportionate roulette wheel selection.
		If pop->mutation_ratio is 1.0, the wheel will be spun
		pop->orig_size times, which matches Holland's original
		implementation.
		This version is for fitness values where 0.0 is bad and
		large positive values are good.  Negative values will
		severely mess-up the algorithm.
                Mother and father may be the same.
  parameters:
  return:	
  last updated: 28 Jun 2004
 **********************************************************************/

boolean ga_select_two_roulette( population *pop,
                                entity **mother, entity **father )
  {
  double	selectval;		/* Select when this reaches zero. */

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

  *mother = NULL;
  *father = NULL;

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

  if (pop->select_state == 0)
    { /* First call of this generation. */
    gaul_select_stats(pop, &(pop->selectdata.mean), &(pop->selectdata.stddev), &(pop->selectdata.sum));
    pop->selectdata.current_expval = pop->selectdata.sum/pop->selectdata.mean;
    pop->selectdata.marker = random_int(pop->orig_size);
/*
printf("Mean fitness = %f stddev = %f sum = %f expval = %f\n", mean, stddev, sum, current_expval);
*/
    }

  pop->select_state++;

  selectval = random_double(pop->selectdata.current_expval)*pop->selectdata.mean;

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= pop->entity_iarray[pop->selectdata.marker]->fitness;

    } while (selectval>0.0);

  *mother = pop->entity_iarray[pop->selectdata.marker];

  selectval = random_double(pop->selectdata.current_expval)*pop->selectdata.mean;

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= pop->entity_iarray[pop->selectdata.marker]->fitness;

    } while (selectval>0.0);

  *father = pop->entity_iarray[pop->selectdata.marker];

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


/**********************************************************************
  ga_select_two_roulette_rebased()
  synopsis:	Fitness-proportionate roulette wheel selection.
		If pop->mutation_ratio is 1.0, the wheel will be spun
		pop->orig_size times, which matches Holland's original
		implementation.
		This version can cope with a mixture of positive and
		negative fitness scores.  The single least fit entity
		will never be selected, but this is not considered a
		problem.
                Mother and father may be the same.
  parameters:
  return:	
  last updated: 28 Jun 2004
 **********************************************************************/

boolean ga_select_two_roulette_rebased( population *pop,
                                        entity **mother, entity **father )
  {
  double	selectval;		/* Select when this reaches zero. */

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

  *mother = NULL;

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

  if (pop->select_state == 0)
    { /* First call of this generation. */
    gaul_select_stats(pop, &(pop->selectdata.mean), &(pop->selectdata.stddev), &(pop->selectdata.sum));
    pop->selectdata.marker = random_int(pop->orig_size);
    pop->selectdata.minval = pop->entity_iarray[pop->orig_size-1]->fitness;
    pop->selectdata.mean -= pop->selectdata.minval;
    if (ISTINY(pop->selectdata.mean)) die("Degenerate population?");
    pop->selectdata.current_expval = (pop->selectdata.sum-pop->selectdata.minval*pop->orig_size)/pop->selectdata.mean;
    }

  pop->select_state++;

  selectval = random_double(pop->selectdata.current_expval);

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= (pop->entity_iarray[pop->selectdata.marker]->fitness-pop->selectdata.minval)/pop->selectdata.mean;

    } while (selectval>0.0);

  *mother = pop->entity_iarray[pop->selectdata.marker];

  selectval = random_double(pop->selectdata.current_expval);

  do
    {
    pop->selectdata.marker++;

    if (pop->selectdata.marker >= pop->orig_size)
      pop->selectdata.marker=0;

    selectval -= (pop->entity_iarray[pop->selectdata.marker]->fitness-pop->selectdata.minval)/pop->selectdata.mean;

    } while (selectval>0.0);

  *father = pop->entity_iarray[pop->selectdata.marker];

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


/**********************************************************************
  ga_select_one_sus()
  synopsis:	Stochastic Universal Sampling selection.
  		pop->mutation_ratio multiplied by pop->orig_size gives
		the number of selections which will be performed.
		This version is for fitness values where 0.0 is bad and
		large positive values are good.  Negative values will
		severely mess-up the algorithm.
  parameters:
  return:	
  last updated: 28 Jun 2004
 **********************************************************************/

boolean ga_select_one_sus(population *pop, entity **mother)
  {
  double	sum;			/* Fitness total. */

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

  *mother = NULL;

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

  if (pop->select_state == 0)
    { /* First call of this generation. */
    pop->selectdata.num_to_select = (pop->orig_size*pop->mutation_ratio);
    sum = gaul_select_sum_fitness(pop);
    pop->selectdata.step = sum/(pop->orig_size*pop->mutation_ratio);
    pop->selectdata.offset1 = random_double(pop->selectdata.step);
    pop->selectdata.current1=0;
    }
  else if (pop->select_state>pop->selectdata.num_to_select)
    {
    return TRUE;
    }
  else