Collaborative Research: Adaptive Search in Global Optimization

协作研究：全局优化中的自适应搜索

• 批准号: 0244286
• 负责人: Zelda Zabinsky
• 金额: --
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-01 至 2007-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0244286&HistoricalAwards=false
• 关键词: Collaborative; Research; Adaptive; Search; Global

Global optimization is a rapidly growing field, due to the increased availability of computing power and improvement in methods. A synergy is occurring where the emerging technology is enabling applications to blossom, and the experience with new applications is inspiring better methods. We are developing the capability, not only to describe complex systems, but also to prescribe solutions. The primary objective of this research is to develop theory and algorithms for global optimization problems that may include both discrete and continuous variables, including ill-structured black-box objective functions for which only an estimate (such as a stochastic simulation) is available. The team's approach is based on theoretical insights drawn from the average linear complexity of Pure Adaptive Search, developed by the authors, for global optimization. Adaptive Search attempts to realize this polynomial efficiency by constructing sampling distributions that yield a high likelihood of sampling improving points. A practical implementation hinges on developing an efficient Markov chain Monte Carlo (MCMC) sampler. A key research step is to develop discrete Hit-and-Run as a general MCMC sampler for a discrete domain and embed it within a generalized Adaptive Search framework to support a hoped for polynomial time, on average, algorithm. An attempt to reap the promise offered by the theoretical studies will be applied to practical arenas.Many global optimization heuristic methods, including simulated annealing and genetic algorithms, would be strengthened by rigorous approaches to determining better algorithmic parameters and stopping criteria. The research will develop the theory and methodology to address these issues for a general global optimization problem. The intellectual merit of this work primarily resides in enriching the field of global optimization, but also may shape, as it has in the past, more fundamental work in MCMC samplers. The broad impact of this work lies in the potential of the algorithms developed to optimize complex engineering systems. The prevalence of powerful computer technology is providing an opportunity to accurately model complex systems with software simulations, replacing traditional closed-form mathematical equations. The resulting models require robust optimization techniques that presume little known structure for the underlying models.

由于计算能力的提高和方法的改进，全局优化是一个快速发展的领域。在新兴技术使应用程序蓬勃发展的地方，正在发生协同作用，而新应用程序的经验正在激发更好的方法。我们正在发展的能力，不仅是描述复杂的系统，而且是规定的解决方案。本研究的主要目标是为全局优化问题发展理论和算法，这些问题可能包括离散变量和连续变量，包括结构不良的黑箱目标函数，只有一个估计（如随机模拟）可用。该团队的方法是基于纯自适应搜索的平均线性复杂性的理论见解，由作者开发，用于全局优化。自适应搜索试图通过构造产生高可能性的采样改进点的采样分布来实现这种多项式效率。一个实际的实现取决于开发一个有效的马尔可夫链蒙特卡罗（MCMC）采样器。一个关键的研究步骤是开发离散肇事逃逸作为离散域的通用MCMC采样器，并将其嵌入到广义自适应搜索框架中，以支持期望的多项式时间，平均，算法。尝试收获理论研究提供的希望，将应用于实际领域。许多全局优化启发式方法，包括模拟退火和遗传算法，将通过确定更好的算法参数和停止准则的严格方法得到加强。该研究将发展理论和方法来解决这些问题的一般全局优化问题。这项工作的智力价值主要在于丰富了全局优化领域，但也可能像过去一样，在MCMC采样器中形成更基础的工作。这项工作的广泛影响在于开发的算法的潜力，以优化复杂的工程系统。强大的计算机技术的普及为用软件模拟精确地模拟复杂系统提供了机会，取代了传统的封闭形式的数学方程。生成的模型需要健壮的优化技术，这些技术假定底层模型的结构鲜为人知。