"Morphing" in evolutionary synthesis of electronic circuits

NASA Tech Briefs, Aug 2002

The search for viable circuits can be conducted more efficiently and thus faster. NASA's jet Propulsion Laboratory, Pasadena, California

A method of automated evolutionary synthesis of electronic circuits has been augmented by a concept called "morphing through fuzzy topologies." Previous versions of the method provided for the evaluation of "crisp" topologies were precisely specified by open/closed (on/off) interconnection switches. The present, augmented version provides for evaluation of topologies specified by switches that support partial degrees of opening. These "fuzzy" topologies with partly open, partly closed switches have behaviors very similar to those obtained by a combination of "crisp" topologies. It is almost as if several "crisp" topologies are superimposed on each other, and are evaluated simultaneously when the fuzzy topology is evaluated. Like the previous versions, the present version is expected to enable the synthesis of a variety of digital and analog circuits with desired functional responses.

Previous, discrete-topology versions of the method were described in "Reconfigurable Arrays of Transistors for Evolvable Hardware" (NPO-20078), NASA Tech Briefs, Vol. 25, No. 2 (February 2001), page 36; and "Evolutionary Automated Synthesis of Electronic Circuits" (NPO-- 20535), NASA Tech Briefs, Vol. 26, No. 7 (July 2002), page 33. To recapitulate: "Evolution" is used here in a quasi-genetic sense, signifying the construction and testing of a sequence of populations of circuits that function as incrementally better solutions of a given design problem. The circuits are implemented either in software simulations or in hardware. Evolution in hardware involves the use of electronically reconfigurable arrays of transistors as analog switches for the selective, repetitive connection and disconnection of transistors and other circuit building blocks. The evolution is guided by a search-and-optimization algorithm (in particular, a genetic algorithm). At each step of the evolutionary process, the circuits are ranked according to how close their behaviors come to the desired behavior. A new population of circuits is generated from a selected pool of best circuits in the previous generation, subject to such genetic operators as chromosome crossover and mutation. The process is repeated for many generations, yielding progressively better circuits. The criterion for stopping the evolution can be the reduction of error below a certain threshold or reaching a predetermined number of generations.

The present, augmented method applies primarily to evolution in hardware and secondarily to software simulations in which highly accurate mathematical models of circuits are used. The hardware implementation would involve the use of field programmable transistor arrays (FPTAs), which contain T-gate transistors as analog switches. These switches differ from the switches of the discrete-topology version of the method in that instead of being limited to "on" or "off" states, their resistances would be continuously variable between low values (tens to hundreds of ohms, in the "on" state) and high values hundreds of MQ in the "off' state).

By virtue of the intermediate values of the switch resistances, the response of a given circuit topology is almost as if one would combine the responses of several circuit topologies specified by on/off switches. The superposition of circuit topologies would be characterized as "fuzzy" because it would blur the borders among distinctive circuit topologies: the resulting circuits would belong, only to certain degrees, to discrete topologies, in each of which any two given components are either connected or not. In effect, a fuzzy topology would contain many "seeding" topologies with superimposed effects. The role of evolution would be, in part, to isolate the most promising one of the seeding topologies present. In still other words, evaluation of a fuzzy topology would be somehow equivalent to simultaneous concurrent evaluation of several superimposed circuit configurations.

The genetic algorithm would specify whether each switch would be in a low-- or high-resistance state, but in a process somewhat reminiscent of annealing, the numerical meanings of "low" and "high" would change gradually as a function of a temperature-like parameter. Initially the temperature-like parameter would be high, causing the "low" and "high" switch status to have values close to each other. Gradually (typically over ==100 generations to ensure quasi-static response), the temperature-like parameter would be made to decrease, causing the switch resistances to become polarized to their extreme high ("off") and low ("on) values. This annealing-like process would induce modifications of the circuit to be evolved. The evolutionary effect of this annealing-like process is what is meant by "morphing through fuzzy topologies."

Tests both in simulations and in hardware by computational simulation have led to the preliminary conclusion that in comparison with a discrete-topology version of the method implemented with binary switches, morphing through fuzzy topologies is about an order of magnitude more efficient as a means of searching for a desired circuit topology. Promising individuals (with higher fitness) have been found much earlier in the search.