WO2000057550A2 - System, method and computer program product for automated circuit design using linear genetic algorithms - Google Patents

Abstract

A system, method and computer program product for designing analog circuits using a linear genome representation and unfolding technique. A finite set of component-placing instructions (602) is defined, which is capable of placing components in a circuit between an input node and an output node. Each instruction has an opcode specifying the connectivity of an associated component and a component value. A plurality of circuit graphs is generated, and each graph comprises a plurality of the instructions selected by mapping opcode and component values to linear genome segments. The graphs are converted to netlists (606) that are tested in a circuit simulation computer program to isolate one or more evolved circuits that best approximates a fitness function.

Description

System, Method and Computer Program Product for Automated Circuit Design Using Linear Genetic Algorithms

Background of the Invention

Statement as to Rights to Inventions Made under Federally-Sponsored Research and Development

Part of the work performed during development of this invention utilized U.S. Government funds. The U.S. Government has certain rights in this invention.

Field of the Invention

The field of the present invention relates generally to analog circuit design, and more particularly, to a system and method for automated circuit design using linear genetic algorithms.

Related Art

Analog circuits are of great importance in electronic system design since the world is fundamentally analog in nature. While the amount of digital design activity far outpaces that of analog design, most digital systems require analog modules for interfacing to the external world. It was recently estimated that approximately 60% of CMOS-based application-specific integrated circuit (ASIC) designs incorporated analog circuits (Gielen, G., et al., Symbolic Analysis for Automated Design of Analog Integrated Circuits, Kluwer, Boston, MA (1991)). With challenging analog circuit design problems and fewer analog design engineers, there are economic reasons for automating the analog design process, especially time-to-market considerations.

Techniques for analog circuit design automation began appearing about two decades ago. These methods incorporated heuristics, knowledge-based, and simulated annealing. (See Sussman. GJ., et al, "Heuristic Techniques in

Computer-Aided Circuit Analysis," IEEE Trans. Circuits and Systems, vol. 22 ( 1975); Harjani, R., et al. , "A Prototype Framework for Knowledge-Based Analog Circuit Synthesis," in Proc. 24th Design Automation Conf (1987); and Ochotta, E.S., et al, IEEE Trans. Computer-Aided Design 15:213-294 (1996).)

Efforts using techniques from evolutionary computation have appeared over the last few years. These include the use of genetic algorithms (GAs) to select filter component sizes to select filter topologies, and to design operational amplifiers using a small set of topologies. (See Holland, J.H., Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, MI ( 1975); Horrocks, D.H., et al., "Genetically Derived Filters using Preferred Value Components ' in Proc. IEE Colloq. on Linear Analogue Circuits and Systems,

Oxford, UK (1994); Grimbleby, J.B., "Automatic Analogue Network Synthesis using Genetic Algorithms/' in Proc. First Int. Conf. Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA) (1995), pp. 53- 58); and Kruiskamp, M. W ^'., Analog Design Automation using Genetic Algorithms and Polytopes, Ph.D. Thesis, Dept. of Elect. Engr., Eindhoven University of

Technology, Eindhoven, The Netherlands (1996).)

The research of Koza and collaborators on analog circuit synthesis by means of genetic programming (GP) is likely the most successful evolutionary computation-based approach to date. (See Koza, J.R., et al., "Automated Synthesis of Analog Electrical Circuits by Means of Genetic Programming, '7EEE

Trans, on Evolutionary Computation 7(2): 109- 128 (1997); and Koza, J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA (1992)). Unlike previous systems, the component values, number of components, and the circuit topologies are evolved by Koza's technique. The genetic programming system begins with minimal knowledge of analog circuit design and generates circuits using a cellular encoding technique and circuit-constructing program trees. (See Gruau, F., "Artificial Cellular Development in Optimization and Compilation," in Toward Evolvable Hardware (Lecture Notes in Computer Science), Ε. Sanchez & M. Tomassini, eds., vol. 1062. Springer-Verlag, Berlin (1996), pp. 48-75.) Various analog filter design problems have been solved using genetic programming (e.g., Koza, J.R., et al, "Use of Architecture- Altering Operations to Dynamically Adapt a Three- Way Analog Source Identification Circuit to Accommodate a New Source ' in Genetic Programming 1997 Conference, Koza, J.R., et al, eds., Morgan Kaufmann (1997), pp. 213-221), and an overview of these techniques, including eight analog circuit synthesis problems is found in Koza, J.R., et al, IEEE Trans, on Evolutionary Computation 7(2):109-128 ( 1997). A comparison of genetic-based techniques applied to filter design appears inZebulum, R.W., etal. "Comparison of Different Evolutionary Methodologies Applied to Electronic Filter Design," 1998 IEEE Int. Conf. on Evolutionary

Computation, IEEE Press, Piscataway, NJ (1998), pp. 434-439. Work on evolving CMOS transistors for function approximation can be found in Stoica, A., "On Hardware Evolvability and Levels of Granularity," Proc. 1997 Int. Conf. Intell Systems and Semiotics (1997), pp. 244-247. The evolutionary computation-based approaches mentioned above are all offline hardware evolution approaches — software simulators are used to evolve software models of hardware. It should be noted that a growing number of researchers are using real hardware to evaluate a circuit's fitness during evolutionary search — the online approach. For example, a system that employs a software-reconfigurable analog circuit to control frequency filtering in cellular phones is reported. (See Murakawa, M., et al, "Analogue EHW Chip for Intermediate Frequency Filters," Proc. of the Second Int 7. Conf. on Evolvable Systems: From Biology to Hardware, Springer- Verlag, Berlin, 1998, pp. 134- 143.) They demonstrate how genetic algorithms are used to shrink circuit sizes and improve manufacturing yield. Another study that uses online evolution investigated the use of evolutionary search to make a field-programmable gate array (FPGA) function like an oscillator. (See Huelsbergen. L., et al, "Evolution of Astable Multivibrators in Silico," Proc. of the Second Int 7 Conf. on Evolvable Systems: From Biology to Hardware, Springer- Verlag, Berlin, 1998. pp. 66-77.) Oscillators are difficult to design using only digital logic gates, so in practice they are made using more expensive analog components. Since FPGAs are digital, the design task is challenging.

