Bought cans of tuna for dinner. Came home & found out I bought cat food instead :(

Raspberry Pi Genetic Algorithm

We can use the concept of evolution and sex to solve problems. It's called a genetic algorithm, and here we are solving a problem of conforming LED colors to a target.

The basic premise of a genetic algorithm is a genome and fitness.

The genome is the raw data that makes up the characteristics of your solution. In biological terms, the physical manifestation of a genome is the phenotype.

The fitness is how you quantify those characteristics. 

In biology, we say that evolution is not progressive. It is a result of species adaptation to its environment in the form of greater fitness. This means if we quantify fitness in a way so that the next generation exhibits a higher fitness than the previous through its genome and connected phenotypes, a species can continue to survive in its environment.

Initially, earth exhibited organisms that reproduced via agamogenesis AKA asexual means. This means a single organism would branch off another being with a (theoretically) identical genome. Sometimes the genome would mutate because of environment, incorrect transcription, etc. Over millions of generations this mutation would create divergent beings. Overall there would be very limited variability amongst individuals at a given point in time. This proved to be insufficient for species survival.

A better means of evolving is through sexual reproduction. Two individuals of one species will come together and combine their gametes, which creates greater diversity in the species. This diversity results in divergent genotypes and phenotypes that will create individuals with greater fitness and adaptation to the current environment over several generations. Sexual beings are also subject to mutation, allowing for even greater diversity. These are the concepts we will use in our genetic algorithm for colors.

Genome Selection- 24 bit color

If our algorithm is that of colors, the genome is easy to pick. We will use the typical RGB color scheme, that results in 24 bits:

The color 0x7BC3EF has R = 123, G = 195, B = 239. It has a base10 value of 8111087. And it's phenotype is the light blue color as shown in the pic background. There's a lot said in just a simple hex number. 

Now we can determine how to find fitness. Fitness is defined here as similarity to a target color we wish to conform to. Perfect fitness, meaning a genome identical to the target, has value 0.

Genetic Algorithm:

  1. Create a population with size t and make their genomes random. Each population member is a citizen.
  2. Create a target color you wish the population to conform to.
  3. Assess the fitness of each citizen.
  4. Sort the population so that the most fit (aka the most like the target) citizens are at the top.
  5. Create a new population of children of size t. This is the next generation.
  6. Take the top 20% of citizens by fitness (20% is the elitism rate) and allow them to survive into the next generation. We want traits of the elites passed on.
  7. Take the top 40% of citizens and allow them to randomly mate. These children are together in the next generation population as those in step 5.
  8. In the child population, randomly point mutate 25% of citizens. In their genome, select a random bit and flip it.
  9. Children become parents, who then make children (repeat steps 3-8)

I used Henner Zeller's Raspberry Pi LED Matrix library to extend the ThreadedCanvasManipulator class and was able to get a flashing example. Here's the code:

/// Genetic Colors
/// A genetic algorithm to evolve colors
/// by bbhsu2 + anonymous
class GeneticColors : public ThreadedCanvasManipulator {
 GeneticColors(Canvas *m, int delay_ms = 200)
  : ThreadedCanvasManipulator(m), delay_ms_(delay_ms) {
    width_ = canvas()->width();