What is a trap function in the context of a genetic algorithm? How is it related to the concepts of local and global optima?
"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.