What are traps in genetic algorithms? Suppose you ran an sGA on trap-3 and examined the population midway through the run. Can someone explain what you would expect the population to look like?

  • $\begingroup$ Hi. Welcome to AI SE. Take a look at our on-topic page ai.stackexchange.com/help/on-topic to know more about our site. Where did you find this term "trap"? I think it may be useful if you contextualize a little bit more your problem. $\endgroup$ – nbro Sep 24 at 23:31

Traps are functions that are designed to have a very obvious gradient that leads to basically the second-best solution, with the best one being very far removed from that, often the complement of the second-best.

Take the 1-max problem. You have N bits, and the fitness of each individual is just the number of 1 bits in the string. If you run a GA on that, you'd expect to see an initial random distribution of 1s and 0s across the population fairly quickly start to converge to strings of all 1s. Now let's add one more clause to the fitness criteria. Instead of f(0)=0, let f(0)=N+1. This gives you a trap function. The "trap" is the solution of all 1s. Everything in the search space points to this being the best solution, but it's actually maximally far away from the best solution.

In terms of dyanmics, now the optimal solution is the string of all 0s. But unless you happen to very quickly stumble across that string, you likely never will. That is, there's some slight chance that your initial population included 00001111 and 11110000 and you crossed them over in the middle and got the optimum. Or maybe you had 00001000 and you got lucky and mutated that one bit to a zero. But if you don't do that immediately, you're screwed, because the algorithm is going to pretty relentless drive all the zero bits out of the population. No matter what it does, flipping a 0 to a 1 is always better unless it would otherwise lead to the single string of all 0s, so there's constant pressure to find more and more 1 bits. A few generations in, you might have 11110110, but you're never realistically going to randomly mutate all six of those 1s to 0s. And you have to get it all in one shot. Any subset of fewer than six of those bits being flipped will have worse fitness than you started with, and be selected against.

| improve this answer | |
  • $\begingroup$ You don't seem to explicitly explain what "trap-3" is. There was already the question about "trap functions" in general, but what is a traps-3 function? See also this other recently asked question. $\endgroup$ – nbro Sep 29 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.