Synchronous and asynchronous parallel simulated annealing with multiple Markov chains
Synchronous and asynchronous parallel simulated annealing with multiple Markov chains
复制标题
DOI：
10.1109/71.539732
复制
发表时间：
1996-10-01
影响因子：
5.3
通讯作者：
Lee, KG
中科院分区：
文献类型：
--
作者：
Lee, SY;Lee, KG
模拟退火是一种通用的优化技术，能够在各种应用中找到最优或近最优解。然而，在实践中，高质量解决方案所需的长执行时间一直是一个主要缺点。为了开发模拟退火的并行算法，已经进行了广泛的研究。它们中的大多数都不是很成功，主要是因为需要多个处理元素（pe）遵循单个马尔可夫链，因此只能利用有限的并行性。在本文中，我们提出了一种新的并行模拟退火算法，该算法允许多个可通信的pe同时跟踪多个马尔可夫链。我们已经考虑了算法的同步和异步实现。对它们的性能进行了详细的分析，并通过大量的实验结果进行了验证。研究表明，对于图划分，所提出的并行模拟退火方案可以比传统的并行方案更快地找到等效（甚至更好）质量的解。在所提出的方案中，pe动态（非固定周期）交换信息的方案性能最好。
Simulated annealing is a general-purpose optimization technique capable of finding an optimal or near-optimal solution in various applications. However, the long execution time required for a good quality solution has been a major drawback in practice. Extensive studies have been carried out to develop parallel algorithms for simulated annealing. Most of them were not very successful, mainly because multiple processing elements (PEs) were required to follow a single Markov chain and, therefore, only a limited parallelism was exploited. In this paper, we propose new parallel simulated annealing algorithms which allow multiple Markov chains to be traced simultaneously by PEs which may communicate with each other. We have considered both synchronous and asynchronous implementations of the algorithms. Their performance has been analyzed in detail and also verified by extensive experimental results. It has been shown that for graph partitioning the proposed parallel simulated annealing schemes can find a solution of equivalent (or even better) quality up to an order of magnitude faster than the conventional parallel schemes. Among the proposed schemes, the one where PEs exchange information dynamically (not with a fixed period) performs best.