Genetic algorithm: Difference between revisions

Revision as of 18:56, 12 December 2024

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

Introduction

Algorithm Discussion

Numerical Example

1. Simple Example

We aim to maximize $f(x)=x^{2}$ , where 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 \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	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 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:

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(\text{Chromosome}) = \frac{\text{Fitness}}{\text{Total Fitness}}.}

Thus,

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 =324+49+625+81=1079}

Compute the selection probabilities:

Chromosome	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)}	Selection 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 324}	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{324}{1,079} \approx 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 49}	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{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)}

@@ Line 16: / Line 16: @@
 The initial population is randomly generated:
 {| class="wikitable"
-|+
 !Chromosome (Binary)
 !x (Decimal)
@@ Line 38: / Line 37: @@
 Calculate the fitness values:
 {| class="wikitable"
-|+
 !Chromosome
 !<math>x</math>
@@ Line 59: / Line 57: @@
 |81
 |}
+===== 1.2.2 Selection =====
+Use roulette wheel selection to choose parents for crossover. Selection probabilities are calculated as:
+<math>P(\text{Chromosome}) = \frac{\text{Fitness}}{\text{Total Fitness}}.</math>
+Thus,
 '''Total Fitness <math>=324+49+625+81=1079</math>'''
+Compute the selection probabilities:
+{| class="wikitable"
+! Chromosome !! <math>f(x)</math> !! Selection Probability
+|-
+| 10010 || <math>324</math> || <math>\frac{324}{1,079} \approx 0.3003</math>
+|-
+| 00111 || <math>49</math> || <math>\frac{49}{1,079} \approx 0.0454</math>
+|-
+| 11001 || <math>625</math> || <math>\frac{625}{1,079} \approx 0.5792</math>
+|-
+| 01001 || <math>81</math> || <math>\frac{81}{1,079} \approx 0.0751</math>
+|}
+Cumulative probabilities:
+{| class="wikitable"
+|-
+! Chromosome !! Cumulative Probability
+|-
+| 10010 || <math>0.3003</math>
+|-
+| 00111 || <math>0.3003 + 0.0454 = 0.3457</math>
+|-
+| 11001 || <math>0.3457 + 0.5792 = 0.9249</math>
+|-
+| 01001 || <math>0.9249 + 0.0751 = 1.0000</math>
+|}
+Random numbers for selection:
+<math>r_1 = 0.32, \quad r_2 = 0.60, \quad r_3 = 0.85, \quad r_4 = 0.10</math>
+Selected parents:
+* Pair 1: 00111 and 11001
+* Pair 2: 11001 and 10010
+===== 3. Crossover =====
+Crossover probability: <math>P_c = 0.7</math>
+'''Pair 1:''' Crossover occurs at position 2.
+* Parent 1: <math>00|111</math>
+* Parent 2: <math>11|001</math>
+* Children: <math>00001 \ (x = 1)</math>, <math>11111 \ (x = 31)</math>
+'''Pair 2:''' No crossover.
+* Children: Child 3: <math>11001 \ (x = 25)</math>, Child 4: <math>10010 \ (x = 18)</math>