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.

Flowchart for GA

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
   • Randomly generate the initial population for a predetermined population size
2. Evaluation
   • Evaluate the fitness of every chromosome in the population to see how good it is. Higher fitness implies better solution, making the chromosome more likely to be selected as a parent of next generation
3. Selection
   • Natural selection serves as the main inspiration of GA, where chromosomes are randomly selected from the entire population for mating, and chromosomes with higher fitness values are more likely to be selected .
4. Crossover
   • The purpose of crossover is to create superior offspring (better solutions) by combining parts from each selected parent chromosome. There are different types of crossover, such as single-point and double-point crossover . In single-point crossover, the parent chromosomes are swapped before and after a single point. In double-point crossover, the parent chromosomes are swapped between two points .
5. Mutation
   • A mutation operator is applied to make random changes to the genes of children's chromosomes, maintaining the diversity of the individual chromosomes in the population and enabling GA to find better solutions.
6. Insertion
   • Insert the mutated children chromosomes back into the population
7. Repeat 2-6 until a stopping criteria is met
   • Maximum number of generations reached
   • No significant improvement from newer generations
   • Expected fitness value is achieved

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$	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 676}
11011	$27$	$729$

1.4 Conclusion

After 2 iterations, the best optimal solution we find is 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 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:

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 f(x, y) = 21.5 + x \sin(4\pi x) + y \sin(20\pi y)}

subject to the constraints:

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 -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 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 x} and 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 y} . We encode these variables into binary strings:

• 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 x} : 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 -3.0 \leq x \leq 12.1} , precision 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.1} , requiring 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 8} bits.
• 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 y} : 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 4.1 \leq y \leq 5.8} , precision $0.01$, requiring 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 8} bits.

Each chromosome is a 16-bit binary string, where the first 8 bits represent 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 x} and the next 8 bits represent 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 y} .

2.2 Initialization

We randomly generate an initial population of 6 chromosomes. Each chromosome is decoded to its respective $x$ and 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 y} values using the formula:

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 \text{Value} = \text{Minimum} + (\frac{\text{Binary Value}}{2^{\text{Bits}} - 1}) \times \text{Range}.}

Initial Population

Initial Population

Chromosome (Binary)	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 x} Bits	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 y} Bits	$x$ (Decimal)	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 y} (Decimal)
10101100 11010101	10101100	11010101	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 7.22}	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 5.52}
01110011 00101110	01110011	00101110	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 2.34}	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 4.49}
11100001 01011100	11100001	01011100	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 9.90}	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 4.86}
00011010 10110011	00011010	10110011	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 -1.88}	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 5.30}
11001100 01100110	11001100	01100110	$6.50$	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 4.72}
00110111 10001001	00110111	10001001	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.88}	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 5.05}

2.3 Evaluation

Calculate the fitness 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 f(x, y)} for each chromosome using the given function. Below are the computed fitness values:

Chromosome (Binary)	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 x}	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 y}	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 f(x, y)}
10101100 11010101	$7.22$	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 5.52}	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 19.35}
01110011 00101110	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 2.34}	$4.49$	$22.65$
11100001 01011100	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 9.90}	$4.86$	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 30.12}
00011010 10110011	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 -1.88}	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 5.30}	$16.40$
11001100 01100110	$6.50$	$4.72$	$28.75$
00110111 10001001	$-0.88$	$5.05$	$21.10$

2.4 Selection

Use roulette wheel selection to choose parents for crossover.

Total fitness:

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 \text{Total Fitness} = 19.35 + 22.65 + 30.12 + 16.40 + 28.75 + 21.10 = 138.37}

Selection probabilities are calculated as:

Chromosome	Fitness 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 f(x, y)}	Selection Probability
10101100 11010101	$19.35$	$0.14$
01110011 00101110	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 22.65}	$0.16$
11100001 01011100	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 30.12}	$0.22$
00011010 10110011	$16.40$	$0.12$
11001100 01100110	$28.75$	$0.21$
00110111 10001001	$21.10$	$0.15$

Selected pairs for crossover:

• Pair 1: Chromosome 3 and Chromosome 5
• Pair 2: Chromosome 2 and Chromosome 6
• Pair 3: Chromosome 1 and Chromosome 4

2.5 Crossover

Perform single-point crossover at position 8 (between $x$ and $y$ bits).

Pair 1:

• 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 11100001 \ 01011100}
• 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 11001100 \ 01100110}
• Child 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 11100001 \ 01100110}
• Child 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 11001100 \ 01011100}

Repeat for other pairs.

2.6 Mutation

Apply mutation with a small probability (e.g., 1% per bit). Suppose a mutation occurs in Child 1 at bit position 5 of the 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 x} bits:

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 \text{Original } x: 11100001 \quad \longrightarrow \quad \text{Mutated } x: 11101001.}

The new child becomes:

${\text{Child 1: 11101001 01100110.}}$

2.7 Insertion

Evaluate the fitness of offspring and combine with the current population. Select the top 6 chromosomes to form the next generation.

Next Generation

Chromosome (Binary)	$x$	$y$	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 f(x, y)}
11101001 01100110	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 10.79}	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 4.78}	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 30.85}
11100001 01011100	$9.90$	$4.86$	$30.12$
11001100 01100110	$6.50$	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 4.72}	$28.75$
10101100 11010101	$7.22$	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 5.52}	$26.30$
01110011 00101110	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 2.34}	$4.49$	$22.65$
00110111 10001001	$-0.88$	$5.05$	$21.10$

2.8 Repeat Steps 2.3-2.7

Using the code to perform the repeating process for 50 more generations we got