ga_core.c

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

 **********************************************************************/

boolean ga_copy_data(population *pop, entity *dest, entity *src, const int chromosome)
  {
  vpointer	tmpdata=NULL;	/* Temporary pointer. */

  if ( !src || !(tmpdata = slink_nth_data(src->data, chromosome)) )
    {
    dest->data = slink_append(dest->data, NULL);
    }
  else
    {
    dest->data = slink_append(dest->data, tmpdata);
    pop->data_ref_incrementor(tmpdata);
    }

  return TRUE;
  }


/**********************************************************************
  ga_copy_chromosome()
  synopsis:	Copy one chromosome between entities.
		If these entities are in differing populations, no
		problems will occur provided that the chromosome
		datatypes match up.
  parameters:
  return:
  last updated: 18/12/00
 **********************************************************************/

static boolean ga_copy_chromosome( population *pop, entity *dest, entity *src,
                            const int chromosome )
  {

  pop->chromosome_replicate(pop, src, dest, chromosome);

  return TRUE;
  }


/**********************************************************************
  ga_entity_copy_all_chromosomes()
  synopsis:	Copy genetic data between entity structures.
		If these entities are in differing populations, no
		problems will occur provided that the chromosome
		properties are identical.
  parameters:
  return:
  last updated: 20/12/00
 **********************************************************************/

boolean ga_entity_copy_all_chromosomes(population *pop, entity *dest, entity *src)
  {
  int		i;		/* Loop variable over all chromosomes. */

  /* Checks */
  if (!dest || !src) die("Null pointer to entity structure passed");

/*
 * Ensure destination structure is not likely be already in use.
 */
  if (dest->data) die("Why does this entity already contain data?");

/*
 * Copy genetic data.
 */
  for (i=0; i<pop->num_chromosomes; i++)
    {
    ga_copy_data(pop, dest, src, i);		/* Phenome. */
    ga_copy_chromosome(pop, dest, src, i);	/* Genome. */
    }

  return TRUE;
  }


/**********************************************************************
  ga_entity_copy_chromosome()
  synopsis:	Copy chromosome and user data between entity
		structures.
  parameters:
  return:
  last updated: 22/01/01
 **********************************************************************/

boolean ga_entity_copy_chromosome(population *pop, entity *dest, entity *src, int chromo)
  {

/* Checks. */
  if (!dest || !src) die("Null pointer to entity structure passed");
  if (chromo<0 || chromo>=pop->num_chromosomes) die("Invalid chromosome number.");

/*
 * Ensure destination structure is not likely be already in use.
 */
  if (dest->data) die("Why does this entity already contain data?");

/*
 * Copy genetic and associated structural data (phenomic data).
 */
/*
  memcpy(dest->chromosome[chromo], src->chromosome[chromo],
           pop->len_chromosomes*sizeof(int));
*/
  ga_copy_data(pop, dest, src, chromo);
  ga_copy_chromosome(pop, dest, src, chromo);

  return TRUE;
  }


/**********************************************************************
  ga_entity_copy()
  synopsis:	Copy entire entity structure.  This is safe
		for copying between populations... provided that they
		are compatible.
  parameters:
  return:
  last updated:	22/01/01
 **********************************************************************/

boolean ga_entity_copy(population *pop, entity *dest, entity *src)
  {

  ga_entity_copy_all_chromosomes(pop, dest, src);
  dest->fitness = src->fitness;

  return TRUE;
  }


/**********************************************************************
  ga_entity_clone()
  synopsis:	Clone an entity structure.
		Safe for cloning into a different population, provided
		that the populations are compatible.
  parameters:	population	*pop	Population.
		entity	*parent		The original entity.
  return:	entity	*dolly		The new entity.
  last updated:	07/07/01
 **********************************************************************/

entity *ga_entity_clone(population *pop, entity *parent)
  {
  entity	*dolly;		/* The clone. */

  dolly = ga_get_free_entity(pop);

  ga_entity_copy_all_chromosomes(pop, dolly, parent);
  dolly->fitness = parent->fitness;

  return dolly;
  }


/**********************************************************************
  Network communication (population/entity migration) functions.
 **********************************************************************/

#if W32_CRIPPLED != 1 && HAVE_MPI == 1

/*
 * Convenience wrapper around MPI_COmm_rank().
 */
