Did you see my recent When Genetic Algorithms Meet Artificial Intelligence column on EEJournal.com? The focus of this column was the fact that the clever little scamps at Algolux are using an evolutionary algorithm (EA) to fine-tune the myriad parameters featured in the camera architectures and image processing pipelines used in computer vision applications.

A Solution…

An EA employs mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. The most popular type of EA is a genetic algorithm (GA). In this case, the problem is represented as strings of numbers (traditionally binary).

The way this works is rather clever. Let’s suppose we have a problem that involves a lot of interrelated and intertwined variables, such that modifying one variable can aggravate, mitigate, intensify, or moderate the effects of one or more other variables. What we want to do is gather the potential values of all these variables into a single string of binary numbers. For example, if one variable could adopt 16 different values, we would use a 4-bit field in our string to represent all of the possible states of this variable.

We commence by generating an initial population of strings, whose contents are seeded using random (or pseudo-random) values as illustrated by (a) in the associated image. Next, we evaluate each of our strings to see how well it performs with regard to achieving the desired result. Of course, this means there must be some output or outputs from the system we can measure to check how close we come to meeting our goal. Based on this, each string is assigned a “fitness” value.

Sad to relate, this is where we have to cull the lower-performing strings and bid them a fond farewell as illustrated by (b) in the associated image. What can I say? They simply didn’t make the grade. Of course, we are going to keep our higher-performing strings — why would we throw them away?

Our high-performing strings become the “parents” of the next generation. This is where things get clever because parent strings “mate” to generate “offspring” strings (in some GAs, the highest performing strings get to mate more than their less successful counterparts).

When it comes to mating two strings, one approach is to randomly generate a crossover point and break both strings into two parts at that point — let’s call these parts X1 and Y1 from string 1, and X2 and Y2 from string 2. We then use X1 and Y2 to form one offspring string, while X2 and Y1 are combined to form another as illustrated in (c) in the associated image. (One experiment would be to consider algorithms using crossover points that were free to occur anywhere in the string, as compared to crossover points that were restricted to occur on boundaries between adjacent variable fields.)

We then repeat the ranking and breeding cycle over and over and over again. Just to stir things up a little, we also replicate the concept of mutation by randomly (and relatively infrequently) flipping the occasional 0 to a 1, and vice versa. In this case, we would probably keep both the unmutated and mutated versions of that string to see which one fares best.

Although all of this may seem a little “wackadoodle” at first, EAs and GAs can be used to quickly and efficiently search through a multi-dimensional solution space and arrive at an optimal — often unexpected — solution. As one example, I offer the 2006 NASA ST5 spacecraft antenna. The convoluted shape of this little rascal was arrived at using an evolutionary algorithm, which was tasked with creating the most favorable radiation pattern.

…Looking for a Problem

Ever since I first heard about genetic algorithms decades ago, I’ve toyed with the idea of experimenting with the little ragamuffins. While I was writing the aforementioned EEJournal column, I started to contemplate my 12 x 12 ping pong ball array, in which each ball is illuminated by a tricolor LED (see Awesome 12 x 12 Ping Pong Ball Array).

What I’m thinking is that it would be really cool to present the ongoing evolution of a genetic algorithm using this display, perhaps by varying shapes and/or colors. Alternatively, maybe our “goal” could be to generate a specific pattern or shape on the display, in which case we could watch how this shape evolves from an “amorphous blob” into its final form. The trick in this case would be for the desired shape to be a function of multiple interrelated variables.

Ideas are bouncing around my noggin like — well, ping pong balls. One of the things I was thinking of implementing with my display was a small Conway’s Game of Life (a.k.a. GoL), which I discussed in my RIP Game of Life Creator column. Well, could I use a GA to determine the optimum rules for a GoL, and — if so — would they be the same as the rules settled on by Conway? Alternatively, could I use a GA to evolve a pattern known as a spaceship, which translates itself across the array?

One of my problems is that I tend to over-engineer things. Maybe we should put the GA driven GoL on the back-burner for a while and start with something simpler.

Let’s remind ourselves that I’m using a Seeeduino XIAO to drive my ping pong ball array. This little beauty, which is only the size of a small postage stamp and costs only $5, is very, very tasty. In addition to a 32-bit Arm Cortex-M0+ processor running at 48 MHz, the XIAO boasts 256 KB of flash memory and 32 KB of SRAM (see also Say Hello to the Seeeduino XIAO).

Suppose we say that the strings in our GA will be 32 bits long. In addition to being the natural word-length of the XIAO, this would give us a solution space of 2^32 = 4,294,967,296 possibilities. If we assume a population of 1,024 strings, then this will consume only 4 KB of our 32 KB SRAM.

In a Nutshell…

So, what I’m looking for in a nutshell is a problem that’s simple in concept (so I can wrap my brain around it) but complex regarding its solution space. Something involving multiple variables that interrelate and interact in intricate and convoluted ways, but which can be represented in a “string” implemented as a 32-bit unsigned integer (I’d be happy to increase the number of bits in our strings and the number of strings if necessary).

This problem should also be one whose goals are easy to define and whose algorithmic output(s) can be measured to see how well each “string” ranks in the scheme of things.

Last, but certainly not least, the problem should lend itself to our displaying the ongoing results of the evolutionary solution on my 12 x 12 ping pong ball array.

So, what say you? Do you have any ideas you’d care to share?