ga_core.c

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

/**********************************************************************
  ga_core.c
 **********************************************************************

  ga_core - Genetic algorithm routines.
  Copyright ©2000-2005, Stewart Adcock <[e-mail]>
  All rights reserved.

  The latest version of this program should be available at:
  http://gaul.sourceforge.net/

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.  Alternatively, if your project
  is incompatible with the GPL, I will probably agree to requests
  for permission to use the terms of any other license.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY WHATSOEVER.

  A full copy of the GNU General Public License should be in the file
  "COPYING" provided with this distribution; if not, see:
  http://www.gnu.org/

 **********************************************************************

  Synopsis:     Routines for handling populations and performing GA
		operations.

		Also contains a number of helper functions providing
		alternative optimisation schemes for comparison and
		analysis purposes.

		BEWARE: MANY FUNCTIONS ARE NOT THREAD-SAFE!

		Internally, and in the public C interface, pointers
		are used to identify the population and entity
		structures.  However, in the scripting interface these
		pointers are unusable, so identifing integers are
		used instead.

  Vague usage details:	Set-up with ga_genesis_XXX(), where XXX is a built-in chromosome type().
			Perform calculations with ga_evolution().
			Grab data for post-analysis with ga_transcend().
			Evolution will continue if ga_evolution() is
			called again without calling ga_genesis_XXX() again.

  To do:	Replace the send_mask int array with a bit vector.
		All functions here should be based on entity/population _pointers_ while the functions in ga_intrinsics should be based on _handles_.
		More "if ( !pop ) die("Null pointer to population structure passed.");" checks are needed.
		Population/entity iterator functions.
		ga_get_struct_whatever() should be renamed to ga_struct_get_whatever().

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

#include "gaul/ga_core.h"

/*
 * Global variables.
 */
static TableStruct	*pop_table=NULL;	/* The population table. */

THREAD_LOCK_DEFINE_STATIC(pop_table_lock);
#ifdef USE_OPENMP
static boolean gaul_openmp_initialised = FALSE;
#endif

/*
 * Lookup table for functions.
 *
 * This is required for saving defined code hooks in files and for
 * some script interfaces.
 */
struct func_lookup {char *funcname; void *func_ptr;};

static struct func_lookup lookup[]={
	{ NULL, NULL },
	{ "ga_select_one_random",                      (void *) ga_select_one_random },
	{ "ga_select_two_random",                      (void *) ga_select_two_random },
	{ "ga_select_one_every",                       (void *) ga_select_one_every },
	{ "ga_select_two_every",                       (void *) ga_select_two_every },
	{ "ga_select_one_randomrank",                  (void *) ga_select_one_randomrank },
	{ "ga_select_two_randomrank",                  (void *) ga_select_two_randomrank },
	{ "ga_select_one_bestof2",                     (void *) ga_select_one_bestof2 },
	{ "ga_select_two_bestof2",                     (void *) ga_select_two_bestof2 },
	{ "ga_select_one_bestof3",                     (void *) ga_select_one_bestof3 },
	{ "ga_select_two_bestof3",                     (void *) ga_select_two_bestof3 },
	{ "ga_select_one_roulette",                    (void *) ga_select_one_roulette },
	{ "ga_select_two_roulette",                    (void *) ga_select_two_roulette },
	{ "ga_select_one_roulette_rebased",            (void *) ga_select_one_roulette_rebased },
	{ "ga_select_two_roulette_rebased",            (void *) ga_select_two_roulette_rebased },
	{ "ga_select_one_sus",                         (void *) ga_select_one_sus },
	{ "ga_select_two_sus",                         (void *) ga_select_two_sus },
	{ "ga_select_one_sussq",                       (void *) ga_select_one_sussq },
	{ "ga_select_two_sussq",                       (void *) ga_select_two_sussq },
	{ "ga_select_one_best",                        (void *) ga_select_one_best },
	{ "ga_select_two_best",                        (void *) ga_select_two_best },
	{ "ga_select_one_aggressive",                  (void *) ga_select_one_aggressive },
	{ "ga_select_two_aggressive",                  (void *) ga_select_two_aggressive },
	{ "ga_select_one_linearrank",                  (void *) ga_select_one_linearrank },
	{ "ga_select_two_linearrank",                  (void *) ga_select_two_linearrank },
	{ "ga_select_one_roundrobin",                  (void *) ga_select_one_roundrobin },
	{ "ga_crossover_integer_singlepoints",         (void *) ga_crossover_integer_singlepoints },
	{ "ga_crossover_integer_doublepoints",         (void *) ga_crossover_integer_doublepoints },
	{ "ga_crossover_integer_mean",                 (void *) ga_crossover_integer_mean },
	{ "ga_crossover_integer_mixing",               (void *) ga_crossover_integer_mixing },
	{ "ga_crossover_integer_allele_mixing",        (void *) ga_crossover_integer_allele_mixing },
	{ "ga_crossover_boolean_singlepoints",         (void *) ga_crossover_boolean_singlepoints },
	{ "ga_crossover_boolean_doublepoints",         (void *) ga_crossover_boolean_doublepoints },
	{ "ga_crossover_boolean_mixing",               (void *) ga_crossover_boolean_mixing },
	{ "ga_crossover_boolean_allele_mixing",        (void *) ga_crossover_boolean_allele_mixing },
	{ "ga_crossover_char_singlepoints",            (void *) ga_crossover_char_singlepoints },
	{ "ga_crossover_char_doublepoints",            (void *) ga_crossover_char_doublepoints },
	{ "ga_crossover_char_mixing",                  (void *) ga_crossover_char_mixing },
	{ "ga_crossover_char_allele_mixing",           (void *) ga_crossover_char_allele_mixing },
	{ "ga_crossover_double_mean",                  (void *) ga_crossover_double_mean },
	{ "ga_crossover_double_mixing",                (void *) ga_crossover_double_mixing },
	{ "ga_crossover_double_allele_mixing",         (void *) ga_crossover_double_allele_mixing },
	{ "ga_crossover_double_singlepoints",          (void *) ga_crossover_double_singlepoints },
	{ "ga_crossover_double_doublepoints",          (void *) ga_crossover_double_doublepoints },
	{ "ga_crossover_bitstring_singlepoints",       (void *) ga_crossover_bitstring_singlepoints },
	{ "ga_crossover_bitstring_doublepoints",       (void *) ga_crossover_bitstring_doublepoints },
	{ "ga_crossover_bitstring_mixing",             (void *) ga_crossover_bitstring_mixing },
	{ "ga_crossover_bitstring_allele_mixing",      (void *) ga_crossover_bitstring_allele_mixing },
	{ "ga_mutate_integer_singlepoint_drift",       (void *) ga_mutate_integer_singlepoint_drift },
	{ "ga_mutate_integer_singlepoint_randomize",   (void *) ga_mutate_integer_singlepoint_randomize },
	{ "ga_mutate_integer_multipoint",              (void *) ga_mutate_integer_multipoint },
	{ "ga_mutate_integer_allpoint",                (void *) ga_mutate_integer_allpoint },
	{ "ga_mutate_boolean_singlepoint",             (void *) ga_mutate_boolean_singlepoint },
	{ "ga_mutate_boolean_multipoint",              (void *) ga_mutate_boolean_multipoint },
	{ "ga_mutate_char_singlepoint_drift",          (void *) ga_mutate_char_singlepoint_drift },
	{ "ga_mutate_char_singlepoint_randomize",      (void *) ga_mutate_char_singlepoint_randomize },
	{ "ga_mutate_char_allpoint",                   (void *) ga_mutate_char_allpoint },
	{ "ga_mutate_char_multipoint",                 (void *) ga_mutate_char_multipoint },
	{ "ga_mutate_printable_singlepoint_drift",     (void *) ga_mutate_printable_singlepoint_drift },
	{ "ga_mutate_printable_singlepoint_randomize", (void *) ga_mutate_printable_singlepoint_randomize },
	{ "ga_mutate_printable_multipoint",            (void *) ga_mutate_printable_multipoint },
	{ "ga_mutate_printable_allpoint",              (void *) ga_mutate_printable_allpoint },
	{ "ga_mutate_bitstring_singlepoint",           (void *) ga_mutate_bitstring_singlepoint },
	{ "ga_mutate_bitstring_multipoint",            (void *) ga_mutate_bitstring_multipoint },
	{ "ga_mutate_double_singlepoint_randomize",    (void *) ga_mutate_double_singlepoint_randomize },
	{ "ga_mutate_double_singlepoint_drift",        (void *) ga_mutate_double_singlepoint_drift },
	{ "ga_mutate_double_allpoint",                 (void *) ga_mutate_double_allpoint },
	{ "ga_mutate_double_multipoint",               (void *) ga_mutate_double_multipoint },
	{ "ga_seed_boolean_random",                    (void *) ga_seed_boolean_random },
	{ "ga_seed_boolean_zero",                      (void *) ga_seed_boolean_zero },
	{ "ga_seed_integer_random",                    (void *) ga_seed_integer_random },
	{ "ga_seed_integer_zero",                      (void *) ga_seed_integer_zero },
	{ "ga_seed_double_random",                     (void *) ga_seed_double_random },
	{ "ga_seed_double_zero",                       (void *) ga_seed_double_zero },
	{ "ga_seed_double_random_unit_gaussian",       (void *) ga_seed_double_random_unit_gaussian },
	{ "ga_seed_char_random",                       (void *) ga_seed_char_random },
	{ "ga_seed_printable_random",                  (void *) ga_seed_printable_random },
	{ "ga_seed_bitstring_random",                  (void *) ga_seed_bitstring_random },
	{ "ga_seed_bitstring_zero",                    (void *) ga_seed_bitstring_zero },
	{ "ga_replace_by_fitness",                     (void *) ga_replace_by_fitness },
	{ "ga_rank_fitness",                           (void *) ga_rank_fitness },
	{ "ga_chromosome_integer_allocate",            (void *) ga_chromosome_integer_allocate },
	{ "ga_chromosome_integer_deallocate",          (void *) ga_chromosome_integer_deallocate },
	{ "ga_chromosome_integer_replicate",           (void *) ga_chromosome_integer_replicate },
	{ "ga_chromosome_integer_to_bytes",            (void *) ga_chromosome_integer_to_bytes },
	{ "ga_chromosome_integer_from_bytes",          (void *) ga_chromosome_integer_from_bytes },
	{ "ga_chromosome_integer_to_string",           (void *) ga_chromosome_integer_to_string },
	{ "ga_chromosome_boolean_allocate",            (void *) ga_chromosome_boolean_allocate },
	{ "ga_chromosome_boolean_deallocate",          (void *) ga_chromosome_boolean_deallocate },
	{ "ga_chromosome_boolean_replicate",           (void *) ga_chromosome_boolean_replicate },
	{ "ga_chromosome_boolean_to_bytes",            (void *) ga_chromosome_boolean_to_bytes },
	{ "ga_chromosome_boolean_from_bytes",          (void *) ga_chromosome_boolean_from_bytes },
	{ "ga_chromosome_boolean_to_string",           (void *) ga_chromosome_boolean_to_string },
	{ "ga_chromosome_double_allocate",             (void *) ga_chromosome_double_allocate },
	{ "ga_chromosome_double_deallocate",           (void *) ga_chromosome_double_deallocate },
	{ "ga_chromosome_double_replicate",            (void *) ga_chromosome_double_replicate },
	{ "ga_chromosome_double_to_bytes",             (void *) ga_chromosome_double_to_bytes },
	{ "ga_chromosome_double_from_bytes",           (void *) ga_chromosome_double_from_bytes },
	{ "ga_chromosome_double_to_string",            (void *) ga_chromosome_double_to_string },
	{ "ga_chromosome_char_allocate",               (void *) ga_chromosome_char_allocate },
	{ "ga_chromosome_char_deallocate",             (void *) ga_chromosome_char_deallocate },
	{ "ga_chromosome_char_replicate",              (void *) ga_chromosome_char_replicate },
	{ "ga_chromosome_char_to_bytes",               (void *) ga_chromosome_char_to_bytes },
	{ "ga_chromosome_char_from_bytes",             (void *) ga_chromosome_char_from_bytes },
	{ "ga_chromosome_char_to_string",              (void *) ga_chromosome_char_to_string },
	{ "ga_chromosome_bitstring_allocate",          (void *) ga_chromosome_bitstring_allocate },
	{ "ga_chromosome_bitstring_deallocate",        (void *) ga_chromosome_bitstring_deallocate },
	{ "ga_chromosome_bitstring_replicate",         (void *) ga_chromosome_bitstring_replicate },
	{ "ga_chromosome_bitstring_to_bytes",          (void *) ga_chromosome_bitstring_to_bytes },
	{ "ga_chromosome_bitstring_from_bytes",        (void *) ga_chromosome_bitstring_from_bytes },
	{ "ga_chromosome_bitstring_to_string",         (void *) ga_chromosome_bitstring_to_string },
	{ "ga_chromosome_list_allocate",               (void *) ga_chromosome_list_allocate },
	{ "ga_chromosome_list_deallocate",             (void *) ga_chromosome_list_deallocate },
	{ "ga_chromosome_list_replicate",              (void *) ga_chromosome_list_replicate },
	{ "ga_chromosome_list_to_bytes",               (void *) ga_chromosome_list_to_bytes },
	{ "ga_chromosome_list_from_bytes",             (void *) ga_chromosome_list_from_bytes },
	{ "ga_chromosome_list_to_string",              (void *) ga_chromosome_list_to_string },
	{ NULL, NULL } };


