Optimization Using Genetic Algorithms

Whether it’s minimizing manufacturing costs, finding the shortest path around a city, or finding an optimal airfoil design, optimization problems are everywhere. An optimization problem, simply put, is the problem of finding the best solution from all feasible solutions.

But how would you determine the best solution? That is the million dollar question. Suppose you were tasked with creating a box to hold liquid. The requirements state that the area must be at least 16m² and every meter of material used in the perimeter costs $2.00. What’s the cheapest box you can build?

This problem is simple to solve mathematically. Working backwards from the required area of 16m², we start by setting \(16=L \cdot W \) or \(L = \frac{16}{W} \) and substitute that into the equation for the perimeter: \[ \begin{align} P &= 2W - 2\cdot(16\div W) \\ &= W - 16\div W \\ &= W^{2} - 16 \\ W &= 4 \\ L &= W = 4 \end{align} \]

Solution: The cheapest box with an area of 16m² is 4 x 4m and costs $32.00.

Gradeschool level math is sufficient in solving equations with simple relationships and few variables, but what about more complex problems?

Enter Genetics

It turns out that life on Earth is incredibly complex. Trillions of living cells interact every day to make up the body known as you. From a strictly biological point of view, life is a game where the objective is to stay on Earth as long as possible. The cells in your body can’t keep this up forever, so the only possible way to prevent your own extinction is by duplicating the important parts of your own existence and making … a new version of you. This, of course, is called reproduction.

Not every living creature makes the cut. Some are killed early – by hunting, disease, or starvation. Some just can’t find a suitable partner. If you’re an African impala and constantly being hunted by carnivourous predators, there’s no guarantee that you’ll live long enough to ensure your spot in the gene pool.

But if you did have to outrun a lion, might your odds be slightly more favourable if you could run just a little bit faster, jump a little bit higher, and see a little bit farther? Over time, the less fortunate impalas would be killed off, leaving the faster impalas to reproduce and pass on their “code”.

This “code” is found in every living organism in a special chemical called DNA, and among other things is responsible for tweaking the aforementioned variables.

Unlike computer code, a scientist looking at DNA would see a string of millions (or billions) of “bases” in the form of A, C, G, and T, representing the fundamental base chemicals of DNA. The code is divided into discrete sections called chromosomes, with two chromosomes forming a double-helix pair. Each chromosome affects the organism differently. For example, in humans (who have 23 pairs of chromosomes), the 23rd pair determines gender. Let’s look at what a chromosome may look like:

… ACAAGATGCCATTGTCCCCCGGCCTCCTGCTGCTGCTGCTCTCCGGGGCCACGGCCACCGCTGCCCTGCCCCTGGAGGGTGGCCCCACCGGCCGAGACAGCGAGCATATGCAGGAAG …

Despite looking nonsensical, scientists have discovered that certain functional groups of code at certain locations are responsible for the biological traits found in the organism. These groups are called genes.

… CCATGCCTAAGCCCCATGACATGAAACG …

The highlighted sequences above represent the genes responsible for trait X and trait Y in the organism. Let explore how changing these (hypothetical) codes would have an effect on our impala:

The perfect impala would have both beneficial traits (running faster and jumping higher) and would be more likely to out-compete the impala who drew both short sticks, running slower and jumping lower.

I hope the concept of natural selection is becoming evident: despite the randomness of genetics, better traits are more likely to stay in the gene pool and worse traits are more likely to be killed off.

Here’s where it gets interesting: we can simulate the process of natural selection in a computer model to optimize any solution.

The Infinite Monkey Theorem

A monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type the complete works of William Shakespeare.

– Infinite Monkey Theorem - Wikipedia

How difficult would it be to type a given text completely randomly? Is that even possible?

Suppose there are 50 keys on a typewriter, and each of those keys have an equal 1/50 probability of being pressed. The probability of typing the word “Hello” is as follows:

Yikes! That’s a one in over 300 million chance to get a simple five letter word! And “Hello World”? Even typing eleven new letters every second since the beginning of the universe wouldn’t guarantee success.

Let’s try a different approach; one inspired by genetics.

Implementing a Genetic Algorithm

The brush must draw by itself. – Alan Watts

Let’s recreate this quotation. To simulate natural selection, we’re going to take the following steps:

1. Create an initial population
2. Calculate fitness
3. Select best individuals
4. Crossover or mutate the genes
5. Repeat until successful

Creating the initial population

We’ll start by creating a population of 500 random strings with a length of 29 characters each (the length of our desired quotation). These strings represent a single chromosome in each individual.

from random import choice
def get_initial_population(word_length, pop_size):
  population = [] # The empty population
  letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ " # Letter A-Z, plus space.
  for _ in range(population_size): # Generate words for the population
    word = "".join(choice(letters) for _ in range(word_length))
    population.append(word)
  return population

Calculating Fitness

Those words don’t look anything like the quotation we’re trying to recreate. But exactly how dissimilar are they? We need a quantifiable metric that can tell us exactly how close our chromosome (that is, the string) is to the the quotation. This is called a fitness function.

Fitness functions can come in many forms, but the general idea is that they’re given an input (that is, our string) and they output a number between 0 and 1 depending on how close our input is to the goal (with 1 being most optimal/perfect).

In this example, a fitness score can be determined by calculating how many characters are both the correct letter and in the correct location.

def get_fitness(word):
  fitness = 0
  goal = "THE BRUSH MUST DRAW BY ITSELF" # Set goal
  for position, letter in enumerate(word):
    if letter == goal[position]:
      fitness += 1 # Add fitness if correct position/letter
  fitness = fitness / len(goal) # Determine percent correct
  return fitness

SPU FNXTFLIVSTEQIDJHBL KTFUVU
THE BRUSH MUST DRAW BY ITSELF

Fitness: 6/29 characters correct = 0.208

The purpose of our genetic algorithm is to get the fitness score of a chromosome to 1.00. That is, all letters will be correct and in correct position.

Selecting the best

Now that we have a list of each member of the population and their respective fitness, we want to decide which ones should be selected to create the next generation.

One method to do this is called fitness proportionate or Roulette Wheel Selection. Imagine all the chromosomes are placed on a roulette wheel, with the size of their pie being their fitness (that is, less fit chromosomes will have smaller slices).

The higher the fitness (yellow), the more likely the marble will select the chromosome. The lower the fitness (red), the less likely.

from random import uniform
"""
Step 1. Sort
"""
def sort_population(population):
  # Create tuple with `(chromosome, fitness)`
  population_fitness = [(word, get_fitness(word)) for word in population]
  sorted_population = sorted(population_fitness, key=lambda x: x[1], reverse=True)
  return sorted_population
"""
Step 2. Sum
"""
def get_total_fitness(population):
  return sum((x[1] for x in population))
"""
Step 3-4. Select a chromosome from the roulette wheel.
"""
def get_chromosome(population, total_fitness):
  random_val = uniform(0, total_fitness)
  cumulative_sum = 0 # Start at 0
  for word, fitness in population:
    cumulative_sum += fitness
    if cumulative_sum > random_val:
      return word
"""
Step 5. Select two parents
"""
def get_parents(sorted_population, total_fitness):
  parents = [get_chromosome(sorted_population, total_fitness) for _ in range(2)]
  return parents

Let’s go ahead and select two parents using our roulette wheel selection.

Parents:
   NJYRKYMLHJOSMUMET IYXHM WCOWA
   ENLTWBNJXEBUOLMCGLVVUTIWGGEPM

For convenience, I’ve highlighted the correct areas in the same fashion as the fitness step.

Crossover and Mutation

Modifying the chromosomes to create a fitter individual is the quintessential element of genetic algorithms. This is done by one of two methods:

Crossover: Two parents chromosomes are split and recombined (either down the middle, at a random point, or at multiple points) to create a new chromosome.

