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.
Download Info
To our knowledge, this item is not available for
download. To find whether it is available, there are three
options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page
whether it is in fact available.
3. Perform a search for a similarly titled item that would be
available.
Publisher Info
Paper provided by Santa Fe Institute in its series Working Papers with number
95-04-039.
For technical questions regarding this item, or to correct its listing, contact: (Thomas Krichel).
Related research
Keywords:
Cited by: (explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)