Print

Print


I'm looking at the paper described below and I'm totally convinced  
that it's not correct.  If "Cumulative Frequency" is to be taken as  
"number of 100% correct solutions", then the values for Genetic  
Programming in the Santa Fe Trail (Figure 5A) are absurdly high.  If  
you do GP with 1000 individuals for about 50 runs, you'll get a  
correct solution roughly once in 20 times.  As you can see, the  
paper's values are *way* different from that.  Likewise, Symbolic  
Regression does not have nearly the success rates given.  Did some  
double-checking with lil-gp to make sure.

I am inclined to presume that what the paper meant, erroneously, was  
some measure of fitness, maybe mean adjusted fitness (1/(1+f)).  Also  
I note that Ant was run for 600 steps rather than 400, which should  
perform somewhat better.  There's some history there: Koza ran for 600  
timesteps but reported it as 400 incorrectly and most of the GP  
literature is based on 400, which is why ECJ's default is 400 (as is  
lil-gp's default).

Now just because this paper seems to have interpretation issues  
doesn't mean that ECJ doesn't have bugs in the brand-new GE facility  
or poor initial choices for parameter settings.  Our goal was to get  
GE working properly and consistently, not to tune it.  So some  
examination would be welcome!

Sean

On Feb 14, 2011, at 1:32 PM, K S wrote:

> Hi Matthew,
> I'm currently at work right now and I don't have time to completely  
> look over your e-mail.  However, the Santa Fe ant demo is included  
> in ECJ under ec.app.ant.  Please checkout that and koza.params under  
> ec.gp.koza.
>
> > Date: Mon, 14 Feb 2011 07:08:01 -0500
> > From: [log in to unmask]
> > Subject: Grammatical Evolution Santa Fe Experiment Problem
> > To: [log in to unmask]
> >
> > Hello,
> > It is great that ecj now has a grammatical evolution  
> implementation. But I
> > am having trouble replicating the results of a basic GE  
> experiment. I am
> > wondering if anyone else has had this problem, can see any  
> mistakes in what
> > I have done, or know of a reason for this.
> > I refer to the results of this paper, for the santa fe ant trail:
> > O'Neill M., Ryan C. Grammatical Evolution. IEEE Transactions on  
> Evolutionary
> > Computation, Vol. 5 No.4, August 2001.
> >
> > In this paper, over 100 runs, GE finds the correct code in  
> approximately 90
> > of the runs. However, my results are consistently around the 25  
> mark.
> >
> > I would normally put any discrepancies down to small differences in
> > implementation between O'Neill's code and ecj, but the results are  
> so
> > dramatically different that it is probably not due to this.
> >
> > My parameters are copied below. You will see I have tried to match  
> the
> > grammar that they use, and use the same genetic operators in the  
> pipeline.
> >
> > Thanks for your help.
> >
> > #Grammar file myant.grammar
> > <start> ::= <code>
> > <code> ::= <line> | (progn2 <code> <line>)
> > <line> ::= (if-food-ahead <line> <line>) | <op>
> > <op> ::= (left) | (right) | (move)
> >
> > #Initialisation
> > pop.subpop.0.size = 500
> > breed.elite.0 = 50
> > pop.subpop.0.species.genome-size = uniform
> > pop.subpop.0.species.min-initial-size = 5
> > pop.subpop.0.species.max-initial-size = 20
> >
> > #GA pipelines
> > pop.subpop.0.species.pipe = ec.vector.breed.GeneDuplicationPipeline
> > pop.subpop.0.species.pipe.likelihood = 0.01
> > pop.subpop.0.species.pipe.source.0 =  
> ec.vector.breed.VectorMutationPipeline
> > pop.subpop.0.species.pipe.source.0.likelihood = 1
> > pop.subpop.0.species.mutation-prob = 0.01
> > pop.subpop.0.species.pipe.source.0.source.0 =
> > ec.vector.breed.ListCrossoverPipeline
> > pop.subpop.0.species.pipe.source.0.source.0.prob = 1
> > pop.subpop.0.species.pipe.source.0.source.0.likelihood = 0.9
> > pop.subpop.0.species.pipe.source.0.source.0.source.0 =
> > ec.select.TournamentSelection
> > pop.subpop.0.species.pipe.source.0.source.0.source.1 = same
> > pop.subpop.0.species.pipe.source.0.source.0.toss = false
> >
> > #function set
> > gp.fs.0.size = 5
> > gp.fs.0.func.0 = ec.app.ant.func.Left
> > gp.fs.0.func.0.nc = nc0
> > gp.fs.0.func.1 = ec.app.ant.func.Right
> > gp.fs.0.func.1.nc = nc0
> > gp.fs.0.func.2 = ec.app.ant.func.Move
> > gp.fs.0.func.2.nc = nc0
> > gp.fs.0.func.3 = ec.app.ant.func.IfFoodAhead
> > gp.fs.0.func.3.nc = nc2
> > gp.fs.0.func.4 = ec.app.ant.func.Progn2
> > gp.fs.0.func.4.nc = ncboth