Genetic Algorithm
Hi, Steemers!
I love math, especially geometry. But also love to observe the world of ideas and what a brilliant application they find in different areas. And today I'd like to tell you small interest fact from algorithm theory. You will learn how important it is to listen to nature.
Everyone knows who is Charles Darwin and his major discovery - the theory of evolution. It so clearly describes the process of formation of the most viable species. Interestingly, this theory played a role in the formation of computing algorithms. And genetic algorithm was born due to the theory. This algorithm mimic features of natural selection and leads to the optimal solution.
The basic principles formulated by Darwin:
- the strongest survive and crips die (natural selection);
- the new individual is obtained by crossing and there is mutation;
As it turned out, this concept is very well suited for finding the maximum of the function. In General, the algorithm can be described in this scheme.
Application Example 1
In the simplest case, the vectors plays the role of the individuals, their arithmetic average is the result of crossing and mutation - adding noise to the coordinates of the vector. So, using the algorithm we can get the best vector (that maximizes the a function). I've found a cool GIF:
More than Gradient descent
Some of us knows that the algorithm GD(gradient descent) is also used for finding the maximum of the function. Moreover, various modification of it finds it faster. But why do we need GA(genetic algorithm)? The answer is simple. GD only works with differentiable functions. This means that arguments are only real numbers. But the genetic algorithm is ready to work with functions, regardless of their arguments - the main thing to determine the crossing of two individuals and mutation.
Application Example 2
Here are an illustrative implementation of the genetic algorithm. Car Generator.
You can play with the settings to achieve maximum results. My maximal score - 140m (I haven't played for a very long time).
Сonclusion
We see another example of copying ideas of nature for solving problems of humanity. The principles which are very easy to formulate and beautiful result - it makes me admire.
This publication is the first in a series of publications about the beauty of nature and science. If you have something you admire from science, then share this fact with me in the comments. Thank you for your attention.
These look like all local optima. Is there a global solution?
It is impossible to guarantee finding the global maximum. In the case of highly corrugated surfaces, the algorithm does not get stuck when getting into a local maximum, in contrast to Gradient Descent.
You should look into the methods of Applied Algebraic Geometry Groebner Bases (Symbolic) or Homotopy Methods (Numeric) which can guarantee finding a global maximum.
Oh, it's really good recommendation. Thank you! I will definitely be studying this issue.
And the reason that it doesn't get stuck (permanently) is that the genetic algorithm is usually stochastic, meaning that the recombination of the parental programs is somewhat random, so it can "jump" local bumps, given enough time.
On the picture you can see that some highs are generally not taken into account. In addition, often a local maximum is taken for global. It is best to specify the function explicitly, and solve it. Moreover, the mathematical apparatus in this area is severely underdeveloped.
If function is differentiable, it is certainly better to solve problem explicitly. If the function is bad, considering it an approximation we can get a lot of false highs.
View review from complexring - perhaps mathematics is developed enough.
Do you plan to give more examples, maybe in future posts? I would love to learn more about that and also get some concrete examples of genetic algorithms so that I could understand better.
Thank you for your attention!) Definitely I will give you more material! Follow me - it will be interesting!)
enjoyable post :) the case of flying machines is interesting though. imitations of bird flight didn't really work in the early days. what worked was a barn door strapped to a lawn mower engine and a bicycle (or the like) ....
Someone noticed that the door is very similar to the wing)