Odyssy 20001

The book is sky rocketing. Amazingly, 8 months (to the day!) since its launch, today we passed the 20,000 copies limit (hitting 20001 to the last check, hence the title of this post). Of these approx 98.7% are (genuine) downloads and 1.3% paper copies.

Many thanks!

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.

10,000 downloads

Yesterday, the field guide reached 10,000 downloads, just over two months from going live, averaging 150 downloads a day. Of course, as the graph at the bottom of the blog shows, many downloads happened in the first few weeks. So, in the last few weeks we seem to be averaging something like 50 downloads a day. Pretty amazing nonetheless! Many thanks!

The Field Guide goes HTML

We have produced an HTML version of the book. This is available here. We used htlatex to do the main conversion from Latex to HTML and then htmldoc to split the resulting huge file into chuncks of more reasonable size. Many manual changes have then been necessary. The result is not perfect, but we think it may be good enough to be useful.

Happy browsing!

The Field Guide is available on Amazon!

Over the weekend the Field Guide apparently completed its complex journey into the land of major on-line retailers and is now available via Amazon and several other on-line vendors.

Bug in TinyGP Java Code

Sander Land found a bug in the constructor "tiny_gp" of the TinyGP system described in appendix B: the "x" array is initialized (lines 345-346) after the population is (line 344), causing invalid fitness evaluations during the initialization of the population, thereby wasting the first generation. The mistakes has been fixed in the code available here. Many thanks Sander (and apologies to all users).

Table of Contents

1 Introduction 1
1.1 Genetic Programming in a Nutshell . . . . . . . . . . . . . . . 2
1.2 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Overview of this Field Guide . . . . . . . . . . . . . . . . . . 4

Part I Basics 7

2 Representation, Initialisation and Operators in Tree-based GP 9
2.1 Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Initialising the Population . . . . . . . . . . . . . . . . . . . . 11
2.3 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Recombination and Mutation . . . . . . . . . . . . . . . . . . 15

3 Getting Ready to Run Genetic Programming 19
3.1 Step 1: Terminal Set . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Step 2: Function Set . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 Closure . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.2 Sufficiency . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3 Evolving Structures other than Programs . . . . . . . 23
3.3 Step 3: Fitness Function . . . . . . . . . . . . . . . . . . . . . 24
3.4 Step 4: GP Parameters . . . . . . . . . . . . . . . . . . . . . 26
3.5 Step 5: Termination and solution designation . . . . . . . . . 27

4 Example Genetic Programming Run 29
4.1 Preparatory Steps . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Step-by-Step Sample Run . . . . . . . . . . . . . . . . . . . . 31
4.2.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.2 Fitness Evaluation . . . . . . . . . . . . . . . . . . . . 32
4.2.3 Selection, Crossover and Mutation . . . . . . . . . . . 32
4.2.4 Termination and Solution Designation . . . . . . . . . 35

Part II Advanced Genetic Programming 37

5 Alternative Initialisations and Operators in Tree-based GP 39
5.1 Constructing the Initial Population . . . . . . . . . . . . . . . 39
5.1.1 Uniform Initialisation . . . . . . . . . . . . . . . . . . 40
5.1.2 Initialisation may Affect Bloat . . . . . . . . . . . . . 40
5.1.3 Seeding . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.2 GP Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.2.1 Is Mutation Necessary? . . . . . . . . . . . . . . . . . 42
5.2.2 Mutation Cookbook . . . . . . . . . . . . . . . . . . . 42
5.3 GP Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.4 Other Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 46

6 Modular, Grammatical and Developmental Tree-based GP 47
6.1 Evolving Modular and Hierarchical Structures . . . . . . . . . 47
6.1.1 Automatically Defined Functions . . . . . . . . . . . . 48
6.1.2 Program Architecture and Architecture-Altering . . . 50
6.2 Constraining Structures . . . . . . . . . . . . . . . . . . . . . 51
6.2.1 Enforcing Particular Structures . . . . . . . . . . . . . 52
6.2.2 Strongly Typed GP . . . . . . . . . . . . . . . . . . . 52
6.2.3 Grammar-based Constraints . . . . . . . . . . . . . . . 53
6.2.4 Constraints and Bias . . . . . . . . . . . . . . . . . . . 55
6.3 Developmental Genetic Programming . . . . . . . . . . . . . 57
6.4 Strongly Typed Autoconstructive GP with PushGP . . . . . 59

7 Linear and Graph Genetic Programming 61
7.1 Linear Genetic Programming . . . . . . . . . . . . . . . . . . 61
7.1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . 61
7.1.2 Linear GP Representations . . . . . . . . . . . . . . . 62
7.1.3 Linear GP Operators . . . . . . . . . . . . . . . . . . . 64
7.2 Graph-Based Genetic Programming . . . . . . . . . . . . . . 65
7.2.1 Parallel Distributed GP (PDGP) . . . . . . . . . . . . 65
7.2.2 PADO . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2.3 Cartesian GP . . . . . . . . . . . . . . . . . . . . . . . 67
7.2.4 Evolving Parallel Programs using Indirect Encodings . 68

