GECCO 2004 Competitions Summary

Entry Statistics

This table categorises the competitions, and shows how the expressions of interest (i.e. number of people to email me in advance) translated into actual entries.  Note that in the case of Tiny GP, there were more entries than expressions of interest!

 
Competition Category Date Ready Interest Entries
Cellz a-life March 2004 6 1
Noisy DFA machine learning Feb 2004 4 3
Tiny GP human programming contest Feb 2004 5 7

The fact that there were more entries for the programming contest than for the contests that actually tested evolutionary algorithms in action might be considered ironic!!!

Cellz

Winner: Jason Brownlee with JB_Smart_Function_v1.1, which achieved a mean fitness of 1997.

Fitness functions for this game are a bit expensive to compute (e.g. tens of ms per evaluation), and extremely noisy - the following shows the performance of a random mutation hill-climber, for example - and this is taking the mean of 10 simulation runs for each fitness evaluation :

The state of the league table at the close of the contest (May 28th 2004) is shown here (note that the on-line league is being kept alive, so may differ when you read this).

Noisy DFA

Results: Only the size 10 problem was solved

DFA (Deterministic Finite Automaton) induction is a classic machine learning problem, and has been studied for over thirty years (at least).

Heuristic state merging algorithms start by building the prefix tree acceptor for the training set.  This perfectly memorises the training data, but handles nothing else.  State merges are then performed to reduce the size of the machine (while remaining consistent with the training data), and consequently increase its generality. 

The problem can be solved easy given a complete sample of training data (all strings up to a certain length, which depends on the depth of the machine) but becomes harder as the training data gets sparser.  Nonetheless, heuristic state merging algorithms can successfully learn machines with hundreds of states from sparse data.

The twist for the GECCO contest was to add a high level of noise to the data.  The feeling was that evolutionary algorithms should be better able to cope with noise than heuristic state merging methods.

This was borne out with the results, in that the statistical state merging algorithm was unable to solve the size 10 problem.

Results on size 10 problem

Entry Mean S.D. Max nSuccess
Gomez        
GAuGE        
RPNI*        

 

Further reading:

Orlando Cicchello and Stefan C. Kremer
Inducing Grammars from Sparse Data Sets:
A Survey of Algorithms and Results

Journal of Machine Learning Research 4 (2003) 603-632
 

Marc Sebban and Jean-Christophe Janodet
On State Merging in Grammatical Inference: A Statistical Approach for Dealing with Noisy Data
Proceedings of International Conference on Machine Learning (2003)

Tiny GP

 

Summary: 

Running the competitions has been a useful exercise, but in future the aim will be to attract more entries. 

Suggestions for future years: