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 20th-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 20th 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 7th 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 8th 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 9th 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 10th 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 20th 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