Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T13:54:56.779Z Has data issue: false hasContentIssue false
  • English
  • Français

Invention and creativity in automated design by means of genetic programming

Published online by Cambridge University Press:  29 April 2005

JOHN R. KOZA ,
MARTIN A. KEANE ,
MATTHEW J. STREETER ,
THOMAS P. ADAMS  and
LEE W. JONES
JOHN R. KOZA
Affiliation:
Stanford University, School of Medicine, Biomedial Informatics Program, 251 Campus Drive, Stanford, California 94305-5479, USA
MARTIN A. KEANE
Affiliation:
Econometrics Inc., 1300 North Lake Shore #22B, Chicago, Illinois 60610, USA
MATTHEW J. STREETER
Affiliation:
Genetic Programming Inc., 990 Villa Street, Mountain View, California 94041, USA
THOMAS P. ADAMS
Affiliation:
Genetic Programming Inc., 990 Villa Street, Mountain View, California 94041, USA
LEE W. JONES
Affiliation:
Genetic Programming Inc., 990 Villa Street, Mountain View, California 94041, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

Some designs are sufficiently creative that they are considered to be inventions. The invention process is typically characterized by a singular moment when the prevailing thinking concerning a long-standing problem is, in a “flash of genius,” overthrown and replaced by a new approach that could not have been logically deduced from what was previously known. This paper discusses such logical discontinuities using an example based on the history of one of the most important inventions of the 20th century in electrical engineering, namely, the invention of negative feedback by AT&T's Harold S. Black. This 1927 invention overthrew the then prevailing idiom of positive feedback championed by Westinghouse's Edwin Howard Armstrong. The paper then shows how this historically important discovery can be readily replicated by an automated design and invention technique patterned after the evolutionary process in nature, namely, genetic programming. Genetic programming employs Darwinian natural selection along with analogs of recombination (crossover), mutation, gene duplication, gene deletion, and mechanisms of developmental biology to breed an ever improving population of structures. Genetic programming rediscovers negative feedback by conducting an evolutionary search for a structure that satisfies Black's stated high-level goal (i.e., reduction of distortion in amplifiers). Like evolution in nature, genetic programming conducts its search probabilistically without resort to logic using a process that is replete with logical discontinuities. The paper then shows that genetic programming can routinely produce many additional inventive and creative results. In this regard, the paper discusses the automated rediscovery of numerous 20th-century patented inventions involving analog electrical circuits and controllers, the Sallen–Key filter, and six 21st-century patented inventions. In addition, two patentable new inventions (controllers) have been created in the same automated way by means of genetic programming. The paper discusses the promising future of automated invention by means of genetic programming in light of the fact that, to date, increased computer power has yielded progressively more substantial results, including numerous human-competitive results, in synchrony with Moore's law. The paper argues that evolutionary search by means of genetic programming is a promising approach for achieving creative, human-competitive, automated design because illogic and creativity are inherent in the evolutionary process.

Keywords

