The 2-epistasis of fitness functions

In this note about Genetic Algorithms (GA~), we study the 2-epistasis of a fitness function over a search space. This concept is a natural generalisation of that of epistasis, previously considered by Davidor in 1991 Suys and Verschoren in 1996 and Van Hove and Verschoren in 1994 for example. We completely characterise fitness functions whose 2-epistasis is minimal: these are exactly the second order functions. The validity of 2-epistasis as a measure of hardness with respect to genetic algorithms is checked over some classical laboratory functions. Finally, we obtain an upper bound of the maximal value of the 2-epistasis when we restrict attention to non-negative functions.