Sam Williams
When machines breed
Evolvable hardware -- gadgets that design themselves -- can get the job done, even if humans have no idea how they do it.
Paul Layzell is a specialist in the budding field of evolvable hardware. Simply put, he helps machines design themselves, using principles borrowed directly from biological evolution.
It’s a job with strange and unexpected twists. Take the time three years back when he and fellow University of Sussex researcher Jon Bird attempted to build an oscillator circuit using genetic algorithms and a handful of transistors. While a few circuits came out fitting the functional profile — steady output, steady frequency — one circuit took a strange path to get there. Instead of building internal feedback loops to reach the desired frequency, it had simply wired itself in a way that the radiated hum of a nearby computer went straight through the circuit and into the attached oscilloscope.
In other words, it cheated. The circuit had hacked the system by becoming a radio.
“The best way I can think to describe it is a mixture of respect and humor,” says Layzell, summing up his reaction. “A bit like when a child solves a common problem in an original way: It always makes you smile.”
Using evolutionary processes to optimize machine performance is nothing new. Since the 1960s, artificial intelligence researchers have exploited the dynamics of Darwinian evolution to solve software problems in fields as diverse as financial investment, manufacturing and biochemistry.
What is new, however, is the application of evolutionary processes in the hardware realm. Thanks to reconfigurable devices such as the field programmable gate array (FPGA) — the microchip designer’s equivalent of an Etch A Sketch — and increasing computational power, researchers who once performed simulations of new circuits with an eye on the clock are suddenly free to let their designs evolve for a while just to see what happens. One might not be sure that one understands how a given circuit achieves what it is supposed to, but if it works, is that really a problem?
For many engineers, the question is already the first major litmus test of the 21st century. Those who answer yes see evolutionary engineering as barely a half step above tinkering. Those who answer no, however, see it as a useful method to break through the complexity barriers limiting both software and hardware innovation.
“I see the evolved radio as an intuition pump,” says Bird — borrowing a phrase from Daniel Dennett, a Tufts University philosopher with a sizable fan base in the world of artificial intelligence research — “a vivid thought experiment that can structure the way we think about a problem.”
Derek Linden, chief science officer for JEM Engineering, an antenna-design firm based in Laurel, Md., has used evolutionary design processes to build antennas for military contractors and NASA’s Jet Propulsion Laboratory. He credits the relatively sudden interest in evolutionary hardware design to economic factors.
“When I started doing this, I was running my simulations on a single Pentium 66 [MHz] PC,” Linden says. “That meant I had to be real careful with how large my problems were and how long it took things to run. Now, you can brute-force things a lot more easily.”
Applying “brute force” in the case of evolutionary design means breaking problems down into smaller, simpler tasks. Just as the human genotype can be rendered as a 3 billion base-pair genome, so can silicon circuits and wire antennas be boiled down to an even simpler, binary numeric form. Split this “genotype” into randomly determined halves, and you have something that can be “mated” with another design, with the resulting offspring farmed out for testing on a separate software simulator. The results aren’t always pretty, but when you filter out the weak designs and let the breeding process run for a thousand or so generations, you get something like the seedless watermelon — all features and no drawbacks.
“Some have called genetic algorithms ‘embarrassingly parallelizable,’” says Linden, who uses a seven-CPU Linux Beowulf cluster to test and optimize antenna designs. Linden and fellow engineers run the recommended genotypes through a second, higher-fidelity simulator. If the results remain promising, they fabricate the antenna for real-world testing.
In the case of circuit designs, especially those employing FPGA chips, the evolutionary design program can try out its own designs on a reconfigurable base of silicon transistors. Dubbed “online evolution,” this form of design is much more complex and tends to generate the most bizarre, and intriguing, results.
So far, the process has worked best in the antenna-design realm. Next year, NASA’s Space Technology 5 mission will deploy the first satellite employing an antenna designed by evolutionary processes. Developed at the NASA Ames Research Center, the antenna looks like an ordinary paper clip after a hard day’s work. Built to fit within a cubic inch of space, it features five sharp bends and one gradual bend. All told, the entire design process took 10 hours, using 35 Linux servers and minimal human intervention.
“We try to give as little antenna knowledge as possible to our software and let evolution be free to design the antenna as it sees fit,” says Jason Lohn, head of the Evolvable Systems Group at the NASA Ames Research Center.
Such comments highlight the dividing line between traditional engineering and evolutionary engineering. Where traditional engineers find comfort in rigid specifications, trusting the computer for number-crunching and testing, evolutionary designers must trust the entire design process.
This can lead to sticky situations. Lohn notes how a number of algorithms have come up with designs patented by other inventors. Novel designs, meanwhile, have a tendency to leave engineers scratching their heads. In a 2002 paper summing up their oscillator experiment, Bird and Layzell note that even the designs that play within the rules were often impenetrable to later analysis.
“It has proved difficult to clarify exactly how these circuits work,” Bird and Layzell write. “Probing a typical one with an oscilloscope has shown that it does not use beat frequencies to achieve the target frequency. If the transistors are swapped for nominally identical ones, then the output frequency changes by as much as 30 percent.”
Lohn, for one, sees the electrical engineering world falling into two schools of thought. “One school of thought says you need a black box that does X, Y and Z. If I use evolution to get something that does X, Y and Z, I don’t care what’s in it as long as it works.”
And the other school? “That one says, ‘I need to understand what’s in there,’” Lohn says. “Those are the people we can’t really help, because a lot of times, we don’t know what’s in there.”
Lohn seems comfortable working in the “black box” camp. He describes antenna design as a “black art” and distances himself from those who, following in the footsteps of British 19th century physicist James Clerk Maxwell, prefer elegant, textbook-worthy solutions to actual working solutions.
“Maxwell wrote down the four equations which govern all of wireless communication,” he says. “They describe the physics, but the weird thing is, you never use them. In practice, this field is so squirrely, the only way to learn is through trial and error. It’s the school of hard knocks.”
Not that the field doesn’t offer the occasional, tantalizing glimpses at a deeper, more theoretical insight waiting to be discovered. Lohn recalls episodes in which he and fellow researchers accidentally cut out sizable portions of a circuit with minimal effect. Lohn likens the lost portion to a vestigial organ, like the human appendix, useless now but useful at one time. Hence the decision to keep it around.
Equally intriguing are the occasional experiments where researchers make a mistake, using a faulty wire to power the circuit, for example. In such instances, fixing the wire often kills off many of the most promising circuits, proof positive that even circuits grow accustomed to a shoddy environment.
“Evolution doesn’t want to see that wire fixed,” Lohn says. “Evolution is sneaky. It’ll exploit anything you put within its reach.”
Firefox — the flag bearer of free software
Mozilla's browser is taking market share away from Microsoft. Sometimes, slow and steady really does win the race.
To misquote F. Scott Fitzgerald, there are no second acts in the lives of software projects.
Oh sure, the developers sometimes move on to bigger and better things. When it comes to the created works, however, the trajectory is depressingly consistent: Functional simplicity gives way to feature bloat, followed by brittleness, unreliability and, barring certain monopoly-friendly market conditions, oblivion.
For the bulk of its six-year existence, the Mozilla project has been the unwitting victim and symbol of this truism. Like Jacob Marley’s ghost in “A Christmas Carol,” the open-source browser seemed doomed to bear the sinful weight of its earlier, proprietary incarnation — Netscape Communicator — for eternity.
Continue Reading CloseThe Wal-Mart supremacy
The giant retailer's introduction of RFID technology is forcing other supermarket chains to catch up. But fiddling with data may not be the best survival strategy in the Wal-Mart future.
What do you call it when a company announces a multibillion-dollar technology initiative with no preexisting infrastructure, no software code and an 18-month deadline to delivery?
In most cases you’d call it a recipe for disaster. In the case of Wal-Mart, a company with the power to force others to follow its technology agenda, you’d simply call it “tough love.”
That two-word description, according to a January article in Computerworld Magazine, is exactly how Wal-Mart CEO H. Lee Scott summed up his company’s philosophy on radio frequency identification (RFID) in a speech to suppliers last winter. For those who missed it, the company sent out letters to top suppliers last June requesting that all pallets and boxes come equipped with RFID tags by Jan. 1, 2005, a request designed to facilitate better warehouse tracking. Suppliers so far seem to have gotten the message. This June, a year after the initial letter campaign requesting 100 participants, Wal-Mart reported that 137 companies had climbed aboard.
Continue Reading CloseComputer, heal thyself
Why should humans have to do all the work? It's high time machines learned how to take care of themselves.
In his 1992 book “To Engineer Is Human: The Role of Failure in Successful Design,” Duke civil engineering professor Henry Petroski tosses out a little-known statistic from the history of bridge design: During the latter half of the 19th century, a period that introduced the locomotive train to most corners of the industrial world, roughly a quarter of all iron truss bridges failed.
The simplified reason: Bridge designers, unused to iron as a structural material and railroad trains as a service load, had yet to grasp the full impact of a minor miscalculation anywhere within their plans. It wasn’t until designers started introducing a conservative fudge factor, now known as the margin of error, that bridge designs developed enough redundancy and robustness to account for the occasional errant crossbeam or overloaded rail car.
Continue Reading CloseInvasion of the spambots
From blog spam to pornbots, new strains of computer programs aimed at pumping up Google page ranks just keep on coming.
For Lawrence Kestenbaum, the realization that a new species of intelligent agent — or “bot” — was prowling the Internet first dawned about two years ago.
It was about that time, Kestenbaum says, that a series of “fluke” addresses started popping up in the HTTP referrer log of his personal Web site, the historical cemetery database Political Graveyard.
“If you’re at all concerned with how your Web site is being received, you’re almost compulsively checking the logs to see who’s coming in and from where,” says Kestenbaum, laying the scene. “You get to know what sites are linking to you. Anything new gets your attention.”
Continue Reading CloseEveryone is an editor
In the wacky wiki world, a Web browser is all you need to start contributing. But when the goal is to create an encyclopedia, such democracy has some pitfalls.
Like most frontier sheriffs, Wikipedia Arbitration Committee member Martin Harper wears his badge with a mixture of pride and caution.
A 24-year-old software engineer from Worcester, England, Harper knows what it’s like to be new. It was only two years ago, after all, that Harper, an immigrant fresh in from the Douglas Adams “Hitchhiker’s Guide to the Galaxy” online encyclopedia project, H2G2, encountered the scary freedom of wiki publishing — where pretty much anyone can add his or her own thoughts to a Web site, even if that means overwriting or “correcting” what someone has already written.
Continue Reading ClosePage 1 of 3 in Sam Williams