/**********************************************************************
  Private utility functions.
 **********************************************************************/

/**********************************************************************
  destruct_list()
  synopsis:	Destroys an userdata list and it's contents.  For
		many applications, the destructor callback will just
		be free() or similar.  This callback may safely be
		NULL.
  parameters:	population *pop	Population.
		SLList *list	Phenomic data.
  return:	none
  last updated:	24 Aug 2002
 **********************************************************************/

static void destruct_list(population *pop, SLList *list)
  {
  SLList        *present;	/* Current list element */
  int		num_destroyed;	/* Count number of things destroyed. */
  vpointer	data;		/* Data in item. */

/* A bit of validation. */
  if ( !pop ) die("Null pointer to population structure passed.");
  if ( !list ) die("Null pointer to list passed.");

/*
 * Deallocate data stored in the list, if required.
 */
  if ( pop->data_destructor )
    {
    num_destroyed = 0;
    present=list;

    while(present!=NULL)
      {
      if ((data = slink_data(present)))
        {
        pop->data_destructor(data);
        num_destroyed++;
        }
      present=slink_next(present);
      }

#if GA_DEBUG>2
/*
 * Not typically needed now, because num_destrtoyed may
 * (correctly) differ from the actual number of chromosomes.
 */
    if (num_destroyed != pop->num_chromosomes)
      printf("Uh oh! Dodgy user data here? %d %d\n",
                 num_destroyed, pop->num_chromosomes);
#endif

    }

/* Deallocate the list sructure. */
  slink_free_all(list);

  return;
  }