8 Probabilistic Genetic Programming 69
8.1 Estimation of Distribution Algorithms . . . . . . . . . . . . . 69
8.2 Pure EDA GP . . . . . . . . . . . . . . . . . . . . . . . . . . 71
8.3 Mixing Grammars and Probabilities . . . . . . . . . . . . . . 74

9 Multi-objective Genetic Programming 75
9.1 Combining Multiple Objectives into a Scalar Fitness Function 75
9.2 Keeping the Objectives Separate . . . . . . . . . . . . . . . . 76
9.2.1 Multi-objective Bloat and Complexity Control . . . . 77
9.2.2 Other Objectives . . . . . . . . . . . . . . . . . . . . . 78
9.2.3 Non-Pareto Criteria . . . . . . . . . . . . . . . . . . . 80
9.3 Multiple Objectives via Dynamic and Staged Fitness Functions 80
9.4 Multi-objective Optimisation via Operator Bias . . . . . . . . 81

10 Fast and Distributed Genetic Programming 83
10.1 Reducing Fitness Evaluations/Increasing their Effectiveness . 83
10.2 Reducing Cost of Fitness with Caches . . . . . . . . . . . . . 86
10.3 Parallel and Distributed GP are Not Equivalent . . . . . . . . 88
10.4 Running GP on Parallel Hardware . . . . . . . . . . . . . . . 89
10.4.1 Masterslave GP . . . . . . . . . . . . . . . . . . . . . 89
10.4.2 GP Running on GPUs . . . . . . . . . . . . . . . . . . 90
10.4.3 GP on FPGAs . . . . . . . . . . . . . . . . . . . . . . 92
10.4.4 Sub-machine-code GP . . . . . . . . . . . . . . . . . . 93
10.5 Geographically Distributed GP . . . . . . . . . . . . . . . . . 93

11 GP Theory and its Applications 97
11.1 Mathematical Models . . . . . . . . . . . . . . . . . . . . . . 98
11.2 Search Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
11.3 Bloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11.3.1 Bloat in Theory . . . . . . . . . . . . . . . . . . . . . 101
11.3.2 Bloat Control in Practice . . . . . . . . . . . . . . . . 104

Part III Practical Genetic Programming 109

12 Applications 111
12.1 Where GP has Done Well . . . . . . . . . . . . . . . . . . . . 111
12.2 Curve Fitting, Data Modelling and Symbolic Regression . . . 113
12.3 Human Competitive Results the Humies . . . . . . . . . . . 117
12.4 Image and Signal Processing . . . . . . . . . . . . . . . . . . . 121
12.5 Financial Trading, Time Series, and Economic Modelling . . 123
12.6 Industrial Process Control . . . . . . . . . . . . . . . . . . . . 124
12.7 Medicine, Biology and Bioinformatics . . . . . . . . . . . . . 125
12.8 GP to Create Searchers and Solvers Hyper-heuristics . . . . 126
12.9 Entertainment and Computer Games . . . . . . . . . . . . . . 127
12.10The Arts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.11Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

13 Troubleshooting GP 131
13.1 Is there a Bug in the Code? . . . . . . . . . . . . . . . . . . . 131
13.2 Can you Trust your Results? . . . . . . . . . . . . . . . . . . 132
13.3 There are No Silver Bullets . . . . . . . . . . . . . . . . . . . 132
13.4 Small Changes can have Big Effects . . . . . . . . . . . . . . 133
13.5 Big Changes can have No Effect . . . . . . . . . . . . . . . . 133
13.6 Study your Populations . . . . . . . . . . . . . . . . . . . . . 134
13.7 Encourage Diversity . . . . . . . . . . . . . . . . . . . . . . . 136
13.8 Embrace Approximation . . . . . . . . . . . . . . . . . . . . . 137
13.9 Control Bloat . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
13.10Checkpoint Results . . . . . . . . . . . . . . . . . . . . . . . . 139
13.11Report Well . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
13.12Convince your Customers . . . . . . . . . . . . . . . . . . . . 140

14 Conclusions 141

Part IV Tricks of the Trade 143

A Resources 145
A.1 Key Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
A.2 Key Journals . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
A.3 Key International Meetings . . . . . . . . . . . . . . . . . . . 147
A.4 GP Implementations . . . . . . . . . . . . . . . . . . . . . . . 147
A.5 On-Line Resources . . . . . . . . . . . . . . . . . . . . . . . . 148

