William A. Dembski and Robert J. Marks II

   

"Judicious Use of Computational Resources in Evolutionary Search"

Abstract: A search algorithm consists of a search space, a target, an oracle (or source of information), available computation resources (with implicit or explicit limits), and an initialization. The initialization is often random and the resource limits are often measured in maximum allowable oracle queries. A programmer's job is to craft an algorithm that best spends the available computational resources to attain the target. The algorithm must make judicious use of its computational resources. According to No Free Lunch theorems for search, average performance of an arbitrary search does no better than blind search. Domain expertise is therefore essential in crafting the search algorithm. The effectiveness of a given algorithm can be measured by the active information introduced to the search. Some search algorithms use oracles poorly. We show this specifically for the case of Hamming oracles and partitioned search. Other algorithms proposed in the literature are too difficult to evaluate analytically and require Monte Carlo simulation. The Avida and ev algorithms are evaluated and shown to use oracles rich in information.

[in preperation]