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.

Before diving into the algorithm, here are definitions of the basic terminologies.

• Gene: The smallest unit that makes up the chromosome (decision variable)
• Chromosome: A group of genes, where each chromosome represents a solution (potential solution)
• Population: A group of chromosomes (a group of potential solutions)

GA involves the following seven steps:

1. Initialization
2. Evaluation
3. Selection
4. Crossover
5. Mutation
6. Insertion
7. Repeat 2-6 until a stopping criteria is met
   

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