Local Search Strategies Using Generalized Hill Climbing Algorithms

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

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.