Genetic Programming is an Automated Invention Machine

There are now 23 instances where genetic programming has duplicated the functionality of a previously patented invention, infringed a previously issued patent, or created a patentable new invention. Specifically, there are 15 instances where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 20^th-century invention, six instances where genetic programming has done the same with respect to an invention patented after January 1, 2000, and two instances where genetic programming has created a patentable new invention. The two new inventions are general-purpose controllers that outperform controllers employing tuning rules that have been in widespread use in industry for most of the 20^th century.

Referring to the list of 36 human-competitive results produced by genetic programming, the table below provides additional information on 21 of these human-competitive results that relate to previously patented inventions. Eleven of the 21 results in the table below infringe previously issued patents and 10 duplicate the functionality of previously patented inventions in a non-infringing way. The first 10 entries in the table below refer to problems that were solved in Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999). The last 11 entries in the table below are described in Genetic Programming IV: Routine Human-Competitive Machine Intelligence (Koza, Keane, Streeter, Mydlowec, Yu, and Lanza 2003). The last six entries in the table below relate to patents for analog circuits that were issued after January 1, 2000.

21 Previously Patented Inventions Reinvented by Genetic Programming

	Invention	Date	Inventor	Place	Patent	Reference
1	Darlington emitter-follower section	1953	Sidney Darlington	Bell Telephone Laboratories	2,663,806	Section 42.3 of Genetic Programming III
2	Ladder filter	1917	George Campbell	American Telephone and Telegraph	1,227,113	Section 25.15.1 of Genetic Programming III and section 5.2 of Genetic Programming IV
3	Crossover filter	1925	Otto Julius Zobel	American Telephone and Telegraph	1,538,964	Section 32.3 of Genetic Programming III
4	“M-derived half section” filter	1925	Otto Julius Zobel	American Telephone and Telegraph	1,538,964	Section 25.15.2 of Genetic Programming III
5	Cauer (elliptic) topology for filters	1934–1936	Wilhelm Cauer	University of Gottingen	1,958,742, 1,989,545	Section 27.3.7 of Genetic Programming III
6	Sorting network	1962	Daniel G. O’Connor and Raymond J. Nelson	General Precision, Inc.	3,029,413	Sections 21.4.4, 23.6, and 57.8.1 of Genetic Programming III
7	Computational circuits	See text	See text	See text	See text	Section 47.5.3 of Genetic Programming III
8	Electronic thermometer	See text	See text	See text	See text	Section 49.3 of Genetic Programming III
9	Voltage reference circuit	See text	See text	See text	See text	Section 50.3 of Genetic Programming III
10	60 dB and 96 dB amplifiers	See text	See text	See text	See text	Section 45.3 of Genetic Programming III
11	PID-D2 (proportional, integrative, derivative, and second derivative) controller	1942	Harry Jones	Brown Instrument Company	2,282,726	Section 3.7 of Genetic Programming IV
12	Philbrick circuit	1956	George Philbrick	George A. Philbrick Researches	2,730,679	Section 4.3 of Genetic Programming IV
13	NAND circuit	1971	David H. Chung and Bill H. Terrell	Texas Instruments Incorporated	3,560,760	Section 4.4 of Genetic Programming IV
14	PID (proportional, integrative, and derivative) controller	1939	Albert Callender and Allan Stevenson	Imperial Chemical Limited	2,175,985	Section 9.2 of Genetic Programming IV
15	Negative feedback	1937	Harold S. Black	American Telephone and Telegraph	2,102,670, 2,102,671	Chapter 14 of Genetic Programming IV
16	Low-voltage balun circuit	2001	Sang Gug Lee	Information and Communications University	6,265,908	Section 15.4.1 of Genetic Programming IV
17	Mixed analog-digital variable capacitor circuit	2000	Turgut Sefket Aytur	Lucent Technologies Inc.	6,013,958	Section 15.4.2 of Genetic Programming IV
18	High-current load circuit	2001	Timothy Daun-Lindberg and Michael Miller	International Business Machines Corporation	6,211,726	Section 15.4.3 of Genetic Programming IV
19	Voltage-current conversion circuit	2000	Akira Ikeuchi and Naoshi Tokuda	Mitsumi Electric Co., Ltd.	6,166,529	Section 15.4.4 of Genetic Programming IV
20	Cubic function generator	2000	Stefano Cipriani and Anthony A. Takeshian	Conexant Systems, Inc.	6,160,427	Section 15.4.5 of Genetic Programming IV
21	Tunable integrated active filter	2001	Robert Irvine and Bernd Kolb	Infineon Technologies AG	6,225,859	Section 15.4.6 of Genetic Programming IV

