What is a trap function in the context of a genetic algorithm?

Question

What is a trap function in the context of a genetic algorithm? How is it related to the concepts of local and global optima?

Answer 1

"Trap" functions were introduced as a way to discuss how GAs behave on functions where sampling most of the search space would provide pressure for the algorithm to move in the wrong direction (wrong in the sense of away from the global optimum).

For example, consider a four-bit function f(x) such that

f(0000) = 5
f(0001) = 1
f(0010) = 1
f(0011) = 2
f(0100) = 1
f(0101) = 2
f(0110) = 2
f(0111) = 3
f(1000) = 1
f(1001) = 2
f(1010) = 2
f(1011) = 3
f(1100) = 2
f(1101) = 3
f(1110) = 3
f(1111) = 4

That is, the fitness of a string is equal to the number of 1s in the string, except f(0000) is 5, the optimal solution. This function can be thought of as consisting of two disjoint pieces: one that contains the global optimum (0000) and another that contains the local optimum at its complement (1111). All points other than these have fitness values such that standard evolutionary algorithm dynamics would lead the algorithms to tend towards the local optimum at 1111 rather than the global optimum at 0000.

That's basically what is meant by a trap function. You can consider variations on this theme, but that's the gist of it.

Answer 2

This answer already gives the idea of what a trap function (sometimes known as deceptive function) is. However, given that the work on trap functions is not abundant in the literature (at least this topic is not covered extensively in one of my reference books, i.e. this one, on page 211, exercises 11.7, only mentions a specific deceptive function, but does not define what a trap function is), let me also provide you with a few references, in case you are looking for more details and formulations.

• Sufficient conditions for deceptive and easy binary functions (1994, by Deb and Goldberg) provides a definition and formulation of a trap function in section 4.1, p. 397, but also many other specific definitions of deceptive functions.

• Global Optimization of Multimodal Deceptive Functions (EvoCOP 2014, by Iclănzan), which defines $k$-trap functions in section 4, p. 150

The book Evolutionary Computation 1: Basic Algorithms and Operators also mentions deceptive functions and deceptive problems several times. Moreover, the Python package GA_kit includes a module to evaluate GAs with deceptive functions, in case you learn more by looking or playing with the code.