Basic Genetic Algorithm for optimising the model in Python

Before going to Genetic Algorithm (GA), we take a look where it comes frome. We have often heard that humans evolved from ancient apes. This view stems from Charles Darwin’s theory of evolution. Parallel to Darwin’s theory of evolution, the core thing of GA is about natural selection, it has several steps and methods. One of them is Evolutionary Algorithms, which are special methods to solve computational problems, such as optimisation problems. They can provide a better output in shorter time period. In this article, I would like to introduce the basics definition of GA, simple implementation of GA in solving problems with Python.

There are 4 components of GA which we should understand:

1. Population: An initial generation will have certain individuals with different characteristics, these features will determine the ability to reproduce, survive, and the ability to meet environmental conditions of each individual in the generation.
2. Natural Selection : Darwin theory indicates the based concepts that following the time, the weaker and non-viable individuals will be eliminated by factors such as food chain disputes, toxic environments, and destruction by other species. ,… Finally, the more preeminent individuals will be retained — Adaptive individuals.
3. Mutation: The next generation will inherit the characteristics of both parents from the previous generation. After a period of time living, a population will set to the limit of the gene pairs of children made up of genes of parents. In order to achieve evolution, Mutation are one of the main reasons, contributing raw materials to the Natural Selection process.
4. Evolution: Mutation and natural selection will be the main factor to decide the survivals during time being. better than other individuals in the population. After a period of reproduction, the mutation genes will dominate and dominate the population.

Basic steps of Genetic Algorithms (Based on Darwins Theory)

Based on those concepts, the demonstration of Genetic Algorithms is trying to model the steps by steps of natural selection process. There are many loop cycle, starting at creating population and finishing at the natural selection.

Evolutionary Algorithms (EA)

Now we will see the 4 main steps of EA are below:

1. Generate an initial population of individuals randomly.
2. Evaluate the fitness of each individual in the population.
3. Repeat as often as you like:
   a) Select individuals with a good fitness score for reproduction.
   b) Let them produce offsprings.
   c) Mutate these offsprings.
   d) Evaluate the fitness of each individual in the population.
   f) Let the individuals with a bad fitness score die.
4. Pick the individual with the highest fitness as the solution.

GA Code Experiment

This part we will try to implement genetic algorithm to verify the correctness of GA, the problem we are trying is finding the maximum and minimum of this below formula:

f(x) = x*sin(x)+1, x∈[0, 2л] 

Firstly, we need to creating the population:

Then, we initially define some other functions of decode, fitness and evaluation

Next, now is the time for crossover and mutation function:

Last, the evolution function can be defined :

Now we can run and see the result of the code, we can adjust parameters (group size, crossover rate, mutation rate, etc.) and compare results. In this runtime, I set the parametters like this:

# The number of individuals in the population is 10,

#The chromosome length is 24, the crossover probability is 0.7

#The mutation probability is 0.15

#The maximum number of evolutionary generations is 150

The result is showing the maximum and minimum through 150 generations.

We can plot the result by using matplotlib to see the the changes via generations:

Visualising the results

Conclusion

In this article, we are going through the basic concept of Genetic Algorithms and have seen how Evolutionary Algorithms work. The example is about implementing the concept into the basic optimising problems. The algorithms can be very fast and yield accurate results. The implementation is seemingly not complicated and we can using same concepts into harder problems.

References

[1] S. Droste, T. Jansen, and I. Wegener, On the analysis of the (1+1) evolutionary algorithm (2002), Theoretical Computer Science, Volume 276, Issues 1–2, 6 April 2002, Pages 51–81

[2] M. Laumanns, L. Thiele, and E. Zitzler, Running Time Analysis of Evolutionary Algorithms on a Simplified Multiobjective Knapsack Problem (2004), Natural Computing 3, 37–51

[3] K. Stanley, R. Miikkulainen, Evolving Neural Networks through Augmenting Topologies (2002), Evolutionary Computation 10(2) 2002, S. 99–127

[4] https://nerophung.github.io/2020/05/28/genetic-algorithm

[5] https://www.programmersought.com/article/97706056653/