/**********************************************************************
  Population handling functions.
 **********************************************************************/

/**********************************************************************
  ga_population_new()
  synopsis:	Allocates and initialises a new population structure,
		and assigns a new population id to it.
  parameters:	const int stable_size		Num. individuals carried into next generation.
		const int num_chromosome	Num. of chromosomes.
		const int len_chromosome	Size of chromosomes (may be ignored).
  return:	population *	new population structure.
  last updated: 16 Feb 2005
 **********************************************************************/

population *ga_population_new(	const int stable_size,
				const int num_chromosome,
				const int len_chromosome)
  {
  population	*newpop=NULL;	/* New population structure. */
  unsigned int	pop_id;		/* Handle for new population structure. */
  int		i;		/* Loop over (unassigned) entities. */

  if ( !(newpop = s_malloc(sizeof(population))) )
    die("Unable to allocate memory");

  newpop->size = 0;
  newpop->stable_size = stable_size;
  newpop->max_size = (1+stable_size)*4;	/* +1 prevents problems if stable_size is 0. */
  newpop->orig_size = 0;
  newpop->num_chromosomes = num_chromosome;
  newpop->len_chromosomes = len_chromosome;
  newpop->data = NULL;
  newpop->free_index = newpop->max_size-1;
  newpop->island = -1;
  newpop->generation = 0;

  newpop->crossover_ratio = GA_DEFAULT_CROSSOVER_RATIO;
  newpop->mutation_ratio = GA_DEFAULT_MUTATION_RATIO;
  newpop->migration_ratio = GA_DEFAULT_MIGRATION_RATIO;
  newpop->scheme = GA_SCHEME_DARWIN;
  newpop->elitism = GA_ELITISM_PARENTS_SURVIVE;

  newpop->allele_mutation_prob = GA_DEFAULT_ALLELE_MUTATION_PROB;
  newpop->allele_min_integer = 0;
  newpop->allele_max_integer = RAND_MAX-1;	/* this may seem like an odd choice, but it is to maintain compatiability with older versions. */
  newpop->allele_min_double = DBL_MIN;
  newpop->allele_max_double = DBL_MAX;

  THREAD_LOCK_NEW(newpop->lock);
#if USE_CHROMO_CHUNKS == 1
  THREAD_LOCK_NEW(newpop->chromo_chunk_lock);
#endif

  if ( !(newpop->entity_array = s_malloc(newpop->max_size*sizeof(entity*))) )
    die("Unable to allocate memory");

  if ( !(newpop->entity_iarray = s_malloc(newpop->max_size*sizeof(entity*))) )
    die("Unable to allocate memory");

  newpop->entity_chunk = mem_chunk_new(sizeof(entity), 512);

/*
 * Wipe the entity arrays.
 */
  for (i=0; i<newpop->max_size; i++)
    {
    newpop->entity_array[i] = NULL;
    newpop->entity_iarray[i] = NULL;
    }

/*
 * Wipe optional parameter data.
 */
  newpop->tabu_params = NULL;
  newpop->sa_params = NULL;
  newpop->climbing_params = NULL;
  newpop->simplex_params = NULL;
  newpop->dc_params = NULL;
  newpop->gradient_params = NULL;
  newpop->search_params = NULL;
  newpop->sampling_params = NULL;
  
/*
 * Clean the callback functions.
 * Prevents erronerous callbacks - helpful when debugging!
 */
  newpop->generation_hook = NULL;
  newpop->iteration_hook = NULL;

  newpop->data_destructor = NULL;
  newpop->data_ref_incrementor = NULL;

  newpop->chromosome_constructor = NULL;
  newpop->chromosome_destructor = NULL;
  newpop->chromosome_replicate = NULL;
  newpop->chromosome_to_bytes = NULL;
  newpop->chromosome_from_bytes = NULL;
  newpop->chromosome_to_string = NULL;

  newpop->evaluate = NULL;
  newpop->seed = NULL;
  newpop->adapt = NULL;
  newpop->select_one = NULL;
  newpop->select_two = NULL;
  newpop->mutate = NULL;
  newpop->crossover = NULL;
  newpop->replace = NULL;
  newpop->rank = ga_rank_fitness;

/*
 * Efficient memory chunks for chromosome handling.
 */
#if USE_CHROMO_CHUNKS == 1
  newpop->chromoarray_chunk = NULL;
  newpop->chromo_chunk = NULL;
#endif

/*
 * Add this new population into the population table.
 */
  THREAD_LOCK(pop_table_lock);
  if ( !pop_table ) pop_table=table_new();

  pop_id = table_add(pop_table, (vpointer) newpop);
  THREAD_UNLOCK(pop_table_lock);

  plog( LOG_DEBUG, "New pop = %p id = %d", newpop, pop_id);

  return newpop;
  }


/**********************************************************************
  ga_population_clone_empty()
  synopsis:	Allocates and initialises a new population structure,
		and fills it with an exact copy of the data from an
		existing population, with the exception that entity
		data is not copied.  The population's user data
		field is referenced.
  parameters:	population *	original population structure.
  return:	population *	new population structure.
  last updated: 16 Feb 2005