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