What is delivered by the actual automated operation of an automated problem-solving method in comparison to the amount of knowledge, information, analysis, and intelligence that is pre-supplied by the human employing the method?
The AI ratio is especially pertinent to methods for getting computers to automatically solve problems because it measures the value added by the artificial problem-solving method.
Manifestly, the aim of the fields of artificial intelligence and machine learning is to generate human-competitive results with a high AI ratio.
Deep Blue: An Artificial Intelligence Milestone (Newborn 2002) describes the 1997 defeat of the human world chess champion Garry Kasparov by the Deep Blue computer system. This outstanding example of machine intelligence is clearly a human-competitive result. Feng-Hsiung Hsu (the system architect and chip designer for the Deep Blue project) recounts the intensive work on the Deep Blue project at IBM’s T. J. Watson Research Center between 1989 and 1997 (Hsu 2002). The team of scientists and engineers spent years developing the software and the specialized computer chips to efficiently evaluate large numbers of alternative moves as part of a massive parallel state-space search. In short, the human developers invested an enormous amount of “I” in the project. In spite of the fact that Deep Blue delivered a high (human-competitive) amount of “A,” the project has a low return when measured in terms of the A-to-I ratio. The builders of Deep Blue convincingly demonstrated the high level of intelligence of the humans involved in the project, but very little in the way of machine intelligence.
The Chinook checker-playing computer program is another impressive human-competitive result. Jonathan Schaeffer recounts the development of Chinook by his eight-member team at the University of Alberta between 1989 and 1996 in his book One Jump Ahead: Challenging Human Supremacy in Checkers (Schaeffer 1997). Schaeffer’s team began with analysis. They recognized that the problem could be profitably decomposed into three distinct subproblems. First, an opening book controls the play at the beginning of each game. Second, an evaluation function controls the play during the middle of the game. Finally, when only a small number of pieces are left on the board, an endgame database takes over and dictates the best line of play. Perfecting the opening book entailed an iterative process of identifying “positions where Chinook had problems finding the right move” and looking for “the elusive cooks” (Schaeffer 1997, page 237). By the time the project ended, the opening book had over 40,000 entries. In a chapter entitled “A Wake-Up Call,” Schaeffer refers to the repeated difficulties surrounding the evaluation function by saying “the thought of rewriting the evaluation routine … and tuning it seemed like my worst nightmare come true.” Meanwhile, the endgame database was painstakingly extended from five, to six, to seven, and eventually eight pieces using a variety of clever techniques. As Schaeffer (page 453) observes,
“The
significant improvements to Chinook came from the knowledge added to the
program: endgame databases (computer generated), opening book (human generated
but computer refined), and the evaluation function (human generated and tuned).
We, too, painfully suffered from the knowledge-acquisition bottleneck of
artificial intelligence. Regrettably, our project offered no new insights into
this difficult problem, other than to reemphasize how serious a problem it
really is.”
Chinook defeated world champion Marion Tinsley. However, because of the enormous amount of human “I” invested in the project, Chinook (like Deep Blue) has a low return when measured in terms of the A-to-I ratio.
The aim of the fields of artificial intelligence and machine learning is to get computers to automatically generate human-competitive results with a high AI ratio¾not to have humans generate human-competitive results themselves.
Ascertaining the return of a problem-solving method requires measuring the amount of “A” that is delivered by the method in relation to the amount of “I” that is supplied by the human user.
Referring to the 36 human-competitive results produced by genetic programming, it is reasonable to say that genetic programming delivered a high amount of “A” for each of them.
The question thus arises as to how much “I” was supplied by the human user in order to produce these 36 results. Answering this question requires the discipline of carefully identifying the amount of analysis, intelligence, information, and knowledge that was supplied by the intelligent human user prior to launching a run of genetic programming.
We make a clear distinction between the problem-specific preparatory steps and the problem-independent executional steps of a run of genetic programming.
The preparatory steps are the problem-specific and domain-specific steps that are performed by the human user prior to launching a run of the problem-solving method. The preparatory steps establish the “I” component of the AI ratio (i.e., the denominator).
The executional steps are the problem-independent and domain-independent steps that are automatically executed during a run of the problem-solving method. The executional steps of genetic programming are defined by the flowchart of genetic programming. The results produced by the executional steps provide the “A” component of the AI ratio (i.e., the numerator).
The five major preparatory steps for the basic version of genetic programming require the human user to specify
(1)
the set of terminals (e.g., the independent variables of the problem,
zero-argument functions, and random constants) for each branch of the
to-be-evolved computer program,
(2)
the set of primitive functions for each branch of the to-be-evolved computer
program,
(3)
the fitness measure (for explicitly or implicitly measuring the fitness of
candidate individuals in the population),
(4)
certain parameters for controlling the run, and
(5)
a termination criterion and method for designating the result of the run.
Genetic programming requires a set of primitive ingredients to get started. The first two preparatory steps specify the primitive ingredients that are to be used to create the to-be-evolved programs. The universe of allowable compositions of these ingredients defines the search space for a run of genetic programming.
The identification of the function set and terminal set for a particular problem (or category of problems) is often a mundane and straightforward process that requires only de minimus knowledge and platitudinous information about the problem domain.
For example, if the goal is to get genetic programming to automatically program a robot to mop the entire floor of an obstacle-laden room, the human user must tell genetic programming that the robot is capable of executing functions such as moving, turning, and swishing the mop. The human user must supply this information prior to a run because the genetic programming system does not have any built-in knowledge telling it that the robot can perform these particular functions. Of course, the necessity of specifying a problem’s primitive ingredients is not a unique requirement of genetic programming. It would be necessary to impart this same basic information to a neural network learning algorithm, a reinforcement learning algorithm, a decision tree, a classifier system, an automated logic algorithm, or virtually any other automated technique that is likely to be used to solve this problem.
Similarly, if genetic programming is to automatically synthesize an analog electrical circuit, the human user must supply basic information about the ingredients that are appropriate for solving a problem in the domain of analog circuit synthesis. In particular, the human user must inform genetic programming that the components of the to-be-created circuit may include transistors, capacitors, and resistors (as opposed to, say, neon bulbs, relays, and doorbells). Although this information may be second nature to anyone working with electrical circuits, genetic programming does not have any built-in knowledge concerning the fact that transistors, capacitors, and resistors are the workhorse components for nearly all present-day electrical circuits. Once the human user has identified the primitive ingredients, the same function set can be used to automatically synthesize amplifiers, computational circuits, active filters, voltage reference circuits, and any other circuit composed of these basic ingredients.
Likewise, genetic programming does not know that the inputs to a controller include the reference signal and plant output and that controllers are composed of integrators, differentiators, leads, lags, gains, adders, subtractors, and the like. Thus, if genetic programming is to automatically synthesize a controller, the human user must give genetic programming this basic information about the field of control.
The third preparatory step concerns the fitness measure for the problem. The fitness measure specifies what needs to be done. The result that is produced by genetic programming specifies “how to do it.” The fitness measure is the primary mechanism for communicating the high-level statement of the problem’s requirements to the genetic programming system. If one views the first two preparatory steps as defining the search space for the problem, one can then view the third preparatory step (the fitness measure) as specifying the search’s desired direction.
The fitness measure is the means of ascertaining that one candidate individual is better than another. That is, the fitness measure is used to establish a partial order among candidate individuals. The partial order is used during the executional steps of genetic programming to select individuals to participate in the various genetic operations (i.e., crossover, reproduction, mutation, and the architecture-altering operations).
The fitness measure is derived from the high-level statement of the problem. Indeed, for many problems, the fitness measure may be almost identical to the high-level statement of the problem. The fitness measure typically assigns a single numeric value reflecting the extent to which a candidate individual satisfies the problem’s high-level requirements. For example:
· If an electrical engineer
needs a circuit that amplifies an incoming signal by a factor of 1,000, the
fitness measure might assign fitness to a candidate circuit based on how
closely the circuit’s output comes to a target signal whose amplitude is 1,000
times that of the incoming signal. In comparing two candidate circuits,
amplification of 990-to-1 would be considered better than 980-to-1.
· If a control engineer wants
to design a controller for the cruise control device in a car, the fitness
measure might be based on the time required to bring the car’s speed up from 55
to 65 miles per hour. When candidate controllers are compared, a rise time of
10.1 seconds would be considered better than 10.2 seconds.
· If a robot is expected to
mop a room, the fitness measure might be based on the percentage of the area of
the floor that is cleaned within a reasonable amount of time.
· If a classifier is needed
for protein sequences (or any other objects), the fitness measure might be
based on the correlation between the category to which the classifier assigns
each protein sequence and the correct category.
· If a biochemist wants to
find a network of chemical reactions or a metabolic pathway that matches
observed data, the fitness measure might assign fitness to a candidate network
based on how closely the network’s output matches the data.
The fitness measure for a real-world problem is typically multiobjective. That is, there may be more than one element that is considered in ascertaining fitness. For example, the engineer may want an amplifier with 1,000-to-1 gain, but may also want low distortion, low bias, and a low parts count. In practice, the elements of a multiobjective fitness measure usually conflict with one another. Thus, a multiobjective fitness measure must prioritize the different elements so as to reflect the tradeoffs that the engineer is willing to accept. For example, the engineer may be willing to tolerate an additional 1% of distortion in exchange for the elimination of one part from the circuit. One approach is to blend the distinct elements of a fitness measure into a single numerical value (often merely by weighting them and adding them together).
The fourth and fifth preparatory steps are administrative.
The fourth preparatory step entails specifying the control parameters for the run. The major control parameters are the population size and the number of generations to be run. Some analytic methods are available for suggesting optimal population sizes for runs of the genetic algorithm on particular problems. However, the practical reality is that we generally do not use any such analytic method to choose the population size. Instead, we determine the population size such that genetic programming can execute a reasonably large number of generations within the amount of computer time we are willing to devote to the problem. As for other control parameters, we have, broadly speaking, used the same (undoubtedly non-optimal) set of minor control parameters from problem to problem over a period of years. Although the results found in our various published books and papers could undoubtedly have been obtained more efficiently by means of a different choice of control parameters, we believe that our policy of substantial consistency in the choice of control parameters helps the reader eliminate superficial concerns that the demonstrated success of genetic programming depends on shrewd or fortuitous choices of the control parameters. We frequently make only one run (or, at most, only a few runs) of each major new problem.
The fifth preparatory step consists of specifying the termination criterion and the method of designating the result of the run.
We have now identified that which is supplied by the human user of genetic programming. For the problems in most of our published books and papers, we believe that it is generally fair to say that only a de minimus amount of “I” is contained in the problem’s primitive ingredients (the first and second preparatory steps), the problem’s fitness measure (the third preparatory step containing the high-level statement of what needs to be done), and the run’s control parameters and termination procedures (the administrative fourth and fifth preparatory steps).
In any event, the amount of “I” required by genetic programming is certainly not greater than that required by any other method of artificial intelligence and machine learning of which we are aware. Indeed, we know of no other problem-solving method (automated or human) that does not start with primitive elements of some kind, does not incorporate some method for specifying what needs to be done to guide the method’s operation, does not employ administrative parameters of some kind, and does not contain a termination criterion of some kind.
In regard to the 36 human-competitive results produced by genetic programming, it can be seen that genetic programming delivered a large amount of “A.” Thus, the AI ratio of the runs of genetic programming that produced these results is high.
· 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 August 27, 2003