TABLE OF CONTENTS GAP.lib/--background-- GAP.lib/--data items-- GAP.lib/CreatePopulation GAP.lib/Crossover GAP.lib/DeletePopulation GAP.lib/EnterGAP GAP.lib/Evolve GAP.lib/Flip GAP.lib/GaussRand GAP.lib/HammingDist GAP.lib/InitRand GAP.lib/InRand GAP.lib/IRange GAP.lib/PopMember GAP.lib/Rnd GAP.lib/Testbit GAP.lib/--background-- GAP.lib/--background-- PURPOSE The Genetic Algorithm Programming Library (GAP-Lib) is intended to make it easier to implement genetic algorithms for any purpose. The library itself implements most of the framework needed to handle one or several populations thus leaving the programmer free to concentrate on the purpose of her program. Some work will still be needed, specifically setting up a genotype, creating a fitness function and in some cases functions for initializing, mutating, crossing and deleting individuals. OVERVIEW GAP-Lib: A Genetic Algorithm Programming Library. A library for programming with genetic algorithms. The library features a simple yet flexible interface coupled with sensible default values and quite powerful built-in functionality to provide for both high and low-level programming. The GAP-Lib is primarily bit-oriented and this is reflected in the existing default-functions for crossover and mutation. It is however possible to use almost any representation as long as the library itself only sees fixed-length individuals (Variable length individuals are possible though). A typical program using the GAP-Lib will begin by initializing the GAP environment by calling EnterGAP() then create a population using CreatePopulation() followed by some number of calls to Evolve() and finally ending with calling DeletePopulation(). The current version as of 22-Apr-1999 is 0.78 (Version 0, Revision 78). Current limitations include: · Not thread-safe (And not dynamically linked). · Need to implement variable-length individuals manually. · No special support for geographical environments. · No special support for parallell implementations. GAP.lib/--data items-- GAP.lib/--data items-- STRUCTURES GAP-Lib has three primary structures to keep track of data. One is the user-defined structure which describes an individual and though this structure is not always nessecary, it is highly recommended that you have one since it will help others to read your code. The other structure is the population structure which in turn includes a statistics structure. A member-by-member explanation of these structures follow here: struct Population { long NumPolys; long Generation; long Flags; struct Popstat Stat; long Bytes; void *Polys; void *Magic; }; NumPolys - This is the number of individuals in the population. Generation - This is how many times a generation shift has taken place. Flags - Internal status, do not touch. Stat - This is the statistics structure, see below. Bytes - Bytes per individual. Polys - This is for the internal list of individuals, do not touch. Magic - This is also internal, do not touch. struct Popstat { double AverageFitness; double MedianFitness; double TypeFitness; long TypeCount; double StdDeviation; double MaxFitness; double MinFitness; void *Max; long Generation; }; AverageFitness - The average fitness of the population. MedianFitness - The median fitness of the population. TypeFitness - The type (most common) fitness value. TypeCount - The number of individuals with the type fitness. StdDeviation - The standard deviation of the fitness values. MaxFitness - The fitness value of the fittest individual. MinFitness - The fitness value of the least fit individual. Max - A pointer to the fittest individual after the last call to Evolve(). Generation - The generation for which these statistics are valid. The Popstat structure is read-only and it is important to remember that even if you copy the structure the Max pointer will become invalid the next time Evolve() is called. TAGLISTS A taglist is a list of pairs, the first member of the pair is the tag and determines what type of data the second member is. A typical member of a taglist could look like this: {EVL_Elite,5} ^ ^ | |-> The data. |-> The type of data. A complete taglist could look like this: struct TagItem MyTaglist[]={ {EVL_Evaluator, fitfunc}, /* Fitness function */ {EVL_Elite, 5}, /* No. of elite individuals */ {TAG_DONE, 0} /* End-Tag */ }; The End-Tag, TAG_DONE, is a special tag common to all taglists. There are currently four such tags defined: TAG_DONE - Marks the end of a taglist. TAG_END - Equivalent to TAG_DONE. TAG_IGNORE - This tag is ignored. TAG_MORE - ti_Data is a pointer to a taglist with more tags, processing of the current taglist will be terminated. As some of you might be a bit lazy ;-), there is also an alternative way of specifying taglists. At least in GAP-Lib there is. As an example we have the function Evolve() which also has and interface named EvolveT(), EvolveT() takes a variable number of arguments, the last of which make up the taglist. To use the above taglist with EvolveT() one would write: EvolveT(Pop,EVL_Evaluator,fitfunc,EVL_Elite,5,TAG_DONE); ^ |->This is not part of the taglist. PRIMITIVE TYPES GAP-Lib defines one primitive data type; IPTR. The IPTR is a type large enough to hold both an integer and a pointer, it is used for the data-part of a tagitem. IPTR can be considered equivalent to intptr_t as defined in the C9X ISO C-Language standard-to-be. GAP.lib/CreatePopulation GAP.lib/CreatePopulation NAME CreatePopulation -- Allocates and initializes a population. CreatePopulationT -- Varargs interface to CreatePopulation. SYNOPSIS struct Population *CreatePopulation(long int,long int,struct TagItem *) struct Population *CreatePopulationT(long int,long int,...); Pop = CreatePopulation(Num,PSize,TagList); Pop = CreatePopulationT(Num,PSize,...); FUNCTION This function will allocate and initialize a population. If no initialization function is given, CreatePopulation() will simply randomize all bits in the created individuals. There is also a predefined initialization function which initializes every individual to a string of zero bits. INPUTS Num - Number of individuals to be created in this population. PSize - The byte-size of the individuals in this population. TagList - A pointer to a taglist. TAGS POP_Init (void (*)(void *)) - A pointer to a function or one of the values RAND_INIT or ZERO_INIT. Currently NULL is equivalent to ZERO_INIT. A function to initialize an individual should take a pointer to an individual and return nothing (void). POP_Destruct (void (*)(void *)) - A pointer to a function to be called when deleting an individual. If you are allocating resources with a custom initialization function, then you should supply this tag. The function should take a pointer to an individual and return nothing (void). POP_Cache (BOOL) - Set this to false if you are modifying the individuals between calls to Evolve() or if you really need to save memory. Default is TRUE which enables some caching of data. RESULT Pop - An initialized population structure or NULL if something failed. NOTE CreatePopulation() could fail if EnterGAP() has not been called previously (Currently not). BUGS None known. SEE ALSO EnterGAP(), DeletePopulation() GAP.lib/Crossover GAP.lib/Crossover NAME Crossover -- Perform crossover on two bitstrings. SYNOPSIS void Crossover(void *,void *,int,int); Crossover(void *Ind1,void *Ind2,int At,int Size); FUNCTION Performs one-point crossover of two bitstrings. The bitstrings must have the same length. INPUTS Ind1 - Pointer to the first bitstring (Individual). Ind2 - Pointer to the second bitstring (Individual). At - Bit to perform crossover at. Size - Size of bitstring in bytes. (OBS!: _BYTES_!!) RESULT None. NOTE Note well that all bitstrings must consist of a whole number of bytes. This is for reasons of simplicity and efficiency. BUGS None known. SEE ALSO Flip GAP.lib/DeletePopulation GAP.lib/DeletePopulation NAME DeletePopulation -- Delete a previously allocated population. SYNOPSIS void DeletePopulation(struct Population *); DeletePopulation(Pop); FUNCTION Deletes a previously allocated population and frees all resources associated with it. If no custom deallocation function was given only the resources allocated by CreatePopulation() will be freed (If CreatePopulation() was called without a custom initialization function, this is probably what you want). INPUTS Pop - Pointer to the population to be deleted. RESULT None. BUGS None known. SEE ALSO CreatePopulation() GAP.lib/EnterGAP GAP.lib/EnterGAP NAME EnterGAP -- Initialize GAP environment. SYNOPSIS void EnterGAP(int Level); EnterGAP(Level); FUNCTION Initializes the GAP environment. INPUTS Level - Level of verbosity at startup, supported values range from 0 to 2 with 0=Quiet, 1=Normal, 2=Verbose. RESULT 0 for failure, non-zero for success. EXAMPLE int main(void) { /* Do some stuff here */ ... if(EnterGAP(1)) { ... ... /* Do everything here. */ ... } else { fprintf(stderr,"Initialization failed.\n"); } return(0); /* Finished, exit. */ } BUGS None known. SEE ALSO GAP.lib/Evolve GAP.lib/Evolve NAME Evolve -- Performs generation shift on a population. EvolveT -- Varargs interface to Evolve(). SYNOPSIS struct Population *Evolve(struct Population *,struct TagItem *); struct Population *EvolveT(struct Population *,Tag,...); Pop = Evolve(Pop,TagList); Pop = EvolveT(Pop,Tag0Type,...); FUNCTION This is the big one. Evolve performs a generation shift, taking a population and returning a new one. INPUTS Pop - Pointer to an initialized population structure. TagList - Pointer to a taglist. TAGS EVL_Evaluator (double (*)(void *)) - Pointer to a function taking a pointer to an individual and returning its fitness value as a double. Note well that this tag is _required_. Also read the NOTE label further down. EVL_Mutator (void (*)(void *,int)) - Pointer to a mutator function taking a pointer to an individual and its size. This function should also decide if a mutation is to take place as it will be called exactly once for every individual in the population. NULL is a permitted value for this tag meaning that no mutation will take place. The default is to use a built-in function designed to mutate bitstrings. EVL_Crosser (void (*)(void *,void *,int)) - Pointer to a function which performs crossover on two individuals. It should take two pointers to individuals and their size and return nothing (void). It will be called exactly once for every individual generated by crossover. NULL is not a permitted value for this tag. The default is to use a built-in function designed to perform crossover on two bitstrings. EVL_Thermostat (double (*)(long,long)) - Pointer to a heat-regulating function for Boltzmann selection (TEMPERATURE). The default function is PopSize*(2.722-pow(1.0+1.0/Generation,Generation)) but this might change in later versions. The function takes the size of the population as first argument and the generation as second. EVL_Elite (int) - Sets the number of top individuals to copy from one generation to the next without crossover (with the risk for mutation though). Setting this value high will result in a steady-state type of GA. The default value is 0. Note!: Setting the Crowding flag currently alters the semantics of this tag! If Crowding is in effect the Elite number is the number of individuals not to generate. That is, in a population of eg. 20 individuals an Elite value of 15 would mean generate 5 new individuals. EVL_Flags (unsigned long int) - Bulk initialization of flag tags available flags are: FLG_InitDumped - Same as EVL_InitDumped FLG_EraseBest - Same as EVL_EraseBest FLG_Crowding - Same as EVL_Crowding FLG_Statistics - Same as EVL_Statistics Example usage: {EVL_Flags,FLG_Crowding|FLG_Statistics} **NOTE** If using EVL_Flags, you must explicitly set FLG_Statistics to generate statistics. EVL_Dump (int) - Sets the number of bottom (worst) individuals to dump by replacing them with copies of the top (best) individuals. Default is 0. EVL_Select (int) - Sets the select method used to determine parents when generating new individuals. Available methods are: DRANDOM : Double-random selection. A random individual and one of those fitter than the first one selected are chosen. (Default) FITPROP : Fitness proportionate selection. SIGMA : Sigma scaled fitness proportionate selection. TOURNAMENT : Tournament selection (fast). INORDER : Inorder selection. The fittest individual is selected together with the rest in descending order of fitness. TEMPERATURE : Boltzmann scaled selection. The selection pressure varies over time as determined by a 'heat' function. See also the EVL_Thermostat tag. UNIVERSAL : Universal stochastic selection (Improved variation on fitness proportionate selectsion). EVL_Stats (BOOL) - Generate statistics. Generating statistics will increase processing time significantly compared to not doing it. If statistics are enabled, the fitness function might be called twice as many times. Once for every old individual for evaluation and once for every new individual for generating statistics. This is dependant on caching and previous state. When caching is disabled, then the fitness function will always be called exactly twice if generating statistics. Default is TRUE. EVL_PreMutate (BOOL) - Mutate old generation instead of new. This will mutate the parent population before generating new individuals. Note that this is done after evaluation so that setting this tag to TRUE will mean that there is no nessecary connection between good genes and a high fitness - only a probability thereof (depending on the mutator function). This emulates mutation occuring in mature individuals in nature. EVL_Newbies (int) - Number of new individuals to generate. The individuals to replace will be randomly selected from the old population. This could for example be used to keep the fitness of a population down when co-evolving populations. EVL_Mensurator (double (*)(void *,void *,int)) - Pointer to a function taking two pointers to individuals and their sizes and returning the absolute value of the distance (dissimilarity measure) between them. Default is to measure the Hamming distance between individuals. EVL_Crowding (BOOL) - Use crowding replacement where each new individual generated replaces the individual most like itself. Note! This tag currently alters the meaning of the EVL_Elite tag! EVL_InitDumped (BOOL) - If dumping individuals (see EVL_Dump above) initialize them instead of replacing them with copies of the fittest indiviuals. EVL_EraseBest (BOOL) - If generating new random individuals (see EVL_Newbies tag above) replace the fittest individuals instead of random ones. RESULT Pop - A pointer to the population structure or NULL is something went horribly wrong. NOTE Note that Evolve always treats higher fitness values as better, this means that you must take care to transform your fitness values accordingly if needed before returning them. BUGS None currently known but if there are any major bugs, this is probably where they are. SEE ALSO GAP.lib/Flip GAP.lib/Flip NAME Flip -- Flip a bit in a bitstring. SYNOPSIS void Flip(void *,int); Flip(Ind,At); FUNCTION Flips a bit in a bitstring. Bits are counted from lower addresses to higher. INPUTS Ind - A pointer to the bitstring (individual). At - The bit-position to be flipped. RESULT None. BUGS None known. SEE ALSO Testbit() GAP.lib/GaussRand GAP.lib/GaussRand NAME GaussRand -- Generate a gaussian pseudo-random number. SYNOPSIS double GaussRand(double,double); Val = GaussRand(My,Sigma); FUNCTION Generates a pseudo random number around My with a Gaussian distribution. INPUTS My - Value around which to generate a random number. Sigma - Standard deviation of the generated numbers. RESULT Val - A random number. BUGS None known. SEE ALSO Rnd(), InitRand(), InRand() GAP.lib/HammingDist GAP.lib/HammingDist NAME HammingDist -- Measure the Hamming distance between two bitstrings. SYNOPSIS unsigned long int HammingDist(void *,void *,int); distance = HammingDist(Ind1,Ind2,Size); FUNCTION Counts the number of differings bits in two bitstrings. INPUTS Ind1 - Pointer to the first bitstring (Individual) Ind2 - Pointer to the second bitstring (Individual) Size - Number of _BYTES_ in each bitstring. RESULT The number of differing bits. BUGS None known. SEE ALSO GAP.lib/InitRand GAP.lib/InitRand NAME InitRand -- Initialize pseudo-random number generator. SYNOPSIS void InitRand(long); InitRand(seed); FUNCTION Initializes the internal pseudo-random number generator. This function should be called with an appropriate seed before any of the random number functions are called. Note that Evolve() also uses the random number functions. A default seed is supplied but it is not recommended to leave this as it is since every run will then be identical. INPUTS seed - A seed value for the pseudo random number generator. RESULT None. EXAMPLE #include /* For definition of NULL */ #include #include ... int main(void) { ... InitRand(time(NULL)); ... return(0); } BUGS A seed value of 0 will not work properly. SEE ALSO Rnd(), InRand(), GaussRand() GAP.lib/InRand GAP.lib/InRand NAME InRand -- Generate a bounded floating point pseudo-random number. SYNOPSIS double InRand(double,double); Val = InRand(Lo,Hi); FUNCTION Generates a pseudo random number between Lo and Hi. The resolution of the generated number is in steps of (Hi-Lo)/2147483646. INPUTS Lo - Lower bound of the range in which to generate a random number. Hi - Upper bound of the range in which to generate a random number. RESULT Val - A random number in the range [Lo,Hi] (inclusive). BUGS None known. SEE ALSO Rnd(), InitRand(), GaussRand() GAP.lib/IRange GAP.lib/IRange NAME IRange -- Map an integer onto a range. SYNOPSIS double IRange(unsigned long int,double,double); v = IRange(Val,Lo,Hi); FUNCTION Maps an unsigned long integer onto the range [Lo,Hi] (inclusive). INPUTS Val - The value to map. Lo - Lower bound of the range. Hi - Higher bound of the range. RESULT v - A value in the range [Lo,Hi]. BUGS None known. SEE ALSO InRand() GAP.lib/PopMember GAP.lib/PopMember NAME PopMember -- Get the n:th member of a population. SYNOPSIS void *PopMember(struct Population *,int); Ind = PopMember(Pop,n); FUNCTION Returns a pointer to the n:th individual in a population (counted from zero). For a population with say 50 individuals, valid numbers would range from 0 to 49. INPUTS Pop - A pointer to an population structure. n - The number of the individual to retrieve. RESULT Ind - A pointer to the n:th individual in the population. BUGS None known. SEE ALSO CreatePopulation() GAP.lib/Rnd GAP.lib/Rnd NAME Rnd -- Generate a pseudo-random integer. SYNOPSIS long int Rnd(long int); Val = Rnd(Hi); FUNCTION Generates a pseudo-random integer between zero and one less than Hi. The random number generator is cyclic and repeats after 2147483645 generated numbers. INPUTS Hi - Upper bound of random number. RESULT Val - An integer in the range [0,Hi[. BUGS Hi can not be greater than 2147483646 (0x7ffffffe = 2^31-1). This means that Rnd() only gives 31 random bits, not 32. Also, the random number algorithm 'sucks' so to speak. SEE ALSO InRand(), InitRand(), GaussRand() GAP.lib/Testbit GAP.lib/Testbit NAME Testbit -- Test the status of an arbitrary bit in a bitstring. SYNOPSIS int Testbit(void *,int); status = Testbit(Ind,At); FUNCTION Tests the status of a bit in a bitstring. Bits are counted from lower addresses to higher. INPUTS Ind - A pointer to the bitstring. At - The number of the bit to be tested. RESULT 0 if the bit is clear, non-zero otherwise. BUGS None known. SEE ALSO Flip()