Abstract：
Simulated Annealing (SA) algorithm is not effective with large optimization problems for its slow convergence. Hence, several parallel Simulated Annealing (pSA) methods have been proposed, where the increase of searching threads can boost the speed of convergence. Although satisfactory solutions can be obtained by these methods, there is no rigorous mathematical analyses on their effectiveness. Thus, this article introduces a probabilistic model, on which a theorem about the effectiveness of multiple initial states parallel SA (MISPSA) has been proven. The theorem also demonstrates that the increasing parallelism in pSA algorithm with the reducing of search depth in each thread could obtain almost the same probability of finding the global optimal solution. We validated our theorem on AutoDock Vina, a widely used molecular docking tool with high accuracy and docking speed. AutoDock Vina uses a pSA strategy to find optimal molecular conformations. Under the premise that the total searching workload (i.e., thread number * iteration depth of each thread) remains unchanged, the docking accuracy from an aggressively parallelized SA searching method is almost the same or even better than those from the default exhaustiveness (parallelism degree) configuration of AutoDock Vina. Taking complex \'1hnn\' as an example,with the increase (125x) in the number of initial states (from 8 to 1000) and the decrease in the search depth for each thread (from 15540 to 124, or 1/125 of the original search depth), the mean energy is -7.80 and -7.94, while the mean RMSD is 3.4 and 3.14, respectively. The result also implies that a considerable speedup (in this case 125x in theory) can be obtained by a highly parallelized SA algorithm implementation.
摘要：
模拟退火（SA）算法收敛速度慢，在大型优化问题中效果不佳。因此，已经提出了几种并行模拟退火(pSA)方法，其中搜索线程的增加可以提高收敛速度。尽管通过这些方法可以获得令人满意的解决方案，对它们的有效性没有严格的数学分析。因此，本文介绍了一个概率模型，关于多个初始状态并行SA(MISPSA)的有效性的定理已经得到证明。该定理还表明，随着每个线程搜索深度的减少，pSA算法的并行性增加可以获得几乎相同的找到全局最优解的概率。我们在AutoDockVina上验证了我们的定理，一种广泛使用的分子对接工具，具有高精度和对接速度。AutoDockVina使用pSA策略来寻找最佳分子构象。在总搜索工作量(即，线程数*每个线程的迭代深度)保持不变，积极并行化SA搜索方法的对接精度几乎与AutoDockVina的默认穷举性（并行度）配置的对接精度相同甚至更好。以复杂的\'1hnn\'为例，随着初始状态数量的增加（125x）（从8到1000）和每个线程的搜索深度的减少（从15540到124，或原始搜索深度的1/125），平均能量为-7.80和-7.94，而平均RMSD分别为3.4和3.14。结果还意味着通过高度并行化的SA算法实现可以获得相当大的加速(在这种情况下理论上为125x)。
