Adaptive Walks with Noisy Fitness Measurements

Adaptive walks are an optimization technique for searching a space of possible solutions, for example, a space of different molecules. The goal is to find a point in space (a molecule) optimal or near-optimal in some property, generally referred to as the ``fitness,'' such as its ability to bind to a given receptor. Adaptive walking is a powerful technique because of its ability to search many parts of the space in parallel. However, errors in the measurements will cause errors in the adaptive walks. Mutant molecules of higher fitness may be ignored or mutants of lower fitness may be accepted. To examine the effect of measurement error on adaptive walks, we simulate single-agent hill-climbing walks on NK landscapes of varying ruggedness where Gaussian noise is added to the fitness values to model measurement error. We consider both constant measurement noise and noise whose variance decays exponentially with fitness. We show that fitness-independent noise can cause walks to ``melt'' off the peaks in a landscape, wandering in larger regions as the noise increases. However, we also show that a small amount of noise actually helps the walk perform better than with no noise. For walks in which noise decreases exponentially with fitness, the most characteristic behavior is that the walk meanders throughout the landscape until it stumbles across a point of relatively high fitness, then it climbs the landscape toward the nearest peak. Finally, we characterize the balance between selection pressure and noise and show that there are several classes of walk dynamic behavior.