Computer Bits Online Portland High Tech Job Fair
Internet Gateway Advertise with Computer Bits Browse our Archives Subscribe to our Mailing List About Us Table of Contents
 June 1996 Volume 6 • Number 6 

Genetic Programming

Will Bill Gates become Billy Appleseed? ... by Darin Molnar

I've never considered myself to be a conspiracy theorist, or even a suspicious person, but events sometimes occur in ways that make even the staunchest skeptic start wondering what the heck is going on. A case in point revolves around everyone's favorite emperor-nerd: Bill Gates.

Not long ago, I was watching C-Span in the wee hours of the morning (perhaps I should be more judicious about whom I call "nerd") and saw the Wise and Wonderful Mr. Bill giving a speech at Georgetown University. Amused by the spectacle of clergy fawning all over Gates, I decided to stick it out to hear what he had to say, especially since he had recently been caught by the Internet explosion with his proverbial pants down.

The speech was a multimedia event, complete with nifty Powerpoint slides and Bill's cracking voice. I was about to change the channel when I stopped, caught by something the Great One said seemingly in passing. I instantly made a connection between several timely Gates-related events and this brief remark. For reasons I will explain later, that one statement scared me more than a Computer Bits deadline.

Genetic Programming

One day while perusing the stacks at Powell's Technical, I came across an appealing title: Genetic Programming: On the Programming of Computers by Means of Natural Selection by John R. Koza. (You'll find his home page at The book interested me for two reasons: as an anthropologist, I have been steeped in the theory of natural selection and, as a computer programmer, I was intrigued by the possibility of combining the two in meaningful ways.

Later, my advisor introduced me to the Santa Fe Institute,, via a volume on Southwestern Archaeology and Complexity. Slowly, but surely, I plowed through books on Artificial Life (ALife), Complex Adaptive Systems (CAS), and Genetic Algorithms (GA), all methods and techniques used by researchers in disciplines as disparate as biology and history, anthropology and physics.

After spending months thinking about ways I could use the knowledge gained by the figurative trip I took to Santa Fe in my archaeological research, I ended up back in my office with Genetic Programming in my lap. You see, Genetic Programming (GP), combines parts of the approaches I mentioned above to produce a wonderfully robust programming technique. How I intend to use GP with archaeological data is the subject of another article, but, clearly, GP is a very attractive approach. Here's why.

GP is based on an intriguing question posed by Koza in Genetic Programming: How can computers learn to solve problems without being explicitly programmed? In other words, how can computers be made to do what needs to be done, without being told exactly how to do it?

Your first response, if you know anything at all about computers is, "They can't." Computers require programs in order to solve problems, and those programs have to be produced with a specific goal in mind by a real, live, pizza-eating, Coke-drinking programmer. But there is a brave, new way for computers to solve problems without being explicitly programmed and John Koza is its father: Genetic Programming.

Darwin's Dilemma

Somewhere hidden in all of this are the principles of evolution. In nature, evolution occurs when the following four conditions are met:
  1. Entities can, and do, reproduce,
  2. Several entities form a population,
  3. Variety exists in the population among the entities, and
  4. Some entities in the population can survive in the environment better than others. When these conditions are met, a population is actively engaged in the evolutionary process.
While evolution acts upon a population, natural selection operates upon individuals. Most simply put, the individuals in the population who can survive in the environment better than others (condition 4) will live to reproduce (condition 1), thereby increasing the number of individuals like them in the population. This is commonly referred to as "fitness." It is the fitness of individuals in a population that influences its structure. Thus we can say that, in the evolutionary process, (population) structure is dependent upon (individual) fitness.

The Genetic Algorithm

Crucial to GP is the utilization of the Genetic Algorithm (GA). An algorithm is nothing more than a set of instructions, much like a computer program. GAs were developed in the 1960s in reaction to the top-down programming approach in vogue with most Artificial Intelligence (AI) researchers at that time.

John Holland of the University of Michigan recognized the need for a different, more robust approach to the problem of AI programming. By trying to define all of the possible environmental rules and conditions for any given set of events, AI researchers were setting themselves up for failure. Holland asked, "What happens when an event arises for which no environmental rule exists?" His answer: Big-time crash. This made AI a hard sell for control systems such as airliner automatic flight controllers.

Holland decided that the best way to create an artificially intelligent system was to work from the bottom up (an inductive approach). By introducing the GA, Holland was seeking to simulate natural evolution in artificial systems. Rather than using the four nucleotide system of natural DNA, Holland devised a system of bit strings made up of 0s and 1s. Once population and string sizes are defined, strings are randomly filled with 0s and 1s, fitness values are determined, and reproduction takes place. Thrown into the mix are other genetic recombination operators such as crossover and mutation. In this way, GAs exploit implicit parallelism and other unique characteristics that make them a most robust and useful technique.

Garbage In, Garbage Out?

Koza's innovation represents an extension of the GA involving more complex structures—computer programs, rather than bit strings. These randomly-generated programs are general and hierarchical, varying in size and shape. GP's main goal is to solve problems by searching for a highly fit computer program in the space of all possible programs that solves the problem at hand. These programs are comprised of code bits appropriate to the problem domain, and the creation of the initial population is merely a blind, random search of the space defined by the problem.

Each program, like the bit strings of the GA, is measured for fitness, the most fit reproducing, the least fit dying off. As generations proceed and populations of individuals are generated based upon the principles of evolution and natural selection, increasingly useful (fit) programs are developed as offspring. Eventually, a program is found that solves the problem. As the problem (environment) changes, the fitness measure will change and, again, new programs will be produced. This is the power of Genetic Programming.

In short: One can harness the principles of Genetic Programming to create software that programs itself.

Back to Bill

This brings us back around to our friend and enemy Bill Gates, on C-Span at three in the morning. His remark went something like this (and I paraphrase): "The next big advance in computer programming will be the development of programs that write themselves." He was speaking in his characteristic condescending, Gatesian monotone, but it hit me like a flash of lightning. Here's why:

Like most graduate students with no time to spare, I spend an inordinate amount of it surfing the Web. While cruising one day, I ran across a page describing Gates's contribution of seed money to fund the construction of the William Gates Computer Science Building at Stanford University in Palo Alto, California.

Now, as nearly everyone knows, Gates never attended Stanford; he dropped out of Harvard years ago to become a gazillionaire. More interesting is a fact that few know: John Koza, the father of Genetic Programming, is a professor at Stanford University.

The Gates-Koza connection came to me in that brief instant and I knew the Next Big Thing would be Genetic Programming. GP will make the Internet look like child's play. Out of that flash came a vision—more of a nightmare, really—of Bill Gates handing out little randomly-generated program fragments like a demented Johnny Appleseed (the only difference being he would charge you and the seed wouldn't really work right until the third distribution) to happy, childlike programmers who would plant those seeds and merrily watch the program do all of the work. All the while Koza is in the background keeping track of his stock profits with a genetically programmed software package.

My vision may be fanciful, but the potential of Genetic Programming and Bill Gates's enthusiasm for this sort of approach to software engineering is not. Gates has stated repeatedly in interviews that he takes a strong interest in Artificial Intelligence-related research.

There is more to such statements than meets the eye. Not only could the nature of software engineering and development be dramatically altered, software will become something different than it is now. Programs will become more generalized and, thus, more powerful. And Bill Gates and Microsoft will be at the leading edge of the shift to this simpler, more advanced technology.

So ends my career as a conspiracy theorist.

About the Author

Darin Molnar is a PhD student in Systems Science program at Portland State University exploring ways to integrate Genetic Programming with archaeological data to make predictions about the past. E-mail to

Search our archives:

You can also get a listing of articles by Darin Molnar
If you need instructions for our search engine, go to our main search page.

This article was originally published in the June 1996 issue of Computer Bits magazine, and is copyright © 1996 by Bitwise Productions, Inc., Forest Grove, OR, (503) 359-9107. All rights reserved. Archival material is provided as-is. Links are not necessarily maintained. Recent events compel us, sadly, to emphasize that your rights to this article are limited to viewing it and printing it for personal use only. You must receive explicit permission from Computer Bits and the author(s) before reprinting or redistributing this article in any medium.