Hyperparameter Optimization with Genetic Algorithms - A Hands-On Tutorial

A step-by-step tutorial of using genetic algorithms for optimization tasks

This post introduces an optimization strategy inspired by the realm of genetics and the process of natural selection, as the name of genetic algorithms suggests - let's call them GAs going forward.

We will formally define how GAs work, but let's first qualitatively try to describe the process, which sounds just like natural selection. As we all recall from biology, natural selection is the nature's way of choosing which traits will be passed on to the next generation, which results in the gradual evolution. With that context in mind, the overall GA process can be broken down into 6 smaller steps:

1. Start Somewhere ("Initialization"): Let's say there is a problem we would like to solve and we do not really know what the solution is. We can just randomly start with some solutions, which collectively we will call the "Population" - and then we can later on evaluate each of the individual solutions within the population. We will represent each solution with a "Chromosome".

2. Evaluate Existing Solutions ("Evaluation"): Now that we have started with some randomly-selected solutions, we will just measure how good or bad these solutions (or Chromosomes) are. The function that we will use to evaluate each solution will be called the "Fitness Function" and the evaluation results for each solution will be called a "fitness score".

3. Selection: Since we have the fitness scores for each of the solutions, we will go ahead and choose the best ones. We are going to call the selected solutions the "Parents", since we will use these parents to create the next generation of solutions, which we will call "Children" or "Offsprings". The weaker solutions that were not selected will be removed, similar to how natural selection works in evolution.

4. Reproduction ("Crossover"): As you probably guessed by now, the surviving "Parents" will use their "Genes" (defined as part of the solution or Chromosome) to create the next set of solutions ("Children"). As the name "Crossover" suggests, we indeed combine genes from two parents to produce an "Offspring", which will be the next generation of solutions. The idea is that regenerating based on the winning solutions that were selected in the "Selection" step will get us slightly and gradually closer to better outcomes - we will review this improvement trend with data in our example!

5. Mutation: Similar to nature and in order to explore more possibilities, some of the children will have random new changes so that our population continues evolving. This in fact happens in our biological genes as well so there is some randomness built into natural systems, such as us humans!

6. Repeat ("Evolution"): We then evaluate the new population with our fitness function and repeat steps 2 to 6 multiple times to evolve and approach better solutions.

Now that we understand the overall process, let's look at how we can implement this in Python. We are going to use genetic algorithms as a hyperparameter optimization methodology. Hyperparameter optimization, as the name suggests, is the process of identifying the best combination of hyperparameters for a machine learning model to satisfy an optimization function (i.e. maximize the performance of the model, given the dataset in study).

Let's better understand this during the implementation!

1. Implementation

In order to implement genetic algorithms , we are going to walk through two examples - a simple one just to better understand the process and then a more complicated problem, which is a better representative of what this optimization methodology can be used for in practice.

1.1. Implementation - Simple Problem

Let's first define an optimization problem. We will then look for optimization it using GA:

Objective: Maximize the function below, when x is between 0 and 1, inclusive:

This is an appropriate function for optimization, because it has multiple local maximums or maxima (and minimums or minima) in the above range so we want to make sure our optimization strategy does not get stuck in a local maximum. Let's visualize the space to better demonstrate the point:

# import librariesimport numpy as npimport matplotlib.pyplot as pltimport randomdef f(x):    return x * np.sin(10 * np.pi * x) + 1x_values = np.linspace(0, 1, 500)y_values = f(x_values)# visualizeplt.plot(x_values, y_values)# plt.title("Plot of f(x) = x * sin(10πx) + 1")plt.xlabel('x')plt.ylabel('f(x) = x * sin(10πx) + 1')plt.grid(True)plt.show()

Results:

As we can see above, this function has multiple local maximums in the range above so let's see if GA can find a good optimization path. Note that we didn't really need the "random" library that I imported above but since we will be using it later, I just added it in.

Let's start with defining the GA in a chronological order: Fitness Function: Fitness Function is how we evaluate each solution in the population and therefore it would be similar to the objective function we defined for our problem. So let's go ahead and define the same function as the Fitness Function:

def fitness_function(x):    return x * np.sin(10 * np.pi * x) + 1

Generate Population: As discussed earlier, we will come up with a random set of solutions as the first "Population" so let's create that as follows:

def generate_population(size):    population = np.random.uniform(low=0.0, high=1.0, size=size)    return population

Fitness Score: Now that we have the population and the fitness function, we can go ahead and evaluate each solution within the population, as measured by "Fitness Score". This function basically just runs the "fitness_function" on our population:

