Thursday, August 03, 2006

Automated design

Design is a search problem. A product or machine has some kind of specification or instructions, and you want to find the best possible specification to suit some purpose. The space of all possible specifications is usually too large to be searched exhaustively. The usual response to this is to exercise human cleverness - what the inventor in the garage does. An alternative is to search the design space using computer algorithms.Why would you do that? Isn't it fun to invent stuff? It is, but the stuff we invent these days is getting so complicated that sometimes human cleverness might not suffice to solve a design challenge. Nanotech stuff will be orders of magnitude more complicated than anything we can make today. So it's good to take a look at this approach.

Automated design is the application of global optimization to design problems using techniques like simulated annealing, genetic algorithms, and ant colony optimization to generate candidate problem solutions, and computer simulations to evaluate the fitness of the candidates. Genetic algorithms are the most widely known of these techniques. Here is a discussion of GAs by John Holland, one of the early pioneers in the field.

There has been a lot of research and development applying GAs to
engines and other machinery.Here are two applications of GAs to optimize the design of diesel engines. Somebody else optimized a valvetrain., and somebody else, an exhaust manifold. There is also work on a flywheel made of composite materials, and some work on reducing engine emissions by optimizing the chemical reaction rate of the fuel. In a more nanotech-ish vein, there is some work on the molecular design of novel fibers and polymers.

One of the more interesting efforts in this field is John Koza's invention machine, which applies GAs to a very wide variety of design problems, and which has produced a number of new patents for designs that did not originate in human imaginations.

NASA used genetic algorithms to design microwave antennas for the ST5 mission to measure the Earth's magnetosphere. There is some discussion of this work on Wikipedia.

While genetic algorithms are the most widely known of this class of algorithms, simulated annealing has a decades-long history of success in the placing and routing of FPGAs and custom integrated circuits. Other applications for global optimization include scheduling and resource allocation.

Random links