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