ga_core.c

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

    {
    if (pop->entity_iarray[rank] == pop->entity_array[id]) return rank;
    rank++;
    }

  return -1;
  }


/**********************************************************************
  ga_get_entity_id_from_rank()
  synopsis:	Gets an entity's id from its rank.
  parameters:
  return:
  last updated: 18 Mar 2002
 **********************************************************************/

int ga_get_entity_id_from_rank(population *pop, int rank)
  {
  int	id=0;		/* The entity's index. */

  while (id < pop->max_size)
    {
    if (pop->entity_array[id] == pop->entity_iarray[rank]) return id;
    id++;
    }

  return -1;
  }


/**********************************************************************
  ga_get_entity_id()
  synopsis:	Gets an entity's internal index.
  parameters:	population *pop
		entity *e
  return:	entity id
  last updated: 18 Mar 2002
 **********************************************************************/

int ga_get_entity_id(population *pop, entity *e)
  {
  int	id=0;	/* The index. */

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

  while (id < pop->max_size)
    {
    if (pop->entity_array[id] == e) return id;
    id++;
    }

  return -1;
  }


/**********************************************************************
  ga_get_entity_from_id()
  synopsis:	Gets a pointer to an entity from it's internal index
		(subscript in the entity_array array).
  parameters:
  return:
  last updated: 29 Apr 2002
 **********************************************************************/

entity *ga_get_entity_from_id(population *pop, const unsigned int id)
  {
  if ( !pop ) die("Null pointer to population structure passed.");

  if ( id>pop->max_size ) return NULL;

  return pop->entity_array[id];
  }


/**********************************************************************
  ga_get_entity_from_rank()
  synopsis:	Gets a pointer to an entity from it's internal rank.
		(subscript into the entity_iarray buffer).
		Note that this only relates to fitness ranking if
		the population has been properly sorted.
  parameters:
  return:
  last updated: 29 Apr 2004
 **********************************************************************/

entity *ga_get_entity_from_rank(population *pop, const unsigned int rank)
  {
  if ( !pop ) die("Null pointer to population structure passed.");

  if ( rank>pop->size ) return NULL;

  return pop->entity_iarray[rank];
  }


/**********************************************************************
  ga_entity_setup()
  synopsis:	Prepares a pre-allocated entity structure for use.
		Chromosomes are allocated, but will contain garbage.
  parameters:
  return:
  last updated: 18 Mar 2002
 **********************************************************************/

static boolean ga_entity_setup(population *pop, entity *joe)
  {

  if (!joe)
    die("Null pointer to entity structure passed.");
  if (!pop->chromosome_constructor)
    die("Chromosome constructor not defined.");

/* Allocate chromosome structures. */
  joe->chromosome = NULL;
  pop->chromosome_constructor(pop, joe);

/* Physical characteristics currently undefined. */
  joe->data=NULL;

/* No fitness evaluated yet. */
  joe->fitness=GA_MIN_FITNESS;

  return TRUE;
  }


/**********************************************************************
  ga_entity_dereference_by_rank()
  synopsis:	Marks an entity structure as unused.
		Deallocation is expensive.  It is better to re-use this
		memory.  So, that is what we do.
		Any contents of entities data field are freed.
		If rank is known, this is much quicker than the plain
		ga_entity_dereference() function.
		Note, no error checking in the interests of speed.
  parameters:
  return:
  last updated:	19 Mar 2002
 **********************************************************************/

boolean ga_entity_dereference_by_rank(population *pop, int rank)
  {
  int		i;	/* Loop variable over the indexed array. */
  entity	*dying=pop->entity_iarray[rank];	/* Dead entity. */

  if (!dying) die("Invalid entity rank");

/* Clear user data. */
  if (dying->data)
    {
    destruct_list(pop, dying->data);
    dying->data=NULL;
    }

  THREAD_LOCK(pop->lock);

/* Population size is one less now! */
  pop->size--;

/* Deallocate chromosomes. */
  if (dying->chromosome) pop->chromosome_destructor(pop, dying);

/* Update entity_iarray[], so there are no gaps! */
  for (i=rank; i<pop->size; i++)
    pop->entity_iarray[i] = pop->entity_iarray[i+1];

  pop->entity_iarray[pop->size] = NULL;

/* Release index. */
  i = ga_get_entity_id(pop, dying);
  pop->entity_array[ga_get_entity_id(pop, dying)] = NULL;

  THREAD_UNLOCK(pop->lock);

/* Release memory. */
  mem_chunk_free(pop->entity_chunk, dying);

/*  printf("ENTITY %d DEREFERENCED. New pop size = %d\n", i, pop->size);*/

  return TRUE;
  }


/**********************************************************************
  ga_entity_dereference_by_id()
  synopsis:	Marks an entity structure as unused.
		Deallocation is expensive.  It is better to re-use this
		memory.  So, that is what we do.
		Any contents of entities data field are freed.
		If rank is known, this is much quicker than the plain
		ga_entity_dereference() function, while this index
		based version is still almost as fast.
		Note, no error checking in the interests of speed.
  parameters:
  return:
  last updated:	19 Mar 2002
 **********************************************************************/

boolean ga_entity_dereference_by_id(population *pop, int id)
  {
  int		i;	/* Loop variable over the indexed array. */
  entity	*dying=pop->entity_array[id];	/* Dead entity. */

  if (!dying) die("Invalid entity index");

/* Clear user data. */
  if (dying->data)
    {
    destruct_list(pop, dying->data);
    dying->data=NULL;
    }

  THREAD_LOCK(pop->lock);

/* Population size is one less now! */
  pop->size--;

/* Update entity_iarray[], so there are no gaps! */
  for (i=ga_get_entity_rank(pop, dying); i<pop->size; i++)
    pop->entity_iarray[i] = pop->entity_iarray[i+1];

  pop->entity_iarray[pop->size] = NULL;

/* Deallocate chromosomes. */
  if (dying->chromosome) pop->chromosome_destructor(pop, dying);

  THREAD_UNLOCK(pop->lock);

/* Release index. */
  pop->entity_array[id] = NULL;

/* Release memory. */
  mem_chunk_free(pop->entity_chunk, dying);

/*  printf("ENTITY %d DEREFERENCED. New pop size = %d\n", id, pop->size);*/

  return TRUE;
  }


/**********************************************************************
  ga_entity_dereference()
  synopsis:	Marks an entity structure as unused.
		Deallocation is expensive.  It is better to re-use this
		memory.  So, that is what we do.
		Any contents of entities data field are freed.
		If rank is known, the above
		ga_entity_dereference_by_rank() or
		ga_entity_dereference_by_id() functions are much
		faster.
  parameters:
  return:
  last updated:	16/03/01
 **********************************************************************/

boolean ga_entity_dereference(population *pop, entity *dying)
  {
  return ga_entity_dereference_by_rank(pop, ga_get_entity_rank(pop, dying));
  }


/**********************************************************************
  ga_entity_clear_data()
  synopsis:	Clears some of the entity's data.  Safe if data doesn't
		exist anyway.
  parameters:
  return:
  last updated: 20/12/00
 **********************************************************************/

void ga_entity_clear_data(population *p, entity *entity, const int chromosome)
  {
  SLList	*tmplist;
  vpointer	data;		/* Data in item. */

  if (entity->data)
    {
    tmplist = slink_nth(entity->data, chromosome);
    if ( (data = slink_data(tmplist)) )
      {
      p->data_destructor(data);
      tmplist->data=NULL;
      }
    }

  return;
  }


/**********************************************************************
  ga_entity_blank()
  synopsis:	Clears the entity's data.
		Equivalent to an optimised ga_entity_dereference()
		followed by ga_get_free_entity().  It is much more
		preferable to use this fuction!
		Chromosomes are gaurenteed to be intact, but may be
		overwritten by user.
  parameters:
  return:
  last updated: 18/12/00
 **********************************************************************/

void ga_entity_blank(population *p, entity *entity)
  {
  if (entity->data)
    {
    destruct_list(p, entity->data);
    entity->data=NULL;
    }

  entity->fitness=GA_MIN_FITNESS;

/*  printf("ENTITY %d CLEARED.\n", ga_get_entity_id(p, entity));*/

  return;
  }


/**********************************************************************
  ga_get_free_entity()
  synopsis:	Returns pointer to an unused entity structure from the
		population's entity pool.  Increments population size
		too.
  parameters:	population *pop
  return:	entity *entity
  last updated: 18 Mar 2002
 **********************************************************************/

entity *ga_get_free_entity(population *pop)
  {
  int		new_max_size;	/* Increased maximum number of entities. */
  int		i;
  entity	*fresh;		/* Unused entity structure. */

/*
  plog(LOG_DEBUG, "Locating free entity structure.");
*/
  THREAD_LOCK(pop->lock);

/*
 * Do we have room for any new structures?
 */
  if (pop->max_size == (pop->size+1))
    {	/* No, so allocate some more space. */
    plog(LOG_VERBOSE, "No unused entities available -- allocating additional structures.");

    new_max_size = (pop->max_size * 3)/2 + 1;
    pop->entity_array = s_realloc(pop->entity_array, new_max_size*sizeof(entity*));
    pop->entity_iarray = s_realloc(pop->entity_iarray, new_max_size*sizeof(entity*));

    for (i=pop->max_size; i<new_max_size; i++)
      {
      pop->entity_array[i] = NULL;
      pop->entity_iarray[i] = NULL;
      }

    pop->max_size = new_max_size;
    pop->free_index = new_max_size-1;
    }

/* Find unused entity index. */
  while (pop->entity_array[pop->free_index]!=NULL)
    {
    if (pop->free_index == 0) pop->free_index=pop->max_size;
    pop->free_index--;
    }

/* Prepare it. */
  fresh = (entity *)mem_chunk_alloc(pop->entity_chunk);

  pop->entity_array[pop->free_index] = fresh;
  ga_entity_setup(pop, fresh);

/* Store in lowest free slot in entity_iarray */
  pop->entity_iarray[pop->size] = fresh;

/* Population is bigger now! */
  pop->size++;

  THREAD_UNLOCK(pop->lock);

/*  printf("ENTITY %d ALLOCATED.\n", pop->free_index);*/

  return fresh;
  }


/**********************************************************************
  ga_copy_data()
  synopsis:	Copy one chromosome's portion of the data field of an
		entity structure to another entity structure.  (Copies
		the portion of the phenome relating to that chromosome)
		'Copies' NULL data safely.
		The destination chromosomes must be filled in order.
		If these entities are in differing populations, no
		problems will occur provided that the
		data_ref_incrementor callbacks are identical or at least
		compatible.
  parameters:
  return:
  last updated: 18/12/00