B TinyGP 151
B.1 Overview of TinyGP . . . . . . . . . . . . . . . . . . . . . . . 151
B.2 Input Data Files for TinyGP . . . . . . . . . . . . . . . . . . 153
B.3 Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
B.4 Compiling and Running TinyGP . . . . . . . . . . . . . . . . 162

Bibliography 167

Index 225

8,000 downloads reached during the weekend

Within just over a month since its launch, the book has been downloaded over 8,000 times!
Many thanks!

The Field Guide appears in ACM's Technews, reddit, numerous blogs

Some recent Field Guide sightings include a nice mention in ACM's Technews roundup for 14 Apr 2008 and a listing by some kind (and unknown, to us) folks on reddit (here and there).

Other recent bloggers to mention the book include

• Postmaster


• Andrea Valente on Biscotti Danesi


• Dan (the author of the Watchmaker Framework for EC)


• JJ Merelo (who says that we were on the del.icio.us hotlist on 12 Apr!)


• theKit (who suggests using GP to evolve 3D designs using RepRap, an Open Source Replicating Rapid Prototyping 3d printer)


• The Mad Scientist

Thanks to everyone for the links and support. To date (about 3 weeks since release) there have been 6873 downloads of the book! Questions and comments always welcome in the comments here, or over in our discussion group.

Over 5,000 downloads!

Man, I go away for a few days of vacation, and the downloads more than double! We're now at just over 5,000 downloads of the book, and 12 more printed copies were ordered in the last five days as well.

Just as I was leaving, Jennifer Willies also posted a ton of good photos from the EvoStar event, including a nice shot of the three Field Guide authors and our cover artist.

More photos from the Field Guide unveiling

Antje Schwefel shared some of her photos from EuroGP, including the shot above of us (Bill, Tyler, Nic, and Riccardo, left to right) posing in our Field Guide shirts with Evelyne Lutton. Thanks to Antje for the photo!

The EvoStar 2008 site also has a link now for EvoStar photos that is in fact a pointer to the "evostar" tag on Flickr. These are currently dominated by the previously mentioned photos from JJ Merelo, and Tyler and myself, but there are also some nice photos from La Singularidad Desnuda, including the nice example of Riccardo's autographing handiwork below.



2,151 downloads and counting!

Over 2,000 downloads!

The PDF version of the Field Guide has now been downloaded 2,049 times from Lulu. Many thanks to everyone who's helped support the book!

We've created a mailing list/discussion group for the Field Guide

There have now been over 1,800 downloads of the Field Guide, and we're beginning to get some good questions, comments, and suggestions from readers. It seemed like we probably wanted to set up some sort of system to help manage and archive that data stream, so we've created a discussion group for the Field Guide: http://groups.google.co.uk/group/field-guide-to-genetic-programming.

Feel free to subscribe if you've got feedback on the book that you'd like to share, or you'd just like to see other people's feedback. I would assume that the traffic on the list will remain light, but that's really up to you folks.

---

Subscribe to Field Guide to Genetic Programming

Email:

Visit this group

Over 1,500 downloads!

As of mid-day on Tuesday (so just under a week after the official release), we've just topped 1,500 downloads of the Field Guide! We've also sold 20 printed copies, plus the 50 we sold at the EvoStar unveiling.

J.K. Rowling doesn't have much to worry about yet on the best seller lists, but we're still quite excited by the number of people that have chosen to download the book - thanks!

Field Guide sightings!

Several kind folks have put in a plug for the Field Guide on-line:

• Paul Myers on the prominent biology blog Pharyngula
• On Paulus De Blogkabouter
  
• Paul Wiegand on the Natural Computation and Coadaptive System Laboratory blog
• Pier Luca Lanzi on the Illinois GA Lab blog

Many thanks to all these folks for helping spread the word. Given our non-standard publishing and distribution model, we're particularly dependent on this sort of word of mouth support. Feel free to let us know if you've posted a plug for the book (in the comments or authors AT gp-field-guide DOT org DOT uk).

We're also looking for photos (like the one above from JJ Merelo) from the grand unveiling at EvoStar/EuroGP Wednesday in Naples, so please pass along those as well.

Photos from the grand unveiling

Tyler Hutchison (the Field Guide's cover artist) and I have uploaded all our EuroGP/EvoStar 2008 photos to Flickr. This includes several shots by Tyler of the grand unveiling of the Field Guide, including this photo of Bill and Wolfgang Banzhaf discussing the book. We also have photos from other EvoStar events such as Bill receiving his EvoStar award, and shots around the city of Naples.

This initial upload is without any cleaning or editing, so there's a fair amount of repetition, etc., but hopefully some folks will find it useful.

I know of one other batch of EvoStar photos that has already been uploaded: JJ Merelo has a nice EvoStar set on Flickr, and a slightly larger set that includes his sightseeing around Naples. If you have any photos from any part of the EvoStar event that you'd be willing to share, feel free to post a link in a comment here, or send us an e-mail at "authors AT gp-field-guide DOT uk DOT org". Being the vain creatures that we are, we're of course especially interested in photos of the book release and autographing :-), but any photos from the event are super cool!

