Genetic algorithm: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
(application)
Line 4: Line 4:


== Introduction ==
== Introduction ==


== Algorithm Discussion ==
== Algorithm Discussion ==
Line 33: Line 32:
#* No significant improvement from newer generations
#* No significant improvement from newer generations
#* Expected fitness value is achieved
#* Expected fitness value is achieved
== Numerical Example ==


=== 1. Simple Example ===
We aim to maximize <math>f(x) = x^2</math>, where <math>x \in [0, 31]</math>. Chromosomes are encoded as 5-bit binary strings since the binary format of the maximum value 31 is 11111.


==== 1.1 Initialization (Generation 0) ====
== Application ==
The initial population is randomly generated:
GA is one of the most important and successful algorithms in optimization, which can be demonstrated by numerous applications. Applications of GA include machine learning, engineering, finance and other domain applications, the following introduces the applications of GA in Unsupervised Regression, Virtual Power Plans and Forecasting Financial Market Indices.
{| class="wikitable"
!Chromosome (Binary)
!x (Decimal)
|-
|10010
|18
|-
|00111
|7
|-
|11001
|25
|-
|01001
|9
|}


==== 1.2 Generation 1 ====
=== Unsupervised Regression ===
 
The Unsupervised regression is a promising dimensionality reduction method[3]. The concept of the Unsupervised regression is to map from low-dimensional space into the high-dimensional space by using a regression model[4]. The goal of the Unsupervised Regression is to minimize the data space reconstruction error[3]. Common optimization methods to achieve this goal are the Nearest neighbor regression and the Kernel regression[3].  
===== 1.2.1 Evaluation =====
Since the mapping from the low-dimensional space into the high-dimensional space is usually complex, the data space reconstruction error function may become a non-convex multimodal function with multiple local optimal solutions. In this case, using GA can overcome local optima because of the population search, selection, crossover and mutation.
Calculate the fitness values:
{| class="wikitable"
!Chromosome
!<math>x</math>
!<math>f(x) = x^2</math>
|-
|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:
 
<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
 
===== 1.2.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>
 
===== 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(4\pi x) + y \sin(20\pi y)</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. 
 
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>.
 
==== 2.2 Initialization ====
We randomly generate an initial population of 6 chromosomes. Each chromosome is decoded to its respective <math>x</math> and <math>y</math> values using the formula: 
 
<math>\text{Value} = \text{Minimum} + (\frac{\text{Binary Value}}{2^{\text{Bits}} - 1}) \times \text{Range}.</math>
 
==== Initial Population ====
{| class="wikitable"
|+
Initial Population
|-
! Chromosome (Binary) !! <math>x</math> Bits !! <math>y</math> Bits !! <math>x</math> (Decimal) !! <math>y</math> (Decimal)
|-
| 10101100 11010101 || 10101100 || 11010101 || <math>7.22</math> || <math>5.52</math>
|-
| 01110011 00101110 || 01110011 || 00101110 || <math>2.34</math> || <math>4.49</math>
|-
| 11100001 01011100 || 11100001 || 01011100 || <math>9.90</math> || <math>4.86</math>
|-
| 00011010 10110011 || 00011010 || 10110011 || <math>-1.88</math> || <math>5.30</math>
|-
| 11001100 01100110 || 11001100 || 01100110 || <math>6.50</math> || <math>4.72</math>
|-
| 00110111 10001001 || 00110111 || 10001001 || <math>-0.88</math> || <math>5.05</math>
|}
 
==== 2.3 Evaluation ====
Calculate the fitness <math>f(x, y)</math> for each chromosome using the given function. Below are the computed fitness values:
 
{| class="wikitable"
|-
! Chromosome (Binary) !! <math>x</math> !! <math>y</math> !! <math>f(x, y)</math>
|-
| 10101100 11010101 || <math>7.22</math> || <math>5.52</math> || <math>19.35</math>
|-
| 01110011 00101110 || <math>2.34</math> || <math>4.49</math> || <math>22.65</math>
|-
| 11100001 01011100 || <math>9.90</math> || <math>4.86</math> || <math>30.12</math>
|-
| 00011010 10110011 || <math>-1.88</math> || <math>5.30</math> || <math>16.40</math>
|-
| 11001100 01100110 || <math>6.50</math> || <math>4.72</math> || <math>28.75</math>
|-
| 00110111 10001001 || <math>-0.88</math> || <math>5.05</math> || <math>21.10</math>
|}
 
==== 2.4 Selection ====
Use roulette wheel selection to choose parents for crossover. 
 
Total fitness: 
 
<math>\text{Total Fitness} = 19.35 + 22.65 + 30.12 + 16.40 + 28.75 + 21.10 = 138.37</math>
 
Selection probabilities are calculated as: 
 
{| class="wikitable"
|-
! Chromosome !! Fitness <math>f(x, y)</math> !! Selection Probability
|-
| 10101100 11010101 || <math>19.35</math> || <math>0.14</math>
|-
| 01110011 00101110 || <math>22.65</math> || <math>0.16</math>
|-
| 11100001 01011100 || <math>30.12</math> || <math>0.22</math>
|-
| 00011010 10110011 || <math>16.40</math> || <math>0.12</math>
|-
| 11001100 01100110 || <math>28.75</math> || <math>0.21</math>
|-
| 00110111 10001001 || <math>21.10</math> || <math>0.15</math>
|}
 
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 <math>x</math> and <math>y</math> bits). 
 
