Parallel Simulated Annealing Using an Adaptive Resampling Interval.
Parallel Simulated Annealing Using an Adaptive Resampling Interval.
复制标题
DOI：
10.1016/j.parco.2016.02.001
复制
发表时间：
2016-04-01
影响因子：
1.4
通讯作者：
Reinitz J
中科院分区：
文献类型：
--
作者：
Lou Z;Reinitz J
本文提出了一种并行模拟退火算法，该算法在多达192个处理器的迭代上能够达到90%的并行效率，在5000维拉斯特金函数上能够达到40%的并行效率。我们的算法通过放弃基于方差的自适应冷却，打破了Chu等人（1999）方法中的可扩展性障碍。由此产生的并行效率的增益远远大于由于缺乏自适应冷却而造成的串行效率的损失。我们的算法周期性地跨处理器重新采样状态。重新采样间隔根据每个特定处理器数量的成功率进行调优。我们进一步提出了一种基于采用率的自适应方法来确定重采样间隔。这种自适应方法能够获得几乎相同的并行效率，但与使用找到的最佳层段的固定层段方法相比，成功率更高。
This paper presents a parallel simulated annealing algorithm that is able to achieve 90% parallel efficiency in iteration on up to 192 processors and up to 40% parallel efficiency in time when applied to a 5000-dimension Rastrigin function. Our algorithm breaks scalability barriers in the method of Chu et al. (1999) by abandoning adaptive cooling based on variance. The resulting gains in parallel efficiency are much larger than the loss of serial efficiency from lack of adaptive cooling. Our algorithm resamples the states across processors periodically. The resampling interval is tuned according to the success rate for each specific number of processors. We further present an adaptive method to determine the resampling interval based on the adoption rate. This adaptive method is able to achieve nearly identical parallel efficiency but higher success rates compared to the fixed interval one using the best interval found.