Genetic algorithms are increasingly popular for solving optimization, search and machine learning problems. The analog between optimizing a fitness function and biological processes of natural selection and genetics is generally attributed to John H. Holland and his students at the University of Michigan. His landmark publication “Adaptation in Natural and Artificial Systems” (Holland, 1975) sparked wide ranging investigations into his approach in a variety of areas ranging from science and engineering to business.
This genetic algorithm implementation supports Holland's basic algorithm with most popular variations. This is achieved by supporting:
1. User defined population size and selection method including roulette, remainder, tournament and stochastic universal sampling both with and without replacement,
2. Random or user defined initial populations,
3. Any combination of four different data types: nominal, binary, integer and real,
4. Base 2 and Gray encoding and decoding of integer and real data types,
5. Automatic encoding and decoding of chromosome information into phenotypes,
6. User specified number of crossover points and three different options for crossover: standard, inversion and partially matched crossover,
7. Elitism to ensure fittest individuals are retained between generations,
8. User supplied fitness functions with or without additional function parameters,
9. User defined crossover and mutation probabilities,
10. Linear and sigma fitness scaling,
11. Customized and predetermined stopping criteria,
12. Measures of algorithm convergence and efficiency – velocity, on-line and off-line fitness.
The genetic encoding of a real or artificial organism is contained within their chromosomes. Each chromosome consists of a large number of genes, each uniquely located on the chromosome. Each gene in turn is composed of several alleles. In artificial organisms, i.e. genetic algorithms, an allele is encoded with discrete values.
The original simple genetic algorithm encoded alleles as either zero or one, represented by a single computer bit. This algorithm uses the same encoding for binary, integer and real phenotype values. In addition, users can specify nominal phenotypes which can use any non-negative value. This expands the basic genetic algorithm to include search domains with any number of symbols encoded as nominal phenotypes.
Each nominal phenotype is encoded into a single non-negative integer. Integer phenotypes, on the other hand, are encoded into a binary representation using either Base-2 or Gray encoding.
The crossover operation in imsls_f_genetic_algorithm handles a wide variety of allele encoding. Users define their allele encoding using single or multiple bits or a combination. In imsls_f_genetic_algorithm nominal, binary, integer and real phenotypes can be defined with any number of crossover points. The crossover and mutation probabilities can be specified. In addition, inversion can be specified for any phenotype and partially matched crossover can be automatically invoked for nominal phenotypes.
This large variety of data types, encoding and crossover options allows users to solve a wide range of search and optimization problems using imsls_f_genetic_algorithm.
In natural systems, chromosomes consist of thousands of genes, each encoded using alleles. In artificial systems, chromosomes are strings of alleles. The relationship between phenotype values and the chromosome allele data structure is created using imsls_f_ga_chromosome.
The chromosome data structure for an individual consists of an integer array representing the alleles, and additional information needed for encoding and decoding nominal, integer and real phenotype values into the allele. This information is used for implementing automatic Base-2 and Gray encoding and differentiating between nominal phenotypes requiring partially matched crossover and other classes of nominal phenotypes.
A detailed description of the Imsls_f_chromosome data structure is given in Table 1 - The Imsls_f_chromosome Data Structure. The data structure not only contains the chromosome information encoded as an integer array of alleles, it also contains phenotype values. By default, information in the allele array is automatically decoded into phenotypes. This behavior can be suppressed using the IMSLS_NO_DECODE option in the imsls_f_genetic_algorithm function.
|
Parameter |
Data Type |
Description |
|
total_length |
int |
Total number of bytes allocated to the data structure. |
|
c_length |
int |
The length of the allele array. |
|
allele |
int[] |
An array of of length c_length containing the allele values (bits) for the chromosome. |
|
n_binary |
int |
The number of binary phenotypes. |
|
n_nominal |
int |
The number of nominal phenotypes. |
|
n_integer |
int |
The number of integer phenotypes. |
|
n_real |
int |
The number of real phenotypes. |
|
n_intBits |
int |
The total number of bits in allele used to represent the integer phenotypes. |
|
n_realBits |
int |
The total number of bits in allele used to represent the real phenotypes. |
|
binaryIndex |
int |
The index of the first bit in allele used to represent the binary phenotypes. |
|
nominalIndex |
int |
The index of the first bit in allele used to represent the nominal phenotypes. |
|
integerIndex |
int |
The index of the first bit in allele used to represent the integer phenotypes. |
|
realIndex |
int |
The index of the first bit in allele used to represent the real phenotypes. |
|
n_categories |
int[] |
An array of of length n_nominal containing the maximum number of categories for each nominal phenotype. |
|
i_intervals |
int[] |
An array of length n_integer containing the number of discrete intervals used to represent each integer phenotype. |
|
i_bits |
int[] |
An array of length n_integer containing the number of bits in the allele array assigned to each integer phenotype. |
|
i_bounds |
int[] |
An array of size n_integer by 2 containing rows of lower and upper limits for each integer phenotype. |
|
r_intervals |
int[] |
An array of length n_real containing the number of discrete intervals used to represent each real phenotype. |
|
r_bits |
int[] |
An array of length n_real containing the number of bits in the allele array assigned to each real phenotype. |
|
r_bounds |
float[] |
An array of size n_real by 2 containing rows of lower and upper limits for each real phenotype. |
Table 1 - The Imsls_f_chromosome Data Structure
An individual consists of an expressed chromosome for the individual. By default the data structure for individuals also contains decoded values for all phenotypes. This allows users to program their fitness function to use phenotype values instead of their encoded allele representation.
A phenotype is the expression of a collection of genes. In organisms, this expression includes physical characteristics, such as eye color, and behavior. In artificial systems, a phenotype is generally thought of as an attribute. For function optimization problems phenotypes might be floating points or integer values. Phenotypes in a search problem might include nominal or binary encoded information about the search space.
Phenotypes are encoded into the chromosome allele as groups of bits. Later, when the fitness function is evaluated, the algorithm decodes the bits in these groups into their phenotype values. By default this is Base-2 encoding, but Gray encoding can be declared in the imsls_f_ga_individual, imsls_f_ga_random_population and imsls_f_genetic_algorithm functions. Support is provided for mapping integer and real values into allele encoding using discretization and either Base-2 or Gray encoding.
Traditional Base-2 encoding of integer and floating point phenotypes can produce binary representations with widely different representations for phenotypes with similar values. Adjacent integral values encoded using Gray's mapping differ by only one bit. For example, in binary, the numbers 15 and 16 have very different representations: 15=“01111” and 16=“10000”. The Gray encoded values for this number are closer, differing by only a single bit: 15=“01000” and 16=“11000”.
Although the majority of applications discretize integer and real phenotypes and then encode them using either Base-2 or Gray encoding, other encoding methods can be implemented by incorporating phenotype encoding and decoding into the fitness function.
Decoding of chromosome information into its associated phenotypes can be suppressed using the IMSLS_NO_DECODING argument in imsls_f_genetic_algorithm. In that case the phenotype values in the Imsls_f_individual data structure will not be updated with every crossover. They are only decoded for the final generation. Encoding can be either Base-2 or Gray. Base-2 is the default, but Gray encoding can be envoked using the IMSLS_GRAY argument in imsls_f_ga_individual, imsls_f_ga_random_population or imsls_f_genetic_algorithm.
Table 2 describes the contents of the Imsls_f_individual data structure.
|
Parameter |
Data Type |
Description |
|
encoding |
int |
Controls encoding of real and integer phenotypes. Encoding is either Base-2, the default, or Gray invoked using the optional IMSLS_GRAY argument with imsls_f_genetics_algorithm. |
|
total_length |
int |
Total number of bytes allocated to the data structure. |
|
nominalPhenotype |
int[] |
An array of integers of
length |
|
binaryPhenotype |
int[] |
An array of integers of
length |
|
integerPhenotype |
int[] |
An array of integers of
length |
|
realPhenotype |
float[] |
An array of floating point values of length chromosome->n_real containing the values of the real phenotypes. |
|
chromosome |
Imsls_f_chromosome* |
A pointer to the chromosome data structure for this individual. |
Table 2- The Imsls_f individual Data Structure
A population is a collection of individuals. A genetic algorithm operates on a population, transforming it from one generation to the next using rules including selection, reproduction, crossover and mutation. A population is described by the chromosome and individual data structures and the number of its members.
The initial population can be created randomly using imsls_f_ga_random_population, or it can be created from a user specified set of individuals using imsls_f_ga_population. Both of these functions return an Imsls_f_population data structure, which is required input to imsls_f_genetic_algorithm.
Table 3 describes the Imsls_f_population data structure.
|
Parameter |
Data Type |
Description |
|
n |
int |
The number of individuals in the population. |
|
indexFittest |
int |
The index in individual of the fittest individual within the population. |
|
indexWeakest |
int |
The index in individual of the weakest individual within the population. |
|
avgFitness |
float |
The average fitness for the population. |
|
stdFitness |
float |
The standard deviation of the fitness for the population. |
|
maxFitness |
float |
The maximum fitness of the population. |
|
minFitness |
float |
The minimum fitness of the population. |
|
fitness |
float* |
An array of the fitness values for each individual in the population. |
|
chromosome |
Imsls_f_chromosome* |
A pointer to the chromosome data structure for the individuals in the population. |
|
individual |
Imsls_f_individual** |
A pointer to an array of size n containing the individuals of the population. |
Table 3- The Imsls_f_population data structure
Note that the fitness values in this data structure are only initialized if the fitness function is passed to the imsls_f_ga_population or imsls_f_ga_random_population. Upon completion, imsls_f_genetic_algorithm updates these parameters to the values associated with the last generation.
The genetic algorithm is designed to find the phenotype that maximizes the fitness function. This is a user supplied function that describes the fitness of a particular phenotype. With each succeeding generation, the genetic algorithm transforms a population into better performing individuals as defined by the fitness function.
The fitness function is a required argument to imsls_f_genetic_algorithm. Phenotype restrictions other than simple lower and upper value boundaries are handled by incorporating a penalty function into the fitness calculation.
The optional argument IMSLS_FITNESS_FCN_WITH_PARMS allows users to have the algorithm pass individuals and parameters to the fitness function. This provides the flexibility to program a single fitness function that can be applied to a wider variety of applications.
There are many variations of the original simple genetic algorithm described by Holland (1975). Many of these were developed for particular applications or data types. imsls_f_genetic_algorithm implements both the simple algorithm as well as more advanced variations. It has also been designed to provide advanced users the flexibility to provide their own initial populations, stopping criteria, and phenotype encoding and decoding.
Once an initial population is constructed, the genetic algorithm finds a solution to the search or optimization problem using five basic operations to evolve the population from one generation to the next: selection, reproduction, crossover, mutation and fitness.
Selection is the process used to select individuals for reproduction to create the next generation. This is driven by a fitness function that makes higher fitness individuals more likely to be selected for creating the next generation.
Optimum selection of individuals for reproduction is important to the efficiency and convergence of a genetics algorithm. Many methods have been researched. imsls_f_genetic_algorithm implements the following variations: deterministic selection, roulette wheel selection with and without replacement, remainder selection with and without replacement, SUS selection, rank selection and two forms of tournament selection. Each of these can be employed with fitness scaling and elitism.
Fitness scaling is not required, but there are two options available: linear scaling and sigma scaling. See IMSLS_LINEAR_SCALING and IMSLS_SIGMA_SCALING.
After individuals are selected, reproduction involves crossing the individual's chromosomes to produce their offspring's chromosome. In the simple case, this involves exchanging genetic information by swapping bits within the parent's chromosome.
Crossover is a random process. It is controlled by the optional arguments IMSLS_CROSSOVERS and IMSLS_CROSSOVER_PROB in imsls_f_genetic_algorithm. Not all parents selected for reproduction are mated. Most genetic algorithms use a crossover probability in the range of 0.6 to 0.9. The IMSLS_CROSSOVER_PROB argument allows users to select any crossover probability between 0 and 1.
Traditionally chromosomes are crossed at a single point. However, some problems benefit from using more crossover points. The IMSLS_CROSSOVERS argument allows users to select any number of crossover points.
Once two parents are selected for crossover and their crossover points are defined, a genetic algorithm proceeds to develop a new offspring by alternately mapping alleles from the two chromosomes, swapping the source of the alleles at each crossover point.
For most applications, this creates a new offspring with a non-zero fitness value. However, for some applications, such as the traveling salesman problem, the offspring produced by this simple crossover operation will likely be infeasible. For these problems partially matched crossover and inversion crossover have been developed to ensure that the resulting offspring is a feasible solution.
Partially matched and inversion crossover are invoked using the IMSLS_PMX_CROSSOVER and IMSLS_INVERT_CROSSOVER optional arguments in imsls_f_genetic_algorithm.
Mutation stochastically switches allele settings using the mutation probability set with IMSLS_MUTATION_PROB in imsls_f_genetic_algorithm. Most applications set the mutation probability to a value in the range 0.01 to 0.001. The IMSLS_MUTATION_PROB argument accepts any probability between 0 and 1. However, high mutation rates cause the genetic algorithm to perform similar to a random search.
For users who prefer to replace imsls_f_genetic_algorithm with their own algorithm, the function imsls_f_ga_mutate can be used for mutation. Decoding of the resulting chromosome into phenotype values can be achieved using imsls_f_ga_decode.
This traditional mutation operator can produce infeasible solutions for some problems. In those cases, swap mutation is used. That is, instead of inverting a single allele value, two alleles are randomly swapped within the nominal portion of the chromosome. This allows mutation to proceed with search problems such as the traveling salesman problem.
The fitness function is a required argument to imsls_f_genetic_algorithm. The genetic algorithm function applies the fitness function to each new individual. It must be scaled to return a non-negative value.
Higher fitness values represent higher performing individuals. Constraints on integer and real phenotypes can be handled by setting lower and upper bounds. Additional constraints for these phenotypes and others should be incorporated using a penalty calculation in the fitness function.
|
Visual Numerics, Inc. PHONE: 713.784.3131 FAX:713.781.9260 |