Genetic algorithm
lAuthor: 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
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
1.2.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) $
1.2.4 Mutation
Mutation probability: $ P_m = 0.1 $
Child 1: $ 00001 $ (bits: $ 0 \ 0 \ 0 \ 0 \ 1 $).
- Mutations: Bit 1 and Bit 4 flip.
- Resulting chromosome: $ 10011 \ (x = 19) $.
Child 2: $ 11111 $ (bits: $ 1 \ 1 \ 1 \ 1 \ 1 $).
- Mutation: Bit 3 flips.
- Resulting chromosome: $ 11011 \ (x = 27) $.
Child 3: $ 11001 $ (bits: $ 1 \ 1 \ 0 \ 0 \ 1 $).
- Mutations: Bit 1 and Bit 5 flip.
- Resulting chromosome: $ 01000 \ (x = 8) $.
Child 4: $ 10010 $ (bits: $ 1 \ 0 \ 0 \ 1 \ 0 $).
- Mutations: Bit 1 and Bit 3 flip.
- Resulting chromosome: $ 00110 \ (x = 6) $.
1.2.5 Insertion
| Chromosome | $ x $ | $ f(x) $ |
|---|---|---|
| 10011 | $ 19 $ | $ 361 $ |
| 11011 | $ 27 $ | $ 729 $ |
| 01000 | $ 8 $ | $ 64 $ |
| 00110 | $ 6 $ | $ 36 $ |
1.3 Generation 2
1.3.1 Evaluation
Calculate the fitness values:
| Chromosome | $ x $ | $ f(x) $ |
|---|---|---|
| 10011 | $ 19 $ | $ 361 $ |
| 11011 | $ 27 $ | $ 729 $ |
| 01000 | $ 8 $ | $ 64 $ |
| 00110 | $ 6 $ | $ 36 $ |
1.3.2 Selection
Total fitness: $ \text{Total Fitness} = 361 + 729 + 64 + 36 = 1,190 $
Compute selection probabilities:
| Chromosome | $ f(x) $ | Selection Probability |
|---|---|---|
| 10011 | $ 361 $ | $ \frac{361}{1,190} \approx 0.3034 $ |
| 11011 | $ 729 $ | $ \frac{729}{1,190} \approx 0.6126 $ |
| 01000 | $ 64 $ | $ \frac{64}{1,190} \approx 0.0538 $ |
| 00110 | $ 36 $ | $ \frac{36}{1,190} \approx 0.0303 $ |
Cumulative probabilities:
| Chromosome | Cumulative Probability |
|---|---|
| 10011 | $ 0.3034 $ |
| 11011 | $ 0.3034 + 0.6126 = 0.9160 $ |
| 01000 | $ 0.9160 + 0.0538 = 0.9698 $ |
| 00110 | $ 0.9698 + 0.0303 = 1.0000 $ |
Random numbers for selection: $ r_1 = 0.20, \quad r_2 = 0.50, \quad r_3 = 0.80, \quad r_4 = 0.95 $
Selected parents:
- Pair 1: 10011 and 11011
- Pair 2: 11011 and 01000
1.3.3 Crossover
Crossover probability: $ P_c = 0.7 $
Pair 1: Crossover occurs at position 2.
- Parent 1: $ 10|011 $
- Parent 2: $ 11|011 $
- Children: $ 10011 \ (x = 19) $, $ 11011 \ (x = 27) $
Pair 2: Crossover occurs at position 4.
- Parent 1: $ 11|011 $
- Parent 2: $ 01|000 $
- Children: $ 11000 \ (x = 24) $, $ 01011 \ (x = 11) $
1.3.4 Mutation
Mutation probability: $ P_m = 0.1 $
- Child 1: No mutations. $ \text{Resulting Chromosome: } 10011 $.
- Child 2: Bit 1 flips. $ \text{Resulting Chromosome: } 01011 \ (x = 11) $.
- Child 3: Bit 5 flips. $ \text{Resulting Chromosome: } 11010 \ (x = 26) $.
- Child 4: No mutations. $ \text{Resulting Chromosome: } 11011 $.
1.3.5 Insertion
| Chromosome | $ x $ | $ f(x) $ |
|---|---|---|
| 10011 | $ 19 $ | $ 361 $ |
| 01011 | $ 11 $ | $ 121 $ |
| 11010 | $ 26 $ | $ 676 $ |
| 11011 | $ 27 $ | $ 729 $ |
1.4 Conclusion
After 2 iterations, the best optimal solution we find is $ f = 729, \ x = 27 $.
Due to the limitation of the page, we will not perform additional loops. In the following examples, we will show how to use code to perform multiple calculations on complex problems and specify stopping conditions.
2. Complex Example
We aim to maximize the function: $ f(x, y) = 21.5 + x \sin(4\pi x) + y \sin(20\pi y) $ subject to the constraints: $ -3.0 \leq x \leq 12.1, \quad 4.1 \leq y \leq 5.8. $
2.1 Encoding the Variables
Each chromosome represents a pair of variables $ x $ and $ y $. We encode these variables into binary strings:
- $ x $: $ -3.0 \leq x \leq 12.1 $, precision $ 0.1 $, requiring $ 8 $ bits.
- $ y $: $ 4.1 \leq y \leq 5.8 $, precision $ 0.01 $, requiring $ 8 $ bits.
Each chromosome is a 16-bit binary string, where the first 8 bits represent $ x $ and the next 8 bits represent $ y $.