Four of the 21 entries in the body of the table above are marked “See text.” These entries relate to groups of previously patented inventions (as opposed to single patents) that are described in detail in Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999). Concerning computational circuits (the 7^th entry), dozens of different computational circuits have been patented, including, for example, square root circuits (Newbold 1962) and logarithmic circuits (Green 1958). Concerning electronic thermometers (the 8^th entry), at least two dozen temperature-sensing circuits have been patented, including, for example, ones by Haeusler (1976) and Massey (1970). Concerning voltage reference circuits (the 9^th entry), Robert C. Dobkin and Robert J. Widlar of National Semiconductor Corporation received U.S. patent 3,617,859 for the voltage reference circuit (Dobkin and Widlar 1971). Subsequent to the renowned Dobkin-Widlar circuit, other patents have been issued for voltage reference circuits, including U.S. patent 3,743,923 to Goetz Wolfgang Steudel of RCA Corporation (Steudel 1973). Hundreds of patents have been issued for amplifiers (the 10^th entry).

The table below shows the two inventions generated by genetic programming for which a patent application has been filed.

2 Patentable Inventions Created by Genetic Programming

	Claimed invention	Date of patent application	Inventors	Reference
1	Improved PID tuning rules that outperform the Ziegler-Nichols and Åström-Hägglund tuning rules	July 12, 2002	Martin A. Keane, John R. Koza, and Matthew J. Streeter	Section 12.3 of Genetic Programming IV
2	3 improved non-PID controllers that outperform a PID controller using the Ziegler-Nichols or Åström-Hägglund tuning rules	July 12, 2002	Martin A. Keane, John R. Koza, and Matthew J. Streeter	Section 13.2 of Genetic Programming IV

The Illogical Nature of Invention and Evolution

Most computer scientists unquestioningly assume that any effective problem-solving process must be logically sound and deterministic.

The consequence of this unproven assumption is that virtually all conventional approaches to artificial intelligence and machine learning possess these characteristics. Yet the reality is that logic does not govern two of the most important processes for solving complex problems, namely

· the invention process (performed by creative humans) and

· the evolutionary process (occurring in nature).

Moreover, neither the invention process nor the evolutionary process is deterministic.

Novelty and creativity are prerequisites for patentability. A new idea that can be logically deduced from facts that are known in a field, using transformations that are known in a field, is not considered to be inventive by the Patent Office. A new idea is patentable only if there is what the courts have called an “illogical step” (i.e., a logically unjustified step). The required illogic distinguishes the proposed invention from that which is readily deducible from what is already known. The required illogical step is also sometimes referred to as a “flash of genius.” In other words, logical thinking is not the key ingredient for one of the most significant human problem-solving activities, namely the invention process. Interestingly, everyday usage parallels the law concerning the point that a lack of logic is a precondition for inventiveness: People who mechanically apply existing facts in well-known ways are summarily dismissed as being uncreative.

Of course, when we say that the invention process is inherently illogical, we do not mean that logical thinking is not helpful to inventors or that inventors are oblivious to logic. Logical thinking often plays the important role of setting the stage for an invention. 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.

The design of complex entities by the evolutionary process in nature is another important type of problem-solving that is not governed by logic. In nature, solutions to design problems are discovered by means of evolution and natural selection. The evolutionary process is probabilistic, rather than deterministic. Moreover, it is certainly not guided by mathematical logic. Indeed, one of the most important characteristics of the evolutionary process is that it intentionally creates and actively maintains inconsistent and contradictory alternatives. Logically sound systems do not do that. The active maintenance of inconsistent and contradictory alternatives (called genetic diversity) is a precondition for the success of the evolutionary process.

The inventions generated by genetic programming exhibit the kind of illogical discontinuity from previous human work that is required to obtain a patent.

Overcoming Established Beliefs

Edwin Howard Armstrong’s approach to amplification using positive feedback was “a nearly universal idiom” during the early part of the 20^th century.

In spite of the elegance and manifest effectiveness of the concept of negative feedback invented by Harold S. Black in 1927, 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:

