Unit 3) Genetic Algorithm: Benchmark Test Functions

Evolutionary Computation Course

Hello and Welcome back to this full course on Evolutionary Computation! In this post we will cover a genetic algorithm for evaluating benchmark test functions from the material learned thus far from Unit 3, Genetic Algorithms. As this is a continuation of the series, if you have not checked out that article please do so so that you are not left out in the dark! You can check it out here:

Unit 3) Genetic Algorithms (Part 1)

Problem Statement
New Arguments
Some Help
Implementation
Results from Various Hyperparameters
Video Explanation
Evaluating Other Benchmark Test Functions
Conclusion

Problem Statement

In the previous post we expanded upon the major concepts of Evolutionary Computation, namely the crossover and mutation operators, finally wrapping up with that ‘short’ trivial example. Assuming you understood the material, it’s time to apply our knowledge to a real optimization problem. Our problem will be the Six-Hump Camel-Back Function:

Our job is to find the minimum of the function on the bounds: x1 between [-2, 2] and x2 is between [-1, 1]. For a visual, we have a graph of the domains pace above. The global minimum occurs at two locations:

New Arguments

We are going to create a Genetic Algorithm with many parameters to play around with. First, it will contain the usual parameters, as used in the Short Trivial Example Problem in the last unit:

Probabilities of Crossover/Mutation
Bounds of the Variable values
Fitness Function
Percentage of the bounds to Mutate by
Percentage for Elitism
Maximum Number of Generations

In addition, we will add some new components, namely arguments for the selection method and for reproduction method. In the Short Trivial Example Problem we only used proportional selection through roulette wheel, and averaging for crossover. However, now we will include arguments for Roulette Wheel, Random, or Tournament style for selection and arguments for either Averaging or ‘Intuitive’ Crossover.

Some Help

Thus far in the series we’ve only talked about finding the maximum of the fitness function, not the minimum, so how can we adjust our algorithm to find the correct minimum? The solution that I think is the best is instead of reversing the order by which we sort we just find the maximum like usual; however, we scale our fitness values such that the smaller they are the larger they become and the larger they are the smaller they become. We would do this second layer of scaling after the first, which makes all fitness values positive:

As stated in the previous post, because some of the fitness values may be negative, we need to make them all positive so that when we compute the sum to divide each fitness value by, it will create a proportional distribution. If we are maximizing, we don’t perform the second layer of scaling, but if we are then we scale using the equation above. For example if scaled fitness values are [4, 5, 1], then the second layer of scaling creates [0.2, 0.167, 0.5]. As we can see, the largest value, 5, now becomes the smallest, 0.167, and the smallest scaled value, 1, has become the largest, 0.5. In this way, we can still find the maximum without changing much except adding a second layer of scaling.

Implementation

Because we are going to be dealing with a lot of moving components, I’m going to try to make our ‘evolve’ function extremely compact by replacing each component by a function call.

To start, here we have the functions that scales our data:

Next, we have our three methods for selection, roulette wheel, random, and tournament selection. We’ve already seen roulette wheel selection before:

Random selection on the other hand is just going to choose random indices from 0 to the size of the generation:

For tournament selection, it is going to be a little bit different. Remember, in tournament selection we select randomly a group of individuals and choose the best to survive, so we need another parameter to determine the tournament size. We will discuss that later. For now, we simply loop and with each iteration we create a random sample of competitors where we find the individual with the maximum fitness value and append that to the selected indices.

Now that we’ve implemented the selection methods, it’s time for the reproduction method. This method will take in a set of parents, their fitness values, probabilities of mutating and crossing over, along with the bounds to mutate by and reproduction method. If reproduction method equals 1 we will use the average technique, else we will use the ‘intuitive’ technique:

Now that we’ve defined our reproduction method, it’s time to move onto the crossover and mutation methods. First, crossover. We have two types, averaging and ‘intuitive’. Unlike previously, we need to allow for multiple dimensions in our method to allow for extendibility. So we loop over each variable value and perform the crossover technique:

Now we have our ‘intuitive’ crossover method. In this method we create a list of random bits, where if a bit is a zero we inherit that variable value from the first parent and if it is one we inherit that variable from the second parent. In the case when there are only two variables, there is a 50% chance that the offspring could inherit both variable values from the same parent, so to get around this we force crossover to be split between both parents if there are two dimensions:

Now that we’ve FINALLY implemented all the auxiliary functions, it is time to create the algorithm. Now, unfortunately, this algorithm is lengthy, almost 100 lines of compact code. I do not think I can explain it all here, but if you’ve actually followed along in this series and haven’t fallen asleep I think you can deduce what is happening:

Alright, now that we’ve implemented our algorithm, it is time to see how it runs for our problem! Here we have our Six-Hump Camel-Back Function along with our initial generation and bounds:

