Adaptive Walks with Noisy Fitness Measurements

Bennett Levitan and Stuart Kauffman

Working Papers from Santa Fe Institute

Abstract: 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.

Date: 1995-04
References: Add references at CitEc
Citations: View citations in EconPapers (12)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:95-04-039

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().