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:

The genetic algorithm routines use a number of specialized data structures, which are described in the following sections. This document uses the names individual, population, and so forth to describe and differentiate between these structures; but please note that they are implemented as unnamed structures.

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 the GENETIC_ALGORITHM Function handles a wide variety of allele encoding. Users define their allele encoding using single or multiple bits or a combination. In the GENETIC_ALGORITHM Function 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 the GENETIC_ALGORITHM Function.

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 the GA_CHROMOSOME Function.

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 data structure is given in Table 14-1: 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 No_Decode keyword in the GENETIC_ALGORITHM Function.

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 GA_INDIVIDUAL Function, the GA_RANDOM_POPULATION Function and the GENETIC_ALGORITHM Function. 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 No_Decode keyword in the GENETIC_ALGORITHM Function. In that case the phenotype values in the 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 Gray_encoding argument in the GA_INDIVIDUAL Function, the GA_RANDOM_POPULATION Function or the GENETIC_ALGORITHM Function.

Table 14-2: The individual Data Structure describes the contents of the 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 the GA_RANDOM_POPULATION Function, or it can be created from a user-specified set of individuals using the GA_POPULATION Function. Both of these functions return a population data structure, which is required input to the GENETIC_ALGORITHM Function.

Table 14-3: population Data Structure describes the population data structure.

Note that the fitness values in this data structure are only initialized if the fitness function is passed to the GA_POPULATION Function or the GA_RANDOM_POPULATION Function. Upon completion, the GENETIC_ALGORITHM Function 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 the GENETIC_ALGORITHM Function. Phenotype restrictions other than simple lower and upper value boundaries are handled by incorporating a penalty function into the fitness calculation.

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. The GENETIC_ALGORITHM Function 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. The GENETIC_ALGORITHM Function 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 two options are available: linear scaling and sigma scaling, specified using the Linear_Scaling and Sigma_Scaling keywords respectively.

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 N_crossover_pts and Crossover_prob keywords in the GENETIC_ALGORITHM Function. 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 Crossover_prob keyword 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 N_crossover_pts keyword 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 Pmx_crossover and Invert_Crossover keyword in the GENETIC_ALGORITHM Function.

Mutation stochastically switches allele settings using the mutation probability set with Mutate_prob in the GENETIC_ALGORITHM Function. Most applications set the mutation probability to a value in the range 0.01 to 0.001. The Mutate_prob keyword 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 the GENETIC_ALGORITHM Function with their own algorithm, the GA_MUTATE Function can be used for mutation. Decoding of the resulting chromosome into phenotype values can be achieved using the GA_DECODE Function.

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 the GENETIC_ALGORITHM Function. 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.

A critical step in applying genetic algorithms to a search or optimization problem is creating a population of artificial organisms and their fitness function.

Most applications of genetic algorithms for search and optimization involve binary, nominal, integer or real phenotypes. Most introductions to genetic algorithms describe applications involving the use of simple binary phenotypes, making it easier to focus on the algorithm operations. Binary phenotypes make it possible to implement basic applications and allow users to develop their own phenotype encoding when default encodings are insufficient.

In most applications, integer and real phenotypes are encoded into chromosome bits by mapping their values into a discrete representation. Users specify upper and lower bounds for these phenotypes as well as the number of discrete intervals used for their encoding.

Nominal phenotypes are treated differently from integer phenotypes. Integer phenotypes use chromosome bits as alleles. Nominal phenotypes use groups of bits as alleles. This allows symbolic chromosome representations other than binary. Search problems such as the traveling salesman problem are best represented using nominal phenotypes with partially mixed crossover rather than binary or integer phenotypes.

Information about the nature of the phenotypes and their chromosome encoding is encapsulated in the chromosome data structure created by the GA_CHROMOSOME Function.

An individual is described by their expressed chromosome, phenotypes and parentage information. Chromosome information is encapsulated into an chromosome data structure. Individuals are represented by the individual data structure, which can be automatically created using the GA_RANDOM_POPULATION Function or systematically specified using the GA_INDIVIDUAL Function and the GA_POPULATION Function.

Typically users create an initial population of 20 to 100 individuals, depending on the length of the chromosome.

Genetic algorithms support a large variety of methods for selecting population individuals for reproduction. The initial population is either randomly selected or systematically specified using the GA_RANDOM_POPULATION Function or the GA_POPULATION Function with the GA_INDIVIDUAL Function, respectively.

Selection between generations can be done using a variety of approaches based upon individual fitness. The most common approach is stochastic selection with replacement based upon the individual’s fitness. Holland (1975) also referred to this as roulette wheel selection with replacement. Under this approach, individuals with higher fitness have a higher probability of selection. The roulette wheel selection works well when the distribution of fitness across the population is not dominated by the high fitness of a few individuals.

If the population includes a few high fitness individuals, then stochastic selection without replacement can work better than selection with replacement. When selection without replacement is used, an individual cannot be selected more than once per generation for reproduction. Effectively, this ensures that the individuals in the next generation are not generated from just a few, high fitness parents.

In addition to stochastic selection with and without replacement, the GENETIC_ALGORITHM Function also supports deterministic, remainder, tournament and stochastic universal sampling.

Reproduction involves selection and crossover using a selection and crossover model. Standard, partially matched and inversion crossover can be selected.

Mutation is the stochastic process applied to chromosome bits after crossover. Standard mutation examines each bit and determines whether it should be changed. The probability that a bit is changed is controlled by the mutation probability set using the keyword Mutate_prob with the GENETIC_ALGORITHM Function.

When partially matched crossover (PMX) is used with nominal phenotypes, the standard mutation algorithm can result in infeasible offspring. When PMX is employed the mutation algorithm is automatically changed. Instead of switching individual bits, two are randomly selected and swapped. The probability they are swapped is controlled by the mutation probability.

Since the mutation probability is generally in the range 0.001 to 0.01, mutation occurs infrequently. Still it plays a key role in halting premature convergence due to early domination by a few fit individuals resulting in a loss of diversity.