The Metropolis algorithm involves producing a Markov chain to converge to a specified target density $\pi$. In order to improve its efficiency, we can use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by evaluating all neighbors. Rejection-Free can be made more efficient through the use of parallelism hardware. However, for some specialized hardware, such as Digital Annealing Unit, the number of units will limit the number of neighbors being considered at each step. Hence, we propose an enhanced version of Rejection-Free known as Partial Neighbor Search, which only considers a portion of the neighbors while using the Rejection-Free technique. This method will be tested on several examples to demonstrate its effectiveness and advantages under different circumstances.
翻译:《大都会算法》涉及生产一个Markov链条,以达到特定的目标密度$\pi$。为了提高效率,我们可以使用“拒绝-自由”版大都会算法,通过评估所有邻居来避免拒绝效率低下。“拒绝-自由”可以通过使用平行硬件来提高效率。然而,对于一些专门硬件,例如数字安纳利装置,单位的数量将限制每一步考虑的邻居数量。因此,我们提议了一个称为“部分邻居搜索”的“拒绝-自由”强化版,它只考虑邻居的一部分,而使用“拒绝-自由技术”来显示其在不同情况下的有效性和优势。