'''Pair 1:''' 
* Parent 1: <math>11100001 \ 01011100</math> 
* Parent 2: <math>11001100 \ 01100110</math> 
* Child 1: <math>11100001 \ 01100110</math> 
* Child 2: <math>11001100 \ 01011100</math> 


Repeat for other pairs.
=== '''Virtual Power Plants''' ===
The renewable energy resources, such as wind power and solar power, have a distinct fluctuating character<sup>[3]</sup>. To address the inconvenience of such fluctuations on the power grid, engineers have introduced the concept of virtual power plants, which bundles various different power sources into a single unit that meets specific properties<sup>[3]</sup>.


==== 2.6 Mutation ====
The optimization goal is to minimize the absolute value of power in the virtual power plants system with a rule base<sup>[3]</sup>. This rule base is also known as the learning classifier system, which allows energy storage devices and standby power plants in the system to respond flexibly in different system states and achieve a balance between power consumption and generation<sup>[3]</sup>.
Apply mutation with a small probability (e.g., 1% per bit). Suppose a mutation occurs in Child 1 at bit position 5 of the <math>x</math> bits:   


<math>\text{Original } x: 11100001 \quad \longrightarrow \quad \text{Mutated } x: 11101001.</math>
Since the rule base has complexity and a high degree of uncertainty, using GA can observably evolve the action part of the rule base. For example, in the complex energy scheduling process, GA can optimize the charge/discharge strategy of the energy storage equipment and the plan of start/stop of standby power plants to ensure the balance of power consumption and generation.


The new child becomes: 
=== Forecasting Financial Market Indices ===
A financial market index consists of a weighted average of the prices of individual shares that make up the market<sup>[5]</sup>. In financial markets, many traders and analysts believe that stock prices move in trends and repeat price patterns<sup>[5]</sup>. Under this premise, using Grammatical Evolution(GE) to forecast the financial market indices and enhance trading decisions is a good choice.


<math>\text{Child 1: 11101001 01100110.}</math>
GE is a machine learning method based on the GA<sup>[5]</sup>. GE uses a biologically-inspired, genotype-phenotype mapping process, evolving computer program in any language<sup>[5]</sup>. Unlike encoding the solution within the genetic material in the GA, the GE includes a many-to-one mapping process, which shows the robustness<sup>[5]</sup>.


==== 2.7 Insertion ====
While using GE to forecast financial market indices, people need to import processed historical stock price data. GE will learn price patterns in this data and generate models which can predict future price movements. These models can help traders and analysts identify the trend of the financial market, such as upward and downward trends.
Evaluate the fitness of offspring and combine with the current population. Select the top 6 chromosomes to form the next generation.


{| class="wikitable"
=== '''Software tools and platforms that utilize Genetic Algorithms''' ===
|+
'''MATLAB''': The Global Optimization Toolbox of MATLAB is widely used for engineering simulations and machine learning.
Next Generation
|-
! Chromosome (Binary) !! <math>x</math> !! <math>y</math> !! <math>f(x, y)</math>
|-
| 11101001 01100110 || <math>10.79</math> || <math>4.78</math> || <math>30.85</math>
|-
| 11100001 01011100 || <math>9.90</math> || <math>4.86</math> || <math>30.12</math>
|-
| 11001100 01100110 || <math>6.50</math> || <math>4.72</math> || <math>28.75</math>
|-
| 10101100 11010101 || <math>7.22</math> || <math>5.52</math> || <math>26.30</math>
|-
| 01110011 00101110 || <math>2.34</math> || <math>4.49</math> || <math>22.65</math>
|-
| 00110111 10001001 || <math>-0.88</math> || <math>5.05</math> || <math>21.10</math>
|}


==== 2.8 Repeat Steps 2.3-2.7 ====
'''Python''': The DEAP and PyGAD in Python provide an environment for research and AI model optimization.
Using the code to perform the repeating process for 50 more generations we got
 
[[File:output.png|800x498px|Fig.2. 50 iteration results]]
 
Fig.2. 50 iteration results
 
Based on Fig. 2 we can find the optimal value to be 35.2769.
 
