NP-Hard Optimization in HP Model Protein Folding: A Systematic Review of Simulated Annealing, Genetic Algorithm, Particle Swarm Optimization, and Tabu Search

Abstract

Protein folding prediction in the HP model is an NP-hard problem which highly needs effective heuristic methods to optimize. Protein folding prediction in the HP model is an NP-hard problem which highly needs effective heuristic methods to optimize. This paper reviews and compares four well-known meta-heuristic algorithms, namely Simulated Annealing (SA), Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Tabu Search (TS), focused on three main aspects: ability to cross the energy barrier, robustness to initial solutions, and computational cost. The results show that each algorithm has its strength, namely, SA searching exceling in early-stage exploration, GA providing a stable solution with population diversity, PSO efficiently achieving rapid convergence while maintaining moderate robustness, and TS escaping local minima. This study does not aim to identify a single optimal method, but to elucidate the contexts and conditions under which each heuristic approach can be effectively applied to the protein folding problem. The review will become a practical guide for selecting an optimization method for protein structure prediction where NP-hard problems exist.