2.1. The genetic programming algorithm

Genetic programming typically starts with a population of randomly generated computer programs composed of the available programmatic ingredients. Genetic programming iteratively transforms a population of computer programs into a new generation of the population by applying analogs of naturally occurring genetic operations. These operations are applied to individual(s) selected from the population. The individuals are probabilistically selected to participate in the genetic operations based on their fitness at solving the problem at hand. The iterative transformation of the population is executed inside the main loop (called a generation) of a run of genetic programming.

Specifically, genetic programming breeds computer programs to solve problems by executing the following three steps:

2.2. Human-competitive results produced by genetic programming

Genetic programming can be applied to problems in a variety of fields, including design problems.

There are, at the time of this writing, 24 known instances where genetic programming has duplicated the functionality of a previously patented invention, infringed a previously issued patent, or created a patentable new invention (Koza, 2003). Specifically, there is one instance where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 19th-century invention, 15 instances where genetic programming has done the same with respect to a previously patented 20th-century invention, six instances where genetic programming has done the same with respect to a previously patented 21st-century invention, and two instances where genetic programming has created a patentable new invention (discussed later in Section 6).

Table 1 provides information on 22 of the above human-competitive results that relate to previously patented inventions. (The two patentable new inventions are discussed later in Section 6.) Twelve of the results in Table 1 infringe previously issued patents, and 10 duplicate the functionality of previously patented inventions in a noninfringing way.

Twenty-two previously patented inventions reinvented by genetic programming

It should also be mentioned that there are, at the time of this writing, 14 other known instances where genetic programming has produced a human-competitive result (using the detailed definition of this term found in Koza, Keane, Streeter, Mydlowec, Yu, & Lanza, 2003) that are not patent related. These include the design of an X-Band Antenna for NASA's Space Technology 5 Mission (Lohn et al., 2004), quantum computing elements (Spector et al., 1998; Spector, Barnum, & Bernstein, 1999; Spector, Barnum, Bernstein, & Swamy, 1999; Spector, 2004), a sorting network (Koza, Bennett, Andre, & Keane, 1999), game-playing strategies (Luke, 1998; Andre & Teller, 1999), algorithms for cellular automata (Andre et al., 1996), and algorithms for protein segment classification (Koza, Bennett, Andre, & Keane, 1999).

2.3. Automatic design of analog electrical circuits by means of genetic programming

Starting in Section 3, this paper presents a number of instances where genetic programming has automatically created both the topology (graphical structure) and sizing (numerical component values) for analog electrical circuits composed of transistors, capacitors, resistors, and other components. In each instance, genetic programming starts from a high-level statement of a circuit's desired behavior and characteristics (e.g., its desired output given its input). The process entails creation of both the topology and the sizing of a satisfactory circuit.

Specifically, the topology of a circuit comprises

• the total number of components in the circuit;
• the type of each component (e.g., resistor, capacitor, transistor) at each location in the circuit; and
• a list of all the connections that may exist between the leads of the circuit's components, input ports, output ports, power sources (if any), and ground.

The sizing of a circuit consists of the value(s), if any, associated with each component. The sizing of a component is usually a numerical value (e.g., the capacitance of a capacitor).

As Aaserud and Nielsen (1995) noted,

Genetic programming can be used to automatically create both the topology and sizing of an electrical circuit by

1. establishing a representation for electrical circuits suitable for use in a run of genetic programming, and
2. defining a fitness measure that measures how well the behavior and characteristics of a candidate circuit satisfy the problem's high-level design requirements.

The representation and fitness measure are then used during the run of genetic programming. During the run, the evaluation of the fitness of each individual in the population involves

1. converting each individual program tree in the population into the type of input accepted by a circuit simulator (i.e., a netlist listing each component in the circuit and the connections between the leads of the components),
2. obtaining the behavior of the individual circuit by simulating it, and
3. using the circuit's behavior and characteristics to calculate its fitness.

When genetic programming is used to automatically create computer programs, the programs are usually represented as program trees (i.e., rooted, point-labeled trees with ordered branches) in the style of the LISP programming language. A program tree is an acyclic graph. However, the structures that engineers typically desire to design are usually not acyclic graphs. In particular, electrical circuits are composed of loops (and, in fact, no dangling leads), and are therefore ordinarily represented by cyclic graphs (or hypergraphs). Genetic programming can be applied to the problem of automatic circuit synthesis by searching for a computer program (an acyclic structure) consisting of the instructions necessary to construct the circuit (a cyclic structure).

