Simultaneous Synthesis of Topology, Sizing, Placement, and Routing of Analog Electrical Circuits
(A Human-Competitive Result Produced by Genetic Programming)
The Result
Genetic programming simultaneously evolved the topology, sizing, placement, and routing of analog electrical circuits (including a lowpass filter and a 60 dB amplifier) as described in Chapter 5 of Genetic Programming IV: Routine Human-Competitive Machine Intelligence (Koza, Keane, Streeter, Mydlowec, Yu, and Lanza 2003). The evolved topology, sizing, placement, and routing of a lowpass filter is shown below.
A genetically evolved amplifier (section 5.3 of Genetic Programming IV) is shown below.
Basis for Claim of Human-Competitiveness
Genetic programming not only automatically synthesized the topology and sizing of a lowpass filter circuit, it is also simultaneously performed the tasks of creating the circuit’s placement and routing.
Genetic programming similarly the topology, sizing, placement, and routing of a 60 dB amplifier as described in section 5.3 of Genetic Programming IV.
Referring to the eight criteria in table 1.2 of Genetic Programming IV: Routine Human-Competitive Machine Intelligence (Koza, Keane, Streeter, Mydlowec, Yu, and Lanza 2003) for establishing that an automatically created result is competitive with a human-produced result, the simultaneous automatic synthesis of the topology, sizing, placement, and routing of these two circuits satisfy the following three of the eight criteria:
(A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention.
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
(G). The result solves a problem of indisputable difficulty in its field.
The problem of automatic placement and routing of a circuit whose topology and sizing has already been devised is alone considered to be a formidable problem.
In connection with the lowpass filter, the genetically evolved circuit has the recognizable features of the circuit for which George Campbell of American Telephone and Telegraph received U.S. patent 1,227,113 in 1917 (Campbell 1917). Claim 2 of Campbell’s patent covers:
“An electric wave filter consisting of a connecting line of negligible attenuation composed of a plurality of sections, each section including a capacity element and an inductance element, one of said elements of each section being in series with the line and the other in shunt across the line, said capacity and inductance elements having precomputed values dependent upon the upper limiting frequency and the lower limiting frequency of a range of frequencies it is desired to transmit without attenuation, the values of said capacity and inductance elements being so proportioned that the structure transmits with practically negligible attenuation sinusoidal currents of all frequencies lying between said two limiting frequencies, while attenuating and approximately extinguishing currents of neighboring frequencies lying outside of said limiting frequencies.”
An examination of the genetically evolved lowpass filter circuit shows that it indeed consists of “a plurality of sections” (specifically, four). Also, as can be seen in the figure, “Each section include[s] a capacity element and an inductance element.” Specifically, the first of the four sections consists of inductor L20 and capacitor C12; the second section consists of inductor L29 and capacitor C18; and so forth. Moreover, “one of said elements of each section [is] in series with the line and the other in shunt across the line.” As can be seen in the figure, inductor L20 of the first section is indeed “in series with the line” and capacitor C12 is “in shunt across the line.” This is also the case for the remaining three sections of the evolved circuit. In addition, the topology of the circuit in the figure exactly matches the topology of the circuit in figure 7 in Campbell’s 1917 patent. Finally, this circuit’s 100%-compliant frequency domain behavior confirms the fact that the values of the inductors and capacitors are such as to transmit “with practically negligible attenuation sinusoidal currents” of the passband frequencies “while attenuating and approximately extinguishing currents” of the stopband frequencies. In short, the circuit created by genetic programming has all the features contained in claim 2 of Campbell’s 1917 patent.
The rediscovery by genetic programming of the Campbell filter circuit came about eight decades after Campbell received a patent for his invention. Nonetheless, the fact that the original human-designed version satisfied the Patent Office’s criteria for patent-worthiness means that the genetically evolved duplicate would also have satisfied the Patent Office’s criteria for patent-worthiness (if only it had arrived earlier than Campbell’s patent application).
The Campbell filter was, in fact, rediscovered by genetic programming in 1995 (and previously reported in Koza, Bennett, Andre, and Keane 1996a, 1996d, and 1999a). This fact is included in the table of human-competitive results. This previous rediscovery of the Campbell filter by genetic programming did not, of course, entail the circuit’s placement and routing.
References
Campbell, George A. 1917. Electric Wave Filter. Filed July 15, 1915. U.S. patent 1,227,113. Issued May 22, 1917.
Koza, John R., Keane, Martin A., Streeter, Matthew J., Mydlowec, William, Yu, Jessen, and Lanza, Guido. 2003. Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Kluwer Academic Publishers.
· The home page of Genetic Programming Inc. at www.genetic-programming.com.
· For information about the field of genetic programming and the field of genetic and evolutionary computation, visit www.genetic-programming.org
· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most published papers) and the home page of John R. Koza at Stanford University
· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University
· Information about the 1992
book Genetic
Programming: On the Programming of Computers by Means of Natural Selection,
the 1994 book Genetic
Programming II: Automatic Discovery of Reusable Programs, the 1999
book Genetic
Programming III: Darwinian Invention and Problem Solving, and the
2003 book Genetic
Programming IV: Routine
Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic
Programming IV book in PDF format.
· 3,440
published papers on genetic programming (as of November 28, 2003) in a
searchable bibliography (with many on-line versions of papers) by over 880
authors maintained by William Langdon’s and Steven M. Gustafson.
· For information on the Genetic Programming and Evolvable Machines journal published by Kluwer Academic Publishers
· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals
· For information about the annual Genetic and Evolutionary Computation (GECCO) conference (which includes the annual GP conference) to be held on June 26–30, 2004 (Saturday – Wednesday) in Seattle and its sponsoring organization, the International Society for Genetic and Evolutionary Computation (ISGEC). For information about the annual Euro-Genetic-Programming Conference to be held on April 5-7, 2004 (Monday – Wednesday) at the University of Coimbra in Coimbra Portugal. For information about the 2003 and 2004 Genetic Programming Theory and Practice (GPTP) workshops held at the University of Michigan in Ann Arbor. For information about Asia-Pacific Workshop on Genetic Programming (ASPGP03) held in Canberra, Australia on December 8, 2003. For information about the annual NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle.
Last updated on December 27, 2003