What is needed is a more robust automated technique capable of generating more sophisticated circuits having a greater number of components and component values.

Summary of the Invention

The present invention is directed to a linear representation and unfolding technique, coupled with modest computer resources, for evolving analog electronic circuitry, for example, analog filters and transistor-based amplifiers. The system, method or computer program product use a defined, finite set of component-placing instructions capable of placing components in a circuit between an input node and an output node. Each instruction has an opcode specifying the connectivity of an associated component and a component value. A plurality of circuit graphs is generated, and each graph comprises a plurality of the instructions selected by mapping opcode and component values to linear genome segments. The graphs are converted to netlists that are tested in a circuit simulation computer program to isolate one or more evolved circuits that best approximates a fitness function.

The invention has the desirable property that all sets of circuit-constructing primitives result in a very high percentage of valid circuit graphs. Thus application of genetic operators will result in valid circuit graphs, while allowing circuit size (number of devices), circuit topology, and device values to be evolved. The present invention is capable of generating a rich set of circuit topologies including many of the useful topologies seen in hand-designed circuits. The present invention minimizes the amount of computer processing and hence run time of the system. Since virtually all of the graph structures generated are valid circuits, the system does not need to perform functions such as the pruning of unconnected circuit branches. The present invention differs from the previously mentioned GA techniques in that the present inventions allow both topology and component sizes to be evolved. In Zebulum, R.W., et al, "Comparison of Different Evolutionary Methodologies Applied to Electronic Filter Design," (1998 IEEE Int. Conf. on Evolutionary Computation, IEEE Press, Piscataway, NJ (1998), pp. 434-439), a

GA approach is presented in which topologies and component values are evolved. However, that system allowed only a small number of components (15 components maximum). The present invention is further distinguished from Zebulum et al. because it employs a linear genetic algorithm. Because the genome resembles a computer program, and because our GA acts upon dynamically-sized representations, it has some elements in common with genetic programming. The genomes in the present invention are fixed to hold a maximum of 150 circuit components, a limit arrived at by surveying the circuit design literature for the various design tasks of interested. Of course, this upper limit can be extended as computations resources are added. Using a cluster of six engineering workstations such as Sun Ultra workstations, manufactured by Sun Microsystems, Palo Alto, California, the inventors have evolved circuit solutions to several circuit designs.

Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with reference to the accompanying figures.

Brief Description of the Figures

The present invention is described with reference to the accompanying figures. In the figures, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. FIGs. 1A, IB and 1C illustrate the effect of the move-to-new, cast-to- previous and cast-to-ground instructions in accordance with the present invention.

FIG.2 illustrates a template circuit: the evolved circuit is located between fixed input and output terminals in accordance with the present invention (v_v is an ideal voltage source, R. is the source resistance, R, is the load resistance in accordance with the present invention).

FIGs.3 A and 3B illustrate default bipolar junction transistor symbols: (a) npn; (b) pnp.

FIGs. 4A and 4B illustrate the labeling of transistor terminals: (a) devices with two terminals have incoming and outgoing terminals; (b) devices with three terminals are treated as two terminal devices by having a fixed connection at the third terminal in accordance with the present invention.

FIG.5 illustrates transistor configurations showing the outgoing and fixed connections when the incoming terminal is the transistor's base terminal in accordance with the present invention.

FIG. 6 illustrates an overview of the circuit evaluation process starting with circuit constructing instructions and ending with the calculation of fitness in accordance with the present invention.

FIG. 7 illustrates the parallelization of a circuit generation technique in accordance with the present invention.

FIG.8 illustrates common low-pass filter terminology and specification in accordance with the present invention. FIG. 9 illustrates gain on a logarithmic amplitude scale for a third-order Butterworth filter in accordance with the present invention.

FIG. 10A illustrates an evolved low-pass filter for use in an electronic stethoscope in accordance with the present invention (units are ohms and farads).

FIG.1 OB illustrates nearly identical frequency response curves for evolved and actual electronic stethoscope circuit in accordance with the present invention (the frequency axis is scaled logarithmically).

FIG. 11 A illustrates an evolved 3rd-order Butterworth low-pass filter in accordance with the present invention (units are ohms, farads, and henries.)

FIG. 1 IB illustrates a frequency response curve for evolved 3rd-order

Butterworth low-pass filter of FIG 11 A in accordance with the present invention (attenuation specifications are also shown; the frequency axis is scaled logarithmically).

FIG. 12A illustrates an evolved circuit satisfying target specifications for filter number three in accordance with the present invention.

FIG. 12B illustrates a frequency response for filter number three of FIG. 12A in accordance with the present invention.

FIG. 13 illustrates an ideal inverting amplifier showing how gain is set by the ratio of the feedback to source resistor.

FIG. 14 illustrates a circuit schematic of an evolved 75 dB amplifier in accordance with the present invention. FIGs. 15A, 15B and 15C illustrate a small signal behavior of 75 dB evolved amplifier in accordance with the present invention: 15 A is a time domain input waveform at 1 kHz; 15B is the waveform of 15 A inverted and amplified; and 15C is a frequency response showing 3 dB bandwidth of 7.59 kHz.

FIG. 16 illustrates the DC transfer characteristic of the 75 dB amplifier in accordance with FIGs. 15A-C.

FIG. 17 illustrates a circuit schematic of an evolved 85 dB amplifier in accordance with the present invention.

FIGs. 18A. 18B and 18C illustrate a small signal behavior of the 85 dB evolved amplifier of FIG. 17 in accordance with the present invention: 18A is the time domain input waveform at 1 kHz; 18B is the waveform of 18A inverted and amplified; and 18C is a frequency response showing a flatband gain of 85.46 dB.

FIG. 19 illustrates the DC Transfer characteristic of the 85 dB amplifier of FIG 17.

FIG. 20 is a block diagram of an exemplary computer system useful for implementing the present invention.

Detailed Description of the Preferred Embodiments

The present invention relates to a system, method, and computer program product for automated circuit design using linear genetic algorithms. The present invention is described in terms of various examples. This is for convenience only and is not intended to limit the application of the present invention. In fact, after reading the following description, it will be apparent to one skilled in the relevant art how to implement the following invention in alternative embodiments.

