Print

Print


Dear Sean,

Thanks for the reply.

I did a really quick hack to see if your hypothesis held. It looks
like a stable sort is necessary but not sufficient to fix the
problem...at least a stable sort changes the answers...perhaps there
are other things that need to change as well. I'll leave it to the
experts. :D

Cheers,
Steve

Here are the old (abbreviated) results:

Generation 0.

Post-Evaluation
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)

Generation 1.

Post-Evaluation
     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

Generation 2.

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
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)
...

Generation 9.

Post-Evaluation
     Evaluated: T
     Fitness: f1091567616|9.0|i7|
     Tree 0:
      (C (B (B x x) x) (B (A (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (C x (C (B (A x) (C x x x)) (B (A x) x) (A (A x))) (B
(B (C x x x) (A x)) (B (A x) (C x x x)))) (A x)) (A (A (B x x)))) x)
x)) x)
     Evaluated: T
     Fitness: f1091567616|9.0|i7|
     Tree 0:
      (C (B (B x x) x) (B (A (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (A x) (A x)) (A (A (B x x)))) x) x)) x)
Post-Breeding
     Evaluated: F
     Fitness: f1091567616|9.0|i7|
     Tree 0:
      (C (B (B x x) x) (B (A (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (C x (C (B (A x) (C x x x)) (B (A x) x) (A (A x))) (B
(B (C x x x) (A x)) (B (A x) (C x x 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 (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (C x (C (B (A x) (C x x x)) (B (A x) x) (A (A x))) (B
(B (C x x x) (A x)) (B (A x) (C x x x)))) (A x)) (A (A (B x x)))) x)
x)) x)

Final.

Post-Evaluation
     Evaluated: T
     Fitness: f1091567616|9.0|i7|
     Tree 0:
      (C (B (B x x) x) (B (A (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (C x (C (B (A x) (C x x x)) (B (A x) x) (A (A x))) (B
(B (C x x x) (A x)) (B (A x) (C x x 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 (A x)) (B (C (A (C (B x x) (B x x) (C x
x x))) (B (C x (C x (C (B (A x) (C x x x)) (B (A x) x) (A (A x))) (B
(B (C x x x) (A x)) (B (A x) (C x x x)))) (A x)) (A (A (B x x)))) x)
x)) x)


Substituting the following code for the call to Quicksort.qsort() in
MuCommaLambdaBreeder:

            Arrays.sort( i,  new Comparator() {
                     public int compare( Object arg0, Object arg1) {
                         if ( gt( arg0, arg1)) return 1;
                         if ( lt( arg0, arg1)) return -1;
                         return 0;
                     }
                     public boolean gt(Object a, Object b) {
                         return ((Individual)a).fitness.betterThan
( ((Individual)b).fitness);
                     }
                     public boolean lt(Object a, Object b) {
                         return ((Individual)b).fitness.betterThan
( ((Individual)a).fitness);
                     }
                 });

I get:

Generation 0. Same as before

Post-Evaluation
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x x)

Generation 1. Same as before

Post-Evaluation
     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

Generation 2. THIS IS NEW...x stayed as the parent

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
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (C (A (C (A x) (C x x x) (A x))) x x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x

Generation 3. x stays again... or at least one of them does.

Post-Evaluation
     Evaluated: T
     Fitness: f1097859072|15.0|i1|
     Tree 0:
      (C (A (C (A x) (C x x x) (A x))) x x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x

Generation 4. x stays again.

Post-Evaluation
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (C (B (B (A x) (A x)) (C (A x) (B x x) x)) (A x) (A (C (A x) x
(A x))))
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x

Generation 5. UM...why wasn't the better guy taken?

Post-Evaluation
     Evaluated: T
     Fitness: f1094713344|12.0|i4|
     Tree 0:
      (C (B (B (A x) (A x)) (C (A x) (B x x) x)) (A x) (A (C (A x) x
(A x))))
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (B x (A (C (A x) (C x x x) (A x))))
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x

...

Generation 9.

Post-Evaluation
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (A x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      x
Post-Breeding
     Evaluated: F
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (C x (B (B (A x) x) (B (C x x x) (B x x))) x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (A x)

Final.

Post-Evaluation
     Evaluated: T
     Fitness: f1095761920|13.0|i3|
     Tree 0:
      (C x (B (B (A x) x) (B (C x x x) (B x x))) x)
     Evaluated: T
     Fitness: f1098907648|16.0|i0|
     Tree 0:
      (A x)


On Sep 18, 2005, at 3:49 PM, Sean Luke wrote:

> 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 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