static int mpi_get_rank(void)
  {
  int	rank;

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);

  return rank;
  }


/*
 * Convenience wrapper around MPI_Recv().
 */
static boolean mpi_receive(void *buf, const int count,
                               const MPI_Datatype type, const int node,
                               const int tag)
  {
  MPI_Status	status;		/* MPI status struct. */

  /* Checks */
  if (!buf) die("Null pointer to (void *) buffer passed.");
  if (mpi_get_rank()==node) die("Why should I send a message to myself?");

  MPI_Recv( buf, count, type, node, tag, MPI_COMM_WORLD, &status );

  /* FIXME: Should check the status structure here! */

  return TRUE;
  }


/**********************************************************************
  ga_population_send_by_mask()
  synopsis:	Send selected entities from a population to another
		processor.  Only fitness and chromosomes sent.
  parameters:
  return:
  last updated: 31 Jan 2002
 **********************************************************************/

void ga_population_send_by_mask( population *pop, int dest_node, int num_to_send, boolean *send_mask )
  {
  int		i;
  int		count=0;
  int		len=0;		/* Length of buffer to send. */
  unsigned int	max_len=0;
  byte		*buffer=NULL;

/*
 * Send number of entities.
 */
  MPI_Send(&num_to_send, 1, MPI_INT, dest_node, GA_TAG_NUMENTITIES, MPI_COMM_WORLD);

/* 
 * Slight knudge to determine length of buffer.  Should have a more
 * elegant approach for this.
 * Sending this length here should not be required at all.
 */
  len = (int) pop->chromosome_to_bytes(pop, pop->entity_iarray[0], &buffer, &max_len);
  MPI_Send(&len, 1, MPI_INT, dest_node, GA_TAG_ENTITYLEN, MPI_COMM_WORLD);

/*
  printf("DEBUG: Node %d sending %d entities of length %d to %d\n",
           mpi_get_rank(), num_to_send, len, dest_node);
*/

/*
 * Send required entities individually.
 */
  for (i=0; i<pop->size && count<num_to_send; i++)
    {
    if (send_mask[i])
      {
/* printf("DEBUG: Node %d sending entity %d/%d (%d/%d) with fitness %f\n",
             mpi_get_rank(), count, num_to_send, i, pop->size, pop->entity_iarray[i]->fitness); */
      MPI_Send(&(pop->entity_iarray[i]->fitness), 1, MPI_DOUBLE, dest_node, GA_TAG_ENTITYFITNESS, MPI_COMM_WORLD);
      if (len != (int) pop->chromosome_to_bytes(pop, pop->entity_iarray[i], &buffer, &max_len))
	die("Internal length mismatch");
      MPI_Send(buffer, len, MPI_BYTE, dest_node, GA_TAG_ENTITYCHROMOSOME, MPI_COMM_WORLD);
      count++;
      }
    }

  if (count != num_to_send)
    die("Incorrect value for num_to_send");

/*
 * We only need to deallocate the buffer if it was allocated (i.e. if
 * the "chromosome_to_bytes" callback set max_len).
 */
  if (max_len!=0) s_free(buffer);

/*  printf("DEBUG: Node %d finished sending\n", mpi_get_rank());*/

  return;
  }


/**********************************************************************
  ga_population_send_every()
  synopsis:	Send all entities from a population to another
		processor.  Only fitness and chromosomes sent.
  parameters:
  return:
  last updated: 31 Jan 2002
 **********************************************************************/

void ga_population_send_every( population *pop, int dest_node )
  {
  int		i;
  int		len;			/* Length of buffer to send. */
  unsigned int	max_len=0;		/* Maximum length of buffer. */
  byte		*buffer=NULL;

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

/*
 * Send number of entities.
 */
  MPI_Send(&(pop->size), 1, MPI_INT, dest_node, GA_TAG_NUMENTITIES, MPI_COMM_WORLD);

/* 
 * Slight kludge to determine length of buffer.  Should have a more
 * elegant approach for this.
 * Sending this length here should not be required at all.
 */
  len = (int) pop->chromosome_to_bytes(pop, pop->entity_iarray[0], &buffer, &max_len);
  MPI_Send(&len, 1, MPI_INT, dest_node, GA_TAG_ENTITYLEN, MPI_COMM_WORLD);

/*
 * Send all entities individually.
 */
  for (i=0; i<pop->size; i++)
    {
    MPI_Send(&(pop->entity_iarray[i]->fitness), 1, MPI_DOUBLE, dest_node, GA_TAG_ENTITYFITNESS, MPI_COMM_WORLD);
    if (len != (int) pop->chromosome_to_bytes(pop, pop->entity_iarray[i], &buffer, &max_len))
      die("Internal length mismatch");
    MPI_Send(buffer, len, MPI_BYTE, dest_node, GA_TAG_ENTITYCHROMOSOME, MPI_COMM_WORLD);
    }

/*
 * We only need to deallocate the buffer if it was allocated (i.e. if
 * the "chromosome_to_bytes" callback set max_len).
 */
  if (max_len!=0) s_free(buffer);

  return;
  }