Furthermore, after reading the following description, it will be apparent to one skilled in the relevant art(s) that the automated circuit design system, method, and computer program product can be implemented by Sun® SPARC® workstations. Other such systems include, for example, Intel® processor-based, IBM compatible PCS, running the Windows 95/98™ or Windows NT™ operating systems, a Macintosh® computer running the Mac® OS operating system, or the like. In general, the present invention may be implemented within any processing device that executes software applications, including, but not limited to, a desktop computer, and the like.

The circuit representation technique is introduced and described in Section I. Section II presents the evolutionary computation, and in Section III experimental results are presented and analyzed. Section IV is a conclusion.

7. Genomic Representation of Circuits

In designing an effective circuit representation for use in evolutionary search, the following properties are among the most desirable. First, the representation should permit any circuit or at least a wide range of circuits to be represented. If it is known a priori that certain topologies are well-suited to a specific design task, topological restrictions inherent in the representation may be beneficial since the search space will be reduced. Conversely, not having this JO-

limitation may bring to light novel designs that human designers have never thought of.

Second, the genotype conversion algorithm (the circuit constructing process also called the genetic algorithm) should run as fast as possible. Clearly if numerous traversals of the circuit graph structure are required in order to guarantee a valid circuit graph, the performance hit will be commensurate. For an n-component circuit, a reasonable upper bound would be for the algorithm to scale proportionately to the number of circuit components.

Third, the representation should be syntactically closed so that genetic operators do not create invalid circuit graphs. Note that a graph could be a valid circuit graph, yet not make sense as an electrical circuit (for example, dissimilar voltage sources connected in parallel) from those that are valid. The circuit representations presented herein were designed to have these properties.

Circuit designs are constructed by an automaton that is programmed via a set of low-level instructions. The automaton is called a circuit-constructing robot or cc-bot. The language that programs the cc-bot is small and, in a preferred embodiment of the present invention, contains only component-placing instructions (e.g., control instructions are not included, but could be impletented in an alternative embodiment). The cc-bot is an abstraction that provides a useful construct for visualizing how an evolved circuit is generated by a computers via execution of the cc-bot instructions. The set of cc-bot instructions has the desirable property that virtually all possible sequences of instructions result in a valid electrical circuit. This property is important because it greatly limits the out-of-bounds regions of the search space containing invalid circuit graphs.

Thus, an evolutionary search will spend nearly all its time generating valid circuit graphs. While this is a beneficial, non-trivial achievement, the ability to generate every possible circuit topology is lost. This is not considered a drawback for the circuit types investigated by the inventors since a vast number of topologies and existing circuit designs can be encoded using the cc-bot approach of the present invention.

Each cc-bot instruction places a circuit component and directs the movement of the cc-bot. The five basic cc-bot instruction types are: x-move-to- new, x-cast-to-previous, x-cast-to-ground, -cast-to-input, x-cast-to-output, where x can be replaced by an electronic device, such as a R (resistor), C (capacitor), L (inductor), or transistor configuration. As would be apparent to a person skilled in the relevant art, other electrical/electronic component or devices can be represented using cc-bot instructions including diodes, thyristors, silicon- controlled rectifiers, voltage or current sources, or the like. In a circuit design task involving only inductors and capacitors (an LC circuit), ten opcodes would be available to construct circuits (five for capacitors and five for inductors).

The meanings of each cc-bot instruction are summarized in Table I. The "move-to-new" instruction places one end of a component at the active node and the other at a newly created node (the "active" node is the current location being processed by the hypothetical cc-bot). The newly created node then becomes the active node. The "cast-to" instructions place one end of the component at the active node and the other at either the ground, input, output, or previously-created node. After executing a cast-to instruction, the cc-bot remains at the active node. The input and output nodes are the overall input and output nodes of the circuit as opposed to the input and output of the placed component. Illustrations of three cc-bot instructions that place components are shown in FIGs. 1 A, IB and 1 C. In FIG. 1 A component xl is connected between active (i.e., current) node CNt and a new node CNt+1 via a move-to-new instruction. In FIG. IB component x2 is connected between two existing nodes and CN remains unchanged via a cast-to- previous instruction. And in FIG. 1 C componentxJ is connected between existing node CNand ground via a cast-to-ground instruction. The cast-to-input and cast- to-output instructions are very similar to the cast-to-ground instruction.

TABLE I

The circuit is constructed by the cc-bot inside of a template circuit. The design tasks presented here use a template having one input and one output terminal as shown in FIG. 2. An ideal voltage source v_s is connected to ground and to a source resistor R . The circuit's output voltage is taken across a load resistor R_f.

The genetic algorithm (GA) used in accordance with the present invention is used to generate variable-length lists of cc-bot instructions (components and component values by mapping bytecodes discussed below) so that the size of the circuit can be evolved. When the cc-bot reaches the last component to place in the circuit, the inventors have chosen to have the last active node connected to the output terminal by a wire (accomplished by connection of a 1 micro ohms (μΩ) resistor). By doing so. unconnected branches are eliminated.

As assembly language instructions are mapped to opcodes, cc-bot instructions are mapped to bytecodes of the GA. The linear GA can be analogized to a list of pseudo-random numbers that are used to select component/opcode and component values. This is accomplished by mapping opcode and component values to a linear genome segment.

In a preferred embodiment of the present invention, each cc-bot instruction is represented by up to four bytecodes of the GA. For cc-bot instructions that take a component value as an argument, the first byte is the component/opcode (e.g., a resister cast to ground), and the next three bytes represent the component value (e.g., the resistance value). For transistors, component values are not needed, because a set of default transistor characteristics is assumed. Using three bytes allows the component values to take on one of 256³ values, a sufficiently fine-grained resolution. The raw numerical value of these bytes is then scaled into a reasonable range, depending on the type of component. Resistor values can be scaled sigmoidally between 1 and 100K ohms using l/(l+exp(- 1.4(1 Ox- 8))) so that roughly 75% of the resistor can be biased to be less than 10K ohms. Capacitor values can be scaled between approximately 10 picofarads (pF) and 200 microfarads (μF) and inductors between roughly 0.1 millihertz (mH) and 1.5 hertz (H.) Transistors are current amplifying and switching devices that have three terminals. (Four if the substrate terminal is included, but connection of the substrate to ground is assumed and hence the fourth terminal is ignored.) The default are n-type and p-type bipolar junction transistors, as shown in FIG.3 A and FIG. 3B. Using devices with three terminals makes it harder to design a circuit representation that achieves the desired properties. If a cc-bot were to connect one terminal of a transistor at a node, then two active nodes would result each requiring its own cc-bot. This could happen repeatedly resulting in an exponential growth of cc-bots constructing the circuit in parallel. Two problems are obvious: how will the multiple constructing "threads" interconnect, and how will the dangling nodes that will likely appear at the end of the circuit constructing process be handled. To allow interconnections between constructing threads, one can introduce a spatial dimension and let the cc-bots form interconnections as they criss-cross each other's path. To handle the dangling node problem, one can deterministically tie dangling nodes to each other, to internal nodes, or to the output node for example. Another solution is to simply prune those nodes.

Although the inventors have considered these and other solutions, a simpler way of handling transistors is also a viable alternative: treating them as having only two terminals.

To work with transistors as devices with two terminals, the third terminal is hardwired (fixed) to one of the following pre-existing circuit nodes: ground, power supply (positive or negative), input, output, the previously placed node, or even to itself. Such a scheme allows a wide variety of configurations. To understand these configurations, the terminals are labeled in a generic way: incoming, outgoing, and fixed. These configurations are illustrated in FIG.4A and FIG.4B. The incoming terminal is the terminal that the cc-bot will connect to the active node. The outgoing terminal will become the new active node (for move-to instructions) or it will be cast to a pre-existing circuit node. The fixed terminal is hardwired as its name implies.

To give a sense of the types of transistor configurations possible, FIG. 5 illustrates 52 configurations for an npn transistor whose base terminal is designated incoming. Terminals labeled in upper case letters denote the fixed terminal connection. Only npn transistors are shown although analogous configurations are present for pnp transistors in accordance with the present invention. Each entry shows the connections that the cc-bot makes when executing the instruction listed in the first column. The last two columns show self-connections, some of which are frequently used by circuit designers. In the last two columns the fixed connection is a self-connection. "PS" denotes the power supply (only the positive version is shown), and "N.A." denotes "not applicable". Similar charts can be produced for npn transistors having the collector and emitter serve as the incoming terminal, as well as the three analogous charts for pnp transistors. There are configuration redundancies so that each chart will not have exactly 52 configurations. In addition, emitter-collector self- connections are not shown since this shorts out the transistor.

The cc-bot approach to representing circuits embodies the desirable properties outlined above. The encoding has syntactic closure since any combination of instructions produces a valid circuit graph, and since every instruction contained in the genome results in a circuit component, there are no non-coding genome segments. The circuit construction process is time- proportionate to the number of circuit components since it does not require any repair (e.g., removal of unconnected nodes) operations. Lastly, the cc-bot approach can generate a wide range of circuit graph topologies. The topological restriction is as follows: circuit branches off of the main constructing thread cannot, in general, contain more than one node (there are some exceptions to this). The constructing thread is the sequence of components that are created by the move-to-new instructions. The constructing thread itself can be of varying lengths and can contain both series and parallel configurations. In spite of these limitations, the system according to the present invention allows creation of circuits with a large variety of topologies, including numerous topologies seen in hand-designed circuits.

II. Evolutionary Search

The evolutionary search employed by the present invention is based on a genetic algorithm (GA). The GA of the present invention has some elements in common with genetic programming since the genomes of the invention resemble computer programs and acts upon dynamically-sized representations. The GA operates on a population of dynamically-sized bytecoded arrays.

In addition to being a sequential list of instructions, the representation used can increase or decrease in size, as opposed to being of a fixed size. The "size" of a circuit is simply the number of components contained in the circuit. For example, a circuit having five resistors and two capacitors has a size of seven. This allows the representation to represent circuits of any size up to a pre- specified maximum size. Since computers have finite memory storage, a maximum size is enforced so that a circuit that would consume all of the computer's memory is prevented from being represented. This maximum circuit size, or MCS, can be set to whatever value is appropriate for the computer on which the algorithm will execute upon.

Providing for dynamic sizing means that the artificial evolution process is able to manipulate the size of a circuit in addition to the connections, component types, and component values. If more components are needed to achieve a desired electronic function, the evolutionary algorithm can increase the size of the circuit. If fewer components are needed, components can be pruned away.

Dynamic sizing is implemented by interpreting the first value in the instruction list as the number of components. This first value in the instruction list is called the circuit size value, or CSV. As an example, if the CSV equaled eight, then the subsequent eight instructions would specify the circuit completely. Since each instruction places exactly one electronic component, the resulting circuit would have eight components. Since the instruction list is initially composed of random values, the CSV could be greater than the maximum size allowed. To solve this problem, the arithmetic modulus function is used to constrain this value to within the maximum number of components allowed as follows: CSV = CSV modulo MCS. During the application of the genetic operators of selection and mutation, the CSV is treated as read-only, i.e., it is not modified. During the genetic operation of crossover, the CSV is updated, if necessary, to reflect the number of components in the resulting instruction list.

