Expedited Novel Research Award; Local Averaging - A Deterministic Analogue of Simulated Annealing

加速小说研究奖；

• 批准号: 8803659
• 负责人: Lov Grover
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-01-15 至 1989-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8803659&HistoricalAwards=false
• 关键词: Expedited; Novel; Research; Award; Local

Simulated annealing has had success in solving complex computational problems by using a form of average to smooth out the local optima of a cost functions, thereby enabling it to make progress towards the global optimum. Based on this idea, PI proposes a new approach called local averaging to derive information about the variation of the cost function. He defines a normalized cost of a state to be its absolute cost minus the average cost of all states. He has discovered that for several NP-complete problems, including the traveling salesman problem and the min-cut graph partitioning problem, the average normalized cost of the neighboring states of any state is a constant multiple a of the normalized cost of that state, where 0 a 1. Using this result, he has shown that local optima of any of these problems have to be better than the average cost of all states. Also, applying the same result, it is found that NP-complete problems satisfy an equation which strongly resembles certain wave equations of mathematical physics. An analysis of simulated annealing is carried out, based on the neighborhood structure of NP-complete problems. Simulated annealing is shown to satisfy a simple continuity equation, based on which it is suggested that the algorithm can be implemented with a combination of random moves and greedy moves. The relative fraction of random moves is decreased with temperature. This implementation is faster than the standard one, since no cost calculations have to be done for the random moves.

模拟退火在解决复杂的计算问题上取得了成功。 问题，通过使用一种形式的平均平滑的局部最优的 成本函数，从而使其能够朝着 全局最优 基于这一想法，PI提出了一种新的方法，称为 局部平均以导出关于成本变化的信息 功能 他将一个国家的标准化成本定义为它的绝对成本， 成本减去所有国家的平均成本。 他发现，对于 几个NP完全问题，包括旅行商问题 和最小割图划分问题，平均归一化 任何状态的相邻状态的成本都是a的常数倍。 该状态的归一化成本，其中0是1。 使用此 结果，他已经表明，任何这些问题的局部最优， 比所有国家的平均成本都要高。 此外，应用 同样的结果，我们发现NP完全问题满足一个方程 它非常类似于某些数学波动方程， 物理学 本文对模拟退火算法进行了分析， NP完全问题的邻域结构 模拟退火 满足一个简单的连续性方程，基于该方程， 建议该算法可以用以下组合来实现： 随机移动和贪婪移动。 随机移动的相对比例 随着温度的升高而降低。 此实现比 标准一，因为没有成本计算必须做的 随机移动