def compute_fitness(population):    fitness = fitness_function(population)    return fitness

Selection: Now it's time for us to simulate the natural selection of keeping good solutions and discarding the bad ones, through our "selection" function. This function receives three variables of population, fitness score and the number of parents. Then it randomly selects two members of the population, compares their fitness scores and keeps the one with the higher score in the "parents" list, which is roughly how natural selection works.

def selection(population, fitness, num_parents):    parents = []    for _ in range(num_parents):        idx1, idx2 = random.sample(range(len(population)), 2)        if fitness[idx1] > fitness[idx2]:            parents.append(population[idx1])        else:            parents.append(population[idx2])    return np.array(parents)

Crossover: As you recall from the overview of GA, once we select the better solutions as parents, we want to create offsprings by combining two randomly-selected parents. The function below does just that:

def crossover(parents, offspring_size):    offspring = []    for _ in range(offspring_size):        parent1, parent2 = random.sample(list(parents), 2)        child = 0.5 * (parent1 + parent2)        offspring.append(child)    return np.array(offspring)

Mutation: This function adds some randomness to our system! Recall that in nature, some levels of randomness get introduced at the genes level. This is our genes' natural way of trying new ideas, exploring and evolving. We will also replicate this process by adding some randomness to our population during a "mutation" process:

def mutation(offspring):    for idx in range(len(offspring)):        if random.random() < 0.1:            mutation_value = np.random.uniform(-0.1, 0.1)            offspring[idx] += mutation_value            offspring[idx] = np.clip(offspring[idx], 0.0, 1.0)    return offspring

GA Optimization: Now that we have defined the functions required for GA, we can start implementing our GA optimization. We are going to make some assumptions to define the parameters of the optimization.

def genetic_algorithm():    num_generations = 20    population_size = 20    num_parents = 10    # initialize population    population = generate_population(population_size)    # empty list to keep the best outputs in    best_outputs = []    # run through natural selection    for generation in range(num_generations):        # fitness scores        fitness = compute_fitness(population)        best_outputs.append(np.max(fitness))        print(f"Generation {generation}, Best Fitness: {np.max(fitness):.4f}")        # selection        parents = selection(population, fitness, num_parents)        # crossover        offspring_size = population_size - parents.shape[0]        offspring = crossover(parents, offspring_size)        # mutation        offspring = mutation(offspring)        # create new population        population = np.concatenate((parents, offspring))    # final population's fitness    fitness = compute_fitness(population)    best_match_idx = np.argmax(fitness)    print("nOptimal Solution:")    print(f"X = {population[best_match_idx]:.4f}")    print(f"Fitness = {fitness[best_match_idx]:.4f}")    # visualize    plt.plot(best_outputs)    plt.xlabel("Generation")    plt.ylabel("Best Fitness")    plt.title("Fitness over Generations")    plt.show()# run the functiongenetic_algorithm()

That looks pretty good! Looking at the diagram that we had earlier, we can see where the actual maximum happens and what the objective function's value at that location is. Looks like the approach is working and we are finding the best fit over generations.

Now that we know how GA works, let's move on to another example and compare the GA optimization outcome to Random Search, which is another method of optimization.

1.2. Implementation - Neural Networks

For this example, we are going to use the Fashion MNIST data set, which includes 70,000 28*28 labeled grayscale images, available under MIT License. This data set is used for benchmarking machine learning algorithms, which makes it a great one for evaluating our optimization approach. We will first run the optimization using GA and then run the same optimization with a Random Search function for comparison to the GA approach.

1.2.1. Neural Network - GA Approach

The overall approach is similar to what we did for the previous example so instead of providing step-by-step descriptions, I will just add descriptive comments in the code.

# import librariesimport tensorflow as tffrom tensorflow import keras# load fashion mnist dataset(X_train, y_train), (X_test, y_test) = keras.datasets.fashion_mnist.load_data()# normalize dataX_train = X_train / 255.0X_test = X_test / 255.0# reshape dataX_train = X_train.reshape(-1, 28 * 28)X_test = X_test.reshape(-1, 28 * 28)# convert labels to categorical# there are 10 classes or labels in the data sety_train = keras.utils.to_categorical(y_train, 10)y_test = keras.utils.to_categorical(y_test, 10)