In practice a maximum size of about 400 bytes (100-150 circuit components; i.e., one byte to select as instructions opcode and additional bytes to select the opcode's component value) is imposed in order to accommodate population sizes of up to about 18,000 individuals. The crossover rate in a preferred embodiment is set at 0.8 (but can range between 0 and 1 ) and mutation

(per locus) rates set to between about 0.05-0J0. Each crossover is single-point with each parent having a separately chosen crossover point. Crossover points are randomly selected and are constrained to lie on component boundaries to yield circuits having at least ten components and at most about 150 components. Various other acceptable settings parameters and component limits would be apparent to a person skilled in the art without departing from the scope of the present invention.

An overview of the evolution process is depicted in FIG. 6. As in the GP system disclosed in Koza. supra, (IEEE Trans, on Evolutionary Computation 1 (2): 109-128 ( 1997)), the present invention employs the public-domain Berkeley SPICE (Simulation Program with Integrated Circuit Emphasis) circuit simulation program to simulate generated circuits. The array of bytecodes 602 are interpreted (by decoding as shown at 604) in the manner described in the previous section, and results in a SPICE netlist 606 representation. The netlist is processed by SPICE at 608 and the output from SPICE is then used to compute fitness (at

610) for each individually generated circuit. Other circuit simulators are envisioned. In a preferred embodiment, the fitness of a circuit is its ideal or "target "output, measured by voltage, current and or reactance, for example. Other circuit fitness metrics would be apparent to one skilled in the relevant art. Since most of the processing time is spent simulating circuit designs, which are independent of one and other, parallelizing the system is greatly beneficial. The parallel genetic algorithm implemented uses master/slave style parallelism over a network of UNIX-based workstations. (See Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison- Wesley, Reading, MA (1989).)

An exemplary master/slave circuit generation system is illustrated in FIG. 7. A controlling host computer performs GA operators and distributes a population of bytecoded-individuals (i.e.. individual evolved circuits) to specified number of worker nodes using socket connections. The worker nodes decode the individuals into SPICE netlists, which are then fed into SPICE via FIFO pipes to minimize disk activity. Fitness is calculated using SPICE's output, and then sent back to the host. Hundreds of individuals (and fitness scores) are packaged into a single message so that external network congestion delays are minimized. Written in the C programming language, the system currently runs on Sun workstations and a variety of other UNIX systems (e.g. SGI workstations, Silicon

Graphics, Mountain View, California, or PCs running Linux, a widely available public-domain computer operating system, giving us the ability to mix various workstations in a single workstation cluster. Running circuit simulations in parallel greatly reduces runtime since nearly all of the processing time is spent simulating circuits in accordance with the present invention. The resulting system performance is sufficient to generate the circuits presented below in a few hours of runtime using clusters of three to twelve workstations. Circuit simulation throughput is a key performance metric, and typical throughputs ranged between 100-150 circuits per cpu second (a "central processing unit" second refers to cpu time only and disregards operating system time). For example, in one of the amplifier design task runs described in the next section, each of three processing nodes was able to simulate 142 circuits per cpu second, giving an aggregate processing rate of 426 circuits per cpu second.

///. Experiments and Results

The goal of the experiments was to automatically design analog filters and transistor-based amplifiers using a genetic algorithm evolutionary search. The choice of using passive analog filters was inspired by the previous studies and is a good choice for testing the effectiveness of the present system for three reasons. First, all components have two-terminals, which is suited for the cc-bot technique. If the proposed system could not evolve useful circuits using devices with two terminals, then attempting to evolve circuits using more complex components (e.g., transistors) would likely prove ineffective. Second, there are no energy sources required within the circuit that further reduces the complexity. Lastly, filter design is a well-understood discipline within circuit design. Its "design space" has been greatly explored, which allows a comparison of evolved designs to well-known designs. (See Huelsman, L.P., Active and Passive Analog Filter Design, McGraw-Hill, New York, NY (1993).) Amplifiers are very common in analog circuit design and are a good choice for experiments for many of the same reasons that filters are. Transistors are used in the amplifier design experiments since the vast majority of such designs today are transistor-based. All of the evolved designs presented below meet the target specifications. For filters, that meant satisfying four parameters. For the amplifier circuits, gain target was a range of values: from 70 dB to the maximum gain attainable for the circuit. Each evolved circuit was hand-probed using simulation software to verify that internal currents and voltages remained at realistic values. This step suggests that these circuits can be physically implemented.

A low-pass filter is a circuit the allows low frequencies to pass through it, but stops high frequencies from doing so. In other words, it is frequency selective in that it "filters out" frequencies above a specified frequency. The unshaded area in FIG. 8 depicts the region of operation for low-pass filters. Below the frequency f_p the input signal is passed to the output, potentially reduced (attenuated) by K_p decibels (dB). This region is known as the passband. Above the frequency , in the region is called the stopband, the input signal is markedly decreased by K_s decibels. Between the passband and stopband the frequency response curve transitions from low to high attenuation. The parameter located in this region,/, is known as the cutoff frequency.

One of the design tasks concerned designing a circuit within the class of Butterworth filters. Butterworth filters are very common and circuits that implement them are readily found in filter design tables. (See Huelsman, L.P., Active and Passive Analog Filter Design, McGraw-Hill, New York, NY (1993).) The attenuation (negative gain) of Butterworth filters is of the form •Jl / (l - (/7/_c)^2Λ ) where /is the input frequency and N is the order of the filter. The higher order a filter has, the sharper the "knee" of its gain curve, and the more complex the circuit. A plot of the attenuation for a third-order Butterworth filter is shown in FIG. 9.

Amplifier circuits generate an output signal that consists of the input signal multiplied by a gain factor, A. Voltage gain is denoted Av and is equivalent to _ui_{p n vv} ft ^is common to express gain values in decibels (dB) using 20 log(A), where the logarithm is base 10. Amplifiers can be either inverting or non- inverting, where an inverted output signal has a 180 degree phase shift compared to the input. The dc gain of an amplifier refers to the gain when only constant voltage/current sources are applied. The ac or small-signal gain is the gain of an ac input signal irrespective of any dc components in the output signal. A dc component that shifts the entire ac signal up or down is called the dc bias of the circuit. For simple amplifiers, like filters, there are published volumes available that catalog many designs. Since there are numerous parameters in amplifier design (input/output impedance, power dissipation, distortion, common-mode rejection, power supply rejection to name a few), the design task can become quite challenging and may require an experienced designer. For the amplifier design experiments below, the inventors took into account only dc and ac gain, dc bias, and linearity, although future developed experiments would be apparent to a person skilled in the art.

A. Filter Design Tasks

Three filter design experiments were performed. In each experiment, 10 runs were performed and the best circuit found across all runs are presented below. The experiments increased in difficulty so that filter 3 represents a challenging design task, while filter 1 is least challenging. Table II lists the target specifications for each of the experiments.

TABLE II

The genetic algorithm parameters remained the same within a given experiment, but changed according to the design task to allow for more evaluations (the total number evaluations is the product of population size and the number of generations). Filter 1 runs had 30.000 evaluations, filter 2 had 3.6 million, and filter 3 had 1 million. For the filter experiments, fitness was calculated to promote the regression of the evolved circuit's frequency response toward that of the target. Error values were computed as the absolute value of the difference of the individual's output and the target output. These error values were summed across evaluation points to arrive at a fitness value.

A.I Electronic Stethoscope Circuit

The first filter design task was set up to generate a filter suitable for use in an electronic stethoscope. In this application, it is desired to filter out the extraneous high-frequency sounds picked up by a microphone that make it difficult to listen to (low-frequency) bodily sounds (e.g., a heart beating). As such, the frequency response specifications do not need to be extremely accurate since the human ear cannot discern frequencies that are close together. The target frequency response data was taken from an actual electronic stethoscope, which was built with a cutoff frequency of 796 Hz corresponding to an output voltage of approximately 1 volt. This circuit is relatively easy to design and so we chose it as our first design task. The cc-bot instruction set consisted often instructions, five for resistors and five for capacitors, which allowed for the construction of an RC low-pass filter. The evolved circuit is shown in FIG. 10A and its frequency response, which matches almost exactly the target is shown in FIG. 10B. It was found in generation 3 of a 10-generation run that had a population size of 3000.

The circuit exhibits the standard design for simple low-pass filters: a resistor (R₂) in series with the source to form a voltage divider at low frequencies (C, open), and a capacitor (C,) across the output to block high frequencies.

A.2 Butterworth Low-pass Filter

The second low-pass filter design task had specifications that were more difficult to achieve than the first filter: both the passband and stopband were longer thus requiring the transition to be sharper. The inventors chose a circuit that can be built using a 3rd-order Butterworth filter and having a frequency response of the form, as seen in FIG. 9. The specifications are listed under filter number two in Table II. Such a filter design can be derived using a ladder topology containing two capacitors and one inductor and component values found in published tables. Because it was desired to design an LC low-pass filter, the cc-bot instruction set consisted of only capacitor and inductor instructions. The evolved circuit that meets these specifications is shown in FIG. 11A and its frequency response is shown in FIG. 11 B. It was found in generation 22 of a run that had a population size of 18,000.

A.3 Third Low-pass Filter

The third low-pass filter design task had specifications that were the most stringent: in addition to the passband and stopband being increased, the attenuation parameters were tightened (see Table II). These specifications are similar to the fifth-order elliptic filter described in Koza, supra, (IEEE Trans, on Evolutionary Computation 7(2): 109-128 (1997)). In that work, the evolved LC circuit satisfies K = 0J dB and K_s = 60 dB. Another evolved low-pass filter circuit (Zebulum, R.W., et al, "Comparison of Different Evolutionary Methodologies Applied to Electronic Filter Design," in 1998 IEEE Int. Conf. on

Evolutionary Computation, IEEE Press, Piscataway, NJ ( 1998), pp.434-439) had the same stopband and passband frequencies, but less demanding attenuation specifications (K_p = 1 :6 dB and K_x = 24:8 dB). The circuit evolved according to the present invention is shown in FIG. 12A and its frequency response is seen in FIG. 12B. Micro-ohm resistors were added as a convergence aid for the circuit simulator, and can be ignored for analytical purposes. The cc-bot instruction sequence and SPICE netlist for this circuit are listed in Tables III and IV, respectively. - J-

Instruction Sequence to generate Evolved Filter Number Three

C_MOVE_TO_NE C 1 2 10837006 C_MOVE_TO_NE C 2 3 3547581 C_CAST_TO_PREV C 3 2 9862769 L_CAST_TO_PREV L 3 2 6880711 L_CAST_TO_INPUT L 1 3 7668359 R_CAST_TO_PREV R 3 2 10844497 L_CAST_TO_INPUT L 1 3 6794434 L_CAST_TO_INPUT L 1 3 10915194 _CAST_TO_INPUT L 1 3 10360067 L_CAST_TO_PREV L 3 2 53267 L_MOVE_TO_NE L 3 4 7713100

C_MOVE_TO_NE C 4 5 3568044 C_MOVE_TO_NEW C 5 6 8573596 C_CAST_TO_GND C 0 6 10481 L_CAST_TO_INPUT L 1 6 10897482 _CAST_TO_I PUT L 1 6 2462113 R_MOVE_TO_NEW R 6 7 12757499 _CAST_TO_PREV 7 6 10259 C_CAST_TO_PREV C 7 6 10161281 L_CAST_TO_INPUT L 1 7 2452274 C_CAST_TO_PREV C 7 6 2457158 _CAST_TO_INPUT L 1 7 15284140 _CAST_TO_PREV L 7 6 1272684 L_MOVE_TO_NE L 7 8 11316166 C_CAST_TO_GND C 0 8 24495 L_CAST_TO_PREV L 8 7 15793607 _CAST_TO_INPUT L 1 8 3300694 L_MOVE_TO_NEW L 8 9 5376858 C_CAST_TO_GND C 0 9 25063 L_CAST_TO_PREV L 9 8 4863538 L_MOVE_TO_NE L 9 10 4364222 C_CAST_TO_GND C 0 10 12564 L CAST TO PREV L 10 9 4489818

TABLE III SPICE circuit netlist for evolved filter number three

Fifth order elliptical lowpass filter VSOURCEl 256 0 DC OV AC 2V RSOURCE1 256 1 1000 RLOAD001 255 0 1000 CAPC0001 1 2 1.083701e-04

CAPC0002 2 3 3.547581e-05 CAPC0003 3 2 9.862769e-05 RSTR0001 3 2 1.042709e+04 LIND0001 1 3 2.147189e-01 LIND0002 3 2 5.285780e-03 LIND0003 3 4 7.713100e-01 CAPC0004 4 6 2.519509e-05 CAPC0005 0 6 1.048100e-07 LIND0004 i 6 2.008357e-01 RSTR0002 6 7 3.648645e+04 CAPC0006 ^~ι 6 1.261844e-04 LIND0005 1 7 2.113217e-01 LIND0006 7 6 1.017696e-03

LIND0007 7 8 1.131617e+00

CAPC0007 8 2.449500e-07 LIND0008 7 1.579361e+00 LIND0009 8 3.300694e-01 LIND0010 9 5.376858e-01 CAPC0008 9 2.506300e-07 LIND0011 8 4.863538e-01 LIND0012 10 4.364222e-01 CAPC0009 10 1.256400e-07

LIND0013 10 9 4.489818e-01

RSTR0003 10 255 1.000000e-06

*** End netlist

*** Total of 25 components

.AC DEC 23 1 100K

.PRINT AC VM(255)

.END

TABLE IV B. Amplifier Design Tasks

Two amplifier design experiments were performed. In each experiment, 10 runs were performed and the following are the highest performance circuits found across all runs. The goal was to design an inverting amplifier capable of a dc voltage gain up to a maximum of either 100 dB or 120 dB, while minimizing dc bias and maximizing linearity over the dc gain. Population size was set to 1200 individuals, and each run proceeded for 5000 generations, giving a total of 6 million circuit evaluations per run. The difference between the two sets of experiments is that in the first set, the maximum gain was set to be 120 dB, and in the second set, 100 dB was the maximum gain. The maximum gain possible is set by using feedback resistors (labeled R,,_B). For an ideal inverting amplifier (as shown in FIG. 13), the magnitude of the gain of the amplifier is simply R _B/R_S, where R_s. is the source resistor. Fitness was calculated in a manner similar to the work on amplifiers in (Koza, J.R., et al, IEEE Trans, on Evolutionary Computation 1(2): X 09- 128 (1997)). An error value is computed as the sum of the dc gain penalty (the target gain minus the observed gain), the dc bias (zero dc bias is ideal), and the degree to which the dc gain is linear.

B. I 75 dB In verting A mplifier

In the first set of experiments the maximum voltage gain was set at 120 dB (10°). The amplifier having the best performance had a dc gain of 74.53 dB

(5324.40). Figure 14 shows the schematic for this circuit. It was found in generation 4866, and had a dc bias of 3.64 volts and a power dissipation of 0.82 watts.

The dc behavior can best understood by examining the major current pathways in the circuit. The current through the load is the key quantity since it is converted to a voltage by the load resistor and hence forms the circuit's output.

Nearly all of the dc current owing through the load resistor originates from the power supply connected to transistor Q7's collector. Q7 is biased in such a way as to supply Q8's base with approximately 36.4 mA of current. This current is divided so that 18.1 mA flows out of Q8's emitter and 18J mA out of Q8's collector. Resistor RJ is a tiny resistance that was positioned in order to connect transistor Q9 to the output (the last component is forced to connect to the output terminal). Thus R2 can be ignored, and transistor Q9's 18.4 mA current flows into the output node. Currents are summed at node 255 to give the load current of 36.4 mA which flows through the load resistance to give 3.64 volts output. Because there is a negligible amount of current owing through transistors Ql through Q4, the utility of these transistors is unclear. Components that are essentially non-functional, are quite commonly seen in evolutionary design applications. FiG. 15A shows the time domain response. Amplification of a 1 kHz sine wave having a 1 microvolt amplitude can clearly be seen in FIG. 15B. FIG. 15C shows the frequency response. The ac gain remains flat at 74.36 dB until it loses 3 dB at 7.59 kHz (its 3 dB bandwidth). FIG. 16 shows the dc transfer characteristic. The dc bias of 3.64 volts can be seen at the voltage input of zero volts.

B.2 85 dB Amplifier

In the second set of amplifier experiments the maximum voltage gain was set at 100 dB (10⁵). The amplifier having the best performance had a dc gain of

85.41 dB (18; 642:33). FIG. 17 shows the schematic for this circuit. Itwas found in generation 3635. and had a dc bias of 5.44 volts and a power dissipation of 8J 7 watts.

The dc current delivered to the load is mostly supplied by the 15 volt battery attached to the collector of transistor Q7. Transistor Q7 is conducting with the sum of its base and collector currents owing out of its emitter. Q7's base current of 13 mA is supplied by transistor Q6. As in the previous amplifier, the utility of transistors Ql and Q3 is unclear. The time domain response to an ac input of 1 microvolt at 1 kHz is illustrated in FIG. 18 A. An inverted, amplification signal is illustrated in in FIG. 18B. FIG. 18C shows the frequency response. The circuit has a flat-band gain of 85.46 dB and a 3 dB bandwidth of 282.8 kHz (FIG. 19B). The 3 dB bandwidth is significantly better than the previous amplifier. FIG. 19 shows the dc transfer characteristic. The dc bias of 5.44 volts can be seen at the voltage input of zero volts. The slope, the magnitude of which is the gain, is negative since the amplifier is inverting the signal.

IV. Example Implementations

The present invention (i.e., the system of FIG. 7, or any part thereof) may be implemented using hardware, software or a combination thereof and may be implemented in one or more computer systems or other processing systems. In fact, in one embodiment, the invention is directed toward one or more computer systems capable of carrying out the functionality described herein. An example of a computer system 2000 is shown in FIG.20. The computer system 2000 includes one or more processors, such as processor 2004. The processor 2004 is connected to a communication infrastructure 2006 (e.g., a communications bus, cross-over bar, or network). Various software embodiments are described in terms of this exemplary computer system. After reading this description, it will become apparent to a person skilled in the relevant art(s) how to implement the invention using other computer systems and/or computer architectures.

Computer system 2000 can include a display interface 2005 that forwards graphics, text, and other data from the communication infrastructure 2002 (or from a frame buffer not shown) for display on the display unit 2030. Computer system 2000 also includes a main memory 2008, preferably random access memory (RAM), and may also include a secondary memory 2010. The secondary memory 2010 may include, for example, a hard disk drive 2012 and/or a removable storage drive 2014, representing a floppy disk drive, a magnetic tape drive, an optical disk drive, etc. The removable storage drive 2014 reads from and/or writes to a removable storage unit 2018 in a well known manner. Removable storage unit 2018, represents a floppy disk, magnetic tape, optical disk, etc. which is read by and written to by removable storage drive 2014. As will be appreciated, the removable storage unit 2018 includes a computer usable storage medium having stored therein computer software and/or data.

In alternative embodiments, secondary memory 2010 may include other similar means for allowing computer programs or other instructions to be loaded into computer system 2000. Such means may include, for example, a removable storage unit 2022 and an interface 2020. Examples of such may include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM, or PROM) and associated socket, and other removable storage units 2022 and interfaces 2020 which allow software and data to be transferred from the removable storage unit 2022 to computer system 2000.

