ga_utility.c

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

			GAdata_ref_incrementor	data_ref_incrementor,
			GAevaluate		evaluate,
			GAseed			seed,
			GAadapt			adapt,
			GAselect_one		select_one,
			GAselect_two		select_two,
			GAmutate		mutate,
			GAcrossover		crossover,
			GAreplace		replace,
			vpointer		userdata )
  {
  population	*pop;	/* The new population structure. */

  plog(LOG_VERBOSE, "Genesis is beginning!");

/*
 * Initialise OpenMP code.
 */
  ga_init_openmp();

/*
 * Allocate and initialise a new population.
 * This call also sets this as the active population.
 */
  if ( !(pop = ga_population_new( population_size, num_chromo, len_chromo )) )
    return NULL;

/*
 * Assign population's user data.
 */
  pop->data = userdata;

/*
 * Define some callback functions.
 */
  pop->generation_hook = generation_hook;
  pop->iteration_hook = iteration_hook;

  pop->data_destructor = data_destructor;
  pop->data_ref_incrementor = data_ref_incrementor;

  pop->chromosome_constructor = ga_chromosome_boolean_allocate;
  pop->chromosome_destructor = ga_chromosome_boolean_deallocate;
  pop->chromosome_replicate = ga_chromosome_boolean_replicate;
  pop->chromosome_to_bytes = ga_chromosome_boolean_to_bytes;
  pop->chromosome_from_bytes = ga_chromosome_boolean_from_bytes;
  pop->chromosome_to_string = ga_chromosome_boolean_to_string;

  pop->evaluate = evaluate;
  pop->seed = seed;
  pop->adapt = adapt;
  pop->select_one = select_one;
  pop->select_two = select_two;
  pop->mutate = mutate;
  pop->crossover = crossover;
  pop->replace = replace;

/*
 * Seed the population.
 */
#if 0
  if (seed==NULL)
    {
    plog(LOG_VERBOSE, "Entity seed function not defined.  Genesis can not occur.  Continuing anyway.");
    }
  else
    {
    ga_population_seed(pop);
    plog(LOG_VERBOSE, "Genesis has occured!");
    }
#endif

  return pop;
  }


/**********************************************************************
  ga_genesis_double()
  synopsis:	High-level function to create a new population and
		perform the basic setup (i.e. initial seeding) required
		for further optimisation and manipulation.
		Double precision real-valued chromosomes.
  parameters:
  return:	population, or NULL on failure.
  last updated:	17 Feb 2005
 **********************************************************************/

population *ga_genesis_double(	const int		population_size,
			const int		num_chromo,
			const int		len_chromo,
			GAgeneration_hook	generation_hook,
			GAiteration_hook	iteration_hook,
			GAdata_destructor	data_destructor,
			GAdata_ref_incrementor	data_ref_incrementor,
			GAevaluate		evaluate,
			GAseed			seed,
			GAadapt			adapt,
			GAselect_one		select_one,
			GAselect_two		select_two,
			GAmutate		mutate,
			GAcrossover		crossover,
			GAreplace		replace,
			vpointer		userdata )
  {
  population	*pop;	/* The new population structure. */

  plog(LOG_VERBOSE, "Genesis is beginning!");

/*
 * Initialise OpenMP code.
 */
  ga_init_openmp();

/*
 * Allocate and initialise a new population.
 * This call also sets this as the active population.
 */
  if ( !(pop = ga_population_new( population_size, num_chromo, len_chromo )) )
    return NULL;

/*
 * Assign population's user data.
 */
  pop->data = userdata;

/*
 * Define some callback functions.
 */
  pop->generation_hook = generation_hook;
  pop->iteration_hook = iteration_hook;

  pop->data_destructor = data_destructor;
  pop->data_ref_incrementor = data_ref_incrementor;

  pop->chromosome_constructor = ga_chromosome_double_allocate;
  pop->chromosome_destructor = ga_chromosome_double_deallocate;
  pop->chromosome_replicate = ga_chromosome_double_replicate;
  pop->chromosome_to_bytes = ga_chromosome_double_to_bytes;
  pop->chromosome_from_bytes = ga_chromosome_double_from_bytes;
  pop->chromosome_to_string = ga_chromosome_double_to_string;

  pop->evaluate = evaluate;
  pop->seed = seed;
  pop->adapt = adapt;
  pop->select_one = select_one;
  pop->select_two = select_two;
  pop->mutate = mutate;
  pop->crossover = crossover;
  pop->replace = replace;

/*
 * Seed the population.
 */
#if 0
  if (seed==NULL)
    {
    plog(LOG_VERBOSE, "Entity seed function not defined.  Genesis can not occur.  Continuing anyway.");
    }
  else
    {
    ga_population_seed(pop);
    plog(LOG_VERBOSE, "Genesis has occured!");
    }
#endif

  return pop;
  }