/**********************************************************************
  ga_population_append_receive()
  synopsis:	Recieve a set of entities from a population on another
		processor and append them to a current population.
		Only fitness and chromosomes received.
  parameters:
  return:
  last updated: 31 Jan 2002
 **********************************************************************/

void ga_population_append_receive( population *pop, int src_node )
  {
  int		i;
  int		len=0;			/* Length of buffer to receive. */
  byte		*buffer;		/* Receive buffer. */
  int		num_to_recv;		/* Number of entities to receive. */
  entity	*entity;		/* New entity. */

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

/*
 * Get number of entities to receive and the length of each.
 * FIXME: This length data shouldn't be needed!
 */
  mpi_receive(&num_to_recv, 1, MPI_INT, src_node, GA_TAG_NUMENTITIES);
  mpi_receive(&len, 1, MPI_INT, src_node, GA_TAG_ENTITYLEN);

/*
  printf("DEBUG: Node %d anticipating %d entities of length %d from %d\n",
           mpi_get_rank(), num_to_recv, len, src_node);
*/

  if (num_to_recv>0)
    {
    buffer = s_malloc(len*sizeof(byte));

/*
 * Receive all entities individually.
 */
    for (i=0; i<num_to_recv; i++)
      {
      entity = ga_get_free_entity(pop);
      mpi_receive(&(entity->fitness), 1, MPI_DOUBLE, src_node, GA_TAG_ENTITYFITNESS);
      mpi_receive(buffer, len, MPI_BYTE, src_node, GA_TAG_ENTITYCHROMOSOME);
      pop->chromosome_from_bytes(pop, entity, buffer);
/*      printf("DEBUG: Node %d received entity %d/%d (%d) with fitness %f\n",
             mpi_get_rank(), i, num_to_recv, pop->size, entity->fitness);
 */
      }

    s_free(buffer);
    }

/*  printf("DEBUG: Node %d finished receiving\n", mpi_get_rank());*/

  return;
  }


/**********************************************************************
  ga_population_new_receive()
  synopsis:	Recieve a population structure (excluding actual
  		entities) from another processor.
		Note that the callbacks wiil need to be subsequently
		defined by the user.
  parameters:
  return:
  last updated: 16 Feb 2005
 **********************************************************************/

population *ga_population_new_receive( int src_node )
  {
  population *pop=NULL;

  plog(LOG_FIXME, "Function not fully implemented");

  mpi_receive(&(pop->stable_size), 1, MPI_INT, src_node, GA_TAG_POPSTABLESIZE);
  mpi_receive(&(pop->crossover_ratio), 1, MPI_DOUBLE, src_node, GA_TAG_POPCROSSOVER);
  mpi_receive(&(pop->mutation_ratio), 1, MPI_DOUBLE, src_node, GA_TAG_POPMUTATION);
  mpi_receive(&(pop->migration_ratio), 1, MPI_DOUBLE, src_node, GA_TAG_POPMIGRATION);
  mpi_receive(&(pop->allele_mutation_prob), 1, MPI_DOUBLE, src_node, GA_TAG_POPALLELEMUTPROB);
  mpi_receive(&(pop->allele_min_integer), 1, MPI_INT, src_node, GA_TAG_POPALLELEMININT);
  mpi_receive(&(pop->allele_max_integer), 1, MPI_INT, src_node, GA_TAG_POPALLELEMAXINT);
  mpi_receive(&(pop->allele_min_double), 1, MPI_DOUBLE, src_node, GA_TAG_POP