Specifically, our approach to the automatic synthesis of circuits using genetic programming employs a developmental process inspired by the principles of developmental biology, Wilson's (1987) pioneering application of developmental biology to genetic algorithms, the use of developmental genetic algorithms to evolve neural networks (Kitano, 1990), the use of developmental genetic programming (cellular encoding) to evolve neural networks (Gruau, 1992a, 1992b), and the use of developmental genetic programming to evolve Lindenmayer systems (Koza, 1993).

The developmental process here is used to transform a program tree (an acyclic graph) into a fully developed electrical circuit (a cyclic graph or hypergraph). The developmental process entails the execution of functions in a circuit-constructing program tree.

The starting point for the developmental process consists of a simple initial circuit. The initial circuit consists of an embryo and a test fixture.

The embryo herein consists of a single isolated modifiable wire that is not initially connected to external inputs or outputs. If the original modifiable wire is not modified by the developmental process, the circuit produces only trivial output. All development originates from the embryo's modifiable wire(s). An analog electrical circuit is developed by progressively applying the functions in a circuit-constructing program tree to the embryo's initial modifiable wire(s) and to succeeding modifiable wires and modifiable components.

The execution of the functions in the program tree transforms the initial circuit into a fully developed circuit. That is, the functions in the circuit-constructing program tree progressively side effect the embryo and its successors until a fully developed circuit eventually emerges.

Test fixtures are commonly used in electrical engineering to measure the behavior of a circuit. When genetic programming is being used to automatically synthesize an electrical circuit, the test fixture is the entity (external to the circuit that is being automatically created) that facilitates measurement of the behavior of the fully developed circuit. The test fixture feeds external input(s) into the circuit of interest. It also enables the circuit's output(s) to be probed. The test fixture is a hard-wired structure composed of nonmodifiable wires and nonmodifiable electrical components. The test fixture has one or more ports that enable the embryo (and, later, the fully developed circuit) to be embedded into it. In turn, the embryo (and, later, the fully developed circuit) has one or more ports that enable it to communicate with the test fixture in which it is embedded. The hard-wired components of the test fixture often include a source resistor and a load resistor. The test fixture supplies the measurements that enable the fitness measure to assign a single numerical value of fitness to the behavior and characteristics of the fully developed circuit. The test fixture can obtain the measurements needed by the fitness measure in various ways. One way (the way that is used for the work described in this paper) is to simulate individual candidate circuits or controllers using a general-purpose simulator, such as SPICE (Quarles et al., 1994). Another way is to create, at very high speeds, a temporary physical embodiment of each candidate circuit using a field-programmable transistor array (Stoica et al., 2001) and directly measure the circuit's behavior and characteristics. Although it would be impractical, another way would be to create a physical embodiment of each candidate circuit on a breadboard or silicon and directly measure the circuit's behavior and characteristics.

The functions in the circuit-constructing program trees are divided into five categories:

• topology-modifying functions (e.g., series division, parallel division, cut, via connecting two distant points in a circuit, via connecting a point in the circuit to ground, via connecting a point to a power supply, via connecting a point to an incoming signal, via connecting a point to an output port) that modify the topology of the developing circuit;
• component-creating functions that insert components (e.g., resistors, capacitors, transistors) into the developing circuit;
• development-controlling functions that control the developmental process by which the embryo and its successor circuits are converted into a fully developed circuit (e.g., the no-operation function);
• arithmetic-performing functions (e.g., addition, subtraction) that may appear in a value-setting subtree that is an argument to a component-creating function and that specifies the numerical value of the component; and
• automatically defined functions that enable certain substructures to be reused (including parameterized reuse).

The component-creating functions have value-setting subtree(s), whereas topology-modifying functions and development-controlling functions do not.

The terminals in the circuit-constructing program trees may include

• constant numerical values,
• perturbable numerical values,
• symbolic values (e.g., discrete alternative types for certain components),
• externally supplied free variables, and
• zero-argument functions (e.g., the development-ending function).

In applying the genetic programming algorithm (Section 2.1) to a particular problem of circuit synthesis, the first step is to generate an initial population (generation 0) of random compositions of the above functions and terminals. These functions and terminals permit the construction (through the developmental process just described) of any circuit composed of transistors, resistors, and capacitors.

