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:
- Formulate solutions to your problem as arrays of numbers.
These arrays, called organisms, will be spliced with each other and will have their values (genes) mutated, somewhat like a chromosome.
- Provide a fitness metric.
Your fitness metric takes in an organism and outputs a number representing how good it is. Organisms with higher fitness stay alive when the population size reduces.
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:
- Mating two organisms allows for the creation of an offspring organism with good qualities from both parents.
- Mutating organisms creates small changes that are encouraged when they move toward a better fitness.
- Natural disasters shake up a population if it's been too long since any significant advancement in fitness.
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:
- I formulate my organisms as arrays of decimal numbers that can hold values between 0 and 10. This array always has the same length.
- To encourage the organisms to have values closer to 10, I define my fitness metric as the sum of the array. This fitness metric will prefer numbers that are higher in general.
- Over the course of the genetic algorithm, organisms that mutate toward higher values are preferred over ones with lower values. Eventually, I will come across an organism with an array of perfect 10's!
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:
- Setup. This function holds anything you need done before the algorithm runs. For my problem, I'm dividing a source file into grains that will be re-assembled and compared against a target file.
- Spawn. This function is responsible for creating new Organisms at the start of the genetic algorithm. If you aren't sure the best way to do this, then a good fallback is initializing the Organism's genes randomly. For my problem, I randomly pick each gene from the indices of grains I have stored.
- Synthesize. This function transmutes an Organism from its gene representation to another representation that is useful for your problem. It is for your own benefit and is not used by the internal genetic algorithm code. (It's often helpful to use the synthesize function in your fitness metric.) For my problem, I convert the Organism's genes into an array of audio float values so that I can do some signal processing to compare the Organism to my target sound.
- Fitness. This function evaluates how good an Organism is! It can often be difficult to conceive of a metric that increases as a solution gets better. Instead, try thinking of a distance metric, which decreases the better something is. The negative of that distance metric works as a fitness metric! For this variant of my algorithm, I sum the differences in the root mean square of many short windows of the organism's sound and the target sound. Then, I multiply this distance by negative one to obtain a fitness metric.
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:
- FloatPlayer, which can hook up an array of floats to other ChucK UGens (unit generators), and can also write arrays of floats to disk as a wav file.
- FloatReader, which can record other ChucK UGens to a float array, or read an audio file from disk to a float array.