Monday, February 11, 2008

Sex, Lies, and Genetic Algorithms

Moving on from the BinInt problem, the next basic research problem to code in ECJ is the classic "deceptive" problem. In this kind of problem, the optimum point is surrounded by very low fitness points, while the points furthest from the global optimum have the second highest fitness. A hill climbing algorithm is tempted to follow the slope away from the global best towards the suboptimal points.
However, a selectorecombinative GA is not a hill climber. Its ability to find the optimum point is based on shuffling combinations of alleles, trying to find good sets.

If the deceptive subproblem is too big, the GA has little better than random chance of finding the optimum, so here also we will rely on building up a problem by concatenating several subproblems.

Based on calculations shown in The Design of Innovation, p. 160, I verified that my code for the trap function was in fact deceptive. Then I looked at a few other sources, including Franz Rothlauf's Representations for Genetic and Evolutionary Algorithms, and I saw that my code for the trap was basically the same as his.

No comments: