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

点击翻译按钮获取中文摘要

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.