Most of the randomly created circuits in generation 0 are, of course, very poor at solving the problem at hand (i.e., have very poor fitness). Many of these randomly created individuals are functionless or nonsensical. For example, many randomly created circuits in generation 0 do not make a connection to all input signals, all output ports, and all necessary power sources. Moreover, many randomly created circuits are so pathological that they cannot even be simulated by the general-purpose circuit simulator (SPICE, described in Quarles et al., 1994) used for the work herein. Nonetheless, even in this primordial ooze of randomly generated circuits, some score a better value of fitness than others. The evolutionary process builds on small differential advantages among the randomly created circuits of generation 0 (and the differential advantages of circuits in successive generations of the run of genetic programming).

In each generation, after the fitness of each individual in the population is ascertained, genetic programming probabilistically selects relatively more fit individuals from the population to participate in the problem-independent genetic operations used in generation programming (e.g., reproduction, mutation, and crossover). An important feature of Darwinian selection is that the selection is not greedy. Individuals that are known to be inferior will be selected to a certain degree. The best individual in the population in a given generation is not guaranteed to be selected. Moreover, the worst individual in the population in a given generation will not necessarily be excluded.

The genetic operations are applied to the selected individuals in the population to create a new population (i.e., a new generation) of offspring individuals. This process of executing each individual in the population to develop a circuit, evaluating the fitness of each fully developed circuit, selecting individuals from the population to participate in the genetic operations, and creating a new population is iterated over many generations.

Over successive generations, the fitness of the best individual in the population and that of the average individual in the population tend to progressively improve. At the same time, functionless, nonsensical, and nonsimulatable individuals tend to disappear as the run of genetic programming progresses. For example, the percentage of nonsimulatable individuals is sometimes as high as 90% for the randomly created individuals of generation 0. However, this percentage typically drops to low single digits after just a couple of generations (because of the effect of selecting more fit individuals to participate in the genetic operations that create the next generation).

Note that, in automatically synthesizing analog electrical circuits composed of transistors, resistors, and capacitors, genetic programming uses only a de minimus amount of platitudinous knowledge about analog circuits. Specifically, genetic programming employs a circuit simulator (e.g., SPICE) for the analysis of already created candidate circuits, but it does not use any knowledge about how to synthesize electrical circuits.

The runs of genetic programming for the various problems described in this paper are intentionally highly uniform. For example, the same function set, the same terminal set, and the same developmental process is used on each particular design problem described in this paper (and also in applying this process to many other problems over a period of years). The main difference between the runs is that a different fitness measure is used for each problem. Construction of a fitness measure requires translating the problem's high-level requirements into a precise computation using measurable characteristics or behavior of the circuit (obtained by means of a general-purpose circuit simulator). In particular, the fitness measure for a problem reflects the performance and characteristics of the desired circuit. The fitness measure specifies the desired time-domain or frequency-domain output value(s), given various specified input value(s). A problem-specific test fixture consisting of certain fixed components (such as an incoming signal source, a source resistor, a load resistor, and output probe points) is connected to the relevant input port(s) and the output port(s) of each candidate circuit.

3.1. The once universal idiom of positive feedback

In The Design of CMOS Radio-Frequency Integrated Circuits, Lee (1998) recounts the history that predated Black's 1927 invention of negative feedback.

Early work on feedback in amplifiers employed positive feedback. This work included rocket pioneer Robert Goddard's 1915 patent for a vacuum tube oscillator using positive feedback (Goddard, 1915) and Edwin Howard Armstrong's 1914 patent on amplifiers, again using positive feedback (Armstrong, 1914). As Lee (1998) observes,

However, Westinghouse's “nearly universal idiom” did not solve a major problem facing AT&T at the time, namely, distortion in amplifiers. As Lee (1998, p. 387) points out,

3.2. Black's first solution in 1923

Such was the state of affairs when Harold S. Black started working in 1921 at AT&T on the problem of reducing amplifier distortion.

As will be seen below, Black solved the problem twice. Black's first solution (described in this subsection) was physically implemented, but was ultimately regarded as impractical. Black's second solution (described in the next subsection) is now regarded as one of the most important inventions of the 20th century in electrical engineering.