Computer system 2000 may also include a communications interface 2024. Communications interface 2024 allows software and data to be transferred between computer system 2000 and external devices. Examples of communications interface 2024 may include a modem, a network interface (such as an Ethernet card), a communications port, a PCMCIA slot and card, etc.

Software and data transferred via communications interface 2024 are in the form of signals 2028 which may be electronic, electromagnetic, optical or other signals capable of being received by communications interface 2024. These signals 2028 are provided to communications interface 2024 via a communications path (i.e., channel) 2026. This channel 2026 carries signals 2028 and may be implemented using wire or cable, fiber optics, a phone line, a cellular phone link, an RF link and other communications channels.

In this document, the terms "computer program medium" and "computer usable medium" are used to generally refer to media such as removable storage drive 2014. a hard disk installed in hard disk drive 2012. and signals 2028. These computer program products are means for providing software to computer system 2000. The invention is directed to such computer program products.

Computer programs (also called computer control logic) are stored in main memory 2008 and/or secondary memory 2010. Computer programs may also be received via communications interface 2024. Such computer programs, when executed, enable the computer system 2000 to perform the features of the present invention as discussed herein. In particular, the computer programs, when executed, enable the processor 2004 to perform the features of the present invention. Accordingly, such computer programs represent controllers of the computer system 2000.

