Overview

The class GeneticAlgorithms from this package implements a set of well-known Genetic Algorithms (GAs), in particular those propagated by Goldberg [1] for biallelic (binary) and triallelic (ternary) chromosomes and Schwefel [2] for those containing floating point numbers as the alphabet of their genes. Those GAs can be used for parameter optimization for arbitrary objective functions. The "chromosomes" carrying the "genetic" information (i.e. the genotype leading to a phenotype which comprises the parameters to be optimized) are thought of containing genes with alleles of a given alphabet. The alphabet is provided by the user and must be given either as a list of alleles or as the type float, in which case the elements of the alphabet are the floating point numbers in the interval [0 .. 1]. In another common case the alleles consist of the sequence of consecutive integers, and the genes are permutation of this sequence. This option is selected by setting the pmx parameter (see below) in the constructor to True. The user must also provide the objective function as a Python function and a Python decoder function that converts a given "genotype" (an instance of the class Genotype from this package) to the parameter list the objective function expects (the phenotype). One such generic decoder function is provided as a static method for biallelic haploid, triallelic diploid chromosomes, and those containing permutations of a sequence of integers as well as those with floating point alleles. In this function, Biallelic chromosomes draw from the alphabet [0,1] and triallelic from the alphabet [-1,0,1], where -1 represents a recessive 1, 0 a 0, and 1 a dominant 1. Alleles of type float and those consisting of sequences of integers are only supported for haploid chromosomes. This generic mapping function works well for most simple cases where parameters should be kept separate in different chromosomes to protect them from inter-parameter crossover. It is, of course, also possible to map the elements of an alphabet or floating point representation of multiple parameters onto a single chromosome. The decoding of this arrangement, however, can no longer be implemented as a generic method since it requires task-specific knowledge about how many parameters there are, in the case of biallelic representation ([0,1] alphabet) how many bits should represent each parameter, and in which order they are; the decoding function must therefore be provided by the user in this case. The user also specifies whether the chromosomes should be haploid or diploid, how many chromosomes there ought to be, and how long each of them is. This class is oblivious to how the chromosomes are converted to the parameters for the objective function and what those parameters mean; all it knows internally are the chromosomes and the genes they contain. Since the class does not use any numerical methods in the space of the parameters for the objective function, such as gradients, it is numerically very stable. The flip side of that is that GAs (just like their biological counterparts) are also rather "dumb" exactly because they cannot employ any information about the problem in any intelligent way - in a sense, they are the perfection of the application of dumb luck.

This class then starts with a random population of genotypes with a given size that must be greater than the size of the allele alphabet (but usually should be much more than an order of magnitude bigger) and computes their "fitness" using the provided decoder to convert the genotype into the a phenotype and objective function, which serves as the environment. The objective function must return a single "fitness" value which must be non-negative and monotonously rising with improved outcome quality or "better" outcome in whatever sense the user has in mind for the optimization. This class then computes a new generation of a population using the genetic manipulations "selective mating," "crossover," "mutation," "selection of the fittest," and "inversion." This process can be repeated arbitrarily many times. In the case of biallelic chromosomes, it can be proven that the beneficial traits (schemata) represented in chromosomes grow exponentially from one generation to the next (Schema Theorem, see [1]).

This class provides a rich set of parameters to fine-tune the behavior of the GAs. Outside of the mentioned alphabet, which defaults to [0,1], and the type, number, and lengths of the chromosomes, there is first the size of the initial population. Then there is a factor to control the population growth and one to control the amount of over-population before the selection of the fittest takes effect. The former defaults to 1 (i.e. there is neither growth nor shrinking of the population from one generation to the next), and the latter defaults to 1.3 (i.e. the population will temporarily grow by a factor of 1.3 and the selection of the fittest will then kill off about one fourth of the population to get to the initial target population size). Then, the probabilities for crossover and mutation can be selected. The former defaults to 0.6 for standard chromosomes, 0 for floating point chromosomes, and 0.9 for integer sequence chromosomes, the latter to 0.0333 for standard chromosomes, to 0.3 for floating point chromosomes, and 0.4 for integer sequence chromosomes. The probability for crossover is on a per-chromosome and per offspring-pair base, that for mutation on a per-allele of all children case. For integer sequence chromosomes, the crossover probability is interpreted as the probability with which two parent chromosomes exchange sequence elements in a procedure called partially matched crossover (pmx - see [1]). The default probability for chromosome-sequence inversion is 0 in all cases. Since the "selective mating" computes mating probabilities directly from the fitness values, dominant (but not optimal) individuals may lead to premature convergence and one may want to reduce the spread of the fitness values to encourage more diversity in that situation at the beginning. Later, when most individuals cluster around the global optimum, one may want to increase the spread of the fitness values to avoid simply random selection of more or less equally performing individuals. To enable an appropriate scaling of the fitness values, a parameter fitnessScale exist that can be set to some value between 1.2 and 2 to achieve this scaling, setting it to None switches fitness scaling off. The default value for fitnessScale is 1.6 for standard chromosomes and None for integer sequence and real valued chromosomes. Then, this class provides a parameter to select monogamous propagation, which, when set to True, will restrict each individual of any generation to produce offspring with one partner only; the default for this value is False. In this context, it is also important to know that this class also allows to select the number of children each couple will produce, which defaults to 2 and must always be a multiple of 2. Since with this default setting the next generation will always have exactly the same number of individuals as the last when monogamous is set to True, couples will be allowed to divorce and re-marry until the target over population size is reached. Lastly, this class also allows to execute the evaluation of the objective function in as many threads as there are cores available. Obviously, this is particularly useful for computationally expensive objective functions. In case of floating point chromosomes, there are also the variables floatSigma and floatSigmaAdapt to set the standard deviation of the normally distributed random numbers for mutation and its adaptation, respectively. When the latter is set to 1, the standard deviation will not change based on the success rate of the mutations, otherwise it will be adjusted; the default value for the standard deviation is 1.2 and that for the standard deviation adaptation is 0.85 (see [2]).

