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
