Thursday, June 9, 2011

Hypothesis: Reordering typical GA operations opens up new opportunities

One of the truisms of the area of evolutionary computation is that time spent on the evaluation of the fitness function dominates the the total resource budget of the run. Therefore, we should want to allocate trials as efficiently as possible, even more so as we are using a method which will inevitably allocate trials to poor choices as part of the exploration of the parameter space.
When GAs are introduced, the fitness function evaluation is typically a single test case, for example evaluating f(x) for some x, which is the phenotype constructed from the individual's genotype. The population might have genotypes of binary strings, these strings then become phenotypes of real numbers, and the phenotypes are evaluated.

For more 'real world' problems, the phenotype has to be evaluated across multiple test cases, perhaps thousands of cases. The outcome of all of these test cases contributes to the overall fitness measure of the individual. As noted in this early paper, the test cases can vary greatly in their discriminant utility. The basic idea here is to break down the test cases into a population of individuals that will co-evolve with the population of possible solutions.

My idea is somewhat simpler. Typically, one individual is tested across all test cases, and a cumulative fitness score generated. In my reordering of operations, all of the new population members are generated, then each member is evaluated on the first test case, then all on the second, etc. We stop the evaluation process at some point to compute a partial fitness score. On the basis of this score, we abandon some members of the population and delete them, replacing them with perturbations of high scoring members.

In terms of the biological analogy, reordering the test case evaluations allows us to select from the population at multiple points in each individuals "lifetime", where the lifetime is the sequence of test cases.

The hypothesis is that this reordering, partial fitness selection, and reward of well performing members will lead to more efficient allocation of trials in problems that are amenable to this reordering.

No comments: