Recent Ant study and Genetic Algorithm Selection Techniques

Recent studies on non-pheromone navigating ants have show that by manipulating an ant's stride length, one could determine whether such insects were using an pedometer-like mechanism to measure the distance, that is by counting off their steps with this "internal pedometer." It turns out that ants appear to have such an internal mechanism [1].

Such a study would have direct application in determining fitness values for chromosome selection in genetic algorithms. There are several different selection criterion for mating chromosomes. A simple geographic mating scheme might be to select a mate within a 1 unit radius. Consider a matrix of chromosomes:

10101 10101 11111
11101 11100 00001
11001 00101 00101

The center chromosome, 11100, could mate with any of the eight chromosomes surrounding it. However, after a few iterations such a limited range of selection could bring about homogeneity among chromosomes. Thus, it would be desirable to extend the mating range. Consider another matrix of chromosomes:

001100 00001 00010 00100 000110
001101 10101 10101 11111 000101
001110 11101 11100 00001 000110
001111 11001 00101 00101 000111
010000 01000 01001 01010 001011

In this case, chromosome 11100 could made with any of the original eight, but also with an additional 16 chromosomes. In fact, counting from right to left, bit five is a 1; thus, this could indicate a mating range two units. If bit five were a 0, this could indicate a mating range of one unit. Naturally, adding more bits would allow a wider range of values for establishing mating range (e.g. 00 = range of 1, 01 = range of 2, 10 = range of 3, 11 range of 4).

Selection might vary over time, where large differences in chromosome morphology give faster climbing fitness in early generations, while smaller differences in chromosome morphology would give faster climbing fitness in later generations. This is not a new idea, since local mating of chromosomes has been shown better than merely random breeding within a chromosome population (i.e. better than "panmictic" selection). [2]

REFERENCES

[1] Bjorn Carey "When Ants Go Marching, They Count Their Steps" Yahoo News (Accessed July 1, 2006)

[2] Robert J. Collins, David R. Jefferson Selection in Massively Parallel Genetic Algorithms (1991) CiteSeer.IST: Scientific Literature Digital Library (Accessed July 02, 2006) http://citeseer.ist.psu.edu/cs