Newer
Older
## [Pre-lecture quiz](https://green-forest-02da2d60f.1.azurestaticapps.net/quiz/121)
**Genetic Algorithms** (GA) are based on an **evolutionary approach** to AI, in which methods of the evolution of a population is used to obtain an optimal solution for a given problem. They were proposed in 1975 by [John Henry Holland](https://wikipedia.org/wiki/John_Henry_Holland).
Genetic Algorithms are based on the following ideas:
* Valid solutions to the problem can be represented as **genes**
* **Crossover** allows us to combine two solutions together to obtain a new valid solution
* **Selection** is used to select more optimal solutions using some **fitness function**
* **Mutations** are introduced to destabilize optimization and get us out of the local minimum
If you want to implement a Genetic Algorithm, you need the following:
* To find a method of coding our problem solutions using **genes** g∈Γ
* On the set of genes Γ we need to define **fitness function** fit: Γ→**R**. Smaller function values correspond to better solutions.
* To define **crossover** mechanism to combine two genes together to get a new valid solution crossover: Γ<sup>2</sub>→Γ.
* To define **mutation** mechanism mutate: Γ→Γ.
In many cases, crossover and mutation are quite simple algorithms to manipulate genes as numeric sequences or bit vectors.
The specific implementation of a genetic algorithm can vary from case to case, but the overall structure is the following:
2. Randomly select one of the operations that will be performed at this step: crossover or mutation
3. **Crossover**:
* Randomly select two genes g<sub>1</sub>, g<sub>2</sub> ∈ G
* Compute crossover g=crossover(g<sub>1</sub>,g<sub>2</sub>)
* If fit(g)<fit(g<sub>1</sub>) or fit(g)<fit(g<sub>2</sub>) - replace corresponding gene in the population by g.
4. **Mutation** - select random gene g∈G and replace it by mutate(g)
5. Repeat from step 2, until we get a sufficiently small value of fit, or until the limit on the number of steps is reached.
1. Schedule optimization
1. Optimal packing
1. Optimal cutting
1. Speeding up exhaustive search
Continue your learning in the following notebooks:
Go to [this notebook](Genetic.ipynb) to see two examples of using Genetic Algorithms:
1. 8 Queens Problem
## Conclusion
Genetic Algorithms are used to solve many problems, including logistics and search problems. The field is Inspired by research that merged topics in Psychology and Computer Science.
## 🚀 Challenge
"Genetic algorithms are simple to implement, but their behavior is difficult to understand." [source](https://wikipedia.org/wiki/Genetic_algorithm) Do some research to find an implementation of a genetic algorithm such as solving a Sudoku puzzle, and explain how it works as a sketch or flowchart.
## [Post-lecture quiz](https://green-forest-02da2d60f.1.azurestaticapps.net/quiz/221)
Watch [this great video](https://www.youtube.com/watch?v=qv6UVOQ0F44) talking about how computer can learn to play Super Mario using neural networks trained by genetic algorithms. We will learn more about computer learning to play games like that [in the next section](../22-DeepRL/README.md).
## [Assignment: Diophantine Equation](Diophantine.ipynb)
Your goal is to solve so-called **Diophantine equation** - an equation with integer roots. For example, consider the equation a+2b+3c+4d=30. You need to find the integer roots that satisfy this equation.
*This assignment is inspired by [this post](https://habr.com/post/128704/).*
1. You can consider roots to be in the interval [0;30]
1. As a gene, consider using the list of root values
Use [Diophantine.ipynb](Diophantine.ipynb) as a starting point.