About the book

Robot with transparent background A Field Guide to Genetic Programming (ISBN 978-1-4092-0073-4) is an introduction to genetic programming (GP). GP is a systematic, domain-independent method for getting computers to solve problems automatically starting from a high-level statement of what needs to be done. Using ideas from natural evolution, GP starts from an ooze of random computer programs, and progressively refines them through processes of mutation and sexual recombination, until solutions emerge. All this without the user having to know or specify the form or structure of solutions in advance. GP has generated a plethora of human-competitive results and applications, including novel scientific discoveries and patentable inventions.

The book is freely downloadable under a Creative Commons license as a PDF and low cost printed copies can be purchased from lulu.com. This web site will be used for information relating to the book, and other pertinent announcements. We also have a discussion group for questions and conversation related to the book.

Tuesday 18 November 2008

A (potential) bug in TinyGP

Many thanks to Muhammad Atif Azad who found a bug in my implementation of the grow method. Quoting from his email:

The 'grow' function returns -1 if we go past the maximum size limit. Consider the following line of code:

return( grow( buffer, grow( buffer, pos+1, max,depth-1), max,depth-1 ) );

Let's say the nested grow returns -1. The outer grow accepts it for 'pos' i.e. index to next location in the tree to grow. There is no check inside the function grow against (pos == -1). Thus, it would raise a run time exception if used.

The reason it may not have occurred so far may be that we reach the depth constraint earlier than the size limit.

Indeed Atif is right: since by default MAX_LEN is set to 10,000, in order for the bug to occur one needs to use very big initial maximum depths so that individuals with more than 10,000 nodes may be created.

The online version of TinyGP (available here) has a fix for this potential bug.

PS: In the original version of TinyGP, the code to perform point mutation replaced terminals with variables. This implied a bias in that random constants were actively removed from the population when mutation was switched on. Atif pointed this out to me recently. The current version of TinyGP does not have this bias.

No comments: