ga_core.c

http://gaul.sourceforge.net/ 这里大部分人讨论的是在Matlab里实现GA的toolbox.以上为一个GA的C语言的软件包.如果你想利用GA做优化算法,非常有用.而且有

  entity	*adam;		/* New population member. */

  plog(LOG_DEBUG, "Population seeding by user-defined genesis.");

  if ( !pop ) die("Null pointer to population structure passed.");
  if ( !pop->seed ) die("Population seeding function is not defined.");

/* NOTE: OpenMP adjusts order of seeding operations here, and therefore alters results. */
#pragma omp parallel for \
   if (GAUL_DETERMINISTIC_OPENMP==0) \
   shared(pop, num) private(i,adam) \
   schedule(static)
  for (i=0; i<num; i++)
    {
/*printf("DEBUG: ga_population_seed() parallel for %d on %d/%d.\n", i, omp_get_thread_num(), omp_get_num_threads());*/
    adam = ga_get_free_entity(pop);
    pop->seed(pop, adam);
    }

  return TRUE;
  }


/**********************************************************************
  ga_population_seed()
  synopsis:	Fills all entities in a population structure with
		genes from a user-specified function.
  parameters:	population
  return:	boolean success.
  last updated: 24 Feb 2005
 **********************************************************************/

boolean ga_population_seed(population *pop)
  {

  plog(LOG_DEBUG, "Population seeding by user-defined genesis.");

  return gaul_population_fill(pop, pop->stable_size);
  }


/**********************************************************************
  ga_funclookup_ptr_to_id()
  synopsis:     Assign a unique id to a callback function for
		population disk format from its pointer.
  parameters:
  return:
  last updated: 10 Apr 2003
 **********************************************************************/

int ga_funclookup_ptr_to_id(void *func)
  {
  int	id=1;	/* Index into lookup table. */

  if ( !func ) return 0;

  while (lookup[id].func_ptr != NULL &&
         func != lookup[id].func_ptr)
    id++;

#if GA_DEBUG>2
  printf("Function id is %d\n", id);
#endif

  return lookup[id].func_ptr!=NULL?id:-1;
  }


/**********************************************************************
  ga_funclookup_label_to_id()
  synopsis:     Assign a unique id to a callback function for
		population disk format from its label.
  parameters:
  return:
  last updated: 10 Apr 2003
 **********************************************************************/

int ga_funclookup_label_to_id(char *funcname)
  {
  int	id=1;	/* Index into lookup table. */

  if ( !funcname ) return 0;

  while (lookup[id].funcname != NULL &&
         strcmp(funcname, lookup[id].funcname) != 0)
    id++;

#if GA_DEBUG>2
  printf("Function id is %d\n", id);
#endif

  return lookup[id].func_ptr!=NULL?id:-1;
  }


/**********************************************************************
  ga_funclookup_label_to_ptr()
  synopsis:     Return the pointer to a callback function
		from its label.
  parameters:
  return:
  last updated: 10 Apr 2003
 **********************************************************************/

void *ga_funclookup_label_to_ptr(char *funcname)
  {
  int	id=1;	/* Index into lookup table. */

  if ( !funcname ) return 0;

  while (lookup[id].funcname != NULL &&
         strcmp(funcname, lookup[id].funcname) != 0)
    id++;

#if GA_DEBUG>2
  printf("Function id is %d\n", id);
#endif

  return lookup[id].func_ptr;
  }


/**********************************************************************
  ga_funclookup_id_to_ptr()
  synopsis:     Returns the pointer to a function from its unique id.
  parameters:
  return:
  last updated: 10 Apr 2003
 **********************************************************************/

void *ga_funclookup_id_to_ptr(int id)
  {

#if GA_DEBUG>2
  printf("Looking for function with id %d\n", id);
#endif

  return (id<0)?NULL:lookup[id].func_ptr;
  }


/**********************************************************************
  ga_funclookup_id_to_label()
  synopsis:     Returns the label for a function from its unique id.
  parameters:
  return:
  last updated: 10 Apr 2003
 **********************************************************************/

char *ga_funclookup_id_to_label(int id)
  {

#if GA_DEBUG>2
  printf("Looking for function with id %d\n", id);
#endif

  return (id<0)?NULL:lookup[id].funcname;
  }


/**********************************************************************
  ga_entity_evaluate()
  synopsis:	Score a single entity.
  parameters:	population *pop
		entity *entity
  return:	double			the fitness
  last updated: 01 Jul 2004
 **********************************************************************/

double ga_entity_evaluate(population *pop, entity *entity)
  {

  if ( !pop ) die("Null pointer to population structure passed.");
  if ( !entity ) die("Null pointer to entity structure passed.");
  if ( !pop->evaluate ) die("Evaluation callback not defined.");

  if (pop->evaluate(pop, entity) == FALSE)
    entity->fitness = GA_MIN_FITNESS;

  return entity->fitness;
  }


/**********************************************************************
  ga_population_score_and_sort()
  synopsis:	Score and sort entire population.  This is probably
		a good idea after changing the fitness function!
		Note: remember to define the callback functions first.
  parameters:
  return:
  last updated: 28/02/01
 **********************************************************************/

