Java error: "Comparison method violates its general contract!"

Question

I have this code:

package org.optimization.geneticAlgorithm;
import org.optimization.geneticAlgorithm.selection.Pair;

public abstract class Chromosome implements Comparable<Chromosome> {
    public abstract double fitness();
    public abstract Pair<Chromosome> crossover(Chromosome parent);
    public abstract void mutation();
    public int compareTo(Chromosome o) {
        int rv = 0;
        if (this.fitness() > o.fitness()) {
            rv = -1;
        } else if (this.fitness() < o.fitness()) {
            rv = 1;
        }
        return rv;
    }
}

And every time I run this code I get this error:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:835)
at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:453)
at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:376)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:182)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:146)
at java.util.Arrays.sort(Arrays.java:472)
at java.util.Collections.sort(Collections.java:155)
at org.optimization.geneticAlgorithm.GeneticAlgorithm.nextGeneration(GeneticAlgorithm.java:74)
at org.optimization.geneticAlgorithm.GeneticAlgorithm.execute(GeneticAlgorithm.java:40)
at test.newData.InferenceModel.main(InferenceModel.java:134)

I use OpenJDK7u3 and I return 0 when the objects are equal. Can someone explain this error to me?

Answer 1

You could get into that situation if you have any NaN values:

For example:

public class Test
{
    public static void main(String[] args) {
        double a = Double.NaN;
        double b = Double.NaN;
        double c = 5;

        System.out.println(a < b);
        System.out.println(a > b);
        System.out.println(b < c);
        System.out.println(c < b);
    }
}

All of these print false. So you could end up in a situation where two non-NaN values were both deemed "equal" to NaN, but one was greater than the other. Basically, you should work out how you want to handle NaN values. Also check that that really is the problem, of course... do you really want NaN values for your fitness?

Answer 2

Most probably your fitness function is broken, in one of two ways:

1. It doesn't always return the same value when called on the same object.
2. It could return NaNs. Your compareTo() is not transitive in the presence of NaNs, as explained by Jon Skeet.

You could rewrite your comparison function using Double.compare():

public int compareTo(Chromosome o) {
    return Double.compare(o.fitness(), this.fitness());
}

This requires less code and takes care of corner cases (NaNs, the negative zero etc). Of course, whether these corner cases should be arising in the first place is for you to decide and address.