In an embodiment where the invention is implemented using software, the software may be stored in a computer program product and loaded into computer system 2000 using removable storage drive 2014, hard drive 2012 or communications interface 2024. The control logic (software), when executed by the processor 2004, causes the processor 2004 to perform the functions of the invention as described herein.

In another embodiment, the invention is implemented primarily in hardware using, for example, hardware components such as application specific integrated circuits (ASICs). Implementation of the hardware state machine so as to perform the functions described herein will be apparent to persons skilled in the relevant art(s).

In yet another embodiment, the invention is implemented using a combination of both hardware and software.

V. Conclusion

The inventors have demonstrated shown that a linear circuit representation and evolutionary search can automatically produce circuit designs of low to medium difficulty in two applications. Detailed simulations of the designs suggest that all are electrically well-behaved and thus suitable for physical implementation. While the evolved designs presented do not exhibit the level of performance of their hand-designed predecessors, the main point was to show that a new representation technique with many desirable properties could automatically design practical circuits. The circuit representation method devised permits a wide range of circuits to be constructed, and results in a construction process that is unburdened with repair operations. In addition, the representation is syntactically closed, making it well-suited for evolutionary search. To gain performance on par with circuits designed by engineers, it will be necessary to place further constraints on the fitness functions. This is an area of future work. With the encouraging results of the system, the inventors are optimistic that a subset of analog circuit design tasks can be routinely accomplished by means of evolutionary computation in the future.

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example, and not limitation. It will be apparent to persons skilled in the relevant art that various changes in form and detail can be made therein without departing from the spirit and scope of the invention as defined in the claim(s). Among other reasons, this is true in light of (later) developing technology and terms within the relevant art(s). Thus the present invention should not be limited by any of the above- described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents. The articles referenced above are background materials, which are incorporated herein by reference in their entirety.

Claims

What Is Claimed Is:

X . A method of designing analog circuits using a linear genome representation and unfolding technique, comprising the steps of: defining a finite set of component-placing instructions, capable of placing components in a circuit between an input node and an output node, each instruction comprising an opcode specifying the connectivity of an associated component and a component value; generating a plurality of circuit graphs, each of the plurality of circuit graphs comprising a plurality of the instructions selected by mapping opcode and component values to linear genome segments; and comparing the plurality of circuit graphs with a fitness function to isolate one or more evolved circuits that best approximates the fitness function.

2. The method of claim 1 , wherein said step of comparing, further comprises the steps of: passing a plurality of subsets of the plurality of circuit graphs to a plurality of slave processors, respectively; generating a netlist from each circuit graph; processing each netlist via a circuit simulator to generate an circuit graph output; and computing a fitness value for each circuit graph output.

3. The method of claim 1, wherein the linear genome segments have a crossover rate of between 0 and 1, and a mutation rates of between 0.05-0J0, each crossover being a single-point with each parent having a separately chosen crossover point, and crossover points being randomly selected so as to be constrained to lie on component boundaries.

4. The method of claim 1, wherein the opcode can comprise a component connectivity including the set of: x-move-to-new, x-cast-to-previous, x-cast-to-ground, x-cast-input, x-cast-to-output, where x comprises an electronic device.

5. A computer program product comprising a computer usable medium having control logic stored therein for causing a computer to design analog circuits using a linear genome representation and unfolding technique, said control logic comprising: a first computer readable program code means for causing the computer to store a finite set of component-placing instructions, capable of placing components in a circuit between an input node and an output node, each instruction comprising an opcode specifying the connectivity of an associated component and a component value; a second computer readable program code means for causing the computer to generate a plurality of circuit graphs, each of the plurality of circuit graphs comprising a plurality of the instructions selected by mapping opcode and component values to linear genome segments; and a third computer readable program code means for causing the computer to compare the plurality of circuit graphs with a fitness function to isolate one or more evolved circuits that best approximates the fitness function.

6. The computer program product of claim 5, wherein said third computer readable program code means comprises: a fourth computer readable program code means for causing the computer to pass a plurality of subsets of the plurality of circuit graphs to a plurality of slave processors, respectively; a fifth computer readable program code means for causing the computer or the plurality of slave processors to generate a netlist from each circuit graph; an sixth computer readable program code means for causing the plurality of slave processors to process the each netlist via a circuit simulator to generate an circuit graph output; and a seventh computer readable program code means for causing the computer or the plurality of slave processors to computing a fitness value for each circuit graph output.