Multi-objectivization, fitness landscape transformation and search performance: A case of study on the hp model for 
protein structure prediction

Abstract

Multi-objectivization represents a current and promising research direction which has led to the development of more 
competitive search mechanisms. This concept involves the restatement of a single-objective problem in an alternative 
multi-objective form, which can facilitate the process of finding a solution to the original problem. Recently, this 
transformation was applied with success to the HP model, a simplified yet challenging representation of the protein 
structure prediction problem. The use of alternative multi-objective formulations, based on the decomposition of the 
original objective function of the problem, has significantly increased the performance of search algorithms. The present 
study goes further on this topic. With the primary aim of understanding and quantifying the potential effects of 
multi-objectivization, a detailed analysis is first conducted to evaluate the extent to which this problem transformation 
impacts on an important characteristic of the fitness landscape, neutrality. To the authors' knowledge, the effects of 
multi-objectivization have not been previously investigated by explicitly sampling and evaluating the neutrality of the 
fitness landscape. Although focused on the HP model, most of the findings of such an analysis can be extrapolated to other 
problem domains, contributing thus to the general understanding of multi-objectivization. Finally, this study presents a 
comparative analysis where the advantages of multi-objectivization are evaluated in terms of the performance of a basic 
evolutionary algorithm. Both the two- and three-dimensional variants of the HP model (based on the square and cubic 
lattices, respectively) are considered.