The Result

Genetic programming evolved the automatic decomposition of the problem of synthesizing a crossover (woofer-tweeter) filter as described in Section 32.3 of Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999).

BBB306

A two-band crossover (woofer-tweeter) filter is a one-input, two-output circuit that passes all frequencies below a certain specified frequency (the crossover frequency) to its first output port and that passes all higher frequencies to its second output port while, at the same time, suppressing all frequencies above the crossover frequency to its first port and suppressing the lower frequencies at its second port. High-fidelity sound systems typically contain a crossover filter to channel the low frequencies to the woofer speaker and the high frequencies to the tweeter speaker.

The woofer part of the evolved circuit has a three-rung lowpass ladder topology (with inductors L3, L43, and L24 in series horizontally across the top of the figure and capacitors C76, C68, and C5 as shunts vertically to ground). As we proceed from node 2 toward the two outputs, there is a bifurcation at L3 and C4, after which there is no further contact between the upper (woofer) portion of the circuit (leading to VOUT1) and the lower (tweeter) portion of the circuit (leading to VOUT2). That is, the evolutionary process created two distinct and separate substructures-one for the woofer output and one for the tweeter output. This evolved circuit is a parallel decomposition into a woofer substructure and a tweeter substructure.

Basis for Claim of Human-Competitiveness

The fact that the problem of the design of a crossover (woofer-tweeter) filter can be decomposed in this manner is now well known to electrical engineers. In fact, Otto Zobel of American Telephone and Telegraph invented this approach and received U.S. patent 1,538,964 for this invention (Zobel 1925).

Genetic programming was not supplied with any knowledge to suggest that it would be advisable to approach this particular problem of circuit synthesis by creating two separate and distinct substructures. Certainly nothing in the fitness measure favored a decomposition (as opposed to a holistic) approach. Moreover, the choice of the embryo did not bias the run of genetic programming in favor of creating separate and distinct substructures. In fact, it was deliberately chosen to be neutral. Instead, this beneficial decomposition emerged automatically during the run of genetic programming. That is, the evolutionary process opportunistically reinvented the well-known Zobel decomposition because it was needed. The user-supplied fitness measure specified "what needs to be done," and genetic programming automatically determined "how to do it." This decomposition is precisely the kind of problem decomposition that a system for automatically creating computer programs should be able to perform automatically. And it is precisely the kind of problem decomposition that usually must be performed, by hand, prior to the start-up of a run of most existing techniques for machine learning and artificial intelligence.

In U.S. patent 1,538,964, Otto Zobel (1925) pointed out that the crossover filter addresses the problem of making

“a long telephone circuit available not only for the ordinary telephoning frequencies but also for "carrier currents" of higher frequency, which may be modulated for additional telegraph or telephone uses. At the receiving station it becomes necessary to separate the frequencies so that those of the ordinary telephone range may go to an ordinary telephone receiving instrument and those of higher frequency may go to proper modulating apparatus. In Fig. 5 [of the patent] the incoming line from the left branches to two wave-filters in parallel, which lead respectively to the apparatus J and K, J for ordinary telephone frequencies, K for higher frequencies. Leading to J is a low-pass wave-filter and to K is a high-pass wave-filter. . . . To insure that frequencies of one range shall not go to the other apparatus from that for which they are intended, there must necessarily be an intermediate band of "lost frequencies," which it is desirable to make as narrow as possible.”

Referring to the eight criteria in chapter 1 of Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999) for establishing that an automatically created result is competitive with a human-produced result, the automatic synthesis of the Zobel filter circuit satisfies the following two 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.

References

Johnson, Walter C. 1950. Transmission Lines and Networks. New York: McGraw-Hill.

Koza, John R., Bennett III, Forrest H, Andre, David, and Keane, Martin A. 1999a. Genetic Programming III: Darwinian Invention and Problem Solving. San Francisco, CA: Morgan Kaufmann.

Zobel, Otto Julius. 1925. Wave Filter. U.S. Patent 1,538,964. Filed January 15, 1921. Issued May 26, 1925.

· 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 28, 2003