Implementation of a genetic algorithm in Python for the purpose of image reconstruction using 100 triangular polygons.
The solution is based on a genetic algorithm where on each generation we select the individuals (group of triangles) that better reconstruct the target image. The hyper parameters of the solution are the number of triangles, the generations, the population size and the mutation rate. Also, we define the base color (background color) to help our solution reach a better reconstruction.
The code is implemented using 3 main classes: Gene, Individual, Population.
- The Gene class defines a triangle.
- The Individual class contains an group of genes and is able to build an image and calculate the fitness. It is also capable of doing crossover and mutation.
- The Population class contains a group of individuals and is capable of performing selection of the fittest individuals and generation evolution.
Using a typical colored small JPEG image (250*250 pixels) and with default hyper parameters (100 genes, 30 individuals, 4000 generations) the code runs in less than 5 minutes.
The genetic algorithm chosen is of the typical form:
- Initial random population
- Fitness evaluation
- Selection of best individuals inside population
- Crossover between selected individuals
- Random gene mutation
- Back to step 2 until convergence or until end of generations
Our choices for the imporant steps:
- Fitness: Chose the pixelwise MSE
- Selection: Each generation selects the best 4 individuals based on fitness (pool)
- Crossover: For each chile we randomly choose 2 parents from the pool and do crossover with 3 random slice indexes
- Mutation: A mutation is equal to a random gene