PO Box 6603

Huntsville, AL 35813, USA

+1-256-970-1906

max@CliveMaxfield.com

A Solution Looking for a Problem

I need a problem that lends itself to being solved using a genetic algorithm; also, one whose evolving results can be displayed on my 12 x 12 ping pong ball array.

Blog Sponsors

Support My Blog


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).
High-level visualization of the genetic algorithm process (Click image to see a larger version — Image source: Max Maxfield)
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).
The 2006 NASA ST5 spacecraft antenna that was designed by an evolutionary algorithm (Image source: NASA)
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).
Your’s truly proudly presenting his ping pong ball array (Click image to see a larger version — Image source: Max Maxfield)
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?

Blog Sponsors

Support My Blog

0 0 vote
Article Rating
Subscribe
Notify of
guest
2 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Vincent

A fun problem I would like to do would be to convert a .wav file to something which can be output over an audio synth chip, or some form of frequency synthesis (e.g. fixed number of waveforms with amplitude, phase and frequency/period). Now of course we could use good ole’ Fourier, but where is the fun in that. Besides Fourier only supports boring sines.

Here is where the genetic algorithm comes in. The ‘DNA’ would be a number of register settings (e.g. 12 😉 ) containing waveform type (depends on the chip, i.e. noise, sine, block, sawtooth) and parameters (freq, envelope, amplitude, phase). I would imagine the waveform would be chopped into short sections of sound, and the genetic algorithm would find the register values which when the chip is activated would as closely as possible match the original short sample. Once the synth chip produces something near to what is expected (or the maximum cycles is reached), it stores the best match into a file or program, maybe a VGM/SID file, and goes to the next block until the wave file is completely encoded as commands for the sound synth chip.

For the actual encoding you could use a real physical chip with a ADC to capture the output wave, or emulation (more precise).

Though it may not produce anything recognizable it should prove interesting.

Blog Sponsors

Buy this space!

Recent Posts

Interviews with the Greats (and Me) 

Eeek! Spectacular Sensors Smackdown! 

Best 4×4 Keyboard Ever? 

World Radio History 

Sending a Message Through Time 

Robinson, Goldberg, and Steampunk Meet Beer and Cucumbers 

Old, Rich, Alone in the World? 

IoT Online Conference: $0 Registration 4 Limited Time 

Awesome Photo of Rocket Passing Moon 

Si? No Thanks! GaN? Yes Please! 

  • LOGIN
  • REGISTER
LOGIN

Already a member? Login


Oops, forgot your password?

Please enter your username or email address.
You will receive a link to create a new password via email.

REGISTER
  • Name

  • Usernames cannot be changed.
  • Contact Info

  • About Yourself

  • Share a little biographical information to fill out your profile. This may be shown publicly.
  • Add or Edit GravatarYou can change your profile picture on Gravatar
  • Type your password.
  • Type your password again.

Edit Profile

You must be logged in to edit your profile.

2
0
Would love your thoughts, please comment.x
()
x