论文标题
通过无排斥的部分邻居搜索优化
Optimization via Rejection-Free Partial Neighbor Search
论文作者
论文摘要
在降低温度下使用大都市步骤的模拟退火被广泛用于解决复杂的组合优化问题。为了提高其效率，我们可以使用Metropolis算法的无拒绝版本，从而避免了通过在每个步骤中考虑所有邻居来避免拒绝的效率低下。作为避免算法陷入当地极端区域的解决方案，我们提出了一种增强的拒绝版本，称为部分邻居搜索（PNS），该版本仅考虑邻居的随机部分，同时不使用拒绝。我们通过将这些方法应用于几个示例，例如QUBO问题，背包问题，3R3XOR问题和二次编程来证明无排斥PNS算法的出色性能。
Simulated Annealing using Metropolis steps at decreasing temperatures is widely used to solve complex combinatorial optimization problems. In order to improve its efficiency, we can use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by considering all the neighbors at every step. As a solution to avoid the algorithm from becoming stuck in local extreme areas, we propose an enhanced version of Rejection-Free called Partial Neighbor Search (PNS), which only considers random parts of the neighbors while applying Rejection-Free. We demonstrate the superior performance of the Rejection-Free PNS algorithm by applying these methods to several examples, such as the QUBO question, the Knapsack problem, the 3R3XOR problem, and the quadratic programming.