boolean ga_population_score_and_sort(population *pop)
  {
  int		i;		/* Loop variable over all entities. */
#if GA_DEBUG>2
  double	origfitness;	/* Stored fitness value. */
#endif

/* Checks. */
  if ( !pop ) die("Null pointer to population structure passed.");
  if ( !pop->evaluate ) die("Evaluation callback not defined.");

/*
 * Score and sort all of the population members.
 *
 * Note that this will (potentially) use a huge amount of memory more
 * than the original population data if the userdata hasn't been maintained.
 * Each chromosome is decoded separately, whereas originally many
 * degenerate chromosomes would share their userdata elements.
 */
#pragma omp parallel for \
   shared(pop) private(i) \
   schedule(static)
  for (i=0; i<pop->size; i++)
    {
#if GA_DEBUG>2
    origfitness = pop->entity_iarray[i]->fitness;
#endif
    pop->evaluate(pop, pop->entity_iarray[i]);

#if GA_DEBUG>2
    if (origfitness != pop->entity_iarray[i]->fitness)
      plog(LOG_NORMAL,
           "Recalculated fitness %f doesn't match stored fitness %f for entity %d.",
           pop->entity_iarray[i]->fitness, origfitness, i);
#endif
    }

  sort_population(pop);

  return TRUE;
  }


/**********************************************************************
  ga_population_sort()
  synopsis:	Sort entire population (i.e. ensure that the entities
		are correctly ordered in ranking array -- currently
		rank is defined only by fitness).
		Note: remember to define the callback functions first.
  parameters:
  return:
  last updated: 30 May 2002
 **********************************************************************/

boolean ga_population_sort(population *pop)
  {

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

  sort_population(pop);

  return TRUE;
  }


#if 0
FIXME: The following 3 functions need to be fixed for the new absracted chromosome types.
/**********************************************************************
  ga_population_convergence_genotypes()
  synopsis:	Determine ratio of converged genotypes in population.
  parameters:
  return:
  last updated: 31/05/01
 **********************************************************************/

double ga_population_convergence_genotypes( population *pop )
  {
  int		i, j;		/* Loop over pairs of entities. */
  int		count=0, converged=0;	/* Number of comparisons, matches. */

  if ( !pop ) die("Null pointer to population structure passed.");
  if (pop->size < 1) die("Pointer to empty population structure passed.");

  for (i=1; i<pop->size; i++)
    {
    for (j=0; j<i; j++)
      {
      if (ga_compare_genome(pop, pop->entity_iarray[i], pop->entity_iarray[j]))
        converged++;
      count++;
      }
    }

  return (double) converged/count;
  }


/**********************************************************************
  ga_population_convergence_chromosomes()
  synopsis:	Determine ratio of converged chromosomes in population.
  parameters:
  return:
  last updated: 31/05/01
 **********************************************************************/

double ga_population_convergence_chromosomes( population *pop )
  {
  int		i, j;		/* Loop over pairs of entities. */
  int		k;		/* Loop over chromosomes. */
  int		count=0, converged=0;	/* Number of comparisons, matches. */

  if ( !pop ) die("Null pointer to population structure passed.");
  if (pop->size < 1) die("Pointer to empty population structure passed.");

  for (i=1; i<pop->size; i++)
    {
    for (j=0; j<i; j++)
      {
      for (k=0; k<pop->num_chromosomes; k++)
        {
/* FIXME: Not counted efficiently: */
        if (ga_count_match_alleles( pop->len_chromosomes,
                                    pop->entity_iarray[i]->chromosome[k],
                                    pop->entity_iarray[j]->chromosome[k] ) == pop->len_chromosomes)
          converged++;
        count++;
        }
      }
    }

  return (double) converged/count;
  }


/**********************************************************************
  ga_population_convergence_alleles()
  synopsis:	Determine ratio of converged alleles in population.
  parameters:
  return:
  last updated: 31/05/01
 **********************************************************************/

double ga_population_convergence_alleles( population *pop )
  {
  int		i, j;		/* Loop over pairs of entities. */
  int		k;		/* Loop over chromosomes. */
  int		count=0, converged=0;	/* Number of comparisons, matches. */

  if ( !pop ) die("Null pointer to population structure passed.");
  if (pop->size < 1) die("Pointer to empty population structure passed.");

  for (i=1; i<pop->size; i++)
    {
    for (j=0; j<i; j++)
      {
      for (k=0; k<pop->num_chromosomes; k++)
        {
        converged+=ga_count_match_alleles( pop->len_chromosomes,
                                           pop->entity_iarray[i]->chromosome[k],
                                           pop->entity_iarray[j]->chromosome[k] );
        count+=pop->len_chromosomes;
        }
      }
    }

  return (double) converged/count;
  }
#endif


/**********************************************************************
  ga_get_entity_rank()
  synopsis:	Gets an entity's rank (subscript into entity_iarray of
		the population).  This is not necessarily the fitness
		rank unless the population has been sorted.
  parameters:
  return:
  last updated: 22/01/01
 **********************************************************************/

int ga_get_entity_rank(population *pop, entity *e)
  {
  int	rank=0;		/* The rank. */

  while (rank < pop->size)
    {
    if (pop->entity_iarray[rank] == e) return rank;
    rank++;
    }

  return -1;
  }


/**********************************************************************
  ga_get_entity_rank_from_id()
  synopsis:	Gets an entity's rank (subscript into entity_iarray of
		the population).  This is not necessarily the fitness
		rank unless the population has been sorted.
  parameters:
  return:
  last updated: 18 Mar 2002
 **********************************************************************/

int ga_get_entity_rank_from_id(population *pop, int id)
  {
  int	rank=0;		/* The rank. */

  while (rank < pop->size)