Genetic algorithm: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
Line 1: Line 1:
Author: Yunchen Huo (yh2244), Ran Yi (ry357), Yanni Xie (yx682), Changlin Huang (ch2269), Jingyao Tong (jt887) (ChemE 6800 Fall 2024)
lAuthor: 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
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu
Line 7: Line 7:


== Algorithm Discussion ==
== Algorithm Discussion ==
The Genetic Algorithm was first introduced by John H. Holland
<ref> Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), 88–105 </ref>
in 1973. It is an optimization technique based on Charles Darwin’s theory of evolution by natural selection.[[File:GA.drawio.png|421x501px|frameless|thumb|right]"Figure 1:"" Flowchart for Genetic Algorithm]


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:
# Initialization
#* Randomly generate the initial population for a predetermined population size
# 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
# 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 <ref name="Mirjalili"> Mirjalili, S. (2018). Genetic Algorithm. Evolutionary Algorithms and Neural Networks, Springer, pp. 43–56 </ref>.
# 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 <ref name="Mirjalili" />. 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 <ref name="Mirjalili" />.
# 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<ref name="Mirjalili" />.
# Insertion
#* Insert the mutated children chromosomes back into the population
# 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 ==
== Numerical Example ==


Line 128: Line 101:
* Pair 2: 11001 and 10010
* Pair 2: 11001 and 10010


===== 3. Crossover =====
===== 1.2.3 Crossover =====
Crossover probability: <math>P_c = 0.7</math>
Crossover probability: <math>P_c = 0.7</math>


Line 139: Line 112:
* Children: Child 3: <math>11001 \ (x = 25)</math>, Child 4: <math>10010 \ (x = 18)</math>
* Children: Child 3: <math>11001 \ (x = 25)</math>, Child 4: <math>10010 \ (x = 18)</math>


===== 1.2.4 Mutation =====
Mutation probability: <math>P_m = 0.1</math> 
'''Child 1:''' <math>00001</math> (bits: <math>0 \ 0 \ 0 \ 0 \ 1</math>). 
* Mutations: Bit 1 and Bit 4 flip. 
* Resulting chromosome: <math>10011 \ (x = 19)</math>.
'''Child 2:''' <math>11111</math> (bits: <math>1 \ 1 \ 1 \ 1 \ 1</math>). 
* Mutation: Bit 3 flips. 
* Resulting chromosome: <math>11011 \ (x = 27)</math>.
'''Child 3:''' <math>11001</math> (bits: <math>1 \ 1 \ 0 \ 0 \ 1</math>). 
* Mutations: Bit 1 and Bit 5 flip. 
* Resulting chromosome: <math>01000 \ (x = 8)</math>.
'''Child 4:''' <math>10010</math> (bits: <math>1 \ 0 \ 0 \ 1 \ 0</math>). 
* Mutations: Bit 1 and Bit 3 flip. 
* Resulting chromosome: <math>00110 \ (x = 6)</math>.
===== 1.2.5 Insertion =====
{| class="wikitable"
|-
! Chromosome !! <math>x</math> !! <math>f(x)</math>
|-
| 10011 || <math>19</math> || <math>361</math>
|-
| 11011 || <math>27</math> || <math>729</math>
|-
| 01000 || <math>8</math> || <math>64</math>
|-
| 00110 || <math>6</math> || <math>36</math>
|}
==== '''1.3 Generation 2''' ====
===== 1.3.1 Evaluation =====
Calculate the fitness values:
{| class="wikitable"
|-
! Chromosome !! <math>x</math> !! <math>f(x)</math>
|-
| 10011 || <math>19</math> || <math>361</math>
|-
| 11011 || <math>27</math> || <math>729</math>
|-
| 01000 || <math>8</math> || <math>64</math>
|-
| 00110 || <math>6</math> || <math>36</math>
|}
===== 1.3.2 Selection =====
'''Total fitness:''' 
<math>\text{Total Fitness} = 361 + 729 + 64 + 36 = 1,190</math>
Compute selection probabilities:
{| class="wikitable"
|-
! Chromosome !! <math>f(x)</math> !! Selection Probability
|-
| 10011 || <math>361</math> || <math>\frac{361}{1,190} \approx 0.3034</math>
|-
| 11011 || <math>729</math> || <math>\frac{729}{1,190} \approx 0.6126</math>
|-
| 01000 || <math>64</math> || <math>\frac{64}{1,190} \approx 0.0538</math>
|-
| 00110 || <math>36</math> || <math>\frac{36}{1,190} \approx 0.0303</math>
|}
Cumulative probabilities:
{| class="wikitable"
|-
! Chromosome !! Cumulative Probability
|-
| 10011 || <math>0.3034</math>
|-
| 11011 || <math>0.3034 + 0.6126 = 0.9160</math>
|-
| 01000 || <math>0.9160 + 0.0538 = 0.9698</math>
|-
| 00110 || <math>0.9698 + 0.0303 = 1.0000</math>
|}
Random numbers for selection:
<math>r_1 = 0.20, \quad r_2 = 0.50, \quad r_3 = 0.80, \quad r_4 = 0.95</math>
Selected parents: 
* Pair 1: 10011 and 11011 
* Pair 2: 11011 and 01000
===== 1.3.3 Crossover =====
Crossover probability: <math>P_c = 0.7</math> 
'''Pair 1:''' Crossover occurs at position 2. 
* Parent 1: <math>10|011</math> 
* Parent 2: <math>11|011</math> 
* Children: <math>10011 \ (x = 19)</math>, <math>11011 \ (x = 27)</math>
'''Pair 2:''' Crossover occurs at position 4. 
* Parent 1: <math>11|011</math> 
* Parent 2: <math>01|000</math> 
* Children: <math>11000 \ (x = 24)</math>, <math>01011 \ (x = 11)</math>
===== 1.3.4 Mutation =====
Mutation probability: <math>P_m = 0.1</math> 
* '''Child 1:''' No mutations. <math>\text{Resulting Chromosome: } 10011</math>.
* '''Child 2:''' Bit 1 flips. <math>\text{Resulting Chromosome: } 01011 \ (x = 11)</math>.
* '''Child 3:''' Bit 5 flips. <math>\text{Resulting Chromosome: } 11010 \ (x = 26)</math>.
* '''Child 4:''' No mutations. <math>\text{Resulting Chromosome: } 11011</math>.
===== 1.3.5 Insertion =====
{| class="wikitable"
|-
! Chromosome !! <math>x</math> !! <math>f(x)</math>
|-
| 10011 || <math>19</math> || <math>361</math>
|-
| 01011 || <math>11</math> || <math>121</math>
|-
| 11010 || <math>26</math> || <math>676</math>
|-
| 11011 || <math>27</math> || <math>729</math>
|}
==== 1.4 Conclusion ====
After 2 iterations, the best optimal solution we find is <math>f = 729, \ x = 27</math>. 
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: 
<math>f(x, y) = 21.5 + x \sin\left(4\pi x\right) + y \sin\left(20\pi y\right)</math> 
subject to the constraints: 
<math>-3.0 \leq x \leq 12.1, \quad 4.1 \leq y \leq 5.8.</math>
==== 2.1 Encoding the Variables ====
Each chromosome represents a pair of variables <math>x</math> and <math>y</math>. We encode these variables into binary strings: 
* <math>x</math>: <math>-3.0 \leq x \leq 12.1</math>, precision <math>0.1</math>, requiring <math>8</math> bits. 
* <math>y</math>: <math>4.1 \leq y \leq 5.8</math>, precision <math>0.01</math>, requiring <math>8</math> bits. 


== References ==
Each chromosome is a 16-bit binary string, where the first 8 bits represent <math>x</math> and the next 8 bits represent <math>y</math>.
<references />

Revision as of 21:41, 12 December 2024

lAuthor: 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 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} , where . 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
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
1.2.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)}
1.2.4 Mutation

