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

模拟退火已经成功地解决了复杂的计算问题，通过使用一种平均形式来平滑成本函数的局部最优，从而使其朝着全局最优方向发展。基于这一思想，PI提出了一种称为局部平均的新方法来获得有关成本函数变化的信息。他将一个状态的标准化成本定义为它的绝对成本减去所有状态的平均成本。他发现，对于几个np完全问题，包括旅行推销员问题和最小切图划分问题，任何状态的相邻状态的平均归一化代价是该状态归一化代价的常数倍a，其中0到1。利用这一结果，他证明了这些问题的局部最优值必须优于所有状态的平均成本。同时，应用同样的结果，发现np完全问题满足一个与数学物理中某些波动方程非常相似的方程。基于np完全问题的邻域结构，对模拟退火进行了分析。模拟退火可以满足一个简单的连续性方程，在此基础上提出了该算法可以采用随机移动和贪婪移动相结合的方式来实现。随机移动的相对比例随温度的升高而降低。这种实现比标准的更快，因为不需要为随机移动进行成本计算。

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.