Genetic Programming Iii: Automatic Programming and Automatic Circuit Synthesis

Rating:
Summary: And the future is...
Review: Genetic programming is like a new Big Bang in computer universe.
Reach the automatic programming level is a revolution that will affect the way things are done today.

In a very cientifyc way, the book shows all the aspects of how to get ready for this evolution.

Rating:
Summary: Still a few bugs in the system...
Review: I own and have read parts of Koza's Genetic Programming I with pleasure. I looked at this book in a bookstore, only to discover that the cover was upside-down with respect to the pages! I'm not about to plunk down 78 bucks for that, but I did get a good laugh out of it. Maybe the authors should write a genetic program to do their proofreading :-)

Rating:
Summary: READ IT BEFORE REVIEWING PLEASE
Review: my five stars are just to counteract the single star from the idiotic reviewer who gave the book one star w/o even bothering to read it. i haven't read this volume yet either, but i just ordered it and it's on its way; i'm certain i won't be disapointed. i'm a programmer and an artist and i use GP effectively to evolve forms both sonic and visual. just because you know your field(s) doesn't mean you can't benefit from a knowledge of evolutionary algorithms, quite the contrary. we have koza and friends to thank for a lot of inspirational work. i for one enjoy the interaction that i have with my algorithms, and since i'm the fitness function, forms crop up which never would have if either i or the machine were working alone. apologies for being guilty of the same crime as said reviewer but i feel in this case it's justified.

Rating:
Summary: Buzz word soup from high priced nerds
Review: Recently I received a video survey of this book, I feel compelled to give a review. If I was sent me the book I might review it, but the is so darn long.

The tape starts off with sixteen criteria to evaluate the effectiveness of a genetic programming program. Pretty good criteria.

It then suggest that programs will be mutated and checked for their value at solving the problem. This also seems reasonable. It is called search. If one can do the search in parallel, then this seems reasonable as we know parallel search is reasonable. Since we know that a program can be thought of as a set of 0's and 1's we could simply mutate the string and bingo new programs. Of course this kind of dumb search would take a lot longer than the universe has been around (a lot lot longer in most cases) but if one has time to read a thousand page book then maybe you have more time than I.

So their solution is to understand the structure of the program and then to make smarter mutations. And here is the rub. You have to understand the structure of the program which is a lot of work.

The authors try to suggest how to do this automatically or generally but of course this really can't be done.( Ask Turing if he were alive) Their method is to essentially paramaterize the program at many levels and then permute these chunks. Nice but it takes the intelligence to find the chunks. However if you find the right chunks , I have no doubt that a computer can finish the problem. Computers are good at finding solutions once the search space has been properly limited.

Bottom line, search takes either a near infinite amount of time or encoded knowledge. A finite program can only encode a finite amount of knowledge so general (finite) search programs can never do well. However if you just have a human keep giving them more knowledge they will do well and that is called programming.

Hope that boring guy in the video gets a life, but he won't do it with my 78 dollars.

Later, Big Fan of Mr. Turing

Rating:
Summary: A hint of the future.....
Review: The authors have written a fine book here and it has and will continue to be a source of good information on the subject. What is most interesting about the approach of genetic programming is that it does not make use of the inference methods of formal logic in the search for the correct program. Correctly observing that logical thinking is insufficient for invention and creativity, the authors follow the "logic considered harmful" philosophy in their attempts to get a computer to find a creative/original solution to a problem. And most importantly, they discuss fourteen examples where genetic programming has produced results that are competitive with human-produced results. The book is almost 1200 pages long, but without reading all the examples one could cover the main points in a reasonable time frame. The reader knowing the LISP language will appreciate the discussion more.

After a brief introduction to the book in chapter 1, the authors move on to a detailed discussion of the philosophy and approaches used in genetic programming. They list the five steps that must be done before applying a genetic algorithm to a problem and give an overview of the LISP background needed to understand genetic programming. The authors emphasize that the genetic algorithm is probabilistic in nature, with the initial populations, individual selection, and genetic operation chosen at random. They give flowcharts illustrating a typical genetic algorithm and program, and then show executable programs can be automatically created. A very extensive list of references on genetic programming is given at the end of the chapter.

In the next part, the authors discuss how to eliminate the requirement that the programmer specify the architecture in advance to the program to be created. After reviewing some methods that were previously used to make the choice of architecture, the authors move on to describing a set of architecture-altering operations that give an automated method for determining the architectures of evolving programs. The discussion on automatically defined recursion is particularly interesting.

The book then shows how to use the results so far to allow problem-solving to be done using genetic programming, the first one being the rotation of automobile tires and the second being evolving a computer program with the behavior of Boolean even-parity functions. This is followed by a discussion of how to use architecture-altering operations to solve a time-optimal control problem. The most interesting part of this discussion is that it illustrates the important point that disadvantageous actions should be taken in the short term so that the long-term objective can be achieved.

In chapter 14, the ant foraging problem is used to illustrate a form of the (Minsky) multiagent problem and architecture-altering operations. This is followed by discussions on the digit recognition problem and the transmembrane segment identification problem. The authors choose the Fibonacci sequence to illustrate how recursion can be used in solving problems with genetic programming. The necessity of using internal storage is illustrated using the cart centering problem.

The authors then overview the use of the Genetic Programming Problem Solver (GPPS) for automatically creating a computer program to solve a problem. Several problems are examined using this Solver, such as symbolic regression, sorting networks, and the intertwined spirals problem.

The next part then considers the application of genetic programming to the automated synthesis of analog electrical circuits. The authors judge, rightfully, that the design process is one that will be a good judge of automated technique versus one that was done by humans, especially considering the fact that analog design is considered by many to be an "art" rather than a "science". The authors show how to import the SPICE simulation system into the genetic programming system, and discuss how validation of circuit design using this simulator would be done by the genetic programming system. After showing how a low-pass filter may be successfully designed using the genetic programming system, the authors show how with a few changes it can be used to design many different types of circuits. Interestingly, the authors cite the rediscovery by genetic programming of the elliptic filter topology of W. Cauer. Cauer arrived at his discovery via the use of elliptic functions, but the genetic program did not make use of these, but relied solely on the problem's fitness measure and natural selection!

An interesting discussion is also given of the role of crossover in genetic programming by comparing the problem of synthesizing a lowpass filter with and without using crossover. The authors conclude that the crossover operation plays a large contribution to the actual solution of the problem.

Then later, the authors show how genetic programming actually evolved a cellular automata that performs better than a succession of algorithms written by humans in the last two decades. Specifically, they show how genetic programming evolved a rule for the majority classification problem for one-dimensional two-state cellular automata that exceeds the accuracy of all known rules.

Most interestingly, the authors show how genetic programming evolved motifs for detecting the D-E-A-D box family of proteins and for detecting the manganese superoxide dismutase family.

The actual performance and implementation issues involved in genetic programming are discussed in the last two parts of the book. They discuss the computer time needed to yield the 14 instances where they claim that genetic programming has produced results that are competitive with human-produced results.

The authors wrap things up in the last chapter of the book and discuss other instances where genetic programming has succeeded in automatically producing computer programs that are competitive with human-produced results. The evidence they have in the book is impressive but there are a few areas that will be ultimate tests of this approach, the most important being the discovery of new mathematical results or algorithms. It is this area that requires the most creativity on the part of the inventor.

Rating:
Summary: Can computers be creative?
Review: The quest for *Automatic Programming* is the holy grail of artificial intelligence. The dream of having computer programs write other useful computer programs has haunted researchers since the nineteen fifties. In Genetic Programming III -Darwinian Invention and problem solving (GP3) by John R. Koza, Forest H Bennet III, David Andre and Martin A Keane, the authors claim that the first inscription on this trophy should be the name Genetic Programming (GP). GP is about applying evolutionary algorithms to search the space of computer programs. The authors paraphrase Arthur Samuel of 1959 and argue that with this method it is possible to "tell the computer what to do without telling it explicitly how to do it".

The main hypothesis of the book is that GP is not only the first instance of true automatic programming but also creative to such an extant that it competes with humans in solving very hard problems and therefore the solutions produced by GP can sometimes be called inventions, thus the name "Darwinian Invention Machine". The book starts by listing sixteen proposed attributes of any automatic programming system. The attribute list begins with obvious properties such as the ability to produce entities that can run on a computer, continues by describing components of full computer programs and ends by expressing fuzzier concepts such as applicability, scalability and competitiveness with human-produced results. The authors argue that GP definitely has most of the 16 attributes and at least to some extent possesses the remaining few. The last attribute, human competitive results, is in turn defined by a list of eight properties where each of them gives enough evidence to conclude competitiveness to results produced by the intellect of a human. This list includes concepts such as whether the results are pantentable, publishable in scientific journals or better then best known human solutions. GP3 reports 14 experiments by the authors where the they claim that GP produced results fulfilling one or more of these properties and thus are competitive with that of a skilled human such as an engineer, mathematician, designer or programmer. Examples of results with the "darwinian invention quality" include sorting networks, analogue electrical circuit synthesis and creation of motifs for protein family detection. Pointers are also given to human competitive solutions evolved by other researchers.

Overall there is no question that this is an important book putting the spotlight on one of the peak performing and most promising candidates for the general AI prize. There is no doubt that this book belongs in the standard library of all GP researchers or practitioners. This volumous book is a bit heterogeneous, probably stemming from the fact that is combined from a number of previously published papers with some new material. On the other hand is the volume important documentation of innovative work done by John Koza and his colleagues. In many place numerous pointers to work by other researchers are given but in the end I believe that the book would have a stronger case for presenting the GP state-of-the-art by including more references to similar research by other research groups.

However most important and intriguing thing about this book is the provocative questions raised concerning definitions and claims of human competitive performance, "Darwinian invention" and artificial intelligence - particularly whether we have already passed an important milestone in the history of AI - automatic programming.

Rating:
Summary: A very nice book on genetic programming.
Review: This excellent book gives a lengthy overview of this very important paradigm in programming. For newcomers to the field in particular, it gives a good overview. The use of Lisp code is a definite plus, as it is a language well suited to this type of programming. A fine book: buy it..it is well worth the price-L.C. (Global Mathematics, Inc).

Rating:
Summary: Why Should You Buy This Book???
Review: Why this book, when there are several shorter books on GP, and its principle author, John Koza, has written two other, more general and equally voluminous books on GP? This book addresses how to evolve program architecture, that's why! Living organisms didn't grow arms and eyes through simple mutation. It required more subtle genetic operators. Traditional genetic operators (as used in genetic algorithms) may be sufficient for evolving solutions to optimization problems where the structure if not the specifics of each solution is pretty much the same. But to effectively evolve program structures, you need architecture altering genetic operators. This book provides motivations in computer science, foundations in biology, and explanations in English.