I’ll be assuming that you know what these terms mean:
- Cost/objective function
- Local/global optima
If you don’t, that’s what Wikipedia and weekends are for.
What Is It?
Genetic algorithms are an optimization technique loosely based on the ideas of evolution and mutation. They’re a metaheuristic, and can used as a generic framework for solving all sorts of problems.
They’re also stupid simple, and I’ll try to prove that to you in this post.
The goal is to find the optimal solution to a problem, or one that’s close to it.
I’ll be using a lot of terminology, but it’ll all be defined properly later. This section is just to get the basic idea.
To start, we generate a bunch of candidate solutions to the problem. Each candidate is called an individual in the spirit of biology. The set of all individuals is the population.
Every iteration of our algorithm (a.k.a each generation), we evaluate the fitness of each individual and keep some amount of the fittest individuals. The rest are culled, except for a few that we randomly select to introduce some diversity that will help us find the global optima.
We create the next generation by breeding the survivors to create children.
Our next big inspiration from biology is mutation. Some fraction of the children are mutated at birth to introduce more diversity in a population.
We keep on doing this until the average fitness of the population has converged to something or we’re bored.
Why Should You Care?
This technique is worth learning if you care about optimizing things, because:
- Can be run in parallel
- Easily distributed
- Doesn’t require fancy tuning for the problem at hand
- Derivative-free, i.e. can be used for problems with lots of discontinuities
- Generic, easily adapted to new problems with minimal tweaking
How To Implement?
Terminology
We start here, since a lot of the barrier for learning these (for me) was the unfamiliar terminology.
- Individual
- A candidate solution for the problem.
- Population
- A set of individuals.
- Fitness Function
-
A function that takes in an individual and returns a real number representing how good a solution the individual is.
This is is usually maximized, but we’ll be minimizing it. So “fitness” is a misnomer, and it’s really a cost function as we’ll be using it.
The Process
Lots of the following steps are independent of the specific problem you’re trying to solve, and I’ll mark the ones that are generic to illustrate that.
To make this more concrete, we’ll be trying to optimize few benchmark functions.
I picked the Rastrigin function because it was first on the list and was easy to type in Python.
We optimize in the interval between \([-5.12,5.12]\) because Wikipedia told me to.
def rastrigin(x, A=10):
return 10 * len(x) + sum((i ** 2 - A * np.cos(2 * np.pi * i)) for i in x)
def sphere(x):
return sum(i ** 2 for i in x)
def booth_fn(x):
return (x[0] + 2 * x[1] - 7) ** 2 + (2 * x[0] + x[1] - 5) ** 2
f = rastrigin
Define the Individual
This is problem-specific. It should be a candidate solution to your problem.
In our case, we just want points in \(N\)-dimensional space, so we just use an array of length \(N\). We’re just going to work in 1-dimensional space to make the computation really fast, but feel free to try it in higher dimensions.
def individual(bound: float=BOUND) -> Individual:
return np.random.uniform(low=-bound, high=bound, size=N)
Define Fitness Function
We’ll be calling this fitness instead of loss for the sake of consistency, but we’re going to be minimizing it.
In our case this is simple. It’s just the objective function we’re trying to minimize, the Rastrigin function.
def rastrigin(x, A=10):
return 10 * len(x) + sum((i ** 2 - A * np.cos(2 * np.pi * i)) for i in x)
f = rastrigin
def fitness(individual: Individual) -> Real:
return f(individual)
Create Population
This is barely problem-specific. You just create some number of individuals. I feel like you could write a more abstract function that makes this generic, but it’s easy to do yourself.
def create_population() -> Population:
return [individual() for _ in range(POPULATION_SIZE)]
Find Average Fitness Of Population (generic)
This is literally just the mean fitness over the population.
def avg_fitness(population):
return sum(fitness(individual) for individual in population) / len(population)
Cull (generic)
Now we get to the law of the jungle. Survival of the fittest. Or rather, death of the un-fittest.
We sort our population by fitness and keep SURVIVAL_RATE percent of
them. A few lucky individuals also get spared for the sake of genetic
diversity.
def cull(population) -> Population:
population.sort(key=fitness)
split_idx = ceil(SURVIVAL_RATE * len(population))
# they survive
fittest = population[:split_idx]
reprieved = random.sample(
population[split_idx:], floor(REPRIEVE_RATE * len(population[split_idx:])))
return fittest + reprieved
Breed and Mutate
Breed
The fun (and tricky part): how to combine parents to get a child.
This is extremely problem-specific, and clever breeding (and mutation) will make the difference between success and failure. Figuring out good strategies comes with practice and understanding the problem domain.
I tried 4 different strategies and the one that worked best was not the first one I thought of.
But for us, we’re going to us a really simple strategy. We just pick the fittest individual out of a random sample and copy it.
Mutate
Mutation is also problem-specific, and as important as breeding. In our
case, mutation will be the main method of solving the problem. We’ll
perturb each array by some number EPSILON, and set the mutation rate
high so that this happens often.
We use np.clip to avoid escaping the area we’re optimizing over.
def breed(parents: Population, mutation_rate: float=MUTATION_RATE) -> Individual:
child = min(
random.sample(parents, NUM_PARENTS),
key=fitness, )
if random.random() < MUTATION_RATE:
child += np.clip(
np.random.uniform(low=-EPSILON, high=EPSILON, size=N),
a_min=-BOUND,
a_max=BOUND, )
return child
Repeat (generic)
Now it all comes together. We repeatedly cull and breed until our average fitness is close enough to optimal or we decide to stop after some number of iterations.
The key line is population = create_new_generation(cull(population)),
where we cull and then create a new generation from the survivors.
def create_new_generation(population) -> Population:
num_children = POPULATION_SIZE - len(population)
num_parents = min(len(population), NUM_PARENTS)
population += [breed(random.sample(population, k=num_parents)) for _ in range(num_parents)]
return population
def evolve():
population = create_population()
FITNESS = avg_fitness(population)
iter = 0
while FITNESS > 1e-7 and iter < MAX_ITERS:
population = create_new_generation(cull(population))
FITNESS = avg_fitness(population)
iter += 1
if iter % 1000 == 0:
best = min(population, key=fitness)
print('--------------------------------------------------------------')
print(f'FITNESS = {FITNESS}, iter = {iter}, BEST = {fitness(best)}')
print(f'iter = {iter}')
best = min(population, key=fitness)
return best
How Well Does It Do?
In the case of our problem setup, it tends to do fairly well. Often it gets stuck at a local minima of about .995, but equally often it finds the global minima in anywhere from 2 (!!) to a few thousand iterations.
Tweaking hyperparameters
You sort of have to play around with parameters like population size, survival rate, mutation rate, and reprieve rate.
You could probably write another genetic algorithm to tweak the hyperparameters of your genetic algorithm. I’ll leave that as an exercise.
Takeaway
Hopefully genetic algorithms will stick in your head long enough for you to find a use for them. When that day comes, read this post again. Soon enough, you’ll be able to make genetic algorithms a part of your toolbox.