A huge thanks to all our proofreaders!

It takes a village to raise a book, and we were extremely fortunate to have an enthusiastic and talented pool of proofreaders. They went through the Field Guide, helping us finding the inevitable typos, and pointing out places where our presentation didn't sparkle quite as much as we thought it did. We spent almost all of the last week before we wrapped the book simply processing their many comments. While I'm sure we didn't address every one of their suggestions, there were hundreds of changes made based on that feedback, and there's no question that the book is better for their hard work and generous efforts.

To quote from the acknowledgements:

We had the invaluable assistance of many people, and we are very grateful for their individual and collective efforts, often on very short timelines. Rick Riolo, Matthew Walker, Christian Gagne, Bob McKay, Giovanni Pazienza, and Lee Spector all provided useful suggestions based on an early technical report version. Yossi Borenstein, Caterina Cinel, Ellery Crane, Cecilia Di Chio, Stephen Dignum, Edgar Galván-López, Keisha Harriott, David Hunter, Lonny Johnson, Ahmed Kattan, Robert Keller, Andy Korth, Yevgeniya Kovalchuk, Simon Lucas, Wayne Manselle, Alberto Moraglio, Oliver Oechsle, Francisco Sepulveda, Elias Tawil, Edward Tsang, William Tozier and Christian Wagner all contributed to the final proofreading festival. Their sharp eyes and hard work did much to make the book better; any remaining errors or omissions are obviously the sole responsibility of the authors.

Thanks again to everyone who helped us get the book out the door!

Bill Langdon receives prestigious EvoStar award!

On Thursday night at the EvoStar banquet in Naples, Bill Langdon (along with Marc Schoenauer) were the fourth and fifth recipients of the prestigious EvoStar award for Outstanding Contributions to the field of Evolutionary Computation in Europe. This is in recognition of his numerous contributions in such areas as the planning and running of conferences and workshops, editing of journals and proceedings, and creation and management of key resources such as the GP Bibliography.

The previous recipients of the award include Field Guide author Riccardo Poli, as well as Jennifer Willies (the indefatigable admin that makes EvoStar happen year after year) and Wolfgang Banzhaf.

Congratulations to Bill - well done and well deserved! I'll shortly be posting photos of Bill receiving his award.

One heck of a party!

Last night's unveiling of A Field Guide to Genetic Programming was a huge success! We had one of the poster "stalls" with 50 copies of the book that we'd purchased from Lulu as our initial "print run". We were wearing cool t-shirts sporting that wonderful cover, had the nice poster shown to the right, and even had spiffy postcards with the cover to give away.

The book was a big hit with the Evo* crowd, and we sold out the full set of 50 pretty quickly. Lots of folks had us autograph their copies, many of which are now destined to be collector's items with the signatures of all three of the authors. Some even have the signature of Tyler Hutchison, who did the nifty cover art for us and helped a lot with the roll-out.

There were tons of photos taken at our booth, including candids of us signing and working the crowd, and posed shots with our cool Field Guide shirts. People have promised to send us photos and links, so check back in the next week or two for some of the finest in EC book release amateur photojournalism! (And if you've got a photo from the event, or a nifty shot of your copy in its place of pride on your bookshelves, please pass it along.)

As mentioned before, the book is now officially released and available to any and all via lulu.com, both in an inexpensive printed form (what we were selling last night) and as a free downloadable PDF.

So go check it out - 50 whole Field Guide fans can't be wrong!

The book is now available!

The grand unveiling is going on as I type here at EuroGP 2008 in Naples. Head over to Lulu.com to purchase an inexpensive printed copy or download the free PDF version!

Almost ready for EuroGP!

We've ordered box or two of advance copies (a privilege of being the authors). They look really nice, and we're quite excited about the grand unveiling on Wednesday at EuroGP! For those of you coming to Naples, definitely stop by our table at the poster session that night -- you'll be able to check out printed copies and maybe even score a postcard featuring that wonderful cover :-).

Whether you're coming to EuroGP or not, we'll be "turning on" the Lulu site Wednesday, so people can buy printed copies and download the PDF for free. And as a teaser, the image above is the entire book, just really, really small! If you click on it you can see it a little bigger, but I still recommend waiting a few days for the Real Deal.

It's nearly ready

We ordered our first test copy a week or two ago just so we could see what the printing would look like from Lulu, what the cover would look like, and how some of our graphs and diagrams would turn out. It was quite exciting to see an actual copy, even if the insides where incomplete and in serious need of the proofreading that was to follow. It somehow made it all seem more real.

Things are currently on track for a late March release. Stay tuned for more details!