Both of Black's solutions were characterized by a logical discontinuity and a singular moment when the previous thinking about this vexatious and long-standing problem was, in a “flash of genius,” overthrown and replaced by a new approach that could not have been logically deduced from what was previously known.

After 2 years of work on the problem, Black had tentatively reached the conclusion in 1923, “There was just no way to meet our ambitious goal” (Black, 1977). As Black then recounts,

Unfortunately, Black's 1923 invention did not turn out to be practical. As Black (1977) laments,

The bottom line concerning the feed-forward amplifier that Black invented in 1923 was “Nothing came of my efforts, however, because every circuit I devised turned out to be far too complex to be practical.”

3.3. Black's second solution in 1927: The flash of genius on the Lackawanna Ferry

Despite this false start, Black continued to work on the problem of reducing distortion in amplifiers for several additional years.

After working on the problem for a total of 6 years, Black (1977) recounted the following:

As previously mentioned, Edwin Howard Armstrong's approach to amplification using positive feedback was “a nearly universal idiom” during the early part of the 20th century. Black's approach did not flow logically from Armstrong's approach or from existing knowledge. Instead, Black's approach represented a logical break from prevailing thinking.

Despite the elegance and demonstrated practical effectiveness of negative feedback, Armstrong's approach was so entrenched in the thinking of electrical engineers that there was widespread resistance to Black's concept of negative feedback for many years after its invention. As Black (1977) recalls,

The British Patent Office was even more resistant. Black (1977) recounted “… our patent application was treated in the same manner as one for a perpetual motion machine.”

The British Patent Office continued to maintain that negative feedback would not work despite the fact that AT&T had “70 amplifiers working successfully in the telephone building at Morristown” for a number of years.

We believe that one reason why it took an inordinate amount of time for negative feedback to gain acceptance was that human thinking often becomes channeled along the well-traveled paths of “established beliefs.” In this situation, logical thinking can become the enemy of creativity.

Of course, when we say that the invention process is inherently illogical, we do not mean that inventors are oblivious to logic or that logical thinking is not helpful to inventors. Logical thinking often plays the important role of setting the stage for an invention. As Black (1977) himself noted, “[s]everal years of hard work on the problem” brought his thinking into the proximity of a solution. However, Black was not able to arrive at the invention by means of logic. Then, at the critical moment, Black made the necessary illogical leap during his now famous ferryboat ride. Although logical thinking may play a role in invention and creativity, at the end of the day, the critical element is a logical discontinuity from established ideas.