== Application ==
GA is one of the most important and successful algorithms in optimization, which can be demonstrated by numerous applications. Applications of GA include machine learning, engineering, finance and other domain applications, the following introduces the applications of GA in Unsupervised Regression, Virtual Power Plans and Forecasting Financial Market Indices.
 
=== Unsupervised Regression ===
The Unsupervised regression is a promising dimensionality reduction method[3]. The concept of the Unsupervised regression is to map from low-dimensional space into the high-dimensional space by using a regression model[4]. The goal of the Unsupervised Regression is to minimize the data space reconstruction error[3]. Common optimization methods to achieve this goal are the Nearest neighbor regression and the Kernel regression[3].
Since the mapping from the low-dimensional space into the high-dimensional space is usually complex, the data space reconstruction error function may become a non-convex multimodal function with multiple local optimal solutions. In this case, using GA can overcome local optima because of the population search, selection, crossover and mutation.


'''OpenGA''': The OpenGA is a free C++ GA library, which is open-source. The OpenGA provides developers with a flexible way to implement GA for solving a variety of optimization problems<sup>[6]</sup>.


== References ==
== References ==
<references />
<references />

Revision as of 18:10, 13 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

The GA was first introduced by John H. Holland[1] in 1973. It is an optimization technique based on Charles Darwin’s theory of evolution by natural selection.

Fig.1. 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 [2].
  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 [2]. 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 [2].
  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[2].
  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


Application

GA is one of the most important and successful algorithms in optimization, which can be demonstrated by numerous applications. Applications of GA include machine learning, engineering, finance and other domain applications, the following introduces the applications of GA in Unsupervised Regression, Virtual Power Plans and Forecasting Financial Market Indices.

Unsupervised Regression

The Unsupervised regression is a promising dimensionality reduction method[3]. The concept of the Unsupervised regression is to map from low-dimensional space into the high-dimensional space by using a regression model[4]. The goal of the Unsupervised Regression is to minimize the data space reconstruction error[3]. Common optimization methods to achieve this goal are the Nearest neighbor regression and the Kernel regression[3]. Since the mapping from the low-dimensional space into the high-dimensional space is usually complex, the data space reconstruction error function may become a non-convex multimodal function with multiple local optimal solutions. In this case, using GA can overcome local optima because of the population search, selection, crossover and mutation.

Virtual Power Plants

The renewable energy resources, such as wind power and solar power, have a distinct fluctuating character[3]. To address the inconvenience of such fluctuations on the power grid, engineers have introduced the concept of virtual power plants, which bundles various different power sources into a single unit that meets specific properties[3].

The optimization goal is to minimize the absolute value of power in the virtual power plants system with a rule base[3]. This rule base is also known as the learning classifier system, which allows energy storage devices and standby power plants in the system to respond flexibly in different system states and achieve a balance between power consumption and generation[3].

Since the rule base has complexity and a high degree of uncertainty, using GA can observably evolve the action part of the rule base. For example, in the complex energy scheduling process, GA can optimize the charge/discharge strategy of the energy storage equipment and the plan of start/stop of standby power plants to ensure the balance of power consumption and generation.

Forecasting Financial Market Indices

A financial market index consists of a weighted average of the prices of individual shares that make up the market[5]. In financial markets, many traders and analysts believe that stock prices move in trends and repeat price patterns[5]. Under this premise, using Grammatical Evolution(GE) to forecast the financial market indices and enhance trading decisions is a good choice.

GE is a machine learning method based on the GA[5]. GE uses a biologically-inspired, genotype-phenotype mapping process, evolving computer program in any language[5]. Unlike encoding the solution within the genetic material in the GA, the GE includes a many-to-one mapping process, which shows the robustness[5].

While using GE to forecast financial market indices, people need to import processed historical stock price data. GE will learn price patterns in this data and generate models which can predict future price movements. These models can help traders and analysts identify the trend of the financial market, such as upward and downward trends.

Software tools and platforms that utilize Genetic Algorithms

MATLAB: The Global Optimization Toolbox of MATLAB is widely used for engineering simulations and machine learning.

Python: The DEAP and PyGAD in Python provide an environment for research and AI model optimization.

OpenGA: The OpenGA is a free C++ GA library, which is open-source. The OpenGA provides developers with a flexible way to implement GA for solving a variety of optimization problems[6].

References

  1. ↑ Holland, J. H. (1973). Genetic algorithms and the optimal allocation of trials. SIAM Journal on Computing, 2(2), 88–105
  2. ↑ 2.0 2.1 2.2 2.3 Mirjalili, S. (2018). Genetic Algorithm. Evolutionary Algorithms and Neural Networks, Springer, pp. 43–56
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Genetic_algorithm&oldid=7291"