Answers.Body: <p><a href="https://ai.stackexchange.com/a/2246/2444">This answer</a> already gives the idea of what a <em>trap function</em> (sometimes known as <strong>deceptive function</strong>) is. However, given that the work on <em>trap functions</em> is not abundant in the literature (at least this topic is not covered extensively in one of my reference books, i.e. <a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf#page=244" rel="nofollow noreferrer">this one</a>, 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.</p>
  <ul>
  <li><p><a href="https://link.springer.com/article/10.1007/BF01531277" rel="nofollow noreferrer">Sufficient conditions for deceptive and easy binary functions</a> (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.</p>
  </li>
  <li><p><a href="https://link.springer.com/chapter/10.1007/978-3-662-44320-0_13" rel="nofollow noreferrer">Global Optimization of Multimodal Deceptive Functions</a> (EvoCOP 2014, by Iclănzan), which defines <span class="math-container">$k$</span>-trap functions in section 4, p. 150</p>
  </li>
  </ul>
  <p>The book <a href="https://digi.lib.ttu.ee/services/copycat-pdf.php?ID=248" rel="nofollow noreferrer">Evolutionary Computation 1: Basic Algorithms and Operators</a> also mentions deceptive functions and deceptive problems several times. Moreover, the Python package <a href="https://github.com/schlatterbeck/GA_kit" rel="nofollow noreferrer">GA_kit</a> includes <a href="https://github.com/schlatterbeck/GA_kit/blob/master/deceptive.py" rel="nofollow noreferrer">a module to evaluate GAs with deceptive functions</a>, in case you learn more by looking or playing with the code.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-08T16:36:03.690Z
Answers.LastActivityDate: 2020-12-08T17:52:40.220Z
Answers.LastEditDate: 2020-12-08T17:52:40.220Z
Answers.UserDisplayName: nbro
Answers.Body: <p>"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).</p>
  
  <p>For example, consider a four-bit function f(x) such that</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p>That's basically what is meant by a trap function. You can consider variations on this theme, but that's the gist of it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-10-31T21:50:22.750Z
Answers.LastActivityDate: 2019-08-22T12:49:16.813Z
Answers.LastEditDate: 2019-08-22T12:49:16.813Z
Answers.UserDisplayName: deong
Body: <p>What is a trap function in the context of a genetic algorithm? How is it related to the concepts of local and global optima?</p>
  
Tags: <definitions><genetic-algorithms><evolutionary-algorithms><trap-functions>
Title: What is a trap function in the context of a genetic algorithm?
UserDisplayName: mountaincloud
ThreadText: # What is a trap function in the context of a genetic algorithm?
  
  (Asked by: username_0 on 2016-10-31)
  
  What is a trap function in the context of a genetic algorithm? How is it related to the concepts of local and global optima?
  
  **Tags:** definitions, genetic-algorithms, evolutionary-algorithms, trap-functions
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2016-10-31. Score: 8 | Accepted answer
  
  "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 by username_1 on 2020-12-08. Score: 0
  
  [This answer](https://ai.stackexchange.com/a/2246/2444) 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](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf#page=244), 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](https://link.springer.com/article/10.1007/BF01531277) (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](https://link.springer.com/chapter/10.1007/978-3-662-44320-0_13) (EvoCOP 2014, by Iclănzan), which defines $k$-trap functions in section 4, p. 150
  
  The book [Evolutionary Computation 1: Basic Algorithms and Operators](https://digi.lib.ttu.ee/services/copycat-pdf.php?ID=248) also mentions deceptive functions and deceptive problems several times. Moreover, the Python package [GA\_kit](https://github.com/schlatterbeck/GA_kit) includes [a module to evaluate GAs with deceptive functions](https://github.com/schlatterbeck/GA_kit/blob/master/deceptive.py), in case you learn more by looking or playing with the code.
  
  
  ---
  
  