Stochastic and population-based search methods (simulated annealing, metropolis, WalkSAT, genetic algorithms) have been successful as optimization heuristics in a number of application areas. However, very little is known about which problems they succeed at, which instances they do well on, or how to make implementation choices to tailor the method to a given application. To address this, recent theoretical work on population-based methods will be used as a guide in an experimental study of the structure of search spaces. Population- based algorithms (in particular go-with-the-winners local optimization, will be used to sample uniformly from the part of the search space that meets a certain minimal standard of optimality. Such samples will be used to discover combinatorial characteristics of search spaces, and then to predict and improve the performance of optimization heuristics. Social Impact: There will be collaboration between theorists and experimenters. This will help forget ties between the two research communities. Graduate students will learn to balance theoretical skills, programming institution, and concern for applications
