Print

Print


Hi Steve.  If your information is correct, it looks to me that the
problem is with QuickSort not being a stable sort.  ECJ's ES library
first sorts the population based on fitness, then uses the first lambda
individuals in the population array as the new parent pool.  Because it
uses QuickSort, equal individuals do not necessarily sort the same way
in the pool.

ECJ's minimum version of Java is now 1.2, meaning we can probably toss
out our QuickSort class and use java.util.List's sort routines,
including stable sorts based on MergeSort.  It'll take us a few days,
but let us see if we can get an upgraded version of at least the ES
package for you fairly soon.

Sean

On Sep 18, 2005, at 3:22 PM, Steve Butcher (Steve-O) wrote:

> Dear Sean et al.
>
> I wish that the List sent you a copy of your own message so that you
> could reply to it and keep everything in the same thread.
>
> In any case, some further investigation into my problem appears to
> reveal that the current logic for ES does not take into account the
> possibility of Individuals having the same fitness and properly
> maintaining the distinction of "parent" and "child" as a result. This
> leads to peculiar or at least counterintuitive results because there
> is genetic drift that is not associated with clear cut improvements in
> fitness.
>
> As I understand the canonical 1 + 1 ES, the current "parent" solution
> is mutated to create a candidate "child" solution. If the child
> solution is better, the parent solution is discarded otherwise the
> parent solution is retained. However, the current ES logic appears to
> discard the parent if they are of equal fitness. This is probably not
> the desired result as it sends you down a possibly different
> evolutionary path. It is at least unexpected.
>
> I have included example output and my params settings. Whether or not
> this is a bug, I guess the question is...how do I fix it to work the
> way I would expect?
>
> As always, your help and assistance is greatly appreciated.
>
> Cheers,
> Steve
>
> "X-Y" is from the method xYStatistics() so that "Pre-Evaluation" means
> that it was output during the call to preEvaluationStatistics(...).
>
> Initial Generation. Only Post-Breeding is shown. I would infer from
> this that x was a mutation on (B x x) since (B x x) was the initial
> individual.
>
> Post-Breeding
>     Evaluated: F
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (B x x)
>
> 1st Generation or "Climb" Everything is fine up until Post-Breeding.
> Post-Evaluation shows that x is no better than (B x x) but in
> Post-Breeding, I'm shown that (C (B (B x x) x) (B (C (A x) x (A x)) (B
> (C x x x) x)) x) is a mutation on x.
>
> Pre-Evaluation
>     Evaluated: F
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (B x x)
> Post-Evaluation
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (B x x)
> Pre-Breeding
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (B x x)
> Post-Breeding
>     Evaluated: F
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
>
> 2nd Generation or "Climb" Clearly (B x x) has been replaced by a not
> worse child. I would think that ES means that parents are only
> replaced by a better child. However, in this case where the child was
> clearly better, it correctly replaces its parent (Post-Breeding (C (B
> (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x) shows replacing
> x).
>
> Pre-Evaluation
>     Evaluated: F
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
> Post-Evaluation
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
> Pre-Breeding
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
>     Evaluated: T
>     Fitness: f1098907648|16.0|i0|
>     Tree 0:
>      x
> Post-Breeding
>     Evaluated: F
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x x
> x) x)) x)
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
>
> 3rd Generation or "Climb" It happens again. Both the parent and child
> of the last climb have the same fitness but the child replaces the
> parent. (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x
> x x) x)) x) replaces (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x
> x) x)) x).
>
> Pre-Evaluation
>     Evaluated: F
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x x
> x) x)) x)
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
> Post-Evaluation
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x x
> x) x)) x)
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
> Pre-Breeding
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x x
> x) x)) x)
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (C (A x) x (A x)) (B (C x x x) x)) x)
> Post-Breeding
>     Evaluated: F
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C (A (C
> (B x x) (B x x) (C x x x))) (B (C x (A x) (A x)) (A x)) x) x)) x)
>     Evaluated: T
>     Fitness: f1091567616|9.0|i7|
>     Tree 0:
>      (C (B (B x x) x) (B (A (C (A x) (C x (C x x x) x) x)) (B (C x x
> x) x)) x)
>
> my.params
>
> pop.subpop.0.size =                     2
> es.mu.0 =                               1
> es.lambda.0 =                           1
> breed =                                 ec.es.MuPlusLambdaBreeder
>
> pop.subpop.0.fitness =                  ec.gp.koza.KozaFitness
> pop.subpop.0.duplicate-retries =        0
> pop.subpop.0.species =                   ec.gp.GPSpecies
> pop.subpop.0.species.ind =              ec.gp.GPIndividual
> pop.subpop.0.species.pipe =             ec.gp.koza.MutationPipeline
> pop.subpop.0.species.pipe.source.0 =    ec.es.ESSelection
>
>
>
> -----------------------------------------------------------------------
> ---------
> On two occasions I have been asked, 'Pray, Mr. Babbage, if you put
> into the machine wrong figures, will the right answers come out?' I am
> not able rightly to apprehend the kind of confusion of ideas that
> could provoke such a question. -- Charles Babbage
>
>
>