Analog CircuitsAutomated DesignCreativityEvolutionary ComputationGenetic Programming
Type
Research Article
Information
AI EDAM , Volume 18 , Issue 3 , August 2004 , pp. 245 - 269
Copyright
© 2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Aaserud, O. & Nielsen, I.R. (1995). Trends in current analog design: A panel debate. Analog Integrated Circuits and Signal-Processing 7(1), 5–9.CrossRefGoogle Scholar
Andre, D. & Teller, A. (1999). Evolving team Darwin united. In RoboCup-98: Robot Soccer World Cup II, Lecture Notes in Computer Science 1604 (Asada, M. & Kitano, H., Eds.), pp. 346–352. Berlin: Springer–Verlag.CrossRef
Andre, D., Bennett, F.H. III, & Koza, J.R. (1996). Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem. In Genetic Programming 1996: Proc. First Annual Conf. (Koza, J.R., Goldberg, D.E., Fogel, D.B. & Riolo, R.L., Eds.), pp. 3–11. Cambridge, MA: MIT Press.
Armstrong, E.H. (1914). Wireless Receiving System. US patent 1,113,149. Filed October 29, 1913, issued October 6, 1914.
Åström, K.J. & Hägglund, T. (1995). PID Controllers: Theory, Design, and Tuning, 2nd ed. Research Triangle Park, NC: Instrument Society of America.
Aytur, T.S. (2000). Integrated Circuit with Variable Capacitor. US patent 6,013,958. Filed July 23, 1998, issued January 11, 2000.
Balkir, S., Dundar, G., & Ogrenci, A.S. (2003). Analog VLSI Design Automation. Boca Raton, FL: CRC Press.
Banzhaf, W., Nordin, P., Keller, R.E., & Francone, F.D. (1998). Genetic Programming—An Introduction. San Francisco, CA: Morgan Kaufmann and Heidelberg.
Black, H.S. (1928). Translating System. US patent 1,686,792. Filed February 3, 1925, issued October 9, 1928.
Black, H.S. (1935). Wave Translation System. US patent 2,003,282. Filed August 8, 1928, issued June 4, 1935.
Black, H.S. (1937a). Wave Translation System. US patent 2,102,670. Filed August 8, 1928, issued December 21, 1937.
Black, H.S. (1937b). Wave Translation System. US patent 2,102,671. Filed April 22, 1932, issued December 21, 1937.
Black, H.S. (1977). Inventing the negative feedback amplifier. IEEE Spectrum December, 55–60.CrossRefGoogle Scholar
Cipriani, S. & Takeshian, A.A. (2000). Compact Cubic Function Generator. US patent 6,160,427. Filed September 4, 1998, issued December 12, 2000.
Daun–Lindberg, T.C. & Miller, M.L. (2000). Low Voltage High-Current Electronic Load. US patent 6,211,726. Filed June 28, 1999, issued April 3, 2001.
Goddard, R. (1915). Method of and Apparatus for Producing Electrical Impulses or Oscillations. US patent 1,159,209. Filed August 1, 1912, issued November 2, 1915.
Graeb, H.E., Zizala, S., Eckmueller, J., & Antreich, K. (2001). The sizing rules method for analog circuit design. Proc. Second IEEE/ACM Int. Conf. Computer Aided Design, pp. 343–349. Piscataway, NJ: IEEE Press.CrossRef
Gruau, F. (1992a). Cellular Encoding of Genetic Neural Networks. Technical Report 92-21. Lyon: Ecole Normale Supérieure de Lyon, Laboratoire de l'Informatique du Parallélisme.
Gruau, F. (1992b). Genetic synthesis of Boolean neural networks with a cell rewriting developmental process. Proc. Workshop on Combinations of Genetic Algorithms and Neural Networks 1992 (Schaffer, J.D. & Whitley, D., Eds.). Los Alamitos, CA: IEEE Press.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, MI: University of Michigan Press.
Ikeuchi, A. & Tokuda, N. (2000). Voltage–Current Conversion Circuit. US patent 6,166,529. Filed February 24, 2000, issued December 26, 2000 in US; filed March 10, 1999 in Japan.
Irvine, R. & Kolb, B. (2001). Integrated Low-Pass Filter. US patent 6,225,859. Filed September 14, 1998, issued May 1, 2001.
Kardontchik, J.E. (1992). Introduction to the Design of Transconductor–Capacitor Filters. Boston: Kluwer Academic.CrossRef
Karki, J. (1999). Analysis of the Sallen–Key Architecture. Texas Instruments Application Report SLOA024A.
Keane, M.A., Koza, J.R., & Streeter, M.J. (2002). Improved General-Purpose Controllers. US patent 6,847,851. Filed July 12, 2002, issued January 25, 2005.
Kitano, H. (1990). Designing neural networks using genetic algorithms with graph generation system. Complex Systems 4, 461–476.Google Scholar
Koza, J.R. (1990). Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems. Technical Report STAN-CS-90-1314. Stanford University, Computer Science Department.
Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.
Koza, J.R. (1993). Discovery of rewrite rules in Lindenmayer systems and state transition rules in cellular automata via genetic programming. Symp. Pattern Formation (SPF-93), Claremont, CA, February 13.
Koza, J.R. (1994a). Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, MA: MIT Press.
Koza, J.R. (1994b). Genetic Programming II Videotape: The Next Generation. Cambridge, MA: MIT Press.
Koza, J.R. & Rice, J.P. (1991). Genetic generation of both the weights and architecture for a neural network. Proc. Int. Joint Conf. Neural Networks, pp. 397–404. Los Alamitos, CA: IEEE Press.
Koza, J.R. & Rice, J.P. (1992). Genetic Programming: The Movie. Cambridge, MA: MIT Press.
Koza, J.R., Bennett, F.H. III, Andre, D., & Keane, M.A. (1999). Genetic Programming III: Darwinian Invention and Problem Solving. San Francisco, CA: Morgan Kaufmann.
Koza, J.R., Bennett, F.H. III, Andre, D., Keane, M.A., & Brave, S. (1999). Genetic Programming III Videotape: Human-Competitive Machine Intelligence. San Francisco, CA: Morgan Kaufmann.
Koza, J.R., Keane, M.A., & Streeter, M.J. (2003). Evolving inventions. Scientific American 288(2), 52–59.CrossRefGoogle Scholar
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., & Lanza, G. (2003). Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Boston: Kluwer Academic.
Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G., & Fletcher, D. (2003). Genetic Programming IV Video: Routine Human-Competitive Machine Intelligence. Boston: Kluwer Academic.
Lancaster, D. (1995). Active Filter Cookbook. Thatcher, AZ: Synergetics Press.
Lee, S.G. (2001). Low Voltage Balun Circuit. US patent 6,265,908. Filed December 15, 1999, issued July 24, 2001.
Lee, T.H. (1998). The Design of CMOS Radio-Frequency Integrated Circuits. Cambridge, MA: Cambridge University Press.
Lipson, H. (2004). How to draw a straight line using a GP: Benchmarking evolutionary design against 19th century kinematic synthesis. In Genetic and Evolutionary Conf. 2005 Late-Breaking Papers (Keijzer, M., Ed.). Seattle, WA: International Society for Genetic and Evolutionary Computation. [CD]
Lohn, J.D., Hornby, G.S., & Linden, D.S. (2004). An evolved antenna for deployment on NASA's Space Technology 5 Mission. In Genetic Programming Theory and Practice II (O'Reilly, U.-M., Riolo, R.L., Yu, G. & Worzel, W., Eds.), Chap. 18. Boston: Kluwer Academic.
Luke, S. (1998). Genetic programming produced competitive soccer softbot teams for RoboCup97. In Genetic Programming 1998: Proc. Third Annual Conf. (Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H. & Riolo, R., Eds.), pp. 214–222, University of Wisconsin, Madison, WI, July 22–25. San Francisco, CA: Morgan Kaufmann.
Quarles, T., Newton, A.R., Pederson, D.O., & Sangiovanni–Vincentelli, A. (1994). SPICE 3 Version 3F5 User's Manual. Berkeley, CA: University of California, Department of Electrical Engineering and Computer Science.
Spector, L. (2004). Automatic Quantum Computer Programming: A Genetic Programming Approach. Boston: Kluwer Academic.
Spector, L., Barnum, H., & Bernstein, H.J. (1998). Genetic programming for quantum computers. In Genetic Programming 1998: Proc. Third Annual Conf. (Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H. & Riolo, R., Eds.), pp. 365–373. San Francisco, CA: Morgan Kaufmann.
Spector, L., Barnum, H., & Bernstein, H.J. (1999). Quantum computing applications of genetic programming. In Advances in Genetic Programming 3 (Spector, L., Langdon, W.B., O'Reilly, U.-M. & Angeline, P., Eds.), pp. 135–160. Cambridge, MA: MIT Press.
Spector, L., Barnum, H., Bernstein, H.J., & Swamy, N. (1999). Finding a better-than-classical quantum AND/OR algorithm using genetic programming. In Proc. 1999 Congr. Evolutionary Computation, pp. 2239–2246. Piscataway, NJ: IEEE Press.CrossRef
Sripramong, T. (2001). The evolution of analogue CMOS circuits using genetic programming. PhD Thesis. London: University of London and Imperial College.
Sripramong, T. & Toumazou, C. (2002). The invention of CMOS amplifiers using genetic programming and current-flow analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21(11), 1237–1252.CrossRefGoogle Scholar
Stoica, A., Zebulum, R., & Keymeulen, D. (2001). Polymorphic electronics. In Evolvable Systems: From Biology to Hardware, 4th Int. Conf., Proc. ICES 2001. Lecture Notes in Computer Science 2210 (Liu, Y., Tanaka, K., Iwata, M., Higuchi, T. & Yasunaga, M., Eds.), pp. 291–302, Tokyo, October. Berlin: Springer–Verlag.
Vladimirescu, A.. (1994). The SPICE Book. New York: Wiley.
Wilson, S.W. (1987). The genetic algorithm and biological development. In Genetic Algorithms and Their Applications: Proc. Second Int. Conf. Genetic Algorithms (Grefenstette, J.J., Ed.), pp. 247–251. Hillsdale, NJ: Erlbaum.
Ziegler, J.G. & Nichols, N.B. (1942). Optimum settings for automatic controllers. Transactions of ASME 64, 759–768.Google Scholar