/**********************************************************************
  ga_genesis_bitstring()
  synopsis:	High-level function to create a new population and
		perform the basic setup (i.e. initial seeding) required
		for further optimisation and manipulation.
		Bitstring-valued chromosomes.
  parameters:
  return:	population, or NULL on failure.
  last updated:	17 Feb 2005
 **********************************************************************/

population *ga_genesis_bitstring(	const int		population_size,
			const int		num_chromo,
			const int		len_chromo,
			GAgeneration_hook	generation_hook,
			GAiteration_hook	iteration_hook,
			GAdata_destructor	data_destructor,
			GAdata_ref_incrementor	data_ref_incrementor,
			GAevaluate		evaluate,
			GAseed			seed,
			GAadapt			adapt,
			GAselect_one		select_one,
			GAselect_two		select_two,
			GAmutate		mutate,
			GAcrossover		crossover,
			GAreplace		replace,
			vpointer		userdata )
  {
  population	*pop;	/* The new population structure. */

  plog(LOG_VERBOSE, "Genesis is beginning!");

/*
 * Initialise OpenMP code.
 */
  ga_init_openmp();

/*
 * Allocate and initialise a new population.
 * This call also sets this as the active population.
 */
  if ( !(pop = ga_population_new( population_size, num_chromo, len_chromo )) )
    return NULL;

/*
 * Assign population's user data.
 */
  pop->data = userdata;

/*
 * Define some callback functions.
 */
  pop->generation_hook = generation_hook;
  pop->iteration_hook = iteration_hook;

  pop->data_destructor = data_destructor;
  pop->data_ref_incrementor = data_ref_incrementor;

  pop->chromosome_constructor = ga_chromosome_bitstring_allocate;
  pop->chromosome_destructor = ga_chromosome_bitstring_deallocate;
  pop->chromosome_replicate = ga_chromosome_bitstring_replicate;
  pop->chromosome_to_bytes = ga_chromosome_bitstring_to_bytes;
  pop->chromosome_from_bytes = ga_chromosome_bitstring_from_bytes;
  pop->chromosome_to_string = ga_chromosome_bitstring_to_string;

  pop->evaluate = evaluate;
  pop->seed = seed;
  pop->adapt = adapt;
  pop->select_one = select_one;
  pop->select_two = select_two;
  pop->mutate = mutate;
  pop->crossover = crossover;
  pop->replace = replace;

/*
 * Seed the population.
 */
#if 0
  if (seed==NULL)
    {
    plog(LOG_VERBOSE, "Entity seed function not defined.  Genesis can not occur.  Continuing anyway.");
    }
  else
    {
    ga_population_seed(pop);
    plog(LOG_VERBOSE, "Genesis has occured!");
    }
#endif

  return pop;
  }


/**********************************************************************
  ga_allele_search()
  synopsis:	Perform complete systematic search on a given allele
		in a given entity.  If initial solution is NULL, then
		a random solution is generated (but use of that feature
		is unlikely to be useful!).
		The original entity will not be munged.
                NOTE: max_val is the maximum value _+_ 1!
		WARNING: Now only works for integer array chromosomes!
		FIXME: Need to make chromosome datatype agnostic.
  parameters:
  return:	Best solution found.
  last updated:	24/03/01
 **********************************************************************/

