Genetic Algorithms

Pre-lecture quiz

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.

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)<fit(g₁) or fit(g)<fit(g₂) - 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
2. Optimal packing
3. Optimal cutting
4. Speeding up exhaustive search

✍️ Exercises: Genetic Algorithms

Continue your learning in the following notebooks:

Go to this notebook to see two examples of using Genetic Algorithms:

1. Fair division of treasure
2. 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 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

Review & Self Study

Watch this great video 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.

Assignment: Diophantine Equation

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.

Hints:

1. You can consider roots to be in the interval [0;30]
2. As a gene, consider using the list of root values

Use Diophantine.ipynb as a starting point.