microsoft/AI-For-Beginners
Publicmirrored fromhttps://github.com/microsoft/AI-For-BeginnersAvailable
6-Other/21-GeneticAlgorithms/README.md
57lines · modecode
| 1 | # Genetic Algorithms |
| 2 | |
| 3 | **Genetic Algorithms** (GA) are based on **evolutionary approach** to AI, in which methods of evolution of population is used to obtain an optimal solution for a given problem. They were proposed in 1975 by [John Henry Holland](https://en.wikipedia.org/wiki/John_Henry_Holland). |
| 4 | |
| 5 | Genetic Algorithms are based on the following ideas: |
| 6 | |
| 7 | * Valid solutions to the problem can be represented as **genes** |
| 8 | * **Crossover** allows us to combine two solutions together to obtain new valid solution |
| 9 | * **Selection** is used to select more optimal solutions using some **fitness function** |
| 10 | * **Mutations** are introduced to destabilize optimization and get us out of the local minimum |
| 11 | |
| 12 | If you want to implement a Genetic Algorithm, you need the following: |
| 13 | |
| 14 | * To find a method of coding our problem solutions using **genes** g∈Γ |
| 15 | * On the set of genes Γ we need to define **fitness function** fit: Γ→**R**. Smaller function values correspond to better solutions. |
| 16 | * To define **crossover** mechanism to combine two genes together to get a new valid solution crossover: Γ<sup>2</sub>→Γ. |
| 17 | * To define **mutation** mechanism mutate: Γ→Γ. |
| 18 | In many cases, crossover and mutation are quite simple algorithms to manipulate genes as numeric sequences or bit vectors. |
| 19 | |
| 20 | Specific implementation of a genetic algorithm can vary from case to case, but overall structure is the following: |
| 21 | |
| 22 | 1. Select initial population G⊂Γ |
| 23 | 2. Randomly select one of the operations that will be performed at this step: crossover or mutation |
| 24 | 3. **Crossover**: |
| 25 | * Randomly select two genes g<sub>1</sub>, g<sub>2</sub> ∈ G |
| 26 | * Compute crossover g=crossover(g<sub>1</sub>,g<sub>2</sub>) |
| 27 | * If fit(g)<fit(g<sub>1</sub>) or fit(g)<fit(g<sub>2</sub>) - replace corresponding gene in the population by g. |
| 28 | 4. **Mutation** - select random gene g∈G and replace it by mutate(g) |
| 29 | 5. Repeat from step 2, until we get sufficiently small value of fit, or until the limit on the number of steps is reached. |
| 30 | |
| 31 | ## Typical Tasks |
| 32 | |
| 33 | Tasks typically solved by GA: |
| 34 | 1. Schedule optimization |
| 35 | 1. Optimal packing |
| 36 | 1. Optimal cutting |
| 37 | 1. Speeding up exhaustive search |
| 38 | |
| 39 | |
| 40 | ## Notebooks |
| 41 | |
| 42 | Go to [Genetic.ipynb](Genetic.ipynb) notebooks to see two examples of using Genetic Algorithms: |
| 43 | |
| 44 | 1. Fair division of treasure |
| 45 | 1. 8 Queen Problem |
| 46 | |
| 47 | ## Assignment |
| 48 | |
| 49 | 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 integer roots that satisfy this equation. |
| 50 | |
| 51 | Hints: |
| 52 | 1. You can consider roots to be in the interval [0;30] |
| 53 | 1. As a gene, consider using the list of root values |
| 54 | |
| 55 | Use [Diophantine.ipynb](Diophantine.ipynb) as a starting point. |
| 56 | |
| 57 | *This assignment is inspired by [this post](https://habr.com/post/128704/).* |
| 58 | |