Many inventions over the years (like Black's two solutions to the problem of reducing distortion in amplifiers) were conceived in a singular moment when the prevailing thinking was replaced by a new approach that could not have been logically deduced from what was previously known.

3.4. Reinvention of negative feedback by genetic programming

In this section, we will show how the once perplexing problem of designing an electrical circuit to reduce distortion in amplifiers can be readily solved in an automated way by means of genetic programming. As will be seen below, Black's solution involving negative feedback readily flows from an evolutionary search guided by a high-level statement of the problem.

Before proceeding, note that one difference between Black's solution in 1927 and our present-day run of genetic programming is that Black invented negative feedback in the era of vacuum tubes. We did not have access to accurate models for the vacuum tubes actually used by Black. However, his patents state levels of performance that he achieved with his inventions. Present-day transistors operate in a manner similar to vacuum tubes. In particular, field-effect transistors (FETs) closely resemble the behavior of vacuum tubes in that they are voltage controlled. Therefore, the transistor-inserting function that we used in our present-day run of genetic programming inserts an IRFZ44 FET into the developing circuit. We maintained substantial consistency with the performance levels obtained by Black in 1927 by using an initial circuit with a voltage source supplying an incoming sine wave with a 4-V amplitude, a 50-ohm source resistor, a 100-ohm load resistor, and a 60-V power supply.

3.4.1. Preparatory steps

The human user communicates the high-level statement of the problem to the genetic programming system by performing certain well-defined preparatory steps.

The five major preparatory steps for the basic version of genetic programming require the human user to specify the following:

1. the set of terminals (e.g., the independent variables of the problem, zero-argument functions, and random constants) for each branch of the program that is to be evolved,
2. the set of primitive functions for each branch of the program that is to be evolved,
3. the fitness measure (for measuring the fitness of individuals in the population),
4. certain parameters for controlling the run, and
5. the termination criterion and method for designating the result of the run.

As previously mentioned, we approach each problem of synthesis of analog electrical circuits (including the eight specific problems discussed in this paper) in substantially the same way. We employ the generic set of functions described in Section 2.3 of this paper (e.g., generic component-creating functions that insert resistors, capacitors, and transistors; generic topology-modifying functions; generic development-controlling functions) and we employ the generic set of terminals described in Section 2.3 (e.g., constant numerical values, perturbable numerical values, symbolic values, zero-argument development-ending functions).

In preparing a run of genetic programming on a particular problem (e.g., the problem of reducing distortion in amplifiers), the emphasis is on the fitness measure. The construction of a problem's fitness measure requires the human user to identify exactly what is wanted. Focusing on what Black wanted leads to a multiobjective fitness measure based on the degree to which a candidate electrical circuit

• amplifies the incoming signal,
• minimizes distortion, and
• minimizes the number of expensive components.

Suppose that we adopt the usual convention that a smaller value of fitness is better, with zero being the (perhaps unattainable) ideal value. Suppose also that the specified amount of amplification is 10 dB. In that event, if a circuit were to receive a perfect sine wave as its input, the desired output of the circuit would be an inverted perfect sine wave whose amplitude is 3.16 times that of the incoming signal. The fitness measure for a candidate circuit can thus be based on the difference between this desired waveform and the output actually produced by the candidate circuit.

We first consider the first element of the three-element fitness measure. If the average absolute difference between a candidate circuit's output and the desired output is small (say, <1%), the circuit can be deemed to deliver a satisfactory amount of amplification and this first element of the fitness measure can be set to 0. Otherwise, the first element of the fitness measure is set to the average absolute difference between the desired output and the actual output.

The second element of the fitness measure is based on total harmonic distortion (THD):

where A₁ is the magnitude of the first harmonic (i.e., the fundamental frequency) and A_i is the magnitude of the ith harmonic (Vladimirescu, 1994). For audio signals of interest over a telephone, it would be reasonable to choose 1000 Hz as the fundamental frequency and to consider N = 9 harmonics. If the total harmonic distortion is less than, say, −45 dB, a circuit can be deemed to be satisfactory in terms of reducing distortion and the second element of the fitness measure can be set to 0. Otherwise, the second element is equal to

The third element of the fitness measure assigns a cost of 1.0 for each transistor and 0.01 for each resistor and capacitor (a choice suggestive of the cost difference in the 1920s of a vacuum tube and a resistor).

The three required elements of this multiobjective problem can be combined in a lexicographic way as follows: fitness can be defined as the sum of the first element (amplification), 10⁻⁶ times the second element (distortion), and 10⁻¹⁸ times the third element (parsimony). This lexicographic scheme causes the search process to first look for a circuit that provides the desired amplification. Once the contribution of the first element (amplification) reaches zero, the second element's contribution remains significant and distortion is taken into account. Once the contribution of the second element (distortion) reaches zero, the third element's contribution remains significant and parsimony is taken into account. This multiobjective fitness measure provides a way to take each of the three required elements into account and to readily compare the performance (desirability) of one candidate circuit to another.

Note that this fitness measure was created by focusing the problem's high-level requirements: amplification, distortion, and parsimony. The fitness measure is concerned with “what needs to be done,” not with “how to do it.” Notice that the fitness measure does not mandate a feed-forward approach (i.e., Armstrong's well-established approach), a feedback approach, or any other particular approach. In addition, if feedback is used at all, the fitness measure is agnostic as to whether the feedback is Armstrong's positive type of feedback or Black's negative type of feedback.

The remaining preparatory steps for Black's problem of designing a circuit to reduce distortion in amplifiers are identical to those for numerous other problems of circuit synthesis that have been solved using genetic programming. For details, see Koza, Keane, Streeter, Mydlowec, Yu, and Lanza (2003).

An important point about the just-described preparatory steps supplied by the human user prior to a run of genetic programming is that genetic programming requires only a de minimus amount of platitudinous knowledge about analog circuits. No knowledge base concerning the synthesis of analog electrical circuits is used. (Indeed, we know of no knowledge-based approach that is capable of automatically synthesizing the topology and sizing of analog circuits from a high-level statement of design requirements). Instead, we use a generic set of primitive functions (capable of creating any circuit composed of resistors, capacitors, and transistors), a generic set of terminals, and a fitness measure that expresses the high-level design requirements of the problem at hand. In the present instance, we used Black's high-level requirements (amplification, distortion, and parsimony) to specify “what needs to be done.”

3.4.2. Results for the problem of reducing amplifier distortion

The best circuit from among the 1,000,000 individuals in the population at generation 0 delivers amplification of −2.91 dB. That is, the best-of-generation circuit acts as an attenuator rather than an amplifier. However, even amplification of −2.91 dB can provide a toe-hold for the evolutionary process aimed at creating an amplifier.

The first best-of-generation circuit that acts as an amplifier appeared in generation 9. Specifically, this individual acts as a 5.37-dB amplifier. In addition to having inadequate amplification, this circuit is unsuitable in that it has a total harmonic distortion of −5.65 dB.

The first circuit in the run satisfying the problem's amplification criterion (10 dB) and having a total harmonic distortion of less than −45 dB appeared in generation 46. This circuit has a total harmonic distortion of −54.2 dB.

This best-of-generation circuit from generation 46 (Fig. 2) consists of three FETs and two resistors (ignoring the source resistor RSRC and the load resistor RLOAD that were hard wired into the test fixture). In viewing the figures, note that a FET's source corresponds to a vacuum tube's cathode, the FET's drain corresponds to the tube's anode, and the FET's gate corresponds to the tube's grid. In this circuit, transistor Q3 is biased off so its removal does not affect the circuit's behavior. However, transistors Q1 and Q2 are overlaid in parallel and together act as a single transistor with twice the transconductance and interelectrode capacitance of Q1. The removal of one of these two identical transistors slightly decreases the circuit's amplification (to 9.64 dB), adversely affects its total harmonic distortion (to −51.9 dB), and changes its bias.

The best-of-generation circuit from generation 46 for the problem of reducing amplifier distortion.

