# Genetic Algorithms ## [Pre-lecture quiz](https://ff-quizzes.netlify.app/en/ai/quiz/41) **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: Γ^{2→Γ.
* 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:

1. Select an initial population G⊂Γ
2. Randomly select one of the operations that will be performed at this step: crossover or mutation
3. **Crossover**:
* Randomly select two genes g₁, g₂ ∈ G
* Compute crossover g=crossover(g₁,g₂)
* If fit(g)1) or fit(g)2) - 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.

## Typical Tasks

Tasks typically solved by Genetic Algorithms include:

1. Schedule optimization
1. Optimal packing
1. Optimal cutting
1. Speeding up exhaustive search

## ✍️ Exercises: Genetic Algorithms

Continue your learning in the following notebooks:

Go to [this notebook](Genetic.ipynb) to see two examples of using Genetic Algorithms:

1. Fair division of treasure
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://ff-quizzes.netlify.app/en/ai/quiz/42)

## Review & Self Study

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/).*

Hints:

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.}