Genetic Algorithms

Searching a maximum of a function

A short introduction in GA

V 1.0e

Diese Seite in Deutsch

Genetic Algorithms (GA) are counted to the adaptive random search methods. In dealing with function optimization, the minimum/maximum of a function (y=f(x)) is found based on a variation of x beginning with one or more starting points. GA envolve a set of points.
The basic element of a GA is the artifical individual. Similar to a natural individual an artifical individual consists of a chromosome and a fitness value. The fitness of an individual describes how well an individual is adapted to the nature. It determines the individual's likelihood for survival and mating. Every changing of the chromosome leads to a changing of the individual fitness.
In our case (Searching a maximum of a function) an artifical individual only consists of a value of x and y (f(x)). x play the role of a chromosome and y the role of the fitness. However, the implemented Genetic Algorithm works with a binary coded x (xc), not with the x themselve.

artifical individual

::=

I = {xc,f(x)}

A set of such individuals is called a population.

population

::=

P = {I₁,I₂,..,I_n}
n: number of individuals

Coding
The underlaying GA implementation works based on coded x value. The aim of coding is to create a representation of x which allows any position of x to be modified, to cut at any position and to splice two cutted parts onto a new x. A coded x is like a chromosome in genetics, in other words a modifiable carrier of information.
The implemented coding method is based on a binary string representation of a number (a string of 0 and 1). In the following some examples of binary-coded x values are shown. For simplification a length of 8 bit and positive integer numbers are used.

examples of coding
x	xc (binary coded x)
114	01001110
132	00100001

The whole algorithm
An initial population (parental generation) is generated at random (randomly chosen x values, calculated y values) . Based on this generation the GA creates the offspring generation by using the genetic operators Selection, Crossover and Mutation. This new generation of artifical individuals will be the new parental generation for the next offspring generation. With each new generation of individuals the overall fitness value of the population should increase. The process of creating offspring generations based on the former generation could be repeated until the optimum is reached.
The following sketch shows a single iteration step of the implemented GA in order to create 2 new individuals. This step is repeated until the number of individuals in the offspring generation is the same as that in the parental generation.

The process of creating new generations can be terminated when a predefined number of generations is achieved or when the overall fitness value of the population is not increased during the last generations.
In the following there are brief descriptions of genetic operators.

Selection
Selection is the process of picking out a suitable individual from the population in order to create a new individual. Suitable individuals are individuals with a good fitness. This operator is the implementation of the principle "survival of the fittest".
The implemented tournament selection chooses two parental individuals (father, mother) in order to create two new individuals of the offspring generation. Suitable parental individuals are such individuals with a high y value because the maximum of the function has to be found.

Examples: Selection (based on the test function F0 ; 0.0 < x < 10)
parents	x	xc (binary-coded x)	Y
P1	4	00100000	0.108
P2	8	00010000	1.22 E-08
P3	7	11100000	2.68 E-04

The upper example shows three x,y-values. P1 and P3 could be selected as "father"- and "mother"-individual. The fitness of these individuals are higher of P2.

Crossover
After the selection of the two parental individuals next step is the crossover.
Crossover is the process of creating a new coded xc by combination of two coded xc. A one-point crossover algorithm is used. Depending on a predefined probability value (p_c: probability of crossover; 0 <= p_c <= 1) the xc values of the parental individuals will be combined or not.
If the xc values are combined (crossover=true) then the binary-coded x values of the parental individuals (a bit-string) will be cutted at a randomly chosen crossover point into 2 parts. Two new coded xc values are generated by an alternate combination of these parts.

Example: Crossover
(based on function F0; 0.0 < x < 10; crossover point= 1)

Parents	x	xc (binary-coded x)	Y-Wert
PF	1	00100000	0.108
PM	7	11100000	2.68 E-04

xc (cutted)	xc (twisted)
0 0100000	1 0100000
1 1100000	0 1100000

xc (binary-coded x)	x	Y	children
10100000	5	0.798	C1
01100000	6	0.108	C2

Mutation
The last step of the Genetic Algorithm is the mutation.
Mutation is a process of changing a coded xc value randomly. An one-point mutation algorithm is implemented. The mutation will be carried out depending on the mutation probability (p_m; 0 <= p_m <= 1.0). If the xc value was mutated then the value of a randomly chosen position of the binary-coded xc is changed. That means if the value at this position is 0 it will be changed into 1 and vice versa.
In the following example C1 should not be mutated; C1 should be mutated. Position 3 of the binary-string xc is changed.

Example: Mutation
(based on function F0 ; 0.0 < x < 10; mutation position = 3)

before mutation	xc (binary-coded x)	x	Y
C1	10100000	5	0.798
C2	01100000	6	0.108

xc (binary-coded x)	x	Y	after mutation
10100000	5	0.798	C1 (no mutated)
01000000	2	1.22 E-08	C2 (mutated)

Institute of Technical Chemistry
University of Leipzig
Linne-Str. 3-4 D-04103 Leipzig
Germany

tel.:: 0341 / 9736 329
Fax: 0341 / 9736 349

email:
moros@sonne.tachemie.uni-leipzig.de

12/21/1998
last update: 12/14/1999
© 1998,1999 ITC-Leipzig/ Ralf Moros	visitors since 01/01/2000: 12/21/1998 - 12/31/1999: 210