Empirical Analysis of Search Spaces Using Population-Based Sampling

使用基于群体的采样对搜索空间进行实证分析

• 批准号: 9734880
• 负责人: Russell Impagliazzo
• 金额: $ 12.5万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-15 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9734880&HistoricalAwards=false
• 关键词: Empirical; Analysis; Search; Spaces; Using

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

随机和基于群体的搜索方法（模拟退火、大都会、WalkSAT、遗传算法）作为优化算法在许多应用领域中已经取得成功。 然而，很少有人知道他们在哪些问题上取得了成功，他们在哪些情况下做得很好，或者如何实现选择，以适应给定的应用程序的方法。 为了解决这个问题，最近的理论工作，基于人口的方法将被用作指导的搜索空间的结构的实验研究。 基于群体的算法（特别是与赢家同行的局部优化）将用于从满足某个最低最优性标准的搜索空间部分均匀采样。 这些样本将被用来发现搜索空间的组合特征，然后预测和改善优化算法的性能。 社会影响：理论家和实验者之间将有合作。 这将有助于忘记两个研究团体之间的联系。 研究生将学习平衡理论技能，编程机构和应用程序的关注