genetic
algorithm

Genetic algorithms are inspired by nature and evolution, which is seriously cool to me. It’s no surprise, either, that artificial neural networks (“NN”) are also modeled from biology: evolution is the best general-purpose learning algorithm we’ve experienced, and the brain is the best general-purpose problem solver we know. These are two very important pieces of our biological existence, and also two rapidly growing fields of artificial intelligence and machine learning study.

Genetic Algorithm Basics

The basic approach to GAs is to generate a bunch of “answer candidates” and use some sort of feedback to figure out how close the candidate is to optimal. Far-from-optimal candidates literally die and are never seen again. Close-to-optimal candidates combine with each other and maybe mutate slightly; this is an attempt to modify the candidates from time to time and see if they get closer to optimal or farther from optimal. These “answer candidates” are called chromosomes. Chromosomes mate, produce offspring, and mutate. They either die due to survival of the fittest, or are allowed to produce offspring who may have more desirable traits and adhere to natural selection.

The Chromosome

The chromosome is a representation of a solution candidate. In our case, the chromosome itself is a string. Let’s assume that all chromosomes have a length of 13 characters (the same as “Hello, World!”). Here are some possible chromosomes that could be solution candidates for our problem:

• Gekmo+ xosmd!
• Gekln, worle”
• Fello, wosld!
• Gello, wprld!
• Hello, world!

Obviously that last one is the “correct” (or globally-optimum) chromosome. But how do we measure the optimality of a chromosome?

Cost Function

The cost function (or error function, or fitness function as the inverse) is some sort of measure of the optimality of a chromosome. If we’re calling it “fitness function” then we’re shooting for higher scores, and if we’re using “cost function” then we’re looking for low scores.

Mating and Death

Mating is a fact of life, and we use it tons in GAs. Mating is a magical moment that two chromosomes in love with each other share. The technical term for mating is “crossover”, but I’ll continue calling it “mating” here, because that paints a more intuitive picture. We haven’t talked about “populations” in GAs yet (we’ll get to that a bit later) but for now I’ll just say that when you run a GA, you don’t just look at one chromosome at a time. You might have a population of 20 or 100 or 5,000 going all at once. Just like in evolution, you might be inclined to have the best and strongest chromosomes of the population mate with each other, with the hope that their offspring will be even healthier than either parent. Mating strings, like in our “Hello, World!” example is pretty easy. You can pick two candidates (two strings; two chromosome) and pick a point in the middle of the string. This point can be dead-center if you want, or randomized if you prefer. Experiment with it! Take that middle point (called a “pivot” point), and make two new chromosomes by combining the first half of one with the second half of the other and vice versa.Take these two strings for example:

• Hello, wprld! (1)
• Iello, world! (1)

Cutting them in half and making two new strings from the alternating halves gives us these two new “children”:

• Iello, wprld! (2)
• Hello, world! (0)

As you can see, the offspring includes one bastard child that has the worst traits of both parents, but also an angel child that has the best traits of both.Mating is how you get from one generation of genes to the next.

Mutation

Mating alone has a problem: in-breeding. If all you do is mate your candidates to go from generation to generation, you’ll get stuck near a “local optimum”: an answer that’s pretty good but not necessarily the “global optimum” (the best you can hope for). Think of the world that these genes are living in as a physical setting. It’s really hilly with all sorts of weird peaks and valleys. There is one valley that’s the lowest of all, but there are also tons of other little valleys — while these other valleys are lower than the land directly around them, they’re still above sea-level overall. Searching for a solution is like starting a bunch of balls on the hills in random places. You let the balls go and they roll downhill. Eventually, the balls will get stuck in the valleys — but many of them will get stuck in the random mini-valleys that are stilly pretty high up the hill (the local optima). It’s your job to make sure at least one of the balls ends up in the lowest point on the whole map: the global optimum. Since the balls all start in random places, it’s hard to do this from the outset, and it’s impossible to predict which ball will get stuck where. But what you can do is visit a bunch of the balls at random and give them a kick. Maybe the kick will help, maybe it’ll hurt — but the idea here is to shake up the system a little bit to make sure things aren’t getting stuck in local optima for too long. This is called mutation. It’s a completely random process by which you target an unsuspecting chromosome and blast it with just enough radiation to make one of its letters randomly change.

The Population

The population is a group of chromosomes. The population generally remains the same size but will typically evolve to better average cost scores over time. You get to choose your population size. I picked 20 for mine below, but you could choose 10 or 100 or 10,000 if you want. There are advantages and disadvantages