Mutation 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_m = 0.1}

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 00001} (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 0 \ 0 \ 0 \ 0 \ 1} ).

  • Mutations: Bit 1 and Bit 4 flip.
  • Resulting 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 10011 \ (x = 19)} .

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 11111} (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 1 \ 1 \ 1 \ 1 \ 1} ).

  • Mutation: Bit 3 flips.
  • Resulting 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 11011 \ (x = 27)} .

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} (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 1 \ 1 \ 0 \ 0 \ 1} ).

  • Mutations: Bit 1 and Bit 5 flip.
  • Resulting 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 01000 \ (x = 8)} .

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} (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 1 \ 0 \ 0 \ 1 \ 0} ).

  • Mutations: Bit 1 and Bit 3 flip.
  • Resulting 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 00110 \ (x = 6)} .
1.2.5 Insertion
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)}
10011 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} 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 361}
11011 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 27} 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 729}
01000 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} 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 64}
00110 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 6} 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 36}

1.3 Generation 2

1.3.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)}
10011 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} 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 361}
11011 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 27} 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 729}
01000 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} 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 64}
00110 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 6} 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 36}
1.3.2 Selection

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} = 361 + 729 + 64 + 36 = 1,190}

Compute 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
10011 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 361} 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{361}{1,190} \approx 0.3034}
11011 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 729} 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{729}{1,190} \approx 0.6126}
01000 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 64} 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{64}{1,190} \approx 0.0538}
00110 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 36} 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{36}{1,190} \approx 0.0303}

Cumulative probabilities:

Chromosome Cumulative Probability
10011 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.3034}
11011 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.3034 + 0.6126 = 0.9160}
01000
00110 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.9698 + 0.0303 = 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.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: 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 10|011}
  • 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|011}
  • 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 10011 \ (x = 19)} , 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 11011 \ (x = 27)}

Pair 2: Crossover occurs at position 4.

  • 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 11|011}
  • 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 01|000}
  • 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 11000 \ (x = 24)} , 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 01011 \ (x = 11)}
1.3.4 Mutation

Mutation 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_m = 0.1}

  • Child 1: No mutations. 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{Resulting Chromosome: } 10011} .
  • Child 2: Bit 1 flips. 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{Resulting Chromosome: } 01011 \ (x = 11)} .
  • Child 3: Bit 5 flips. 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{Resulting Chromosome: } 11010 \ (x = 26)} .
  • Child 4: No mutations. 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{Resulting Chromosome: } 11011} .
1.3.5 Insertion
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)}
10011 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} 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 361}
01011 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} 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 121}
11010 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 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 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 27} 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 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\left(4\pi x\right) + y \sin\left(20\pi y\right)} 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 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.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} .

Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Genetic_algorithm&oldid=7113"