Foresight Update 38
A publication of the Foresight Institute
The FAD Fad
by J. Storrs Hall, IMM
In the First NASA/DoD Workshop on Evolvable Hardware, a paper by Pollack, et al., begins "We address the fundamental issue of fully automated design (FAD) and construction of inexpensive robots and their controllers". A quick Alta-Vista search for FAD reveals "Flash AD memory cards", "Find-a-Doctor", "flavin adenine dinucleotide", "Finnish Aid in Development", and "Financial Audit Division", but no Fully Automated Design. (This is slightly facetious simply searching for "automated design" garners nearly 3 million hits.)
A substantial paper by Pollack and Funes in the book Evolutionary Design by Computers (Morgan Kaufmann, 1999) entitled "Computer Evolution of Buildable Objects" gives some insight into the state of the field. This is the paper in which they describe evolving designs for structures built with Lego bricks for various purposes (bridges, cantilevers, towers, etc).
The basic idea is straightforward (although one wonders if it would have been considered straightforward 25 years ago!). There is a program that maintains a population of data structures, each of which describes a structure of Lego bricks. Each structure is simulated, being subjected to some load that the ultimate design is supposed to support. How well a particular structure supports the load determines its "fitness score", and the population is pruned and new individuals generated based on the fitness scores.
In my experience, and I have worked with genetic algorithms in design for some time, the success of the approach depends critically on three factors in the particular application. First and foremost is the representation. This determines the size, and density of solutions in, the search space -- and GA's are very much a search strategy. A good representation displays the salient aspects of the structure, hides the inessential ones, and in particular allows the generation of new structures that can retain the useful substructures already evolved, intact.
Second is scoring -- there needs to be a test which not only distinguishes the best from the nearly best solutions, but also distinguishes worthless from nearly worthless ones, and everywhere in between on the scale.
Finally, the evaluation (simulation in many cases) must be fast, yet accurate. In practice, this means that evaluation codes used by actual design engineers are useless. The engineer will be using the code on considerably fewer candidate designs, so it can be (and always is) much slower; and the engineer won't apply the code to ridiculous structures and expect it to tell him that they are ridiculous. The GA will apply the evaluation code to anything and everything. The commonsense limits on what the code has to handle don't apply.
The specific algorithm used to manage the population and pick individuals to breed doesn't seem to matter as much. Funes and Pollack pick a method, a steady-state population with probabilistic replacement based on fitness, that is also a favorite of mine because of its simplicity. They give good explanations of their representation and simulation method. This is a fun paper and worth reading. (You can see the abstracts, and download full papers, from http://www.demo.cs.brandeis.edu/papers/long.html . NB -- the Lego paper is nearly 5 megabytes, as it is well supplied with figures.)
For those who want to get into the field in great detail, there is Genetic Programming III by Koza et al (not to mention Genetic Programming, and Genetic Programming II, and Genetic Programming: the Movie, all by Koza). Koza is known as the originator of the subfield of genetic algorithms in which the structures bred are small snippets of LISP code, and the first to show in a systematic way that genetic search can produce useful programs that way. (He is also known for producing epic tomes -- GP III is 1154 pages long.)
GP III is of interest to those of us in automated design because it has a substantial section on the design of analog circuits, and a good introduction to evolvable hardware. Analog circuit design (amplifiers, bandpass filters, and the like) is something of a black art, and the ability of GA's to do it is quite impressive. Again, the representation is the crucial element. Rather than represent the circuit as a graph of components the way one might expect, Koza evolves programs that construct circuits. This leads to a much more connected search space of circuits that have any function at all, and appears to make the overall circuit evolution task feasible.
"Evolvable hardware" in this context refers to the use of a rapidly reprogrammable gate array in the genetic algorithm. The case in point is the design of a sorting network. A sorting network is a parallel sorting machine built of compare/exchange units. (See, e.g., Knuth vol. 3. Sorting and Searching) In the genetic algorithm, the gate array is used to build the sorting network under consideration and test it on all possible input sequences consisting of 1's and 0's. (There is a proof that a network that sorts all such sequences will sort any sequence.) Doing this in hardware makes the exhaustive testing feasible.
My take on the current research is that it has shown that fully automated design, by GA's or other search-and-simulate methods, is clearly feasible for some kinds of systems with at most a few tens of parts. However, to be feasible for complex systems, some significant breakthroughs are needed. One promising avenue of research, which I am looking into, is the use of abstraction in system specification. Abstraction is clearly used by human designers, but simulating abstract designs, and integrating designs that are specified at a number of different levels of abstraction, is an open problem, and likely to remain so for some time to come.
Proceedings of the First NASA/DOD Workshop on Evolvable Hardware. A. Stoica, D. Keymeulen, J. Lohn, eds. Los Alamitos, Calif.: IEEE Computer Society (1999).
Web sites offering additional information about evolvable and evolutionary hardware:
John Koza's Genetic Programming Web site.
Tetsuya Higuchi's Evolvable Systems Laboratory at the Electrotechnical Laboratory.
Evolutionary Electronics Web page at the University of Sussex in Brighton, England.
J. Storrs Hall is an IMM Research Fellow
Foresight Credits and Kudos
Special thanks this quarter go to the 1999 Feynman Prize judges, all former winners of the prize themselves: Reza Ghadiri (Scripps), James Gimzewski (IBM Zurich), Ralph Merkle (Xerox PARC and Institute for Molecular Manufacturing), Charles Musgrave (Stanford), Nadrian Seeman (NYU), and Deepak Srivastava (MRJ/NASA Ames).
Thanks go to departing Office Manager Harriet Hillyer, for all her work, but no thanks go to her church, which stole her away from us to be their office manager. Seriously: best wishes to Harriet on her new adventure.
Major thanks also to IMM's CFO Paul Melnyk, who is handling the agonizing process of getting Foresight a new lease for our office in the highly competitive Silicon Valley real estate market.
For commissioning a poster on the Foresight Group Genius event, thanks to Christopher Allen of Alacrity Ventures. Attendees will get one automatically, and we'll have extras for sale: see the website.
For work on the Fall Gathering, many volunteers deserve thanks, including Chris Hibbert and Ken Kittlitz for work on the Idea Futures process, and Sunah Cherwin for emceeing the Open Mike session. Thanks also to Pierluigi Zappacosta and Enrica D'Ettorre for hosting our fall fundraiser reception dinner, and as always to Mark and Judy Muhlestein for doing the food at these events.
Thanks to Max More and Natasha Vita-More for inviting Foresight to present at the EXTRO 4 Life Extension Conference in Berkeley‹an excellent meeting (see article in this issue).
For sending information, thanks go to‹among others‹John Burke, John Faith, Dave Forrest, Hilary Fylstra, Dave Krieger, Tom Mazanec, John Murrell, Richard Nesbit, Chris Phoenix, Mark Poole, Gerald Portis, Richard Terra, Tihamer Toth-Fejel, Russell Whitaker.
Executive Director, Foresight Institute
K. Eric Drexler and Chris Peterson
From Foresight Update 38, originally
published 30 September 1999.