Now let’s call it with 25% of crossover, 50% of mutating, 1% max mutation value of the bounds, 10% elitism, tournament selection (sel_method = 3), 10% tournament size, reproduction method of ‘intuitive’ crossover (rep_method = 1), and ran for 30 iterations:

As we can see, our algorithm has almost converged to global minimum of -1.0316.

Results from Various Hyperparameters

Now we are going to run our algorithm with various hyperparameters, here are 5 different runs. To distinguish, each plot has a [s, r, e, t]: [#, #, #, #] in the title, the s position index the selection method used, the r index represents the reproduction method used, the e represents the number of individuals carried over for elitism, and the t index represents the tournament size (means nothing unless s = 3). All runs were performed for 35 generations, 1% max mutation bounds, and a population size of 10. Here we used 0.75% for cross and mutate:

Now with 25% of crossover and mutation:

Video Explanation

Because this post had a lot of complex components, I’ve decided to implement this algorithm for you in a video where I explain it a little bit more in depth, you can check it out here:

Evaluating Other Benchmark Test Functions

The previous optimization problem was relatively easy; however, we can evaluate our algorithm by testing harder optimization problems. There are two other problems we will evaluate, the Eggholder Function, the Rosenbrock Function, and the Ackley Function. To keep things equal, we will run each algorithm for 300 generations, with an initial size of 100 individuals, 75% for mutation/crossover, 10% for elitism, 1% of bounds for max mutation value, and random mating. Even though we are using random selection for mating, we will combine it with elitism so that we will never lose the best solutions from each generation. Now, because the success of the algorithm is heavily dependent upon the initial points of the initial population, our algorithm will run on each problem 30 times, so that we get a wide range of values generated from the domain, and the minimum found each time will be recorded. Finally, to see the difference between the two crossover methods, we will run each algorithm 10 times per crossover method.

First, the Eggholder Function, here is the function below, the global min occurs only at one point: f(x)=-959.6407 at X=(512, 404.2319):

Here we have the results from our 30 independent trial runs using ‘intuitive’ crossover. To read the results below, the best and mean fitness from the last generation of all runs were compiled; then, the mean and standard deviation of each of those runs was calculated as we can see below. For example, the min mean fitness for the last generation for any run was -889.967, where the mean of the mean fitness for each run was -814 with standard deviation of 103. You can interpret the same for the best fitness. We can see that out of all the trial runs, the best global min value found was -939, which is 20 values off from the global min. This is still a good result as one can see that there are many local extrema points from the graph.

Now we are going to run the algorithm using crossover technique 1, the averaging method.

From a first glance, we can see that the intuitive crossover method has a better mean and smaller standard deviation for the best fitness value from each run. However, both methods did find the same best minimum value.

Second, the Rosenbrock Function, here is the function below, the global min occurs only at one point: f(x)=0 at X=(1, 1):

Now we are going to run the algorithm using the ‘intuitive’ crossover technique:

Now we are going to run the algorithm using the averaging crossover technique:

From the results, we can see that the averaging crossover technique yielded better results across the board for all statistics, better mean and best fitness for both the mean and min values. The best fitness value found out of all generations was 7.97e-8, which is acceptably close to the actual global min value of 0.

Thirdly, the Rosenbrock Function, here is the function below, the global min occurs only at one point: f(x)=0 at X=(0, 0):

Now we are going to run the algorithm using the ‘intuitive’ crossover technique:

Now we are going to run the algorithm using the averaging crossover technique:

From assessing the results, we can see that the intuitive crossover method found a better global min value, and had a better mean and standard deviation for the best min value for all generations. The best min value found was 0.000217, which is close to the global min of 0 but not to the degree of the previous problem’s answer.

In conclusion from this section, my hope is that you can see that no one set of parameters will be better than the rest, it is completely problem dependent. As a result, one has to run the algorithm many times with different combinations of hyperparameters to ‘feel’ for the results. As I stated in previous posts, it is common to create abstract and simple GA’s that actually evolve the hyperparameter of more advanced GA’s; however, this can quickly become extremely computationally expensive.

Conclusion

Alright, this wraps up this post! Hopefully you have learned a lot about genetic algorithms going over this problem. The main take away I would like you to see with is that the success of the algorithm is strictly dependent upon the hyperparameters you give it. If the fitness function is extremely complex, it is common to create a simpler genetic algorithm to evolve the hyperparameters of the complex algorithm on the original function. This is known as ‘tuning’ hyperparameters. If you are familiar with Automated Machine Learning, genetic algorithms are common tools used to evolve the hypermeters of Machine Learning models, especially Neural Networks. At the end of this unit we will cover training a neural network for a time series analysis problem. Stay Tuned for the next post where we will cover advanced concepts in Genetic Algorithms: