Index of Genetic Algorithm

• 1. Introduction
• 2. Structure
  • 2.1 Population
  • 2.2 Individual
  • 2.3 Chromosome
    • 2.3.1 Multi point crossover
    • 2.3.2 Uniform crossover
    • 2.3.3 Intermediate Recombination
    • 2.3.4 Line Recombination
    • 2.3.5 Mutation
• 3. Examples
• 4. Links

1. Introduction

A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

Definition by Wikipedia

In general the genetic algorithm uses the following search strategy:

1. Creates an initial population
2. Repeat until a good solution is found or time exceeded
   1. Evaluate the fitness of each individual
   2. Select individuals for reproducation
   3. Create new individuals using the crossover and mutation
   4. Replace individuals in the population

Each loop of the reproduction is called a generation. To quit the loop there are two common possibilities: If a good solution is found or after a given number of generations (time).

The genetic algorithm of Zeus-Framework is implememted in ZeusMath Package. It implements it in a very abstract way, so it can be used and adapted for different problem domains. There are may different options for each step of the genetic algorithm. Some are implemented in the current version of Zeus-Framework.

2. Structure

The main structure is the population. The population is a set of possible solution items, called individuals. The number of individuals can vary from problem to problem. In some cases a grows is wished. In the implementation of Zeus only a constant number of individuals is supported.

The individual is built out of chromosomes. Each chromosome defines a specific problem of the individual. For simple problems one chromosome is enough.

A chromosome contains genes. Each gene contains a parameter of the problem represented by the whole chromosome.

2.1 Population

The population in Zeus-Framework is the main object and is represented with the class TGAPopulation. Lots of different options can be set for the population:

• Evaluation types
  • Small fitness is better
  • Large fitness is better
• How to cross the individuals
  • Crossing of the best individuals only
  • Crossing using all individuals, but giving the best individuals a better chance to get crossed
• How many individuals have to be crossed for each generation.
• How large is the mutation propability
• How to replace the individuals for new population
  • Replace all crossed individuals
  • Replace all individuals
  • Keep the best individuals of the existing population

To create a population a factory method is needed to create specific individuals. Look at the example how to create a population.

2.2 Individual

The individual class is abstract and must be adapted for different problem findings. It contains a list of chromosomes. Each chromosome represents a complete problem description. If there are multible problems to be solved at once using an overall fitness evaluation, each problem can be encoded in a seperate chromosome. Of course we could encode it also in one chromosome, but there are two good reasons to use different chromosomes:

1. It's easier to encode and test problems seperately and merge them together later
2. Depending on the problem the crossing might be different. Each chromosome can have a different method in crossing over.

2.3 Chromosome

The class TGAChromosome represents the chromosome of an individual. In general the chromosome is a data array and can be seen as a binary data string. This data string is split into different sections called genes. Each gene has a specific meaning and represents a parameter of the problem space. In the current implementation the size of the genes is fixed for a chromosome.

The genes are an important structure in genetic algorithm. When ever chromosomes are crossed over the genes mark the border line for crossing. It's not possible to split genes. But depending of the crossing method genes of the child might be different from the parent. Lets look at the crossing methods.

• Multi point crossover
• Uniform crossover
• Intermediate Recombination
• Line recombination

2.3.1 Multi point crossover

This crossover method is widly used to shuffle the different characteristics of an individual and create children out of parents inheriting the characteristics directly. A chromosome of the Parent A and the same chromosomes of the Parent B are aligned. Each border of the genes can be used as a crossing point (1).

Depending on the number of multi crossing points the crossing method choses the crossing points randomly (2).

Once chosen this points the children can be created. Lets start with child A. Child A gets the first genes of parent A until the first crossing point is reached. Then all genes of parent B are copied to the chromosome of child A until the next crossing point is reached. This procedure is continued until the whole chromosome of child A is generated (3).

The chromosome of child B is created in the similar way but starting copying the genes of parent B first (4).

2.3.2 Uniform crossover

The uniform crossover works in the similar way than the multi crossover method, but uses a binary crossover mask with the same length as the chromosome. The parity of the mask bits tell whether to use the information of parent A or B. Using this method crossing at any point is possible (bit tells the borders not the genes). This crossing is not yet supported with Zeus-Framework.

2.3.3 Intermediate Recombination

The inter recombination method can be used for genes of integer or real value type. Each gene can be seen as a component of a chromosome vector. The new genes of the child can be found inside an area called value space. To keep is simple it is implemented as a rectangle (cube etc, depending on the number of dimensions). The space can overlapp. For each gene a factor between [-overlapp] and [1 + overlapp] is chosen randomly.

2.3.4 Line Recombination

This recombination method works in the similar way as inter recombination does. But instead of finding a children in a value space, the children are found on a line. Therefore the randomly chosen factor is used for all genes.

2.3.5 Mutation

Using the mutation some features are randomly changed. Using this method can lead to new individuals in the problem space, where no individuals created by regular crossing exists. Sometimes this can lead to new and better results. Mathematically we can say that using crossing over will find a local optima, where as with mutation new and better optima can be found.

Mutation is not applied to every new child, but applied with a low probability, typically between 0.001 and 0.01. The mutation can be applied directly to the chromosome meaning the binary data string. Or it can be applied as a numerical value, where a number between a defined range is randomly chosen.

In Zeus-Framework the binary mutation is applied if multicrossover is used. For intermediate and line recombination the numerical mutation is used

3. Examples

Within the Zeus-Framework there are examples included for

• Goldstein Price problem
• Travelling Salesman Problem

Download the Zeus-Framework here to see the implementation.

How to use the genetic implementation of Zeus-Framework, you find some informations at the Genetic example page.

4. Links

• Detailed description about GA you find at Wikipedia
• An other site describing the problem. Genetic Algorithms.