Genetic Algorithms
The GA is inspired by the Darwinian theory of evolution and is a stochastic search-based optimization technique.
The Problem of Optimization
It is a methodology for minimizing/maximizing a function of variables.
For example, \(\min_x f(x)\).
That is, we need to find a value of variable \(x\) for which the function \(f(x)\) attains a minimum value.
|
Note
|
\(\max_x f(x) = \min_x(-f(x))\) |
Why are GAs necessary?
Gradient descent methods have to fulfill certain preconditions:
-
The function has to be differentiable
-
It must be convex, that is
\[\frac{d^2 f(x)}{dx^2} \gt 0\] -
Local optima may create problems
GAs need not follow these preconditions
Genes
A gene is the basic physical and functional unit of heredity.
It is made up of DeoxyriboNucleic Acid (DNA).
A gene contains the code for a specific protein that functions in one or more types of cells.
Some genes give instructions to make proteins.
-
A protein’s job is to tell your body what types of physical characteristics you should have
Some genes code RNA which does other jobs.
DNA looks like a spiral staircase (double helix).
-
The rungs are base pairs and rails are sugar and phosphate molecules.
Adenine (A) A - T
Cytosine (C) C - G
Thymine (T)
Guanine (G)
There are estimated 3 billion base pairs in a human body (only 1% is what makes you unique).
Chromosomes
Chromosomes consist of genes and are found in the cell nucleus
They appear in tiny spaghetti-like structures
Darwinian Theory of Evolution
Evolution occurs in a process of natural selection.
Stronger individuals are likely to be winners in a competing environment.
Drawing analogy with Darwinian evolution, GA does the following:
-
A set of randomly chosen candidate solutions, called population, is initially created.
-
Each candidate solution stands for an individual in the evolutionary process.
-
-
In a problem domain, a candidate solution is represented by a set of parameter values which are supposed to optimize an objective function.
-
The parameters are regarded as genes
-
The parameter values of a candidate solution, encoded in the form of a binary string, is regarded as a chromosome.
-
Let a candidate solution \((p_1, p_2) = (8, 11)\).
Assuming a 4-bit representation for each parameter, we will have the binary encoding of the candidate solution as:
Applying GA to Least Square Optimization
@TODO: add images of linear regression graph, error surface
Genetic Algorithm Steps
-
\(P_0 =\) initial population
-
Compute \(f_\text{fit}\) with all potential solutions in \(P_0\)
-
If some termination criterion is reached, then exit with solution
-
Select some potential solutions with high \(f_\text{fit}\) values from \(P_0\) and \(P_1\).
-
Perform crossover and mutation on potential solutions encoded as chromosomes in \(P_1\).
-
\(P_0 = P_1\)
-
Go to step 2
-
End
Example: Maximizing Number of '1' Bits
Let \(f(x) =\) the number of \(1\)'s in binary string \(x\)
The task is to apply GA to find a value for \(x\) that will maximize \(f(x)\).
Consider a fitness function \(f_\text{fit} = \frac{f(x)}{10}\).
Let \(P_0 =\) a randomly formed initial population.
Let us visualize the generational cycle of this simple GA.
| \(x_i\) | Population \(P_0\) | \(f_\text{fit}(x)\) | \(\bar{f_\text{fit}}(x) = \frac{f_\text{fit}(x)}{\text{avg. fitness value}}\) | \(p_\text{select}(x)= \frac{\bar{f_\text{fit}}(x)}{\sum_x{\bar{f_\text{fit}}(x)}}\) |
|---|---|---|---|---|
\(x_1\) |
\(0000011100\) |
\(0.3\) |
\(0.5\) |
\(0.125\) |
\(x_2\) |
\(1000011111\) |
\(0.6\) |
\(1.0\) |
\(0.25\) |
\(x_3\) |
\(0110101011\) |
\(0.6\) |
\(1.0\) |
\(0.25\) |
\(x_4\) |
\(1111111011\) |
\(0.9\) |
\(1.5\) |
\(0.375\) |
\(\text{sum} = 2.4\) |
\(\text{sum} = 4.0\) |
\(\text{sum} = 1.0\) |
Here, avg. fitness value \(= \frac{\sum_x f_\text{fit}(x)}{\text{population size}} = \frac{2.4}{4} = 0.6\)
Now we (stochastically) select potential solutions with high \(f_\text{fit}\) value from \(P_0\) and store them in \(P_1\).
|
Note
|
The actual number of offsprings is obtained through roulette wheel. |
| \(x_i\) | Population \(P_1\) | \(f_\text{fit}(x)\) | \(\bar{f_\text{fit}}(x) = \frac{f_\text{fit}(x)}{\text{avg. fitness value}}\) | \(p_\text{select}(x)= \frac{\bar{f_\text{fit}}(x)}{\sum_x{\bar{f_\text{fit}}(x)}}\) |
|---|---|---|---|---|
\(x_1\) |
\(1000011111\) |
\(0.6\) |
\(0.8\) |
\(0.2\) |
\(x_2\) |
\(0110101011\) |
\(0.6\) |
\(0.8\) |
\(0.2\) |
\(x_3\) |
\(1111111011\) |
\(0.9\) |
\(1.2\) |
\(0.3\) |
\(x_4\) |
\(1111111011\) |
\(0.9\) |
\(1.2\) |
\(0.3\) |
\(\text{sum} = 3.0\) |
\(\text{sum} = 4.0\) |
\(\text{sum} = 1.0\) |
Now, these four strings are paired randomly for crossover.
At a crossover rate of \(0.5\), only the pair of strings \(x_1\) and \(x_4\) are selected.
| \(x_i\) | Population \(P_1\) before crossover | \(f_\text{fit}(x)\) |
|---|---|---|
\(x_1\) |
\(10000\)\(\vert\)\(11111\) |
\(0.6\) |
\(x_2\) |
\(0110101011\) |
\(0.6\) |
\(x_3\) |
\(1111111011\) |
\(0.9\) |
\(x_4\) |
\(11111\)\(\vert\)\(11011\) |
\(0.9\) |
| \(x_i\) | Population \(P_1\) after crossover | \(f_\text{fit}(x)\) |
|---|---|---|
\(x_1\) |
\(10000\)\(\vert\)\(11011\) |
\(0.5\) |
\(x_2\) |
\(0110101011\) |
\(0.6\) |
\(x_3\) |
\(1111111011\) |
\(0.9\) |
\(x_4\) |
\(11111\)\(\vert\)\(11111\) |
\(1.0\) |
Now, we assume a mutation rate of \(0.05\).
We have \(4\) strings, each with \(10\) bits, giving us a total of \(4 \times 10 = 40\) bits.
Thus \(40 * 0.05 = 2\) bits need to be selected randomly prior to mutating them.
| \(x_i\) | Population \(P_1\) before mutation | \(f_\text{fit}(x)\) |
|---|---|---|
\(x_1\) |
\(1000011011\) |
\(0.5\) |
\(x_2\) |
\(01101\)\(\underline{0}\)\(1011\) |
\(0.6\) |
\(x_3\) |
\(1111111011\) |
\(0.9\) |
\(x_4\) |
\(\underline{1}\)\(111111111\) |
\(1.0\) |
| \(x_i\) | Population \(P_1\) after mutation | \(f_\text{fit}(x)\) |
|---|---|---|
\(x_1\) |
\(1000011011\) |
\(0.5\) |
\(x_2\) |
\(01101\)\(1\)\(1011\) |
\(0.7\) |
\(x_3\) |
\(1111111011\) |
\(0.9\) |
\(x_4\) |
\(0\)\(111111111\) |
\(0.9\) |
\(3.0\) |
Avg. \(f_\text{fit}(x) = \frac{3.0}{4} = 0.75 \)
Stopping Criteria
-
A GA may be terminated after running for a fixed number of generations.
-
A chromosome with a high fitness value may cause termination of a GA.
-
A GA may be terminated when the average fitness value of all chromosomes in a population has crossed some threshold.