Genetic Algorithm in C

This was an implementation of a genetic algorithm in C. This program takes in values from the command line and computes the best solution to minimize the Rastrigin function, with the option to enable and disable elitism.

# Biology? In my bits and bytes?

(it's more likely than you think)

Heuristic methods are kind of magical if you think about it. You're taking a complex problem, one that might have hundreds of thousands of parameters, and approximating it to the point where you can say "Eh, close enough," and it just works. So, imagine how awestruck I was when I found out that you simulate evolution within a program to solve problems.

What really got me into this way of thinking was through the videos on this YouTube channel (they make amazing visualizations). Take for example, this video showing how simulated creatures can learn how to work together:

(isn't that just awesome?)

It couldn't be that hard to implement my own evolutionary algorithm, right?

# Code and Features

The algorithm I decided to go for was a genetic algorithm. In a nutshell, randomize a population, let them make "children", allow these individuals to mate and mutate and hopefully, after some amount of generations, you're left with an answer that"s just close enough. To keep things simple for my first attempt at this, I decided to optimize a well-known test function, the Rastrigin function, before I moved on to anything larger.

As for why I chose C as the language, some of the courses I was taken were already using C and I didn't feel like swapping between languages for projects, so it made sense to settle on that. Nevertheless, here are the features.

• Accepts CLI arguments to modify values like population, max generations, mutagenesis factors, etc.
• Heuristically computes the minimal solution to the Rastrigin function with a genetic algorithm.
• Able to enable and disable elitism to preserve the most fit individuals in the population.
• Computes the wall clock time spent computing the solution.

# Reflection

There were two pretty big takeaways from this, despite being your usual college project.

## Counterintuitive Results

When I was looking for methods to improve my performance with the genetic algorithm, I came across elitism, a strategy to improve the fitness of the population by reserving a few seats for the most fit individuals. The idea is that by keeping the fittest alive, any further children will most likely be fit, as well.

However, this was not actually the case, and it turns out here that counterintuitively, elitism was worse than the genetic algorithm by itself. It would make sense that keeping the most fit individuals alive would create more fit offspring. What actually happens though is that by guaranteeing the survival of a select few individuals, you end up lowering the genetic diversity of the population, and are therefore more likely to end up stuck in a local minimum.

The main lesson here is that intuition can be misleading at times, especially in complex systems. Instead of just going with what "makes sense", I should strive to test initial assumptions,

## Planning Ahead

Another issue I encountered during this project was figuring out how to make my program run faster. It wasn't egregiously slow, but it was still slow enough to warrant concern. I figured that besides the small optimizations I could make, like using a binary search algorithm for finding parents, I ought to parallelize the program with a library like OpenMP. However, when I went to do that, I found that with the way the current program was written meant that it wasn't embarrassingly parallelizable.

The lesson here was to plan ahead of time, as it saves a lot of headache later. Had this had been a bigger project where I had to make a major change after-the-fact, the effort spent refactoring the whole codebase would've been a nightmare—a nightmare that could be avoided with careful planning.