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.