GAUL is Copyright © 2000-2009, "Stewart A. Adcock" <gaul@linux-domain.com>
This document is © 2004-2009, Stewart Adcock.
All rights reserved.
This draft document is intended as the definitive reference guide for the GAUL evolutionary computation library. It currently corresponds to GAUL version 0.1850-0.
All existing documentation, including a tutorial and a FAQ, is available on the the website. You are welcome to join the mailing list, gaul-devel@lists.sourceforge.net, where all of your questions can be answered. Visit http://lists.sourceforge.net/lists/listinfo/gaul-devel to register for this mailing list.
| Homepage: | http://gaul.sourceforge.net/ |
| Documentation: | http://gaul.sourceforge.net/documentation.html |
| Development homepage: | http://sourceforge.net/projects/gaul/ |
| Download page: | http://gaul.sourceforge.net/downloads.html |
The reader is assumed to be familiar with evolutionary computation in general, and genetic algorithms in particular. The reader is referred to http://gaul.sourceforge.net/intro.html for a basic introduction to evolutionary computation.
This document should be used in concert with the online tutorial starting at http://gaul.sourceforge.net/tutorial/simple.html.
The reader may notice that a few functions are described only with the phrase "Deliberately undocumented at present". The form or behaviour of such functions are not deemed to be finalized at this time. Use these functions with extreme caution.
1. Preface
2. Introduction to GAUL
3. Obtaining GAUL
4. Installation
5. Bug Submission
6. Using GAUL
6.1. Data structures
6.1.1. Entity and population structures
6.1.2. Enumerated types
6.2. Callback functions
6.2.1. Analysis and termination functions
6.2.2. Standard GA operator functions
6.2.3. Genome handling functions
6.2.4. Phenome handling functions
6.2.5. Heuristic search function operations
6.3. Functions available through the public API
6.3.1. Basic entity handling functions
6.4. Basic population handling functions
6.5. Evolution functions
6.6. MPI specific functions
6.7. Disk I/O functions
6.8. Built-in Selection operators
6.9. Built-in Crossover operators
6.10. Built-in Mutation operators
6.11. Built-in Genesis operators
6.12. Built-in Replacement operators
6.13. Built-in Rank operators
6.14. Genesis functions
6.15. Miscellaneous support functions
6.16. Statistics functions
6.17. Chromosome definition functions
6.18. Bitstring functions
6.19. Genome comparison functions
7. Alternative search functions
7.1. Tabu search
7.2. Simplex search
7.3. Deterministic crowding
7.4. Differential evolution
7.5. Simulated annealling
7.6. Hill climbing
7.7. Gradient methods
7.8. Systematic search
7.9. Random search
8. Environment variables
9. S-Lang scripting
10. Perl Scripting
11. Support functions
11.1. List datastructure
11.2. Tree datastructure
11.3. Memory handling
11.4. Portable, Stateful, Pseudo-Random Number Generator
11.5. Log functions
11.6. Indexed table datastructure
11.7. Timer functions
11.8. Compatibility Functions
12. Example programs
12.1. "Pingpong" problem solver
12.2. Simple polynomial solver
12.3. "Wildfires" problem solver
12.4. Goldberg's Examples
12.5. Holland's Royal Road Problem
12.6. The Struggle for Existence
12.7. Neural Network Evolution
12.8. Reading and Writing Population Data
The Genetic Algorithm Utility Library (or, GAUL for short) is a flexible programming library designed to aid in the development of applications that use evolutionary algorithms. It provides data structures and functions for handling and manipulation of the data required for various serial and parallel genetic algorithms. A number of alternative non-evolutionary algorithms are additionally provided for comparison to the genetic algorithms. Much of the functionality is also available through a simple S-Lang interface.
GAUL is OSI Certified Open Source Software.
Current features include:
The main development platform for GAUL is Linux with the gcc compiler, but it is trivial to use GAUL on any POSIX compliant systems. Recent versions of GAUL have been successfully used with a variety of operating systems, including RedHat Linux, FreeBSD, Sun's Solaris and SGI's IRIX. Full use is made of the GNU maketools to aid portability issues. A table of platforms known to be fully is located at http://gaul.souceforge.net/platforms.html.
This version of GAUL is distributed under the terms of the GNU General Public License. See the file ./COPYING for full details. A professionally supported version is also available.
The most recent, publicly released, version of GAUL is always available at http://gaul.sourceforge.net/downloads.html.
Alternatively, the latest "bleeding-edge" source code (which may, or may not, be entirely stable or even compile) is always available via anonymous CVS hosted by SourceForge. To download, follow these instructions:
See file ./INSTALL or visit http://gaul.sourceforge.net/installation.html for detailed instructions.
On most UNIX or UNIX-like systems, the typical user would want to type:
./configure && make && make install
If you find a bug, please send details of your system, the version of GAUL that you are using and concise instructions for reproducing the crash or erroneous result to gaul@linux-domain.com.
Assuming that GAUL is correctly installed and configured, programs utilizing its features should link to libgaul, libgaul_util, and depending upon the system and compile-time options, to libm, libmpi and/or libpthread. If the built-in S-Lang support is compiled, then libslang must be linked too.
libgaul_util provides portable programming routines and may be used separately. These functions are described later in this guide.
The GAUL header needs to be referenced in the source code before any GAUL functions may be used, i.e.
#include "gaul.h"
This is fully discussed in the GAUL tutorial available on the website. The GAUL header defines the GAUL datatypes and all publicly accessible functions.
The entity datatype is used for the storage of single individuals. The population datatype stores multiple individuals (entities) in addition to all run-time parameters required for their evolution. These are the fundamental datatypes used by the GAUL library.
Enumerated types are used to define particular variants of the GA algorithms. These are used as parameters to certain functions.
The evolutionary mode is specified using the ga_scheme_type_t type. This enumerated type is defined as shown below. Evolutionary mode indicates the form of adaptation that should be used. GA_SCHEME_DARWIN relates to a standard GA, while the others relate to so-called hybrid genetic algorithms. The composite options GA_SCHEME_LAMARCK_PARENTS|GA_SCHEME_BALDWIN_CHILDREN and GA_SCHEME_LAMARCK_CHILDREN|GA_SCHEME_BALDWIN_PARENTS are also acceptable, albeit unusual, choices.
typedef enum ga_scheme_type_t
{
GA_SCHEME_DARWIN = 0,
GA_SCHEME_LAMARCK_PARENTS = 1,
GA_SCHEME_LAMARCK_CHILDREN = 2,
GA_SCHEME_LAMARCK_ALL = 3,
GA_SCHEME_BALDWIN_PARENTS = 4,
GA_SCHEME_BALDWIN_CHILDREN = 8,
GA_SCHEME_BALDWIN_ALL = 12
} ga_scheme_type;
Like the evolutionary mode, the elitism mode is specified via an enumerated type. This is used to control the form of elitism used by the GA, that is the pattern of survival from one generation to the next. The enumerated constants GA_ELITISM_PARENTS_SURVIVE, GA_ELITISM_ONE_PARENT_SURVIVES, and GA_ELITISM_PARENTS_DIE indicate whether all (subject to fitness), one or zero entities survive, respectively, into the next generation. GA_ELITISM_RESCORE_PARENTS is a special-case alternative to GA_ELITISM_PARENTS_SURVIVE where the fitness of every parent entity is recalculated. These parents will survive if, but only if, they are sufficiently fit after rescoring. This option is useful for applying aging to the population or, more commonly, for reassessing fitness when it has a stochastic component.
typedef enum ga_elitism_type_t
{
GA_ELITISM_UNKNOWN = 0,
GA_ELITISM_NULL = 0,
GA_ELITISM_PARENTS_SURVIVE=1,
GA_ELITISM_ONE_PARENT_SURVIVES=2,
GA_ELITISM_PARENTS_DIE=3,
GA_ELITISM_RESCORE_PARENTS=4
} ga_elitism_type;
GAUL makes extensive use of so-called callback functions. These are user-definable functions which provide certain functionality for the core GAUL routines.
Most callback function types have several built-in examples distributed in GAUL. The user is free to use these or, at their option, provide custom functions. This is the chief source of flexibility of the GAUL library.
Many callback functions are suitable only for particular chromosome types. In such cases, this is clear from the functions' names.
typedef boolean (*GAgeneration_hook)(const int generation, population *pop);
GAgeneration_hook is called at the beginning of each generation by all evolutionary functions. If this callback function returns FALSE the evolution will terminate.
typedef boolean (*GAiteration_hook)(const int iteration, entity *entity);
GAiteration_hook is called at the beginning of each iteration by all non-evolutionary search or optimization functions. If this callback function returns FALSE the evolution will terminate.
The standard GA operators are all defined though callbacks. A large set of common and standard operators are built-in to the GAUL library. Any of these may be substituted with user-provided functions instead.
typedef boolean (*GAevaluate)(population *pop, entity *entity);
GAevaluate determines the fitness of an entity.
typedef boolean (*GAseed)(population *pop, entity *adam);
GAseed initializes the genomic contents of an entity.
typedef entity *(*GAadapt)(population *pop, entity *child);
GAadapt optimizes/performs learning for an entity.
typedef boolean (*GAselect_one)(population *pop, entity **mother);
GAselect_one selects a single entity from the population, e.g. for mutation or migration.
typedef boolean (*GAselect_two)(population *pop, entity **mother, entity **father);
GAselect_two selects a pair of entities from the population, e.g. for crossover.
typedef void (*GAmutate)(population *pop, entity *mother, entity *daughter);
GAmutate introduces a mutation into an entity.
typedef void (*GAcrossover)(population *pop, entity *mother, entity *father, entity *daughter, entity *son);
GAcrossover produces two new sets of chromosomes from two parent sets.
typedef void (*GAreplace)(population *pop, entity *child);
GAreplace inserts a new entity into the population.
typedef int (*GArank)(population *popalpha, entity *alpha, population *popbeta, entity *beta);
GArank determines relative ranking for two entities.
A set of callback functions are used to define chromosome types. These enable the user to develop their own, task specific, chromosome types within the GAUL framework. These are fully described in the online GAUL tutorial.
Note that these functions will only be required by more advanced applications of GAUL.
typedef boolean (*GAchromosome_constructor)(const population *pop, entity *entity);
GAchromosome_constructor is used to allocate single chromosomes.
typedef void (*GAchromosome_destructor)(const population *pop, entity *entity);
GAchromosome_destructor is used to deallocate single chromosomes.
typedef void (*GAchromosome_replicate)(const population *pop, entity *parent, entity *child, const int chromosomeid);
GAchromosome_replicate is used to clone single chromosomes.
typedef unsigned int (*GAchromosome_to_bytes)(const population *pop, entity *joe, byte **bytes, unsigned int *max_bytes);
GAchromosome_to_bytes is used to pack genomic data into a contiguous block of memory.
typedef void (*GAchromosome_from_bytes)(const population *pop, entity *joe, byte *bytes);
GAchromosome_from_bytes is used to unpack genomic data from a contiguous block of memory.
typedef char *(*GAchromosome_to_string)(const population *pop, const entity *joe, char *text, size_t *textlen);
GAchromosome_to_string is used to generate a human readable representation of genomic data.
GAUL provides a powerful data handling system - a general purpose data cache. This is deliberately undocumented at present. It is termed "phenomic data" to mirror the terms used in the study of natural evolution.
typedef void (*GAdata_destructor)(vpointer data);
GAdata_destructor is used to deallocate phenomic data.
typedef void (*GAdata_ref_incrementor)(vpointer data);
GAdata_ref_incrementor is used for reference counting of phenomic data.
A variety of miscellaneous functions are also used by the alternative, non-evolutionary, optimization or search functions that GAUL provides.
| GAtabu_accept | Tabu-search tabu and aspiration criteria. |
| GAsa_accept | Simulated Annealing acceptance criteria. |
| GAmutate_allele | Mutate a single, specified, allele. |
| GAto_double | Map chromosomal data to double-precision float array. |
| GAfrom_double | Map chromosomal data from double-precision float array. |
| GAgradient | Return array of gradients. |
| GAscan_chromosome | Produce next permutation of genome. |
| GAcompare | Compare two entities (in either genomic or phenomic space) and return their mutual distance. |
typedef boolean (*GAtabu_accept)(population *pop, entity *putative, entity *tabu); typedef boolean (*GAsa_accept)(population *pop, entity *current, entity *trial); typedef boolean (*GAmutate_allele)(population *pop, entity *parent, entity *child, const int chromosomeid, const int alleleid); typedef boolean (*GAto_double)(population *pop, entity *entity, double *darray); typedef boolean (*GAfrom_double)(population *pop, entity *entity, double *darray); typedef double (*GAgradient)(population *pop, entity *entity, double *darray, double *varray); typedef boolean (*GAscan_chromosome)(population *pop, entity *entity, int enumeration_num); typedef double (*GAcompare)(population *pop, entity *alpha, entity *beta);
Each of these is discussed more fully in the part of this guide which covers the relevant heuristic search function.
Not all public functions are described below. However, you are advised to use extreme caution when using any function not listed below since such functions might be modified, or might be removed, in future versions of GAUL.
All public functions are defined in the gaul.h header file.
Internally, the entities in a population are referenced via unique integer identifiers. These are exposed via the public API and may be used in your programs, although they are really intended for use by scripting language wrappers. ( If you are familiar with the Daylight toolkit then you might be comfortable using these identifiers. See http://www.daylight.com/ )
These identifiers are not unique between multiple populations.
boolean ga_entity_seed(population *pop, entity *e);
Generates the chromosome(s) in an entity. the method used to generate the chromosome(s) is dependent upon the properties of the population structure.
The entity does not need to be from the passed population, but the populations need to be compatible (not necessary identical).
double ga_entity_evaluate(population *pop, entity *entity);
Evaluates the fitness of an entity. the fitness function is dependent upon the properties of the population structure.
The entity does not need to be from the passed population, but the populations need to be compatible (not necessary identical).
int ga_get_entity_rank(population *pop, entity *e);
Return the rank of the entity in its population. This function will only yield the correct result after evolution or after a sorting function is called.
int ga_get_entity_id(population *pop, entity *e);
Return the unique internal identifier of the entity in its population. This identifier is only unique within the specific population.
entity *ga_get_entity_from_id(population *pop, const unsigned int id);
Return the entity structure with the passed identifier, or NULL on error.
entity *ga_get_entity_from_rank(population *pop, const unsigned int rank);
Return the entity structure with the passed rank, or NULL on error.
int ga_get_entity_rank_from_id(population *pop, int id);
Return the rank of the entity with the passed identifier.
int ga_get_entity_id_from_rank(population *pop, int rank);
Return the unique internal identifier of the entity with the passed rank.
boolean ga_entity_dereference(population *p, entity *dying);
This removes the specified entity from the population structure and deallocates all associated memory. Also, reduces the population size.
boolean ga_entity_dereference_by_rank(population *pop, int rank);
This removes the specified entity from the population structure and deallocates all associated memory. Also, reduces the population size.
boolean ga_entity_dereference_by_id(population *pop, int id);
This removes the specified entity from the population structure and deallocates all associated memory. Also, reduces the population size.
void ga_entity_clear_data(population *p, entity *entity, const int chromosome);
Erases the entity's user data associated with the specified chromosome.
entity *ga_get_free_entity(population *pop);
Returns pointer to an unused entity structure in the population. Increments population size too.
void ga_entity_blank(population *p, entity *entity);
This is an efficient alternative to calling ga_entity_dereference() immediately followed by ga_get_free_entity().
boolean ga_copy_data(population *pop, entity *dest, entity *src, const int chromosome);
Copy the userdata from one chromosome of an entity to another entity. The destination chromosomes must be filled in order. If these entities are in differing populations, no problems will occur provided that the chromosome properties are identical.
boolean ga_entity_copy_all_chromosomes(population *pop, entity *dest, entity *src);
Copy all genetic data between entity structures. If these entities are in differing populations, no problems will occur provided that the chromosome properties are identical. Any userdata is also copied.
boolean ga_entity_copy_chromosome(population *pop, entity *dest, entity *src, int chromo);
Copy one chromosome between entities. If these entities are in differing populations, no problems will occur provided that the chromosome datatypes match up. Any userdata is also copied.
boolean ga_entity_copy(population *pop, entity *dest, entity *src);
Copy entire entity structure. This is safe for copying between populations, provided that they are compatible. Any userdata is also copied.
entity *ga_entity_clone(population *pop, entity *parent);
Clone an existing entity structure into a newly allocated entity structure. Safe for cloning into a different population, provided that the populations are compatible.
double ga_entity_get_fitness(entity *e); boolean ga_entity_set_fitness(entity *e, double fitness);
Functions for accessing and setting the fitness of entities.
boolean ga_entity_set_data(population *pop, entity *e, SLList *data); SLList *ga_entity_get_data(population *pop, entity *e);
Functions for accessing and setting entity-specific data. Deliberately undocumented at present.
population *ga_population_new( const int stable_size, const int num_chromosome, const int len_chromosome);
Allocate and initialize a population structure. stable_size specifies the size of the population at the end of each generation. num_chromosome and len_chromosome specifies the number of chromosomes in each entity and the length of those chromosomes. Depending upon the particular chromosome type used, the length parameter might be ignored but it is honoured by all of the built-in chromosome types.
Except in advanced applications, this function is generally not needed.
population *ga_population_clone_empty( population *pop );
Allocates a new population and copy all contents except the constituent entities from an existing population.
population *ga_population_clone( population *pop );
Allocates a new population and copy all contents including the constituent entities from an existing population. The internal entity identifiers will not correspond between the original population and the clone.
boolean ga_population_seed(population *pop);
Allocate and initialize entities in a population. A number of entities equal to the stable_size population parameter will be initialized. The previously specified seed function will be used to seed each of these entities. The fitness of each entity is not determined.
boolean ga_population_score_and_sort(population *pop);
Score all unscored entities in a population and then sort the population by fitness.
boolean ga_population_sort(population *pop);
Sort all entities in a population by fitness. The fitness of each entity must have been previously determined. This is the case after any evolution has been performed.
void ga_population_set_parameters( population *pop, const ga_scheme_type scheme, const ga_elitism_type elitism, const double crossover, const double mutation, const double migration); void ga_population_set_scheme( population *pop, const ga_scheme_type scheme ); void ga_population_set_elitism( population *pop, const ga_elitism_type elitism ); void ga_population_set_crossover( population *pop, const double crossover ); void ga_population_set_mutation( population *pop, const double mutation ); void ga_population_set_migration( population *pop, const double migration ); void ga_population_set_allele_mutation_prob( population *pop, const double probability ); double ga_population_get_crossover(population *pop); double ga_population_get_mutation(population *pop); double ga_population_get_migration(population *pop); double ga_population_get_allele_mutation_prob(population *pop); ga_scheme_type ga_population_get_scheme(population *pop); ga_elitism_type ga_population_get_elitism(population *pop);
Functions for accessing and setting population-specific optimization parameters. In typical use, these functions must be called prior to successful use of any evolution function. It is, however, acceptable to set these functions at any time, including during evolution. This enables dynamic modification of the crossover ratio, for example.
The exact meaning of the crossover, mutation and migration parameters depends upon the particular GA operators being used. User-defined operators are even free to ignore these parameters entirely. The default values for all newly created populations are 0.9, 0.1 and 0.1 for crossover, mutation and migration, respectively.
The ga_population_set_allele_mutation_prob() function may be used to specify the probability of each individual allele being mutated in the "multipoint" mutation operators. The default probability is 0.2 for all newly created populations.
All of these parameters may take any value, including values greater than one, or even values less than zero. Depending upon the specific GA operators being used such values might not be meaningful, however.
int ga_population_get_stablesize(population *pop); int ga_population_get_size(population *pop); int ga_population_get_maxsize(population *pop); boolean ga_population_set_stablesize(population *pop, int stable_size);
Additional population parameters are available through these functions. stablesize refers to the number of entities in the population at the end of each generation. size refers to the current number of entities at the point that the function is called. maxsize refers to the maximum number of entities that the population can currently hold. This parameter is dynamically adjusted as the actual population size grows.
It is acceptable to set these functions at any time, including during evolution. This enables dynamic resizing of the population's stablesize, for example.
int ga_population_get_allele_min_integer( population *pop ); int ga_population_get_allele_max_integer( population *pop ); double ga_population_get_allele_min_double( population *pop ); double ga_population_get_allele_max_double( population *pop ); void ga_population_set_allele_min_integer( population *pop, const int value); void ga_population_set_allele_max_integer( population *pop, const int value); void ga_population_set_allele_min_double( population *pop, const double value); void ga_population_set_allele_max_double( population *pop, const double value);o
These functions allow ranges for the double and integer chromosomes to be imposed or inspected. They work with the current built-in operators (seed, mutation, etc.).
population *ga_transcend(unsigned int id);
Deliberately undocumented at present.
unsigned int ga_resurect(population *pop);
Deliberately undocumented at present.
boolean ga_extinction(population *extinct);
Fully clean and deallocate a population, including all of its constituent entities.
boolean ga_genocide(population *pop, int target_size);
Reduce the size of the population to the specified number of most fit entities. All additional entities are deallocated.
boolean ga_genocide_by_fitness(population *pop, double target_fitness);
Deallocate all entities with a fitness equal to or worse than the specified value.
boolean ga_population_set_data(population *pop, vpointer data); vpointer ga_population_get_data(population *pop);
Define or inspect population specific data.
int ga_population_get_generation(population *pop);
Returns the current generation number for the population. After an evolutionary function has completed, this returns the number of generations completed. This will return zero prior to any evolution. This value is reset to zero whenever any evolutionary function is called with this population. It is safe to call this function at any time, including inside the various selection, mutation, etc. functions.
int ga_population_get_island(population *pop);
Returns the current island number for the population. After an evolutionary function has completed, this returns the island during the previous island-model evolutionary function. This will return -1 prior to any evolution. This value is not adjusted by any non-island-based evolutionary function. It is safe to call this function at any time, including inside the various selection, mutation, etc. functions.
int ga_get_num_populations(void); population *ga_get_population_from_id(unsigned int id); unsigned int ga_get_population_id(population *pop); unsigned int *ga_get_all_population_ids(void); population **ga_get_all_populations(void);
Deliberately undocumented at present.
void ga_init_openmp( void );
Deliberately undocumented at present.
int ga_funclookup_ptr_to_id(void *func); int ga_funclookup_label_to_id(char *funcname); void *ga_funclookup_label_to_ptr(char *funcname); void *ga_funclookup_id_to_ptr(int id); char *ga_funclookup_id_to_label(int id);
Deliberately undocumented at present.
A variety of functions exist for performing evolution. Note that some of these functions are not compiled, by default, on all computer platforms.
int ga_evolution( population *pop, const int max_generations ); int ga_evolution_mpi( population *pop, const int max_generations ); int ga_evolution_forked( population *pop, const int max_generations ); int ga_evolution_threaded( population *pop, const int max_generations ); int ga_evolution_steady_state( population *pop, const int max_iterations ); int ga_evolution_archipelago( const int num_pops, population **pops, const int max_generations ); int ga_evolution_archipelago_mpi( const int num_pops, population **pops, const int max_generations ); int ga_evolution_archipelago_forked( const int num_pops, population **pops, const int max_generations ); int ga_evolution_archipelago_threaded( const int num_pops, population **pops, const int max_generations );
The purposes and actions of the the above functions are discussed in some detail in the online tutorial.
The following two functions should be considered being deprecated and will be removed in a future version of GAUL:
int ga_evolution_mp( population *pop, const int max_generations ); int ga_evolution_archipelago_mp( const int num_pops, population **pops, const int max_generations );
void ga_attach_mpi_slave( population *pop ); void ga_detach_mpi_slaves(void);
These functions are used only in MPI-based parallel code. They are demonstrated in the distributed examples/struggle_mpi.c and examples/struggle5_mpi.c examples.
Functions are provided for reading and writing populations or entities to disk. These functions are not guaranteed to produce cross-platform data files.
fname is the filename to use.
Note that some data can not be stored to disk at present.
boolean ga_population_write(population *pop, char *fname); population *ga_population_read(char *fname); boolean ga_entity_write(population *pop, entity *entity, char *fname); entity *ga_entity_read(population *pop, char *fname);
The selection operator to be used in GAUL is defined through a callback mechanism. Several common types of selection have been implemented, and it is easy to add your own.
In GAUL there are two classes of selection operator - those which select only one individual (i.e. for mutation and migration), and those which select two non-identical individuals (i.e. for crossover). The advantage of having a specialist operator for selecting two individuals is that it may optionally include incest control - that is prevent pairs of closely related individuals from being selected.
These follow the GAselect_one or GAselect_two function prototypes, as appropriate.
These functions return TRUE when sufficient selections have been made with respect to the mutation or crossover parameter, as appropriate. This indicates to the core routines that the evolutionary algorithm should proceed to the next step and no more selections will occur until the next generation. The selected entities, may occasionally be NULL, indicating that no entity was successfully chosen.
boolean ga_select_one_random(population *pop, entity **mother); boolean ga_select_two_random(population *pop, entity **mother, entity **father);
Random selection of entities, irrespective of their fitnesses/ranks.
boolean ga_select_one_every(population *pop, entity **mother); boolean ga_select_two_every(population *pop, entity **mother, entity **father);
Every entity (or combination of entities) will be systematically selected. The mutation and crossover ratios are ignored by these selection functions.
boolean ga_select_one_randomrank(population *pop, entity **mother); boolean ga_select_two_randomrank(population *pop, entity **mother, entity **father);
Systematically select each entity in turn along with a random, more fit, entity. The select_one function doesn't return the systematically selected entity.
boolean ga_select_one_bestof2(population *pop, entity **mother); boolean ga_select_two_bestof2(population *pop, entity **mother, entity **father);
Simple pairwise tournament selection.
boolean ga_select_one_bestof3(population *pop, entity **mother); boolean ga_select_two_bestof3(population *pop, entity **mother, entity **father);
Simple three-way tournament selection.
boolean ga_select_one_roulette( population *pop, entity **mother ); boolean ga_select_two_roulette( population *pop, entity **mother, entity **father ); boolean ga_select_one_roulette_rebased( population *pop, entity **mother ); boolean ga_select_two_roulette_rebased( population *pop, entity **mother, entity **father );
Standard roulette wheel selection.
boolean ga_select_one_sus( population *pop, entity **mother ); boolean ga_select_two_sus( population *pop, entity **mother, entity **father ); boolean ga_select_one_sussq( population *pop, entity **mother ); boolean ga_select_two_sussq( population *pop, entity **mother, entity **father );
Universal stochastic sampling.
boolean ga_select_one_aggressive( population *pop, entity **mother ); boolean ga_select_two_aggressive( population *pop, entity **mother, entity **father );
Random selection, but heavily biased toward fit entities.
boolean ga_select_one_best( population *pop, entity **mother ); boolean ga_select_two_best( population *pop, entity **mother, entity **father );
Select the single best entity only. The select_two function also selects a random entity.
boolean ga_select_one_linearrank( population *pop, entity **mother ); boolean ga_select_two_linearrank( population *pop, entity **mother, entity **father );
Select an entity based on linear probability distribution with respect to rank.
boolean ga_select_one_roundrobin( population *pop, entity **mother );
Select entities using a round-robin algorithm. Each entity is selected in turn, returning to the first once the last entity has been selected.
The crossover operator to be used in GAUL is defined through a callback mechanism. Several common types of crossover have been implemented, and it is easy to add your own. Crossover operators are specific to particular chromosome types.
These follow the GAcrossover function prototype.
Crossover operators take two parent entities and mixes their chromosomes to create two offspring entities.
| Operator | Action |
| ..._singlepoints | Single-point crossover |
| ..._doublepoints | Two-point crossover |
| ..._mean | Allele averaging |
| ..._mixing | Random reassignment of whole chromosomes |
| ..._allele_mixing | Random reassignment of individual alleles (uniform selection) |
void ga_crossover_integer_singlepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_integer_doublepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_integer_mean(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_integer_mixing(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_integer_allele_mixing( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_boolean_singlepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_boolean_doublepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_boolean_mixing(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_boolean_allele_mixing( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_char_singlepoints( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_char_doublepoints( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_char_mixing(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_char_allele_mixing( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_double_singlepoints( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_double_doublepoints( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_double_mean(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_double_mixing(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_double_allele_mixing( population *pop, entity *father, entity *mother, entity *son, entity *daughter ); void ga_crossover_bitstring_singlepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_bitstring_doublepoints(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_bitstring_mixing(population *pop, entity *father, entity *mother, entity *son, entity *daughter); void ga_crossover_bitstring_allele_mixing( population *pop, entity *father, entity *mother, entity *son, entity *daughter );
The mutation operator to be used in GAUL is defined through a callback mechanism. Several common types of mutation have been implemented, and it is easy to add your own. Mutation operators are specific to particular chromosome types.
These follow the GAmutate function prototype.
Mutation operators perturb an entities chromosomes randomly to create a new entity.
| Operator | Action |
| ..._singlepoint_drift | Single allele tweak mutation |
| ..._singlepoint_randomize | Single allele reassignment mutation |
| ..._multipoint | Allele reassignment mutation at multiple sites (currently 20% of alleles) |
| ..._allpoint | Allele tweak mutation at all alleles |
These functions, and any user-defined replacements, should return FALSE on failure or TRUE otherwise. If they do fail, GAUL will handle this gracefully. In reality, most of these function never fail.
void ga_mutate_integer_singlepoint_drift(population *pop, entity *father, entity *son); void ga_mutate_integer_singlepoint_randomize(population *pop, entity *father, entity *son); void ga_mutate_integer_multipoint(population *pop, entity *father, entity *son); void ga_mutate_integer_allpoint(population *pop, entity *father, entity *son); void ga_mutate_boolean_singlepoint(population *pop, entity *father, entity *son); void ga_mutate_boolean_multipoint(population *pop, entity *father, entity *son); void ga_mutate_char_singlepoint_drift(population *pop, entity *father, entity *son); void ga_mutate_char_singlepoint_randomize(population *pop, entity *father, entity *son); void ga_mutate_char_allpoint(population *pop, entity *father, entity *son); void ga_mutate_char_multipoint(population *pop, entity *father, entity *son); void ga_mutate_printable_singlepoint_drift(population *pop, entity *father, entity *son); void ga_mutate_printable_singlepoint_randomize(population *pop, entity *father, entity *son); void ga_mutate_printable_allpoint(population *pop, entity *father, entity *son); void ga_mutate_printable_multipoint(population *pop, entity *father, entity *son); void ga_mutate_bitstring_singlepoint(population *pop, entity *father, entity *son); void ga_mutate_bitstring_multipoint(population *pop, entity *father, entity *son); void ga_mutate_double_singlepoint_drift( population *pop, entity *father, entity *son ); void ga_mutate_double_singlepoint_randomize( population *pop, entity *father, entity *son ); void ga_mutate_double_multipoint(population *pop, entity *father, entity *son); void ga_mutate_double_allpoint(population *pop, entity *father, entity *son);
The genesis (or seed) operator to be used in GAUL is defined through a callback mechanism. These operators are used to initialize the actual contents of chromosomes. Several common types of genesis have been implemented, and it is easy to add your own. Genesis operators are specific to particular chromosome types.
These follow the GAseed function prototype.
| Operator | Action |
| ..._random | Random assignment |
| ..._zero | Assign zero (0 or 0.0, as appropriate) |
| ..._random_unit_gaussian | Random assignment from a normal distribution. Average of 0.0, Standard deviation of 1.0. |
boolean ga_seed_boolean_random( population *pop, entity *adam ); boolean ga_seed_boolean_zero( population *pop, entity *adam ); boolean ga_seed_integer_random( population *pop, entity *adam ); boolean ga_seed_integer_zero( population *pop, entity *adam ); boolean ga_seed_double_random( population *pop, entity *adam ); boolean ga_seed_double_zero( population *pop, entity *adam ); boolean ga_seed_double_random_unit_gaussian( population *pop, entity *adam ); boolean ga_seed_char_random( population *pop, entity *adam ); boolean ga_seed_printable_random( population *pop, entity *adam ); boolean ga_seed_bitstring_random( population *pop, entity *adam ); boolean ga_seed_bitstring_zero( population *pop, entity *adam );
Replacement operators are only meaningful for steady-state (i.e. non-generational) evolutionary algorithms.
These follow the GAreplace function prototype.
void ga_replace_by_fitness(population *pop, entity *child);
Deliberately undocumented at present.
Ranking operators are used for assigning relative rank between two entities (e.g. for sorting population).
These follow the GArank function prototype.
int ga_replace_by_fitness(population *popalpha, entity *alpha, population *popbeta, entity *beta);
Deliberately undocumented at present.
The following functions are the recommended means for creating and initializing new population structures. They are fully discussed in the online GAUL tutorial. They primarily specify the set of callback functions to be used with a newly created and fully set-up population.
A separate function exists for each of the built-in chromosome types.
population *ga_genesis_integer( 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 *ga_genesis_boolean( 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 *ga_genesis_char( counts 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 *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 *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 );
void ga_diagnostics( void );
Writes various diagnostic data to the console.
int ga_get_major_version( void ); int ga_get_minor_version( void ); int ga_get_patch_version( void );
Return version information.
If the GAUL version is 0.1846-8, for example, then these functions will return 0, 1846 and 8, respectively.
Some simple statistics functions are available. They may be safely called at any time. But the results are likely to only be meaningful during or after evolution.
These functions should return TRUE on success and FALSE should they ever fail.
boolean ga_fitness_mean( population *pop, double *average );
boolean ga_fitness_mean_stddev( population *pop,
double *average, double *stddev );
boolean ga_fitness_stats( population *pop,
double *max, double *min,
double *mean, double *median,
double *variance, double *stddev,
double *kurtosis, double *skew );
These functions may be used on-line or off-line (i.e. during and after evolution).
The core GAUL code is datatype agnostic, this means any representation for the chromosomes may be defined and used. The user is encouraged to use whichever chromosome type would be most appropriate for the search or optimization task being considered. For convenience, code for several of the more common chromosome types is built into GAUL:
If none of the above chromosome types are appropriate, it is a simple matter to create a new datatype for use with GAUL. The calling program just needs to define a handful a functions which are then used as callback functions. Instructions for such user-defined chromosomes are provided.
It is even possible to mix chromosome types, for example you could use an integer-valued array chromosome and a Gray coded bitstring chromosome simultaneously. Although this would require slightly more creativity to be displayed by the programmer. This process is demonstrated in the distributed examples/mixed.c example.
GAUL is extensively, and routinely, used with more exotic chromosome types including trees and molecular graphs.
Some low-level bitstring handling functions are made available through the public API for convenience.
byte *ga_bit_new( int length ); void ga_bit_free( byte *bstr ); void ga_bit_set( byte *bstr, int n ); void ga_bit_clear( byte *bstr, int n ); void ga_bit_invert( byte *bstr, int n ); boolean ga_bit_get( byte *bstr, int n ); void ga_bit_randomize( byte *bstr, int n ); void ga_bit_copy( byte *dest, byte *src, int ndest, int nsrc, int length ); size_t ga_bit_sizeof( int length ); byte *ga_bit_clone( byte *dest, byte *src, int length ); /* Integer conversion. */ unsigned int ga_bit_decode_binary_uint( byte *bstr, int n, int length ); void ga_bit_encode_binary_uint( byte *bstr, int n, int length, unsigned int value ); int ga_bit_decode_binary_int( byte *bstr, int n, int length ); void ga_bit_encode_binary_int( byte *bstr, int n, int length, int value ); int ga_bit_decode_gray_int( byte *bstr, int n, int length ); unsigned int ga_bit_decode_gray_uint( byte *bstr, int n, int length ); void ga_bit_encode_gray_uint( byte *bstr, int n, int length, unsigned int value); /* Real conversion. */ double ga_bit_decode_binary_real( byte *bstr, int n, int mantissa, int exponent); void ga_bit_encode_binary_real( byte *bstr, int n, int mantissa, int exponent, double value ); double ga_bit_decode_gray_real( byte *bstr, int n, int mantissa, int exponent ); void ga_bit_encode_grayy_real( byte *bstr, int n, int mantissa, int exponent, double value ); /* Test. */ boolean ga_bit_test( void );
todo
This is a set of functions for computing the similarity between two entities' genomes.
double ga_compare_char_hamming( population *pop, entity *alpha, entity *beta ); double ga_compare_char_euclidean( population *pop, entity *alpha, entity *beta ); double ga_compare_integer_hamming( population *pop, entity *alpha, entity *beta ); double ga_compare_integer_euclidean( population *pop, entity *alpha, entity *beta ); double ga_compare_double_hamming( population *pop, entity *alpha, entity *beta ); double ga_compare_double_euclidean( population *pop, entity *alpha, entity *beta ); double ga_compare_boolean_hamming( population *pop, entity *alpha, entity *beta ); double ga_compare_boolean_euclidean( population *pop, entity *alpha, entity *beta ); double ga_compare_bitstring_hamming( population *pop, entity *alpha, entity *beta ); double ga_compare_bitstring_euclidean( population *pop, entity *alpha, entity *beta );
The genome comparison functions either return the Hamming distance or the Euclidean distance between all chromosomes in the two entities.
These functions are typically used as comparison operator callbacks in the Deterministic Crowding algorithm, but my be used seperately in any code.
A number of non-evolutionary search and optimization functions are provided. These are intended for use as local optimization methods or for comparison against the genetic algorithms. However, they may also be used in their own right.
All of the alternative functions are used in a similar way. A function named ga_population_set_XXX_parameters() is used to define appropriate run-time options, where XXX is the name of the optimization method. A separate function, generally similar to the ga_evolution() function, is used to perform the actual optimization.
The Tabu search has been proven effective at solving many search and optimization problems. It is a heuristic method which guides a local search procedure to explore the search space in such a way that entrapment in local minima is avoided. Unlike simple hill-climbing search techniques, but like simulated annealling, the Tabu search often moves from a current solution to one which is worse, with the expectation that this move will eventually lead to an even better solution.
void ga_population_set_tabu_parameters( population *pop, GAtabu_accept tabu_accept, const int list_length, const int search_count); int ga_tabu( population *pop, entity *initial, const int max_iterations );
ga_tabu() is called to perform a tabu search. The initial entity parameter may be NULL, in which case the standard seed operator is used to create a starting solution for the search. max_iterations specifies the maximum number of iterations to perform. The actual number of iterations performed is returned.
As with the usual evolutionary optimization functions, the optimization may be terminated earlier. One difference is that the GAiteration_hook callback defined in the population structure is used instead of GAgeneration_hook.
Before ga_tabu() may be used, the population must be initialized and ga_population_set_tabu_parameters() must be called to specify the tabu search parameters.
The list_length parameter specifies to maximum length of the tabu list. search_count is the number of search moves to make at each step, or iteration. The best choice of values for these two parameters are highly problem dependent.
tabu_accept is a callback function that is used to perform the necessary tabu and aspiration checks. Five built-in functions are provided for use with the built-in chromosome types.
boolean ga_tabu_check_integer( population *pop, entity *putative, entity *tabu ); boolean ga_tabu_check_boolean( population *pop, entity *putative, entity *tabu ); boolean ga_tabu_check_char( population *pop, entity *putative, entity *tabu ); boolean ga_tabu_check_double( population *pop, entity *putative, entity *tabu ); boolean ga_tabu_check_bitstring( population *pop, entity *putative, entity *tabu );
The search moves are made using any of the standard mutation operators.
The simplex algorithm is commonly applied to solve linear programming problems. It is relatively effective on noisy fitness landscapes but often does not sample the entire search space. A canonical simplex search algorithm places N+1 points randomly in the N dimensional search space. The worst point is reflected across the plane defined by the other N points. Then the points are contracted or expanded according to the characteristics of the search space that they cover. These two steps are repeated until some convergence criteria are satisfied. In two or three dimensional space, the set of points resemble an amoeba creeping around to the global maximum.
void ga_population_set_simplex_parameters( population *pop,
const int dimensions, const double step,
const GAto_double to_double, const GAfrom_double from_double );
int ga_simplex( population *pop, entity *initial, const int max_iterations );
int ga_simplex_double( population *pop, entity *initial, const int max_iterations );
todo
Functions are included for performing an optimization using the method known as deterministic crowding. This approach is useful when you desire a significant amount of diversity in the resulting population. This was originally conceived as as a niching algorithm rather than a true optimization algorithm.
In this implementation, children potentially replace their parents as soon as they are created rather than replacing them at the end of the generation. Thus, this differs slightly from the canonical deterministic crowding algorithm.
void ga_population_set_deterministiccrowding_parameters( population *pop, const GAcompare compare ); int ga_deterministiccrowding( population *pop, const int max_generations );
The deterministic crowding function can almost be used as a drop in replacement for the standard GA function, except that ga_population_set_deterministiccrowding_parameters() must be called to specify a chromosome comparison function. This comparison function is specific to the chromosome datatype and it defines the required distance metric. The built-in genome comparison functions may be used here, or the programmer might wish to create task specific comparison functions.
Functions are included for performing an optimization using the Differential Evolution algorithm.
Differential Evolution (DE) is a population-based, stochastic function optimiser using vector differences for perturbing the population. DE often exhibits a compelling performance advantage over conventional genetic algorithms. GAUL's implementation of DE thus offers a powerful method for optimising vectors. The crucial idea behind DE is the scheme for generating trial parameter vectors that adds the weighted difference between vectors in the population to a selected vector.
void ga_population_set_differentialevolution_parameters( population *pop,
const ga_de_strategy_type strategy,
const ga_de_crossover_type crossover,
const int num_perturbed,
const double weighting_min,
const double weighting_max,
const double crossover_factor );
int ga_differentialevolution( population *pop, const int max_generations );
The deterministic crowding function can almost be used as a drop in replacement for the standard GA function, except that ga_population_set_differentialevolution_parameters() must be called prior to ga_differentialevolution().
strategy can take the values GA_DE_STRATEGY_BEST, GA_DE_STRATEGY_RAND or GA_DE_STRATEGY_RANDTOBEST and this determines the selection strategy.
crossover can take the values GA_DE_CROSSOVER_BINOMIAL or GA_DE_CROSSOVER_EXPONENTIAL and this determines the crossover strategy.
num_perturbed specifies the number of selected solutions for each perturbation. This may take values of 1, 2 or 3 for GA_DE_STRATEGY_BEST or GA_DE_STRATEGY_RAND and 1 or 2 for GA_DE_STRATEGY_RANDTOBEST.
weighting_min and weighting_max correspond to the F parameter (and also the K parameter in some cases) in the original published description of the algorithm. If these share the same value, they relate to the weighting of perturbations exactly as originally described. If these have different values, they impose bounds for a random selection of weighting factor at the beginning of each generation.
crossover_factor corresponds to the CR parameter in the original published description of the algorithm. This relates to the proportion of alleles that are perturbed in a selected solution.
Simulated annealling techniques have been applied to a wide variety of optimization problems, including the clustering problem and the job scheduling problem.
Annealing techniques simulate the physical annealling process in which metals are heated and then slowly cooled, with the result being a solid having a state of lower energy than the original solid. In an annealling process a solid is heated until liquefied, and slowly cooled sifficiently slowly that the system is, at any time, approximately at thermodynamic equilibrium. As cooling proceeds, the system becomes more ordered and approaches a state of lowest energy. Systems that are slowly cooled (annealled) may reach a global minimum in energy, as opposed to becoming solidified in a local minima because the process of slow cooling allows the constituent molecules time to reorder themselves in states of progressively less energy.
The simulated annealling routines in GAUL are sufficiently flexible to enable Monte Carlo simulations to be performed too.
boolean ga_sa_boltzmann_acceptance(population *pop, entity *original, entity *new);
boolean ga_sa_linear_acceptance(population *pop, entity *original, entity *new);
void ga_population_set_sa_temperature(population *pop, const double temp);
double ga_population_get_sa_temperature(population *pop);
void ga_population_set_sa_parameters(population *pop,
GAsa_accept sa_accept,
const double initial_temp, const double final_temp, const double temp_step, const int temp_freq);
int ga_sa(population *pop, entity *initial, const int max_iterations);
todo
A couple of hill climbing heuristic algorithms are provided in GAUL for local searches and for comparison to GAs. The basic concept of all hill climbing algorithms is very simple. Individual alleles are modified in such a way that the overall fitness is maximized. Hill climbing algorithms are typically very efficient at locating local maxima although this leads to their major deficiency; they tend to get stuck at local maxima rather than continuing to the proper global maximum.
void ga_population_set_hillclimbing_parameters(population *pop, GAmutate_allele mutate_allele); int ga_next_ascent_hillclimbing(population *pop, entity *initial, const int max_iterations); int ga_random_ascent_hillclimbing(population *pop, entity *initial, const int max_iterations);
todo
Routines for local search and optimization using non-evolutionary methods. These methods are all first-order, that is, they require first derivatives.
Note that, these algorithms require that chromosomes may be reversibly mapped to arrays of double-precision floating-point array chromosomes. If this is not possible, ten these functions can not be used.
It is often important to think carefully about the appropriate convergence criteria.
void ga_population_set_gradient_parameters( population *pop,
const GAto_double to_double, const GAfrom_double from_double, const GAgradient gradient,
const int dimensions, const double step_size);
int ga_steepestascent( population *pop, entity *initial, const int max_iterations );
int ga_steepestascent_double( population *pop, entity *initial, const int max_iterations );
ga_steepestascent() performs optimization on the passed entity by using a steepest ascents method (i.e., steepest descent, except maximizing the fitness function). The passed entity will have its data overwritten. The remainder of the population will be let untouched. Note that it is safe to pass a NULL initial structure, in which case a random starting structure will be generated, however the final solution will not be available to the caller in any obvious way.
ga_steepestascent_double() is a version that does not require definition of the to_double, from_double and dimensions parameters. These may be specified as NULL, NULL and 0 to the ga_population_set_gradient_parameters() function. It is, however, restricted to populations with a single double-array chromosome.
todo
A function that implements a systematic search procedure.
void ga_population_set_search_parameters( population *pop, GAscan_chromosome scan_chromosome ); int ga_search( population *pop, entity *initial );
todo
Unlike the other search methods, this does not require prior definition of any parameters.
int ga_random_search( population *pop, entity *initial, const int max_iterations );
This performs a random search procedure by repeatedly calling the seed and evaluation operators. The passed entity will have its data overwritten. The remainder of the population will be let untouched. Note that it is safe to pass a NULL initial structure, in which case a random starting structure will be generated, however the final solution will not be available to the caller in any obvious way.
It is strongly recommended that this function is only used for benchmarking purposes!
GAUL respects the values of a number of environment variables. These are listed and described below, but not that the actual names of the variables may been altered at compile time.
| GAUL_NUM_PROCESSES | The maximum number of processes to spawn at one time in ga_evolution_forked(). |
| GAUL_NUM_THREADS | The maximum number of threads to use at any one time. |
To do. For now see the S-Lang tutorial for GAUL.
Perl wrapper for GAUL are in an experimental stage. Interested readers are referred to the CVS archive for the current freely available code.
Several libraries of utility functions are distributed with the GAUL source code. These were written for rapid and easy development of portable C code.
Any of these functions may be used independently of GAUL. Many of them are routinely used in several projects, both licensed under the GPL and propriety. They are generally very simple to use. These sets of functions include:
| linkedlist | Single-link and double-link list datastructures. |
| avltree | Adel'son-Velskii and Landis tree (or, height-balanced 1-tree) datastructure. |
| memory_util | Memory handling routines. |
| random_util | Stateful-pseudo-random number generation routines. |
| log_util | Multithread/Multiprocessor-safe logging routines routines. |
| table_util | Indexed data table routines. |
| timer_util | Simple timer routines. |
| compatibility | Compatibility functions. |
Linked lists are very powerful, yet simple, container structures. Two versions are implemented.
Wrappers are also provided to mimic the glib list functions. These can, generally, be used as a drop in replacement.
typedef int (*LLCompareFunc)(constvpointer data1, constvpointer data2);
typedef boolean (*LLForeachFunc)(vpointer data, vpointer userdata);
typedef void (*LLDestructorFunc)(vpointer data);
typedef struct DLList_t
{
struct DLList_t *next; /* Next element. */
struct DLList_t *prev; /* Prev element. */
vpointer data; /* Data stored in this element. */
} DLList;
typedef struct SLList_t
{
struct SLList_t *next; /* Next element. */
vpointer data; /* Data stored in this element. */
}
void linkedlist_init_openmp(void);
SLList *slink_new(void);
void slink_free_all(SLList *list);
void slink_free(SLList *list);
SLList *slink_append(SLList *list, vpointer data);
SLList *slink_prepend(SLList *list, vpointer data);
SLList *slink_insert_next(SLList *list, vpointer data);
SLList *slink_insert_index(SLList *list, vpointer data, int index);
SLList *slink_delete_data(SLList *list, vpointer data);
SLList *slink_delete_all_data(SLList *list, vpointer data);
SLList *slink_delete_link(SLList *list, SLList *link);
SLList *slink_clone(SLList *list);
SLList *slink_reverse(SLList *list);
SLList *slink_nth(SLList *list, const int index);
vpointer slink_nth_data(SLList *list, const int index);
SLList *slink_find(SLList *list, vpointer data);
SLList *slink_find_custom(SLList *list, vpointer data, LLCompareFunc func);
int slink_index_link(SLList *list, SLList *link);
int slink_index_data(SLList *list, vpointer data);
SLList *slink_last(SLList *list);
int slink_size(SLList *list);
boolean slink_foreach(SLList *list, LLForeachFunc func, vpointer userdata);
SLList *slink_sort_merge (SLList *l1, SLList *l2, LLCompareFunc compare_func);
SLList *slink_sort(SLList *list, LLCompareFunc compare_func);
DLList *dlink_new(void);
void dlink_free_all(DLList *list);
void dlink_free(DLList *list);
DLList *dlink_append(DLList *list, vpointer data);
DLList *dlink_prepend(DLList *list, vpointer data);
DLList *dlink_insert_next(DLList *list, vpointer data);
DLList *dlink_insert_prev(DLList *list, vpointer data);
DLList *dlink_insert_index(DLList *list, vpointer data, int index);
DLList *dlink_delete_all_data(DLList *list, vpointer data);
DLList *dlink_delete_data(DLList *list, vpointer data);
DLList *dlink_delete_link(DLList *list, DLList *link);
DLList *dlink_clone(DLList *list);
DLList *dlink_reverse(DLList *list);
DLList *dlink_nth(DLList *list, const int index);
DLList *dlink_pth(DLList *list, const int index);
vpointer dlink_nth_data(DLList *list, const int index);
vpointer dlink_pth_data(DLList *list, const int index);
DLList *dlink_find(DLList *list, vpointer data);
DLList *dlink_find_custom(DLList *list, vpointer data, LLCompareFunc func);
int dlink_index_link(DLList *list, DLList *link);
int dlink_index_data(DLList *list, vpointer data);
DLList *dlink_last(DLList *list);
DLList *dlink_first(DLList *list);
int dlink_size(DLList *list);
boolean dlink_foreach(DLList *list, LLForeachFunc func, vpointer userdata);
boolean dlink_foreach_reverse(DLList *list, LLForeachFunc func, vpointer userdata);
DLList *dlink_sort_merge(DLList *l1, DLList *l2, LLCompareFunc compare_func);
DLList *dlink_sort(DLList *list, LLCompareFunc compare_func);
void linkedlist_diagnostics(void);
todo
Tree structures are discussed in all good programming textbooks. This is an efficient implementation of the AVL tree structure.
typedef AVLKey (*AVLKeyFunc)(constvpointer data);
typedef boolean (*AVLTraverseFunc)(AVLKey key, vpointer data, vpointer userdata);
typedef boolean (*AVLMatchFunc)(constvpointer data, vpointer userdata);
typedef int (*AVLSearchFunc)(constvpointer data, vpointer userdata);
typedef void (*AVLDestructorFunc)(vpointer data);
typedef struct AVLTree_t
{
struct AVLNode_t *root; /* opaque from hereonin. */
AVLKeyFunc key_generate_func;
} AVLTree;
void avltree_init_openmp(void);
AVLTree *avltree_new(AVLKeyFunc key_generate_func);
void avltree_delete(AVLTree *tree);
void avltree_destroy(AVLTree *tree, AVLDestructorFunc free_func);
boolean avltree_insert(AVLTree *tree, vpointer data);
vpointer avltree_remove(AVLTree *tree, vpointer data);
vpointer avltree_remove_key(AVLTree *tree, AVLKey key);
vpointer avltree_lookup(AVLTree *tree, vpointer data);
vpointer avltree_lookup_lowest(AVLTree *tree);
vpointer avltree_lookup_highest(AVLTree *tree);
vpointer avltree_lookup_key(AVLTree *tree, AVLKey key);
vpointer avltree_ordered_search(AVLTree *tree, AVLSearchFunc search_func, vpointer userdata);
vpointer avltree_search(AVLTree *tree, AVLMatchFunc search_func, vpointer userdata);
void avltree_traverse(AVLTree *tree, AVLTraverseFunc traverse_func, vpointer userdata);
int avltree_height(AVLTree *tree);
int avltree_num_nodes(AVLTree *tree);
void avltree_diagnostics(void);
todo
Flexible wrapper around the standard malloc() routines, along with an efficient memory pool implementation.
memory_util.c is intended as a general purpose, portable, memory tracking package that replaces the system calls realloc(), calloc(), realloc(), strdup() and free() with "safer" routines while keeping track of all the memory currently allocated. Additional facilities to enable array overflow checks are included.
The neat thing about all this is that it can sit over the top of any other memory debugging library which replaces the standard malloc routines, transparently.
Has an easy-to-use memory chunk implementation. Chunks are created/destroyed using mem_chunk_new() and mem_chunk_destroy(). Individual atoms are created/destroyed using mem_chunk_alloc() and mem_chunk_free(). This may be disabled by defining MEMORY_NO_CHUNKS at compile time.
Compile the code with MEMORY_ALLOC_SAFE for simple wrappers around the standard system allocation memory routines. Compile with MEMORY_ALLOC_DEBUG for fully auditing wrappers. Compile with neither for the standard routines only. When MEMORY_ALLOC_DEBUG is defined or MEMORY_NO_CHUNKS is not defined, my AVL tree implementation is required.
FAQ:
Q. Why not just use Purify?
A. I can't afford it.
Q. Well, ElectricFence is free - so why not use that?
A. It is horrendously slow, and a huge memory hog.
s_malloc(X) s_calloc(X,Y) s_realloc(X,Y) s_malloc_labelled(X, Y) s_strdup(X) s_strndup(X, Y) s_free(X)
typedef struct MemChunk_t MemChunk; void mem_chunk_init_openmp(void); MemChunk *mem_chunk_new(size_t atom_size, unsigned int num_atoms); MemChunk *mem_chunk_new_unfreeable(size_t atom_size, unsigned int num_atoms); boolean mem_chunk_has_freeable_atoms(MemChunk *mem_chunk); boolean mem_chunk_isempty(MemChunk *mem_chunk); void mem_chunk_destroy(MemChunk *mem_chunk); void *mem_chunk_alloc(MemChunk *mem_chunk); void mem_chunk_free(MemChunk *mem_chunk, void *mem); void mem_chunk_clean(MemChunk *mem_chunk); void mem_chunk_reset(MemChunk *mem_chunk); boolean mem_chunk_test(void); boolean mem_chunk_check_all_bounds(MemChunk *mem_chunk); boolean mem_chunk_check_bounds(MemChunk *mem_chunk, void *mem); void mem_chunk_diagnostics(void);
todo
Routines for random number generation.
Portable routines for generating pseudo random numbers with the following features:
The algorithm used is the Mitchell and Moore variant of the standard additive number generator. The required array of numbers is populated by a using single seed value by using a linear congruential pseudo random number generator.
This routines have been tested and provide the same output (within the limits of computational precision) on (at least) the following platforms:
Usage:
typedef struct random_state_t
{
unsigned int v[RANDOM_NUM_STATE_VALS];
int j, k, x;
} random_state;
unsigned int random_rand(void);
void random_seed(const unsigned int seed);
void random_tseed(void);
void random_init(void);
boolean random_isinit(void);
char *random_get_state_str(void);
unsigned int random_get_state_str_len(void);
void random_set_state_str(char *state);
random_state random_get_state(void);
void random_set_state(random_state state);
boolean random_boolean(void);
boolean random_boolean_prob(const double prob);
unsigned int random_int(const unsigned int max);
int random_int_range(const int min, const int max);
double random_double_full(void);
double random_double(const double max);
double random_double_range(const double min, const double max);
double random_double_1(void);
double random_unit_uniform(void);
double random_gaussian(const double mean, const double stddev);
double random_unit_gaussian(void);
void random_diagnostics(void);
boolean random_test(void);
float random_float_full(void);
float random_float(const float max);
float random_float_range(const float min, const float max);
float random_float_1(void);
float random_float_unit_uniform(void);
float random_float_gaussian(const float mean, const float stddev);
float random_float_unit_gaussian(void);
float random_float_cauchy(void);
float random_float_exponential(void);
void random_int_permutation(const int size, int *iarray, int *oarray);
todo
Flexible log handling.
enum log_level_type {
LOG_NONE=0, /* No messages - I recommend that this isn't used! */
LOG_FATAL, /* Fatal errors only */
LOG_WARNING, /* Warning messages */
LOG_QUIET=3, /* Normal messages */
LOG_NORMAL=3, /* - " - */
LOG_VERBOSE, /* Verbose messages */
LOG_FIXME, /* Development reminders */
LOG_DEBUG /* Debugging messages */
};
typedef void (*log_func)(const enum log_level_type level,
const char *func_name,
const char *file_name,
const int line_num,
const char *message);
void log_init(enum log_level_type level, char *fname, log_func func,
boolean date);
void log_set_level(enum log_level_type level);
void log_set_file(const char *fname);
extern enum log_level_type log_get_level(void);
void log_output( const enum log_level_type level,
const char *func_name,
const char *file_name,
const int line_num,
const char *format, ... );
void plog( const enum log_level_type level, const char *format, ... );
todo
Simple indexed table implementation.
typedef struct TableStruct_t
{
vpointer *data;
unsigned int *unused;
unsigned int size;
unsigned int numfree;
unsigned int next;
} TableStruct;
TableStruct *table_new(void);
void table_destroy(TableStruct *table);
boolean table_set_size(TableStruct *table, unsigned int size);
vpointer table_remove_index(TableStruct *table, unsigned int index);
unsigned int table_remove_data(TableStruct *table, vpointer data);
unsigned int table_remove_data_all(TableStruct *table, vpointer data);
vpointer table_get_data(TableStruct *table, unsigned int index);
vpointer *table_get_data_all(TableStruct *table);
unsigned int *table_get_index_all(TableStruct *table);
unsigned int table_lookup_index(TableStruct *table, vpointer data);
unsigned int table_add(TableStruct *table, vpointer data);
unsigned int table_count_items(TableStruct *table);
void table_diagnostics(void);
todo
Simple timer routines. S-Lang intrinsic function wrappers are provided.
typedef struct
{
clock_t begin_clock, save_clock;
time_t begin_time, save_time;
} chrono_t;
void timer_diagnostics(void);
void timer_start(chrono_t *t);
double timer_check(chrono_t *t);
todo
Functions and wrappers used to simplify porting efforts. These may be used to overcome the problem of functions used being missing on certain target platforms.
int ipow(int n, int e); double dpow(double n, int e); size_t strlen(const char *str); int strcmp(const char *str1, const char *str2); int strncmp(const char *str1, const char *str2, size_t len); char *strcpy(char *str1, const char *str2); char *strncpy(char *str1, const char *str2, size_t len); char *strpbrk(const char *s, const char *accept); char *strsep(char **str, const char *delim); int strcasecmp(const char *str0, const char *str1); int strncasecmp(const char *str0, const char *str1, size_t n); void usleep(unsigned long usec); void memcpy(char *dest, const char *src, size_t len); char *strdup(const char *str); char *strndup(const char *str, size_t n); void dief(const char *format, ...); size_t strspn(const char *string, const char *accept); size_t strcspn(const char *string, const char *reject); pid_t waitpid(pid_t pid, int *pstatus, int options); int min(int a, int b); int max(int a, int b); void sincos( double radians, double *s, double *c ); int gethostname(char *name, size_t len);
Each of these functions are missing on at least one of the systems on which GAUL might be used. Most of these functions might be considered standard and are replicated to faciliate porting of GAUL. dief() is an unusual function that is used by GAUL in case of a fatal error.
Numerous example programs are distributed with GAUL. Some of these are discussed or annotated in the online tutorial.
Solves the table-tennis championship problem presented in: Dennis E. Shasha, "Dr Ecco's Omniheurist Corner: Foxy", Dr Dobb's Journal, 323:148-149 (2001). Uses a single 25 integer chromosome with custom mutation and crossover operators. This is a perturbation problem. Equivalent, non-GA, versions are also given for the purpose of demonstarating and comparing the built-in search heuristics.
Solves a function of the form (0.75-A)+(0.95-B)^2+(0.23-C)^3+(0.71-D)^4 = 0. Equivalent, non-GA, versions are also given for the purpose of demonstrating and comparing the built-in search heuristics.
Solves the fire-fighting problem presented in: Dennis E. Shasha, "Dr Ecco's Omniheurist Corner: Wildfires", Dr Dobb's Journal, 320:193-194 (2001). Uses a single boolean array chromosome.
Ports of the examples from Goldberg's book. Note that I have never read Goldberg's book, so I can't check these. If someone wants to donate the book to me then I would be very grateful ;)
John Holland's Royal Road problem.
This is a set of examples, each adds or modifies procedures from the previous ones as explained in detail in the GAUL tutorial. These programs aim to generate the final sentence from Chapter 3 of Darwin's "The Origin of Species", entitled "Struggle for Existence". They all use a basic character-valued array chromosome.
This example evolves a fixed topology neural network. Although the topology of the network is fixed, certain learning parameters are evolved along with the weights. The genome consists of a single chromosome which is simply a datastructure containing the neural network. This is an example where population->len_chromosome is ignored. Both crossover and mutation rates are comparatively low, whilst the Lamarckian adaptation affects all members of the population by performing standard back-propagation with momentum.
An adaptation of the struggle example to illustrate the ga_population_read() and ga_population_write() functions for storing data in files.
This program may be used as follows. When a population is read back from disk, evolution will continue from the point at which it finished prior to being saved to disk.
saveload [-n INTEGER] [-i FILENAME] -o FILENAME -o FILENAME Write a population file to FILENAME. -i FILENAME Read population from FILENAME, otherwise create a new population. -n INTEGER Number of generations to perform. [default=10]
Last Updated 5th April, 2009 by Stewart Adcock.