On the effectiveness of evolutionary search in high-dimensionalNK-landscapes

摘要

NK-landscapes offer the ability to assess the performance ofevolutionary algorithms on problems with different degrees of epistasis.In this paper, we study the performance of six algorithms inNK-landscapes with low and high dimension while keeping the amount ofepistatic interactions constant. The results show that compared togenetic local search algorithms, the performance of standard geneticalgorithms employing crossover or mutation significantly decreases withincreasing problem size. Furthermore, with increasing K, crossover basedalgorithms are in both cases outperformed by mutation based algorithms.However, the relative performance differences between the algorithmsgrow significantly with the dimension of the search space, indicatingthat it is important to consider high-dimensional landscapes forevaluating the performance of evolutionary algorithms