Genetic algorithm
Author: Yunchen Huo (yh2244), Ran Yi (ry357), Yanni Xie (yx682), Changlin Huang (ch2269), Jingyao Tong (jt887) (ChemE 6800 Fall 2024)
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu
Introduction
Algorithm Discussion
The Genetic Algorithm was first introduced by John H. Holland [1]
in 1973. It is an optimization technique based on Charles Darwin’s theory of evolution by natural selection.
Numerical Example
1. Simple Example
We aim to maximize $ f(x) = x^2 $, where $ x \in [0, 31] $. Chromosomes are encoded as 5-bit binary strings since the binary format of the maximum value 31 is 11111.
1.1 Initialization (Generation 0)
The initial population is randomly generated:
| Chromosome (Binary) | x (Decimal) |
|---|---|
| 10010 | 18 |
| 00111 | 7 |
| 11001 | 25 |
| 01001 | 9 |
1.2 Generation 1
1.2.1 Evaluation
Calculate the fitness values:
| Chromosome | $ x $ | $ f(x) = x^2 $ |
|---|---|---|
| 10010 | 18 | 324 |
| 00111 | 7 | 49 |
| 11001 | 25 | 625 |
| 01001 | 9 | 81 |
1.2.2 Selection
Use roulette wheel selection to choose parents for crossover. Selection probabilities are calculated as:
$ P(\text{Chromosome}) = \frac{\text{Fitness}}{\text{Total Fitness}}. $
Thus,
Total Fitness $ =324+49+625+81=1079 $
Compute the selection probabilities:
| Chromosome | $ f(x) $ | Selection Probability |
|---|---|---|
| 10010 | $ 324 $ | $ \frac{324}{1,079} \approx 0.3003 $ |
| 00111 | $ 49 $ | $ \frac{49}{1,079} \approx 0.0454 $ |
| 11001 | $ 625 $ | $ \frac{625}{1,079} \approx 0.5792 $ |
| 01001 | $ 81 $ | $ \frac{81}{1,079} \approx 0.0751 $ |
Cumulative probabilities:
| Chromosome | Cumulative Probability |
|---|---|
| 10010 | $ 0.3003 $ |
| 00111 | $ 0.3003 + 0.0454 = 0.3457 $ |
| 11001 | $ 0.3457 + 0.5792 = 0.9249 $ |
| 01001 | $ 0.9249 + 0.0751 = 1.0000 $ |
Random numbers for selection:
$ r_1 = 0.32, \quad r_2 = 0.60, \quad r_3 = 0.85, \quad r_4 = 0.10 $
Selected parents:
- Pair 1: 00111 and 11001
- Pair 2: 11001 and 10010
3. Crossover
Crossover probability: $ P_c = 0.7 $
Pair 1: Crossover occurs at position 2.
- Parent 1: $ 00|111 $
- Parent 2: $ 11|001 $
- Children: $ 00001 \ (x = 1) $, $ 11111 \ (x = 31) $
Pair 2: No crossover.
- Children: Child 3: $ 11001 \ (x = 25) $, Child 4: $ 10010 \ (x = 18) $
References
- ↑ Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), 88–105