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	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 625}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{625}{1,079} \approx 0.5792}
01001	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 81}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{81}{1,079} \approx 0.0751}

Cumulative probabilities:

Chromosome	Cumulative Probability
10010	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.3003}
00111	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.3003 + 0.0454 = 0.3457}
11001	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.3457 + 0.5792 = 0.9249}
01001	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.9249 + 0.0751 = 1.0000}

Random numbers for selection:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_c = 0.7}

Pair 1: Crossover occurs at position 2.

• Parent 1: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 00|111}
• Parent 2: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11|001}
• Children: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 00001 \ (x = 1)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11111 \ (x = 31)}

Pair 2: No crossover.

• Children: Child 3: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11001 \ (x = 25)} , Child 4: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10010 \ (x = 18)}