Clustered Memetic Algorithm for Protein Structure Prediction

Memetic algorithm (MA) often perform better than other evolutionary algorithm due to their combining the local search with the process of global optimization. However, like any other evolutionary algorithm (EA), MA due to the problem of genetic drift often result in sub-optimal solutions. The problem is more aggravated when EAs are applied to search complex landscape of NP complete problem like protein structure prediction. In this paper, to help mitigate the problem of genetic drift and also to cover large search space, we propose a novel initial population generation process and a novel MA which applies clusters for seeding the initial population. Apart from reducing the impact of genetic drift, the proposed MA also avoids processing of unnecessary individuals in the population, thus significantly reducing the computational burden, especially for large protein sequences. Simulation results presented using the 2D lattice HP model show the superiority of the proposed algorithm.