Can HP-protein folding be solved with genetic algorithms? Maybe not
Publication date
2023
Document type
Konferenzbeitrag
Author
Organisational unit
Conference
15th International Joint Conference on Computational Intelligence (IJCCI 2023) ; Rome, Italy ; November 13–15, 2023
Publisher
SciTePress
Book title
Proceedings of the 15th International Joint Conference on Computational Intelligence
First page
131
Last page
140
Part of the university bibliography
✅
Language
English
Abstract
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.
Version
Published version
Access right on openHSU
Metadata only access