#ifndef COMPILE_DEPRECATED_FUNCTIONS

entity *ga_allele_search(	population	*pop,
				const int	chromosomeid,
				const int	point,
				const int 	min_val,
				const int 	max_val,
				entity		*initial )
  {
  int		val;			/* Current value for point. */
  entity	*current, *best;	/* The solutions. */

/* Checks. */
/* FIXME: More checks needed. */
  if ( !pop ) die("Null pointer to population structure passed.");

  current = ga_get_free_entity(pop);	/* The 'working' solution. */
  best = ga_get_free_entity(pop);	/* The best solution so far. */

  plog(LOG_WARNING, "ga_allele_search() is a deprecated function!");

/* Do we need to generate a random solution? */
  if (initial==NULL)
    {
    plog(LOG_VERBOSE, "Will perform systematic allele search with random starting solution.");

    pop->seed(pop, best);
    }
  else
    {
    plog(LOG_VERBOSE, "Will perform systematic allele search.");

    ga_entity_copy(pop, best, initial);
    }

/*
 * Copy best solution over current solution.
 */
  ga_entity_copy(pop, current, best);
  best->fitness=GA_MIN_FITNESS;

/*
 * Loop over the range of legal values.
 */
  for (val = min_val; val < max_val; val++)
    {
    ((int *)current->chromosome[chromosomeid])[point] = val;
    ga_entity_clear_data(pop, current, chromosomeid);

    pop->evaluate(pop, current);

/*
 * Should we keep this solution?
 */
    if ( best->fitness < current->fitness )
      { /* Copy this solution best solution. */
      ga_entity_blank(pop, best);
      ga_entity_copy(pop, best, current);
      }
    else
      { /* Copy best solution over current solution. */
      ga_entity_blank(pop, current);
      ga_entity_copy(pop, current, best);
      }

    }

  plog(LOG_VERBOSE,
            "After complete search the best solution has fitness score of %f",
            best->fitness );

/*
 * Current no longer needed.  It is upto the caller to dereference the
 * optimum solution found.
 */
  ga_entity_dereference(pop, current);

  return best;
  }
#endif


/**********************************************************************
  ga_population_dump()
  synopsis:	Dump some statistics about a population.
  parameters:	population	*pop
  return:	none
  last updated:	17 Feb 2005
 **********************************************************************/

void ga_population_dump(population	*pop)
  {
  printf("Population id %d\n", (int) ga_get_population_id(pop));
  printf("Max size %d Stable size %d Current size %d\n", pop->max_size, pop->stable_size, pop->size);
  printf("Crossover %f Mutation %f Migration %f\n", pop->crossover_ratio, pop->mutation_ratio, pop->migration_ratio);
  printf("Allele mutation prob %f\n", pop->allele_mutation_prob);
  printf("Allele ranges %d - %d %f - %f\n", pop->allele_min_integer, pop->allele_max_integer, pop->allele_min_double, pop->allele_max_double);
  printf("Chromosome length %d count %d\n", pop->len_chromosomes, pop->num_chromosomes);
  printf("Best fitness %f\n", pop->entity_iarray[0]->fitness);

  return;
  }


/**********************************************************************
  ga_entity_dump()
  synopsis:	Dump some statistics about a entity.
  parameters:	entity	*john
  return:	none
  last updated:	24 Dec 2002
 **********************************************************************/

void ga_entity_dump(population *pop, entity *john)
  {
  printf( "Entity id %d rank %d\n",
          ga_get_entity_id(pop, john),
          ga_get_entity_rank(pop, john) );
  printf( "Fitness %f\n", john->fitness );
  printf( "data <%s> data0 <%s> chromo <%s> chromo0 <%s>\n",
          john->data?"defined":"undefined",
          john->data!=NULL&&((SLList *)john->data)->data!=NULL?"defined":"undefined",
          john->chromosome?"defined":"undefined",
          john->chromosome!=NULL&&john->chromosome[0]!=NULL?"defined":"undefined" );

  return;
  }