Evolutionary Algorithms and Computer Cables
By greimer on Aug 29, 2007
The other day I was over at The Panda's Thumb reading about how evolutionary algorithms (EAs) provide yet another class of evidence for biological evolution. As a result I've had EAs on the brain. Also, this week I had a new computer shipped to my door, so I set it up and moved my old box behind my desk. This of course meant dealing with a ferocious snarl of computer cables.
During all the unplugging and subsequent untangling, it hit me. Tangles of cables are complex problems with potentially large solution spaces, which makes them good candidates for EAs. What's more, the typical human response to such tangles is an EA!
When confronted with a pile of cables, we're all familiar with the tug-and-jiggle maneuver. In other words, we pull on a loose end of cable, shake, and with luck, free it from the snarl. This is an EA, complete with populations, generations, mutations, selection, a fitness function and local maxima!
The tug is the algorithm, the first generation of which isn't very "fit" simply because pulling on a tangle rarely works on the first try. But we mutate the algorithm by continuously jiggling the pile and shifting it around in a random fashion. Thus we build up a "population" of algorithms, each having one shot at passing the fitness test. Eventually, things shift in such a way that a bit more cable is freed. This new state of affairs is superior, so we "select" it by pulling out the freed bit of cable while the chance exists. Then we continue jiggling through a second generation and so on. Often, we encounter local maxima during this process, where the tangle has decided to resolve itself into a knot. No amount of tugging and jiggling will free the cable now. Par for the course for EAs.