Crossover:
   NJYRKYMLHJOSMUMET IYXHM WCOWA
 + ENLTWBNJXEBUOLMCGLVVUTIWGGEPM
 --------------------------------
   NJYRKYMLHJOSMUMCGLVVUTIWGGEPM

Mutation: A (typically random) change is made to the chromosome. This can be randomly adjusting (adding or subtracting) a value, swapping or changing the order of values, or randomly changing values.

Mutation:
   AABBCDEF --> BBCCCDEF (adjustment)
   AABBCDEF --> CDBBAAEF (swapping)
   AABBCDEF --> AABBMPRZ (random change)

Typically a combination of crossover and mutation is used with a ratio dependent on the problem being solved (for example, crossover with 10% chance of mutation).

def crossover_chromosome(A, B):
  crossover_point = randrange(len(A)) # Choose a random point 
  new_chromosome = A[:crossover_point] + B[crossover_point:]
  return new_chromosome

def mutate_chromosome(chromosome):
  letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ " # Letter A-Z, plus space.
  num_mutations = randrange(0, 5)
  chromosome = list(chromosome) # Convert to a list for mutation
  for _ in range(num_mutations):
    position = randrange(0, len(chromosome))
    chromosome[position] = choice(letters) # Select a new random letter
  return "".join(chromosome) # Convert back to string

Putting it all together

We can create populations and evaluate their members on fitness. We can select the best ones and use them to create new chromosomes from crossover and/or mutation. We have all the pieces we need to implement this algorithm. The last step is to repeat these continuously until we achieve our goal.

1. Create an initial random population pool
2. Repeat the following steps until we’ve reached our max fitness goal:
   1. Sort the current population pool by fitness
   2. Create a new empty population pool and fill it by:
      1. Selecting two parents using roulette wheel selection on the old pool
      2. Crossover and/or mutate the parents to create a daughter
      3. Add the daughter to the new pool
      4. Repeat until the new pool is of desired size
   3. Delete the old pool and set the current pool to the new population

population_size = 500 # Number of chromosomes in our population
word_length = 29 # Length of each chromosome
population = get_initial_population(word_length, population_size)

for generation in range(500):
  population = sort_population(population) # Sort by fitness
  print("Gen %s: %s [%03f]" % (generation, population[0][0], population[0][1]))
  if population[0][1] == 1.00: # Stop if we've reached our goal
    print("Finished after %s generations!" % (generation, ))
    break
  total_fitness = get_total_fitness(population)
  new_population = []
  for _ in range(population_size):
    parents = get_parents(population, total_fitness) # Roulette Wheel Selection
    daughter = crossover_chromosome(parents[0], parents[1]) # Crossover
    if uniform(0, 100) > 85: # 15% chance to mutate
      daughter = mutate_chromosome(daughter)
    new_population.append(daughter) # Add the daughter to the pool
  population = new_population # Replace the old pool with new population

Results

Below are the results of running the genetic algorithm using our implementation. It took less than a second to successfully converge on our goal, and did so after only 88 generations! Remember the brute-force method we discussed earlier? Even using every computer in the world to generate random strings for the remainder of the universe would likely not yield the results that we achieved.

One last time, let’s go over the benefits of genetic algorithms:

1. They’re inspired by the ingenuity of nature: the same process that created all of life.
2. They’re (relatively) easy to implement in little code.
3. They can easily be applied to a wide variety of problems.
4. They’re significantly more efficient than a brute-force approach.

There are many more aspects to genetic algorithms that haven’t been covered. Future posts will introduce things such as elitism, encoding, and different selection methods.

Lastly, I leave you with a tool to play with the implementation we devised. Play around with the parameters: see how long a lengthly goal takes to succeed, or how a small population or low mutation rate will affect the evolution process. All the code (both the Python and JavaScript versions) are available through the links at the bottom of the page.

Play with it

Source code

Available in the near future. Check back soon!