EVOLUTIONARY COMPUTATION: Genetic Algorithms

This is the implementation of the general approach of Genetic Algorithms to solve the classic problem of the needle in the haystack. Here is solve to test the effect on variation on mutation rate, crossover, number and site of partitions.

Code here

General or traditional concept of Genetic Algorithms is explained in figure 1

According to figure 1, a genetic algorithm, the most intuitive problems that GA solve are those on maximization, where the best possible solution has to be found. This solution can be represented as a combination of elements (bits generally) which represent a composed solution, or a coded simple one.

AG starts for construction populations of chromosomes, each representing a solution to the problem. These are combined by crossover and mutation. Then they are evaluated using a fitness function. Those individuals that represent the better option found at this point are selected as parents for the next generation and population. This selection is done by a roulette wheel of probabilities.

In this project I solve the classic problem called the needle in the haystack, this is, there is one single solution in a huge amount of possible individuals or population. Even this problem is trivial, this project has as main objective to investigate the role of the changes on hyper-parameters of genetic algorithms, such as rate of crossover, mutation, and point of crossover.

Some results of this research can be expressed as follows:

1. At some point a population can be seen as a family of solutions that share same genes. This is, they could represent a specific exploration on the space of solutions, then, crossover allows the exploration of this family of solutions. If the rate of crossover is high exploration can be take more time, but for sure will be find the best of the possible individuals between it.

2. Mutation allows to perform "jumps" between families! This perhaps can be considered as exploring dimensions or solutions.

3. In other hand, the place of partitions let parts of the problem be static, and be explored as a especific combination, which can be seen like inherit specific characteristic between individuals.

In conclusion I can see how genetic algorithms is a kind of predecessor of reinforcement learning in the sense that tries to make an environment of experimentation to choose the best of the individuals. Of course, in Reinforcement Learning we try to the agent to learn in the static environment, in GA, the environment evaluates agnostic agents.

Imagine combination of both paradigms, a selective environment of learning agents!

Well this will be the topic to future researches of mine.