Genetic Algorithms


Genetic algorithms solve complicated problems by providing a method for ranking the solutions in a group, rather than providing a method for directly computing the best solution.

To create a genetic algorithm for solving a problem, you must do two things:

Over time, your population of solutions will evolve toward an organism that is a particularly good fit for your fitness algorithm:

These processes run every generation:

Defining a Fitness Metric

The most crucial part of a genetic algorithm is the fitness metric. The solutions your algorithm produces are entirely dependent on how your fitness function captures what is "good" about potential solutions to your problem.

Let's walk through an example fitness function for a toy problem:

I'd like to make an array of numbers hold the value 10 in every spot. Rather than setting the values directly, I formulate a genetic algorithm:

Here's the code for my fitness function in ChucK:

View the full source code for this problem.

An Example Algorithm

Now let's walk through all the code you need to write to run a genetic algorithm using the framework I've written in ChucK. We'll walk through one of the genetic algorithms I built for the purpose of mimicking timbre using granular synthesis. To write your own genetic algorithm, download any of the code examples on this page and modify it in these key places, which are also clearly marked within the files.

Spawner Class

The Spawner class is where all the information specific to the domain of your problem lives. Here, you need to let the framework know some key constants such as the minimum and maximum values that Organism genes can hold, and the ChucK time your fitness function takes to run. (The latter is needed because the computation of fitness is parallelized to speed the algorithm up.) You will also provide the definitions of four key functions:

Population Class

The Population class is responsible for running the genetic algorithm. For the most part, you can ignore this class. However, you may find it useful to edit the After Each Generation function, which allows you to interact with the results of the genetic algorithm at the end of every generation.

For my algorithm, I only run code after the first generation and every 10 generations from then on. I find the Organism with the highest fitness in my population, synthesize it, write its synthesized form to disk, and check its fitness. If the fitness goes beyond a threshold I find acceptable, I halt the algorithm early. (Otherwise, it will run for the maximum number of generations, which I have defined in the Population class to be 1000.)

Congratulations! The file for running your genetic algorithm extends for several hundred lines after this, but you've read and edited everything you need to for your algorithm to work.

Source Code

Here's the source code for all the genetic algorithms I've written for this project:

And here's a couple utility classes for working with audio as arrays of floats in your algorithms:


About the uncanny valley.
About this project.