ga_select.c

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

    {
    pop->selectdata.offset1 += pop->selectdata.step;
    }

  while (pop->selectdata.offset1 > pop->entity_iarray[pop->selectdata.current1]->fitness)
    {
    pop->selectdata.offset1 -= pop->entity_iarray[pop->selectdata.current1]->fitness;
    pop->selectdata.current1++;
    if (pop->selectdata.current1 >= pop->orig_size)
      pop->selectdata.current1-=pop->orig_size;
    }

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

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_two_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_two_sus(population *pop, entity **mother, entity **father)
  {
  double	sum;			/* Fitness total. */
  int		*ordered;		/* Ordered indices. */
  int		i;			/* Loop variable over indices. */

  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->crossover_ratio);
    sum = gaul_select_sum_fitness(pop);
    pop->selectdata.step = sum/pop->selectdata.num_to_select;
    pop->selectdata.offset1 = pop->selectdata.offset2 = random_double(pop->selectdata.step);
    pop->selectdata.current1=0;
    pop->selectdata.current2=0;
    pop->selectdata.permutation=NULL;

/*
    if (pop->selectdata.permutation!=NULL)
      die("Internal error.  Permutation buffer not NULL.");
*/

    pop->selectdata.permutation = s_malloc(sizeof(int)*pop->orig_size);
    ordered = s_malloc(sizeof(int)*pop->orig_size);
    for (i=0; i<pop->orig_size;i++)
      ordered[i]=i;
    random_int_permutation(pop->orig_size, ordered, pop->selectdata.permutation);
    s_free(ordered);
    }
  else if (pop->select_state > pop->selectdata.num_to_select)
    {
    s_free(pop->selectdata.permutation);
    pop->selectdata.permutation=NULL;
    return TRUE;
    }
  else
    {
    pop->selectdata.offset1 += pop->selectdata.step;
    pop->selectdata.offset2 += pop->selectdata.step;
    }

  while (pop->selectdata.offset1 > pop->entity_iarray[pop->selectdata.current1]->fitness)
    {
    pop->selectdata.offset1 -= pop->entity_iarray[pop->selectdata.current1]->fitness;
    pop->selectdata.current1++;
    if (pop->selectdata.current1>=pop->orig_size) pop->selectdata.current1-=pop->orig_size;
    }

  while (pop->selectdata.offset2 > pop->entity_iarray[pop->selectdata.permutation[pop->selectdata.current2]]->fitness)
    {
    pop->selectdata.offset2 -= pop->entity_iarray[pop->selectdata.permutation[pop->selectdata.current2]]->fitness;
    pop->selectdata.current2++;
    if (pop->selectdata.current2>=pop->orig_size) pop->selectdata.current2-=pop->orig_size;
    }

  *mother = pop->entity_iarray[pop->selectdata.current1];
  *father = pop->entity_iarray[pop->selectdata.permutation[pop->selectdata.current2]];

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_one_sussq()
  synopsis:	Stochastic Universal Sampling selection using
		squared fitnesses.
  		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_sussq(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_sq_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
    {
    pop->selectdata.offset1 += pop->selectdata.step;
    }

  while (pop->selectdata.offset1 > pop->entity_iarray[pop->selectdata.current1]->fitness * pop->entity_iarray[pop->selectdata.current1]->fitness)
    {
    pop->selectdata.offset1 -= (pop->entity_iarray[pop->selectdata.current1]->fitness * pop->entity_iarray[pop->selectdata.current1]->fitness);
    pop->selectdata.current1++;
    if (pop->selectdata.current1>=pop->orig_size) pop->selectdata.current1-=pop->orig_size;
    }

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

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_two_sussq()
  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_two_sussq(population *pop, entity **mother, entity **father)
  {
  double	sum;			/* Fitness total. */
  int		*ordered;		/* Ordered indices. */
  int		i;			/* Loop variable over indices. */

  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->crossover_ratio);
    sum = gaul_select_sum_sq_fitness(pop);
    pop->selectdata.step = sum/pop->selectdata.num_to_select;
    pop->selectdata.offset1 = pop->selectdata.offset2 = random_double(pop->selectdata.step);
    pop->selectdata.current1=0;
    pop->selectdata.current2=0;
    pop->selectdata.permutation=NULL;

/*
    if (pop->selectdata.permutation!=NULL)
      die("Internal error.  Permutation buffer not NULL.");
*/

    pop->selectdata.permutation = s_malloc(sizeof(int)*pop->orig_size);
    ordered = s_malloc(sizeof(int)*pop->orig_size);
    for (i=0; i<pop->orig_size;i++)
      ordered[i]=i;
    random_int_permutation(pop->orig_size, ordered, pop->selectdata.permutation);
    s_free(ordered);
    }
  else if (pop->select_state>pop->selectdata.num_to_select)
    {
    s_free(pop->selectdata.permutation);
    pop->selectdata.permutation=NULL;
    return TRUE;
    }
  else
    {
    pop->selectdata.offset1 += pop->selectdata.step;
    pop->selectdata.offset2 += pop->selectdata.step;
    }

  while (pop->selectdata.offset1 > pop->entity_iarray[pop->selectdata.current1]->fitness * pop->entity_iarray[pop->selectdata.current1]->fitness)
    {
    pop->selectdata.offset1 -= (pop->entity_iarray[pop->selectdata.current1]->fitness * pop->entity_iarray[pop->selectdata.current1]->fitness);
    pop->selectdata.current1++;
    if (pop->selectdata.current1>=pop->orig_size)
      pop->selectdata.current1-=pop->orig_size;
    }

  while (pop->selectdata.offset2 > pop->entity_iarray[pop->selectdata.current2]->fitness * pop->entity_iarray[pop->selectdata.current2]->fitness)
    {
    pop->selectdata.offset2 -= (pop->entity_iarray[pop->selectdata.current2]->fitness * pop->entity_iarray[pop->selectdata.current2]->fitness);
    pop->selectdata.current2++;
    if (pop->selectdata.current2>=pop->orig_size) pop->selectdata.current2-=pop->orig_size;
    }

  *mother = pop->entity_iarray[pop->selectdata.current1];
  *father = pop->entity_iarray[pop->selectdata.permutation[pop->selectdata.current2]];

  pop->select_state++;

  return FALSE;
  }


/**********************************************************************
  ga_select_one_aggressive()
  synopsis:	Select an entity using a very aggressive procedure.
  parameters:
  return:	
  last updated: 18 Apr 2003
 **********************************************************************/

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

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

  pop->select_state++;

  *mother = pop->entity_iarray[random_int(1+pop->select_state%(pop->orig_size-1))];

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


/**********************************************************************
  ga_select_two_aggressive()
  synopsis:	Select a pair of entities, both by a very aggressive
		procedure.  The entities may be the same.
  parameters:
  return:	
  last updated: 18 Apr 2003
 **********************************************************************/

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

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

  pop->select_state++;

  *father = pop->entity_iarray[random_int(1+pop->select_state%(pop->orig_size-1))];
  *mother = pop->entity_iarray[random_int(1+pop->select_state%(pop->orig_size-1))];

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


/**********************************************************************
  ga_select_one_best()
  synopsis:	Select the best entity only.
  parameters:
  return:	
  last updated: 18 Apr 2003
 **********************************************************************/

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

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

  pop->select_state++;

  *mother = pop->entity_iarray[0];

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


/**********************************************************************
  ga_select_two_best()
  synopsis:	Select a pair of entities, one of which is random, the
                other is the best entity.
  parameters:
  return:	
  last updated: 18 Apr 2003
 **********************************************************************/

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

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

  pop->select_state++;

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

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


/**********************************************************************
  ga_select_one_linearrank()
  synopsis:	Select an entity based on linear probability
		distribution with respect to rank.
  parameters:
  return:	
  last updated: 19 Mar 2004
 **********************************************************************/

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

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

  pop->select_state++;

  *mother = pop->entity_iarray[(int)((1.0-sqrt(random_unit_uniform()))*pop->orig_size)];

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


/**********************************************************************
  ga_select_two_linearrank()
  synopsis:	Select two entities based on linear probability
		distribution with respect to rank.
  parameters:
  return:	
  last updated: 19 Mar 2004
 **********************************************************************/

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

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

  pop->select_state++;

  *mother = pop->entity_iarray[(int)((1.0-sqrt(random_unit_uniform()))*pop->orig_size)];
  do
    {
    *father = pop->entity_iarray[(int)((1.0-sqrt(random_unit_uniform()))*pop->orig_size)];
    } while (*mother == *father);

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


/**********************************************************************
  ga_select_one_roundrobin()
  synopsis:	Select an entities in a round-robin fashion.
  parameters:
  return:	
  last updated: 23 Aug 2004
 **********************************************************************/

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

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

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

  pop->select_state++;

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