by David Owen

Abstract—What can we learn from a shot in the dark? What can a relatively simple, random procedure tell us about an unknown and potentially complex space? Simple techniques based on randomized algorithms have been surprisingly successful in solving very dificult computational problems. This may be due to a phase transition observed for certain problems: most problem cases are easy to solve or easily shown unsolvable; few approach the worst case. Or it may be because of funnels: small sets of key variables, found in many systems, that largely determine the behavior of the entire system. We summarize experiments motivated by these ideas, experiments in which 1) a simple random search outperformed more sophisticated strategies in finding subtle errors in software models, and 2) machine learning was used to determine which models are best and worst candidates for random search. We conclude with a broader application of these ideas, suggesting that the success of random search procedures, sometimes cited as evidence that intelligent design is unnecessary, may actually be evidence of intelligent design present in the search space.

The full paper is available below:
A Shot in the Dark

Back to PCID Double Issue, Volumes 2.1 and 2.2