“Although the invention had been submitted to the U.S. Patent Office on August 8, 1928, more than nine years would elapse before the patent was issued on December 21, 1937. … One reason for the delay was that the concept was so contrary to established beliefs.” (Emphasis added.)

The British Patent Office was even more resistant. As 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 in spite of 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.”

One of the virtues of genetic programming is that it is not aware, much less concerned, about whether a solution is “contrary to established beliefs.” Genetic programming approaches a problem in an open-ended way that is not encumbered by previous human thinking. 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. Genetic programming often unearths novel solutions to problems because it does not travel along the well-trod paths of previous human thinking.

In “Genetic Programming Takes a Ride on the Lackawanna Ferry” (section 14.1 of the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence), genetic programming is used to reinvent negative feedback. As will be seen, if one begins with a high-level statement of the problem that Harold Black was trying to solve in the 1920’s, Black’s solution flows almost effortlessly from a run of genetic programming. It does so because Black’s solution is a correct solution to the problem and, as they say, necessity is the mother of invention.

Automating the Invention Process

For over 200 years, the U.S. Patent Office has been in the business of receiving written descriptions of human-designed inventions and judging whether the purported inventions are

· “new,”

· “improved,”

· “useful,” and

· “[un]obvious … to a person having ordinary skill in the art to which said subject matter pertains.” (35 United States Code 103a)

When the Patent Office passes judgment on a patent application, it generally works from written documents and operates at arms length from the inventor. When an automated method duplicates the detailed structure of a previously patented human-created invention, the fact that the human-designed version originally satisfied the Patent Office’s criteria for patent-worthiness means that an automatically created duplicate would also have satisfied the Patent Office’s criteria for patent-worthiness had it arrived at the Patent Office prior to the human inventor’s submission.

When genetic programming is applied to a problem whose solution is a previously patented invention, there are three possible outcomes:

· failure of the run to solve the problem,

· creation of a solution that infringes a previously issued patent, or

· creation of a non-infringing solution that duplicates the functionality of a previously patented invention.

There are two sub-cases associated with the third case.

First, a non-infringing solution may be a previously known solution (i.e., prior art). The previously known solution may or may not have been patented in the past.

Second, a non-infringing solution may be a new solution to the problem.

In this second sub-case, a new, genetically evolved, non-infringing solution may be patentable if it satisfies the additional requirements of being “useful”, “improved,” and “unobvious.”

A genetically evolved solution would generally be deemed to be “useful” for the same reasons that the originally patented invention was deemed to be “useful.”

Almost every alternative solution to a particular problem usually has some attribute that can be reasonably viewed (from some standpoint) as being “improved” in some respect or to some degree.

Because genetically evolved solutions often contain features that would never occur to human scientists or engineers, a genetically evolved alternative solution will often be “unobvious” to someone “having ordinary skill in the art.”

U.S. law suggests that inventions created by automated means are patentable by saying:

“Patentability shall not be negatived by the manner in which the invention was made.” (35 United States Code 103a)

Patentable New Inventions Produced by Genetic Programming

Given that genetic programming has solved problems whose solutions were previously patented, it is a natural extension to try to use genetic programming to generate patentable new inventions.

Chapters 12 and 13 of he 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence describe a patent application filed on July 12, 2002, for improved PID (proportional, integrative, and derivative) tuning rules and non-PID controllers that were automatically created by means of genetic programming. The genetically evolved tuning rules and controllers outperform controllers tuned using the widely used Ziegler-Nichols tuning rules (1942) and the recently developed Åström-Hägglund tuning rules (1995). The applicants believe that the new tuning rules and controllers satisfy the statutory requirement of being “improved” and “useful.” They are certainly “new.” Because they contain features that would never occur to an experienced control engineer, they are certainly “unobvious” to someone “having ordinary skill in the art.” If (as expected) a patent is granted, it will (we believe) be the first patent granted for an invention created by genetic programming.

---

· The home page of Genetic Programming Inc. at www.genetic-programming.com.

· For information about the field of genetic programming in general, visit www.genetic-programming.org

· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most papers) and the home page of John R. Koza 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.

· For information on 3,198 papers (many on-line) on genetic programming (as of June 27, 2003) by over 900 authors, see William Langdon’s bibliography on genetic programming.

· 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 NASA/DoD Conference on Evolvable Hardware Conference (EH) to be held on June 24-26 (Thursday-Saturday), 2004 in Seattle. 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.

---

Last updated on December 30, 2003

---