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

Algorithm Discussion

The Genetic Algorithm was first introduced by John H. Holland

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)$