What is a genetic algorithm?

(check here to use this graphic)

Genetic algorithms are highly effective tools in machine learning. But they come with a catch.

Genetic algorithms are cool. You breed and mutate models until you have a near optimal solution. They are also easy to understand and to code. So where is the catch?

It is understanding what they are used for.

What are genetic algorithms used for?

A genetic algorithm works very differently from most other ML algorithms:

• no input data that goes into the algorithm
• the model itself is the prediction of the algorithm
• the prediction can be another algorithm

Confusing huh? So it doesn’t classify cat photos?

A genetic algorithm use case boils down to this:

I need this thing. I can tell the difference between a thing and a better thing. Also, I need the best thing. But there are too many possible things to try out.

So a genetic algorithm always optimizes a piece of information. Some use cases would be:

• a route on a map
• an antenna for a spacecraft
• code
• an ML algorithm

So how to know if your use case suits a genetic algorithm?

1. The information must be separable into building blocks(genes) (Like code into words, an antenna into its bendings etc.)
2. There must be to many possibilities to try and no mathematical algorithm to calculate the absolute optimum. Or the algorithm is to computationally expensive. Otherwise, you don’t need the genetic algorithm.
3. You must be able to test the information and differ it from better or worse information (Like having a tool that can calculate a specific antennas performance)

How does a genetic algorithm work?

The algorithm itself is pretty simple.

1. Create a number of random examples of the information you need. (random route, random antenna, random neural network)
2. Check which of them perform the best. Discard a predefined portion of the worst examples.
3. Breed new examples by using parts of the best examples to generate new ones. (Most of the time until you have filled up the discarded worst)
4. Mutate some of the examples by switching some of their building blocks with random ones.
5. Repeat 2 – 4 until you run out of time or have reached the quality you need.

And that’s it. Heres a simple example:

We want an algorithm that creates the highest possible number. The information is built out of integers. Let’s create some random samples

123; 857; 372

Lets check which of them are the highest and discard the lowest:

857;372 -> 123

Create a new one by using random parts of the “Parents”(keep the order as its information too):

857;372; <-877

Mutate some randomly

887;375;877

Check which one is best and discard the worst one:

887, 877 -> 375

Repeat.

As you see it’s not that complicated.

Genetic algorithms can be incredibly useful. But especially the “Check for the best” part can be difficult.

In the next post, we will check out a more complex example using python.