Thursday, January 31, 2008

ECJ - building a BinInt problem

I've gotten a little farther with my learning of ECJ.

The tutorial 1 provided with ECJ uses the MaxOnes as a sample problem. MaxOnes simply adds up the number of "1" bits in the genome of an individual to create a fitness for that individual.

BinInt changes the problem by reinterpreting the genome as a binary integer. In my version, I've written it so that you can cut the genome up into several integers. For example, a genome of 150 bits can be interpreted as 30 5-bit integers, 5 30-bit integers, or even 16 9-bit integers with one 6-bit integer.

BinInt is a class of problems that imposes two new kinds of difficulty on the GA. First, BinInt shows scaling. Different bits are worth exponentially more than other bits. Secondly, bits are related to each other to form sub-problems. All the bits of a particular sub-problem contribute to the solution of that part of the overall problem.

Scaling in particular challenges a GA. The large fitness contribution from just a few bits can cause individuals lucky enough to have those bits turned on early in the run to quickly dominate the population, even before the population has found the best arrangement for the other bits. This problem is called premature convergence.

I had fun building the BinInt problem in ECJ. It was straightforward to modify the MaxOnes problem fitness evaluation function. The learning came in when I wanted to create a custom parameter to control the sizes of the integers. I invoked the OTSOG (On The Shoulders Of Giants) principle, and asked for help from the ECJ discussion list, with very helpful and immediate answers. Thanks guys!

No comments: