Local Search Strategies Using Generalized Hill Climbing Algorithms

使用广义爬山算法的本地搜索策略

• 批准号: 9907980
• 负责人: Sheldon Jacobson
• 金额: $ 18.56万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-01-01 至 2003-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9907980&HistoricalAwards=false
• 关键词: Local; Search; Strategies; Using; Generalized

This grant provides funding to study local search strategies for discrete optimization problems, using the generalized hill climbing algorithm framework. Generalized hill climbing algorithms provide a well-defined structure for classifying and studying a large body of local search algorithms typically used to address a wide variety of (real-world) manufacturing and service industry problems that canbe modeled as discrete optimization problems. This project presents and classifies local search algorithms(including simulated annealing, threshold accepting, and tabu search, among others) using the generalized hill climbing algorithm framework, identifies and develops convergence results and new finite-time performance measures for such algorithms (that more closely match how practitioners would apply them), studies the implications of these convergence results and finite-time performance measures on particular algorithm formulations, and evaluates the application of such algorithms to manufacturing and service industry discrete optimization problems. The results of this research will provide a well-defined structure for comparing and evaluating different types of local search algorithms using a common set of performance measures. This, in turn, will provide a practical vehicle by which new local search algorithms can be systematically developed, hence provide the potential to efficiently address larger and more challenging manufacturing and service industry problems. Moreover, an industrial partner has committed to implementing several such generalized hill climbing algorithms into a discrete manufacturing process design optimization computer software tool that they are developing and commercializing through a Phase II Small Business Innovation Research (SBIR) contract. This tool will also include a visualization capability of the generalized hill climbing algorithm performance measures developed in this project.

这笔赠款提供资金，用于研究离散优化问题的局部搜索策略，使用通用爬山算法框架。广义爬山算法提供了一种定义良好的结构，用于分类和研究大量的局部搜索算法，这些局部搜索算法通常用于解决可建模为离散优化问题的各种(真实世界)制造业和服务业问题。本项目使用广义爬山算法框架提出并分类局部搜索算法(包括模拟退火法、阈值接受和禁忌搜索等)，识别和开发这些算法的收敛结果和新的有限时间性能指标(更接近实践者应用它们的方式)，研究这些收敛结果和有限时间性能指标对特定算法公式的影响，并评估这些算法在制造业和服务业离散优化问题中的应用。这项研究的结果将提供一个明确的结构，用于使用一组共同的性能衡量标准来比较和评估不同类型的本地搜索算法。这反过来将提供一个实用的工具，通过它可以系统地开发新的本地搜索算法，从而提供有效地解决更大和更具挑战性的制造业和服务业问题的潜力。此外，一家工业合作伙伴已承诺将几种这样的通用爬山算法实施到离散制造过程设计优化计算机软件工具中，他们正在开发该工具，并通过第二阶段小型企业创新研究(SBIR)合同进行商业化。该工具还将包括在该项目中开发的通用爬山算法性能测量的可视化能力。