First time that competitions have been associated with GECCO
Aim: improve participation for future years
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!
|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!!!
Winner: Jason Brownlee with JB_Smart_Function_v1.1, which achieved a mean fitness of 1997.
This was an extremely challenging a-life game - perhaps it was too hard. While this contest generated the most expression of interest, this failed to translate into a good number of entries.
Simple idea: a set of cells must acquire as much cell mass (by eating food and not burning too much energy) within the given number of time steps.
Twist: cell division: when designing a controller, you don't know how many cells will be on the play area.
Twist: Continuous dynamics + non-linear controllers: tends to produce highly chaotic systems, and unexpected behaviours
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 :
An entry consisted of a cell controller, specified as a directed graph function graph
Hence, GP-style expression-trees and neural networks could be submitted.
BUT: the set of functions was restricted.
The game used an on-line league table - so contestants could see exactly how well their entry was doing compared to the other ones.
This might have caused an 'auction' effect - where contestants delayed their entries to the last minute, to avoid 'showing their had too early' - but in the event this did not happen.
I provided a sample directed graph controller, constructed from an evolved perceptron, and a hand-coded controller.
The winning entry was submitted by Jason Brownlee using ECJ to evolve the weights of a hand-designed neural net - and behaved similarly to a hand-coded Java controller supplied in the developer kit.
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).
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
Orlando Cicchello and Stefan
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)
Running the competitions has been a useful exercise, but in future the aim will be to attract more entries.
Suggestions for future years:
Pick problems that are more 'bread and butter' for GECCO community. For example, symbolic regression?
Publicise and finalise competitions further in advance (e.g. Summer 2004 for GECCO 2005)