# step 1 - fitness functiondef fitness_function(individual):    # decode individuals    neurons = int(individual[0])    learning_rate = individual[1]    batch_size = int(individual[2])    activation = ['relu', 'tanh', 'sigmoid'][int(individual[3])]    # print hyperparameters for reference    print(f"Training with neurons: {neurons}, learning_rate: {learning_rate}, batch_size: {batch_size}, activation: {activation}")    # validate hyperparameters    if neurons <= 0:        print("Invalid number of neurons. Setting to 32.")        neurons = 32    if learning_rate <= 0:        print("Invalid learning rate. Setting to 0.001.")        learning_rate = 0.001    if batch_size <= 0 or batch_size > len(X_train):        print(f"Invalid batch size. Setting to 32.")        batch_size = 32    # build the model    model = keras.models.Sequential()    model.add(keras.layers.Dense(neurons, activation=activation, input_shape=(784,)))    model.add(keras.layers.Dense(10, activation='softmax'))    # compile the model    # using adam as optimizer    optimizer = keras.optimizers.Adam(learning_rate=learning_rate)    model.compile(optimizer=optimizer, loss='categorical_crossentropy', metrics=['accuracy'])    try:        # train the model for 5 epochs - hopefully won't take long        history = model.fit(            X_train, y_train,            epochs=5,            batch_size=batch_size,            validation_data=(X_test, y_test),            verbose=0        )    except Exception as e:        print(f"An error occurred during model training: {e}")        return 0  # default fitness value when error    # validation accuracy of the last epoch    val_accuracy = history.history['val_accuracy'][-1]    return val_accuracy

# step 2 - generate populationdef generate_population(size):    population = []    for _ in range(size):        neurons = random.randint(32, 256)        learning_rate = 10 ** random.uniform(-4, -1)        batch_size = random.choice([32, 64, 128])        activation = random.randint(0, 2)        individual = [neurons, learning_rate, batch_size, activation]        population.append(individual)    return population

# step 3 - selection (returns parents)def selection(population, fitness_scores, num_parents):    parents = []    for _ in range(num_parents):        idx1, idx2 = random.sample(range(len(population)), 2)        if fitness_scores[idx1] > fitness_scores[idx2]:            parents.append(population[idx1])        else:            parents.append(population[idx2])    return parents

# step 4 - crossover (returns offsprings)def crossover(parents, offspring_size):    offspring = []    for _ in range(offspring_size):        parent1, parent2 = random.sample(parents, 2)        crossover_point = random.randint(1, len(parent1)-1)        child = parent1[:crossover_point] + parent2[crossover_point:]        offspring.append(child)    return offspring

# step 5 - mutation (adds randomness)def mutation(offspring):    for individual in offspring:        if random.random() < 0.1:            mutation_index = random.randint(0, len(individual)-1)            if mutation_index == 0:                individual[mutation_index] = random.randint(32, 256)            elif mutation_index == 1:                individual[mutation_index] = 10 ** random.uniform(-4, -1)            elif mutation_index == 2:                individual[mutation_index] = random.choice([32, 64, 128])            elif mutation_index == 3:                individual[mutation_index] = random.randint(0, 2)    return offspring

# step 6 - ga optimizationdef genetic_algorithm():    num_generations = 5    population_size = 10    num_parents = 5    global best_accuracies      best_accuracies = []        average_accuracies = []    population = generate_population(population_size)    best_individual = None    best_accuracy = 0    for generation in range(num_generations):        print(f"nGeneration {generation}")        # evaluate fitness        fitness_scores = []        for idx, individual in enumerate(population):            print(f"Evaluating Individual {idx+1}/{len(population)}")            accuracy = fitness_function(individual)            fitness_scores.append(accuracy)            print(f"Validation Accuracy: {accuracy:.4f}")            if accuracy > best_accuracy:                best_accuracy = accuracy                best_individual = individual        # record metrics        best_accuracies.append(max(fitness_scores))        average_accuracies.append(sum(fitness_scores) / len(fitness_scores))        # selection        parents = selection(population, fitness_scores, num_parents)        # crossover        offspring_size = population_size - len(parents)        offspring = crossover(parents, offspring_size)        # mutation        offspring = mutation(offspring)        # next generation of population        population = parents + offspring    # final Output    print("nBest Individual:")    neurons = int(best_individual[0])    learning_rate = best_individual[1]    batch_size = int(best_individual[2])    activation = ['relu', 'tanh', 'sigmoid'][int(best_individual[3])]    print(f"Neurons: {neurons}")    print(f"Learning Rate: {learning_rate}")    print(f"Batch Size: {batch_size}")    print(f"Activation Function: {activation}")    print(f"Best Validation Accuracy: {best_accuracy:.4f}")    # visualize    generations = range(1, num_generations + 1)    plt.figure(figsize=(10, 6))    plt.plot(generations, best_accuracies, label='Best Accuracy')    plt.plot(generations, average_accuracies, label='Average Accuracy')    plt.xlabel('Generation')    plt.ylabel('Validation Accuracy')    plt.title('Genetic Algorithm Performance')    plt.legend()    plt.show()

# run the functionimport timet1 = time.time()genetic_algorithm()t2 = time.time()elapsed_time = t2-t1print(f"GA optimization took {round(elapsed_time/60, 1)} minutes.")

Results:

The GA optimization above took about 4.5 minutes on my laptop. What is more interesting than the final results, is the visualization above. As you can see, GA is learning at each step of the way through the natural selecting process of keeping the winning members of the population and discarding the rest and therefore with more iterations, it is getting closer by improving the average accuracy.

Now that we have the results above, let's implement the same optimization problem, using the Random Search approach and compare the results.

1.2.2. Neural Network - Random Search Approach

Random Search is a popular and yet simple optimization approach. I have discussed this approach in detail in a separate post linked below:

Hyperparameter Optimization - Intro and Implementation of Grid Search, Random Search and Bayesian...

I will not go into details in the current post but generally, Random Search looks at the "Search Space", which is the universe of values for all the hyperparameters involved in an optimization task and then randomly selects a set of hyperparameters and calculates the objective function for the randomly-selected set. Then it simply picks the best combination, based on the objective function. What is important is that Random Search, unlike GA, does not learn from each iteration and rather starts from scratch every time and randomly selects the parameters. Therefore, if it gets lucky during the random selection, it can find a very good combination but in more complex search spaces with a large search space, such as this example, finding a good combination becomes less likely. On the other hand, Random Search can be very computationally light since it only calculates the objective function for a fixed number of times, instead of learning through iteration that GA does. So in conclusion, each approach has its pros and cons.

Let's implement the Random Search approach and look at the results

def random_search(num_trials):    best_accuracy = 0    best_params = None    accuracies = []    for i in range(num_trials):        neurons = random.randint(32, 256)        learning_rate = 10 ** random.uniform(-4, -1)        batch_size = random.choice([32, 64, 128])        activation = random.randint(0, 2)        individual = [neurons, learning_rate, batch_size, activation]        print(f"Trial {i+1}/{num_trials}")        accuracy = fitness_function(individual)        accuracies.append(accuracy)        print(f"Validation Accuracy: {accuracy:.4f}")        if accuracy > best_accuracy:            best_accuracy = accuracy            best_params = individual    print("nBest Parameters from Random Search:")    print(f"Neurons: {best_params[0]}")    print(f"Learning Rate: {best_params[1]}")    print(f"Batch Size: {best_params[2]}")    print(f"Activation Function: {['relu', 'tanh', 'sigmoid'][int(best_params[3])]}")    print(f"Best Validation Accuracy: {best_accuracy:.4f}")    # Plotting    trials = range(1, num_trials + 1)    plt.figure(figsize=(10, 6))    plt.plot(trials, accuracies, marker='o')    plt.xlabel('Trial')    plt.ylabel('Validation Accuracy')    plt.title('Random Search Performance')    plt.show()

# run the function, tracking timet1 = time.time()random_search(num_trials=10)t2 = time.time()elapsed_time = t2-t1print(f"Random Search optimization took {round(elapsed_time/60, 1)} minutes.")

Results:

As you can see, Random Search can come across good results and also poor ones, since it just randomly selects the hyperparameters. Using the GA we managed to get to 0.880 accuracy in 4.5 minutes, while Random Search reached 0.866 in less than a minute. The decision between the two approaches depends on the problem being solved and business considerations. For example, if the optimization will impact a large number of users, we may be willing to pay the higher computational cost of GA optimization to get to better results. On the other hand, if we are not very sensitive about finding the best outcomes, Random Search can be the way to go, which also runs significantly faster.

In this post, we introduced Genetic Algorithms as a hyperparameter optimization methodology. We described how these algorithms are inspired by the natural selection - an iterative approach of keeping the winners while discarding the rest. We then implemented this approach for two examples, a simple and a more advanced one and then compared the performance of the advanced example to Random Search. We finally reviewed the trade-off between finding the better optimization using Genetic Algorithms at a much higher computational cost, compared to Random Search.

Thanks For Reading!

If you found this post helpful, please follow me on Medium and subscribe to receive my latest posts!

(All images, unless otherwise noted, are by the author.)