A kind of epistasis-tunable test functions for genetic algorithms

摘要

Genetic algorithm (GA) is one of the most popular algorithms of evolutionary computation. To evaluate the performance of GAs, test functions with different levels of epistasis have been included in most of the commonly used benchmark platforms. Such test functions have been produced in general by assuming an underlying linear model for the fitness of a string, in which variable interaction should be known beforehand. This paper proposes to compose epistasis-tunable test functions via linear combinations of simple basis functions so as to avoid explicit dependence on the knowledge of variable interaction. It is remarked that, for a GA with a binary encoding, a linearly separable fitness function, ie, a zero-epistasis fitness function, can be decomposed into a superposition of periodical basis functions whose frequencies are exponential to 2. A kind of epistasis-tunable test functions is accordingly produced by summing up sinusoidal basis functions with such frequencies and proper phases. The merits of thus constructed test functions are: Both the locations and values of the global maxima are trivially known; their degrees of epistasis are smoothly tunable simply by changing the locations of the global maxima. Finally, illustration examples are studied, and the results confirm the claims about the merits.