IEEE/ACM Trans Comput Biol Bioinform. 2023 Nov-Dec;20(6):3830-3841. doi: 10.1109/TCBB.2023.3323552. Epub 2023 Dec 25.
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）方法，其中增加搜索线程的数量可以提高收敛速度。虽然这些方法可以得到令人满意的解决方案，但它们的有效性没有严格的数学分析。因此，本文引入了一个概率模型，在此基础上证明了多初始状态并行模拟退火（MISPSA）的有效性定理。该定理还表明，随着每个线程搜索深度的减少，pSA 算法的并行度增加，可以获得几乎相同的找到全局最优解的概率。我们在 AutoDock Vina 上验证了我们的定理，AutoDock Vina 是一种广泛使用的具有高精度和快速对接速度的分子对接工具。AutoDock Vina 使用 pSA 策略来寻找最佳分子构象。在总搜索工作量（即线程数*每个线程的迭代深度）保持不变的前提下，激进并行化的 SA 搜索方法的对接精度几乎与 AutoDock Vina 的默认详尽度（并行度）配置相同甚至更好。以复杂的 '1hnn' 为例，随着初始状态数量的增加（从 8 到 1000，增加了 125 倍）和每个线程搜索深度的减少（从 15540 到 124，或原始搜索深度的 1/125），平均能量分别为-7.80 和-7.94，而平均 RMSD 分别为 3.4 和 3.14。结果还表明，通过高度并行化的 SA 算法实现可以获得相当大的加速（在这种情况下，理论上为 125 倍）。
