The starting point of Evolution Strategies: the EE-(1+1) algorithm
In this post I will explain my experience programming the most basic Evolution Strategy (EE-(1+1) algorithm) and testing it for minimizing four different testing functions: Sphere, Ackley, Himmelblau and Rastrigin. This post is the first one of a series of posts about this topic that will be released in the next weeks.
I did this as a preamble to the work I had to do for a subject of the Master’s degree in Research in Artificial Intelligence (the subject is called Evolutive Computing and Evolution Strategies are just a small part of it) that I am studying. In this work I had to code another Evolution Strategy (a more advanced one) but following the same methodology introduced in this post.
The post is divided in tree parts. In the first one briefly explain what an Evolution Strategy is, what it is for and how it works. In this part I will explain this particular algorithm too. The second part will be dedicated to the methodology and the functions selected. The last one contains the results (just progress curves, the next indicators will be commented in future posts) and the conclusions of this small experimentation.
Evolution Strategies and the EE-(1+1) algorithm
The Evolutionary Computing is a branch of the computation that uses methods of stochastic search based in the natural evolution for solving optimization problems [1]. The Evolution Strategies are a paradigm of Evolutionary Computing created by Ingo Rechenberg and Hans P. Schewefel [2]. This algorithms are useful in all kinds of problems, from optimization to design and planning. They are widely used for their capacity of finding solutions as good as the founded by expert humans and for their surprising capacity of finding new and brillant solutions no considered before.
In general this algorithms works creating a population of individuals that represent in some way (the genome of the indivudual) the posible elements of the space of posible solutions (in this case the choosen representation is just the point in space, the real representation is the more suitable for this particular problem) [3].
The individuals of this population are evaluated again a function called the fitness function that measures how well this particula individual resolves the problem. This gives us the fitness value for the evaluated individual. In our case the fitness function will be the function to be optimized.
The next stage is to chek if some of the indivuduals holds the termination condition (in this case if the fitness value is equal to zero). If this is true the solution has been found and the program ends. Observe that in some cases the desired solution is not known, in this case the termination condition could be the number of generations and the best found individual our solution.
The next phase is to select the parents, recombinate and mutate them in order to create the new generation and select their indivuduals. In this case our population will consist only in one parent and one offspring (this is way the algorithm is called EE-(1+1)), so we do not have to recombinate or select the offsprings and our mutation consists only in a small perturbation in the values given by a paramether sampled from a normal distribution.
The implementation in Python of the algorithm is pretty streightforward:
Methodology
The idea of this experimentation is evaluate the the effectiveness of the algorithm minimizing functions whose real minimum we know (will be 0 in all the cases and, except in the case of the function of Himmelblau, it is unique and located in (0, …, 0)). In order to do that we will apply the algorithm to the same function several times (just 10 in this case) and keep the results. The number of generations has been limited to 1000 in all cases. The number of repetitions is low just for make the visualization of the progress curves prettier, in the next post where quantitative indicators will be explained the number will be bigger.
The algorithm has been coded in Python and executed in version 3.8.3 inside a virtual environment. The resources for replicate the hole experiment (including the requirements.txt file) can be found on my Github profile. The instructions for installing the virtual environment and install the libraries can be found on the README.md file in the root of the repository.
The functions I have chosen to test the algorithm are the next ones:
- Sphere function: defined for a real space of dimensionality N. In this post only dimension 2 has been considered. The global minimun of this function is (0, 0) and the value is 0. More information can be found on Wikipedia.
- Ackley Function: just like the previous one, in this post only the 2-dimensional form is considered in order to be able to represent the paths along with the function. This function present several local minimuns as you can see in the picture. More information can be found on Wikipedia.
- Rastrigin function: only 2-dimensional version has been considered. This function present several local minimuns as you can see in the picture. More information can be found on Wikipedia.
- Himmelblau’s function: this function is defined only for 2-dimensional real spaces. This his function has more then one minimums as you can see in the image. Again, more information can be found on Wikipedia.
Results and conclusions
As you can see in the results below, this algorithm with this number of executions only works properly when the function has not local minima where the solution candidates can be gotten stuck.
Just an important observation: in this case we know the solution in advance (we can compute it analytically) and that is why we use this functions to test our algorithms. In a real situation we would not know the real solution or whether or not there are local minimums and of course it is highly probable that the dimension of the problem is greater and we cannot visualize the solution that we find.
That is the main reason why in next posts I will continue with this experiment presenting indicators like the number of generations for reaching success (a measure of the rate of convergence), and increasing the dimensionality of the problem, the number of repetitions of the experiment and the number of maximun generations.
- Sphere function: In this case all the executions find the minimun in (0,0), the best individual of each generation has a fitness value very close to 0 (the real minimun of the function).
- Ackley Function: we can observe than in this case only in one of the repetitions our algorithm has found the minimum of the function. This seems and indication that our values are not mutating enough to escape the local minimums of the function.
- Rastrigin function: in this case we observe the same phenomen that affects the Ackley function, the solutions get stuck in the function’s local minima and are not able to escape.
- Himmelblau’s function: in this case the paths found the local minima but does not escape from there as the number of generations grow.
The main conclusion is this algorithm is able to find the solution to simple minimization problems but is not useful in complex cases where a high mutation rate of the individuals is needed. From the experiementation here presented only can conclude this in a low dimension and we can not extrapolate this behave to higher dimensions without testing it (spoiler: the dimensionality affects highly, but in order to study this we need indicators that will be introduced in next posts) due to the curse of dimensionlity effect.
References
[1] Bäck, T., Fogel, D. B., & Michalewicz, Z. (Eds.). (2018). Evolutionary computation 1: Basic algorithms and operators. CRC press.
[2] Beyer, H. G., & Schwefel, H. P. (2002). Evolution strategies–a comprehensive introduction. Natural computing, 1(1), 3–52.
[3] Carmona, E. J., & Galán, S. F. (2020). Fundamentos de la Computación Evolutiva. Marcombo.
