Effectiveness Analysis of Multiple Initial States Simulated Annealing Algorithm, a Case Study on the Molecular...

Area of Science:

• Computational Chemistry
• Optimization Algorithms
• Bioinformatics

Background:

• Simulated Annealing (SA) struggles with large optimization problems due to slow convergence.
• Parallel Simulated Annealing (pSA) methods improve speed but lack rigorous mathematical analysis.
• Molecular docking tools like AutoDock Vina utilize pSA for conformational searches.

Purpose of the Study:

• To introduce a probabilistic model for analyzing the effectiveness of pSA.
• To mathematically prove the effectiveness of multiple initial states parallel SA (MISPSA).
• To demonstrate that increased parallelism in pSA, with reduced search depth, maintains optimal solution probability.

Main Methods:

• Developed a probabilistic model for pSA.
• Proved a theorem on the effectiveness of MISPSA.
• Validated the theorem using AutoDock Vina for molecular docking.
• Compared aggressively parallelized SA with default configurations under constant workload.

Main Results:

• The theorem shows increased parallelism in pSA with reduced search depth yields similar global optimal solution probability.
• Validation on AutoDock Vina demonstrated comparable or improved docking accuracy with aggressive parallelization.
• For '1hnn', increasing initial states 125x and decreasing thread search depth 125x improved mean energy and reduced mean RMSD.
• A theoretical speedup of 125x was achieved with the highly parallelized SA implementation.

Conclusions:

• The probabilistic model and theorem provide mathematical rigor for pSA effectiveness.
• Aggressively parallelized SA, with reduced search depth per thread, is effective for molecular docking.
• This approach offers significant speedup potential for optimization problems without sacrificing accuracy.