Working around patent licensing problems with evolutionary algorithms.

08 October 2007

Evolutionary computer algorithms are good at solving a relatively common set of problems through trial and error - the set of problems that we know of with a large number of equally valid possible solutions, of which some subset of those are faster or more efficient. The only way to see which of these solutions will do what you want is to try one and mess around with it for a while, and then try a slightly different approach. In other words, by tinkering, tweaking, and hacking around, which is great on a small scale but when you're looking at a few dozen to a few thousand possibilities, time, money, and materials make doing so prohibitive. As the name implies, evolutionary algorithms treat problems as sets of genes: They try one set, see how well it works, then change a variable (mutation) and try again. The lists of mutations that get you the farthest toward your goal are kept, while the rest are stored until their possibilities have been fully explored and pruned of dead ends. For this reason, some genetic algorithms (I don't know for certain because this isn't my field of expertise) are well suited for massively parallel computation, i.e., throwing lots of CPUs at copies of the algorithms and letting them churn for some period of time, because lots of attempts made at the same time are more likely to result in successes in shorter periods of time.

There was a pretty cool presentation done on this topic at LayerOne this year by Rooster - if you're curious, you can watch the whole thing here.

Genetic algorithms are being used to develop all sorts of things that you wouldn't ordinarily expect, such as optical fibres, antennae, flash memory, and tissue biopsy analysis because they involve, among other attributes, shapes and patterns that can be described with geometry, or with such methods as filling in cells on a grid (very much after the fashion of cellular automata). What would take a team of engineers and hackers weeks or months of constant effort can be done by these systems in days with current computation technology. They can also be used, it should be noted to design around certain parameters - the article gives as an example of this a research team at Stanford University designing an antenna for 802.11 wireless networking without licensing a patent from Cisco because the evolutionary development system they used was instructed to look at the publically available information in the text of the patent and then try everything not covered by the patent (exclusionary mutation).