The class collects relevant fitness statistics from each generation and makes them available as a list of dictionaries. The keys into these dictionaries are the strings: "mean", "variance", "min", "max", "crossovers", "mutations", "inversions", and "divorcerate," the latter only when monogamous is set to True. The list is available via the attribute "statistics."

Apart from these statistics, the class also provides the mutable properties pCrossover, pMutation, pInversion, populationGrowth, overPopulation, and fitnessScale, as well as floatSigma and floatSigmaAdapt to dynamically change these parameters, e.g. based on the collected statistics after any generation via a user-supplied function hook( ga ), which is given as its only argument the instance of this class that performs the genetic optimization. Thereby, this class can be extended to almost arbitrary GAs that follow the basic principles of "selective mating," "crossover," "mutation," "crossover," and "selection of the fittest" using haploid or diploid sets of chromosomes with arbitrary allele alphabets. Apart from the above mentioned read/write class properties, this class also provides the read-only properties objfunc, decoder, statistics, generation, population, pmx and best fit for the hook function to access the objective function, the decoding function, the statistics list, the number of the current generation, the current population, the pmx flag, and a tuple consisting of genome of best performing individual, phenotype of that individual as well as fitness value, respectively.

Usage Notes

To tackle a problem with this class, the first thing to do is think of an appropriate coding scheme to map the parameters to be optimized onto genes. The simplest way to do that is certainly to just use the parameters themselves as floating point values, which is easily accomplished by selecting the allele alphabet as type float. If there are more than one parameter, the others can be arranged in the same chromosome or each as its own chromosome. The latter method excludes the possibility of creating offspring using the crossover genetic procedure between the parameters in different chromosomes.

It can be shown (see [1]) that smaller alphabets in general exhibit better performance than bigger ones, which renders the use of floating point numbers as the alphabet a less than optimal choice in most cases, as there are infinitely many alleles in the alphabet of real numbers in [0 .. 1]. It is therefore usually a better idea to use bits as individual genes and interpret them as bits of integers, which then can be converted to floating point numbers in [0 .. 1] in the decoding function if the application requires that. In that case it is usually a good idea to use separate chromosomes for different parameters to shield them from the effects of crossover between different parameters.

Lastly, the method of partially matched crossover is provided for cases when the allele alphabet consists of integer sequences and the individual genomes in a population are permutations are permutations of each other. A famous application for this type is the Traveling Salesman Problem (TSP) where the sequence of integers in each genome represents the sequence the salesman would visit the cities in on his tour. However, to be more precise, what the GAs can solve in this case is the "blind" TSP, i.e. a case where the algorithm is unaware of the graph of cities or their distance matrix. This is not a very interesting case mathematically, as the only hope for success is then dumb luck, which is, as we have seen, the area where GAs excel. However, they do so only within a relatively narrow limit. If the sequence length (the number of cities) becomes much larger than 20, GAs will perform poorly.

The constructor of the class GeneticAlgorithms provides a number of sensible defaults for most of the parameters that should probably be tried first unless there are good reasons not to use them.

The unit test included in this file can serve as an example of how to use this class.

[1] David E. Goldberg, "Genetic Algorithms in Search, Optimization & Machine Learning," Addison-Wesley, 1989.

[2] Hans-Paul Schwefel, "Numerische Optimierung von Computer-Modellen mittels Evolutionsstrategie (Numerical Optimization of Computer Models using Evolution Strategy)," Birkhäuser, 1977.