Skip to main content

Research Repository

Advanced Search

Can HP-protein folding be solved with genetic algorithms? Maybe not

Jansen, Reitze; Horn, Ruben; van Eck, Okke; Version, Kristian; Thomson, Sarah L.; van den Berg, Daan


Reitze Jansen

Ruben Horn

Okke van Eck

Kristian Version

Daan van den Berg


Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations increases with instance size when randomly sampling individuals, as we will show in an experiment. Thereby, the probability of randomly sampling a valid individual decreases exponentially with instance size. This immediately prohibits resampling, and repair mechanisms might also be non-applicable. Backtracking could generate a valid random individual, but it runs in exponential time, and is therefore also unsuitable. No wonder that previous approaches do not report how (often) random samples are created, and only address small instances. We contrast our findings with TSP, which is also NP-hard, but does not have these problems.

Presentation Conference Type Conference Paper (Published)
Conference Name ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications
Start Date Nov 13, 2023
End Date Nov 15, 2023
Acceptance Date Sep 27, 2023
Publication Date 2023
Deposit Date Sep 28, 2023
Publisher Scitepress Digital Library
Pages 131-140
Book Title Proceedings of the 15th International Joint Conference on Computational Intelligence
ISBN 978-989-758-674-3
Keywords Protein Folding, Genetic Algorithms, Evolutionary Computing, Constraints, Constraint Hierarchy
Public URL
Related Public URLs