Galapagos
A Genetic Algorithm Framework in Java
Home

...by Andy Meneely
in his Senior Project at Calvin College.

There are some problems in Genetic Algorithms that don't use a "fitness" simply because their ability to solve the problem cannot be quantified. In this case, selection operators like Tournament in Galapagos work by only comparing genomes. Galapagos provides this flexibility, but there's an important caveat: your comparing must be transitive.

Java's Comparator and Comparable interface is used throughout the Galapagos Framework, but it makes an assumption which is very important to note. Every time a Genome is used as either a Comparator or a Comparable, the compare operation MUST be transitive. That is, if object A is greater than object B, and B greater than C, then A MUST be greater than C.

The reason that Comparators and Comparables must be transitive (other than following Java's wishes) is that Java's sorting mechanism uses an object's Comparator and it assumes transitivity. Just think that if you had three objects A,B, and C and if A>B, B>C, and C>A. How do you sort those? You can't, and Java's sorting mechanism will either go into an infinite loop or spit out nasty errors - to no fault of Galapagos.

Note that this is not a problem for QuantifiableGenome, as the Comparator is tied directly to the fitness (and integers are always transitive).

One example that I can think of for a non-transitive genome would be game players. Perhaps you're optimizing a particular set of parameters for a Chess player, and you measure your compare's by actually playing games. In this case, you can have three players who each win and lose a game - and the transitivity falls apart.