The 174-ohm resistor R2 in Figure 2 is the mechanism for providing negative feedback from Q1 and Q2. Because Q1 and Q2 reverse the phase of the incoming signal, the feedback is negative; that is, the signal from the drains (corresponding to a vacuum tube's plate) of Q1 and Q2 is subtracted from the incoming signal at the point-labeled VINSRC.

Table 2 shows, in column 2, the amplitude (decibels) of the fundamental frequency (1000 Hz) and various harmonics for the best-of-generation circuit from generation 46 (Fig. 2). Column 3 shows the amplitude (decibels) with respect to the fundamental frequency.

Distortion for the best-of-generation circuit from generation 46 for the problem of reducing amplifier distortion

The best-of-run circuit (Fig. 3) emerged in generation 48. The average absolute error (measuring amplification) of this best-of-run circuit from generation 48 is 0.065 V (about two-thirds of that of the best-of-generation circuit from generation 46). The best-of-run circuit has amplification of 10.06 dB and total harmonic distortion of −51.2 dB. This circuit is more parsimonious than the best-of-generation circuit from generation 46 in that it has only one transistor and two resistors (again ignoring RSRC and RLOAD). As can be seen, the 182-ohm resistor R2 is the mechanism for providing the negative feedback from the drain of transistor Q1 to the point-labeled VINSRC.

The parsimonious best-of-run circuit from generation 48 for the problem of reducing amplifier distortion.

Table 3 shows, in column 2, the amplitude (decibels) of the fundamental frequency (1000 Hz) and various harmonics for the best-of-run circuit from generation 48 (Fig. 3). Column 3 shows the amplitude (decibels) with respect to the fundamental frequency.

Distortion of the best-of-run circuit from generation 48 for the problem of reducing amplifier distortion

Thus, after 48 generations, genetic programming succeeded in recreating the invention of negative feedback. In reinventing negative feedback, the genetic programming algorithm did not rely on logic. Instead, it conducted a probabilistic search in the space of circuit-constructing computer programs. This probabilistic search was guided by the high-level requirements of Black's problem of minimizing distortion in amplifiers. In addition, this probabilistic search process arrived at the same creative solution that Black conceived in 1927.

Black received US patents 2,003,282 (Black, 1935), 2,102,670 (Black, 1937a), and 2,102,671 (Black, 1937b) that relate to his work on the problem of reducing distortion in amplifiers, as well as US patent 1,686,792 (Black, 1928,) for the earlier impractical solution described in Section 1.2. The overall goal of all these efforts is stated in the description of US patent 2,102,670 (Black, 1937a):

It is common experience that increase of the power output of vacuum tubes or electric space discharge devices tends to increase distortion of signaling or other waves transmitted by the devices, and tends to lower the gain of the circuits of the devices….

Therefore, a major problem in devising vacuum tube systems, as for example vacuum tube amplifier systems, is the securing of high output of power without attendant disadvantages, as for example without increase of first cost or decrease of operating efficiency of the systems, and especially in the case of vacuum tube amplifiers and repeaters, without sacrifice of quality of signal reproduction.

The best-of-run circuit from generation 48 (Fig. 3) infringes claims 1 and 3 of US patent 2,102,671 (Black, 1937b). Claim 1 covers,

In a wave translating device or system having amplifying properties, an input portion and an output portion, means to apply fundamental waves to said input portion, said system carrying fundamental components in said output portion, and having means producing other wave components in said output portion, and means controlling the relative magnitudes of said components in said output portion comprising means to feed waves from said output portion to said input portion to decrease the gain of the system.

The FET Q1 is the “wave translating device or system.” The incoming voltage signal source is the “means to apply fundamental waves to said input portion.” Resistor R2 is the “means to feed waves from said output portion to said input portion to decrease the gain of the system.” The negative feedback “decrease[s] the gain of the system.”

Claim 3 of US patent 2,102,671 (Black, 1937b) covers the following:

In a wave translating system operating to amplify applied fundamental waves, and to produce distortion components as a function of nonlinearity in the system, means to increase the ratio of the amplified fundamental wave component to distortion components comprising means to utilize a portion of the waves translated by said system to reduce the gain of the system below the gain with zero feedback in the system of the waves translated by the system.

Thus, we have seen that if one begins with a high-level statement of the problem that Black was trying to solve, Black's solution readily flows from a run of genetic programming. It does so because Black's solution is a correct solution to the problem of reducing distortion in amplifiers and, as they say, necessity is the mother of invention.

One of the virtues of genetic programming is that it approaches a problem in an open-ended way that is not encumbered by previous human thinking. Genetic programming is not aware, much less concerned, about whether a solution is “contrary to established beliefs.” For this reason, genetic programming often unearths solutions that might have never occurred to human scientists and engineers who are steeped in the thinking of the day.

4.1. Preparatory steps

As previously mentioned, we approach each problem of analog circuit synthesis in substantially the same way. We use the generic set of functions described in Section 2.3 (e.g., generic component-creating functions that insert resistors, capacitors, and transistors; generic topology-modifying functions; and generic development-controlling functions) and the generic set of terminals described in Section 2.3 (e.g., constant numerical values, perturbable numerical values, symbolic values, zero-argument development-ending functions). Thus, in preparing for a run of genetic programming on the problem of synthesizing a Sallen–Key filter, the emphasis is on the fitness measure.

The fitness measure consists of 10 elements. The 10 elements are divided into two groups, each consisting of 5 elements. Within each group of 5 elements, the first element of each group evaluates the circuit in the frequency domain with the aim of getting a circuit whose frequency-domain behavior matches that of the model circuit whose behavior represents that of a Sallen–Key filter. For the second and third elements of each group, the circuit is evaluated in the passband with the aim of getting its output to match the incoming waveform as closely as possible. For the fourth and fifth elements within each group, the circuit is evaluated in the stopband with the aim of getting its output to be suppressed to nearly zero (without regard to the shape of the suppressed waveform).

For all elements of the fitness measure, all internal points of the circuit are probed. If any voltage at any point in the circuit ever falls outside the interval [−30, +30], the individual receives a high-penalty fitness (e.g., 10⁸). An individual also receives a high-penalty fitness if the circuit cannot be simulated. In the absence of these two extreme situations, fitness is a weighted sum of the performance penalty and the parsimony penalty. The performance penalty is the sum, over all 10 elements of the fitness measure, of the detrimental contribution to fitness associated with that element of the fitness measure. The parsimony penalty is equal to the number of op amps in the circuit plus 0.25 times the number of other components in the circuit.

The performance penalty and the parsimony penalty can be combined into a multiobjective fitness measure in a lexicographic way similar to that used in the previous section of this paper. During the early part of the run, the emphasis is on performance. After a satisfactory level of performance is achieved, the emphasis is on parsimony.

4.2. Results

The best-of-run individual (Fig. 4) was produced at generation 183.

The genetically evolved best-of-run circuit from generation 183.

Figure 5 shows the behavior, in the frequency domain, of the genetically evolved best-of-run circuit from generation 183. The attenuation for the decade of frequency between 1000 and 10,000 Hz is 39.1 dB. The frequency response of this circuit indicates that it is a satisfactory solution to the problem. Examination of the topology of the circuit (Fig. 4) reveals that the genetically evolved solution is a Sallen–Key filter.

The behavior in the frequency domain of the genetically evolved best-of-run circuit from generation 183.

5.1. Fitness measures for the six 21st-century patented inventions

5.2. Results for the six 21st-century patented inventions

5.2.1. Low-voltage balun circuit

Genetic programming automatically created the circuit shown in Figure 6. This best-of-run evolved circuit was produced in generation 97 and has a fitness of 0.429. The patented circuit has a fitness of 1.72. That is, the evolved circuit is roughly a fourfold improvement (less being better) over the patented circuit in terms of our fitness measure. In addition, the evolved circuit is superior to the patented circuit both in terms of its frequency response and its harmonic distortion.

An evolved balun circuit.

In the patent documents, Lee (2001) shows a previously known conventional (prior art) balun circuit (Fig. 7).

A prior art balun circuit shown in US patent 6,265,908 (Lee, 2001).

Lee's (2001) patented low-voltage balun circuit is shown in Figure 8. Lee states that the essential difference between the prior art and his invention is a coupling capacitor (C₂) located between the base and the collector of the transistor (Q₂). Lee explains the essence of his invention as follows:

The structure of the inventive balun circuit [Fig. 8 of this paper] is identical to that of [Fig. 7 of this paper] except that a capacitor C₂ are further provided thereto. The capacitor C₂ is a coupling capacitor disposed between the base and the collector of the transistor Q₂ and serves to block DC components that may be fed to the base of the transistor Q₂ from the collector of the transistor Q₂.

The Lee (2001) low-voltage balun circuit shown in US patent 6,265,908.

As can be seen, the best-of-run genetically evolved circuit (Fig. 6) possesses the very feature that Lee identifies as the essence of his invention, namely, the coupling capacitor C₃₀₂ in Figure 6 and C₂ in Figure 8.

The genetically evolved circuit also possesses three additional elements of claim 1 of Lee's 2001 patent. Interestingly, although the genetically evolved circuit embodies the essence of Lee's invention, it does not infringe Lee's patent because it does not possess the remaining elements of claim 1.

5.2.2. Mixed analog–digital register-controlled variable capacitor

Over our 16 fitness cases, the patented circuit has an average error of 0.803 mV. In generation 95, a circuit emerged with average error of 0.808 mV, or approximately 100.6% of the average error of the patented circuit. During the course of this run, we harvested the smallest individuals produced on each processing node with a certain maximum level of error. Examination of these harvested individuals revealed a circuit from generation 98 (Fig. 9) that approximately matches the topology of the patented circuit (without infringing). The genetically evolved circuit possesses all but one of the elements of claim 1 of the patented circuit (and hence does not infringe the patent).

An evolved compliant register-controlled capacitor circuit.

5.2.5. Low-voltage cubic signal generator

The best-of-run evolved circuit (Fig. 10) was produced in generation 182 and has an average error of 4.02 mV. The patented circuit had an average error of 6.76 mV. That is, the evolved circuit has approximately 59% of the error of the patented circuit over our four fitness cases.

An evolved cubic signal generation circuit.

The claims in US patent 6,160,427 (Cipriani & Takeshian, 2000) amount to a very specific description of the patented circuit. The genetically evolved circuit does not read on these claims and, in fact, bears hardly any resemblance to the patented circuit. In this instance, genetic programming again produced a circuit that duplicates the functionality of the patented circuit with a very different structure.

5.2.6. Tunable integrated active filter

Averaged over the nine values of frequency, the best-of-run circuit from generation 50 (Fig. 11) has 72.7-mV average absolute error for frequencies in the passband and 0.39-dB average absolute error for frequencies to the right of the passband.

An evolved circuit for the tunable integrated active filter.

The best-of-run genetically evolved circuit possesses every element of claim 1 of US patent 6,225,859 (Irvine & Kolb, 2001) and therefore infringes the patent.