Answers.Body: <p>In the paper <a href="http://eplex.cs.ucf.edu/papers/lehman_alife08.pdf" rel="nofollow noreferrer">Exploiting Open-Endedness to Solve Problems Through the Search for Novelty</a> (2008), by Joel Lehman and Kenneth O. Stanley, which introduced the novelty search approach, it is written</p>
  <blockquote>
  <p>Thus this paper introduces the novelty search algorithm, which searches with no objective other than continually finding <strong>novel behaviors</strong> in the search space.</p>
  </blockquote>
  <p>and</p>
  <blockquote>
  <p>instead of searching for a final objective, the learning method is rewarded for finding any instance whose <strong>functionality</strong> is significantly different from what has been discovered before</p>
  </blockquote>
  <p>and</p>
  <blockquote>
  <p>The novelty of a newly generated individual is computed with respect to the <strong>behaviors</strong> (i.e. <strong>not the genotypes</strong>) of an archive of past individuals whose behaviors were highly novel when they originated</p>
  </blockquote>
  <p>Therefore, the goal of a novelty search is to search for novel behavior and not necessarily novel chromosomes (or genotypes).</p>
  <p>In the experiments reported in the novelty search paper, the authors use neural networks to represent the <a href="https://stackoverflow.com/q/46260775/3924118">policy</a> that controls a robot that needs to navigate a maze, while evolving these neural networks with <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf" rel="nofollow noreferrer">NEAT</a> (a <a href="https://en.wikipedia.org/wiki/Neuroevolution" rel="nofollow noreferrer">neuroevolution</a> method) and a <em>novelty metric</em> (rather than a fitness metric, which is used in the original <a href="http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf" rel="nofollow noreferrer">NEAT</a>). In the same experiments section, Lehman and Stanley write</p>
  <blockquote>
  <p>Thus, for the maze domain, the behavior of a navigator is defined as its ending position. The novelty metric is then the Euclidean distance between the ending positions of two individuals. For example, two robots stuck in the same corner appear similar, while one robot that simply sits at the start position looks very different from one that reaches the goal, though they are both equally viable to the novelty metric.</p>
  </blockquote>
  <p>Therefore, the evolution of the neural networks, which represent the controllers, is not necessarily guided by the novelty of (the architecture of) the neural networks but by the novelty of the behavior generated by the neural networks, even though novel neural networks might correspond or lead to novel behaviors.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-22T15:18:34.200Z
Answers.Text: Adding to this just a tad, in the implementation, for determining the novelty of an individual in a population ken states on the users page that an average (euclidean, as nbro said) distance from the k-nearest neighbors has proven to be an effective measure.
Answers.UserDisplayName: nickw
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-22T15:21:49.510Z
Answers.Text: @nickw Yes, in the paper, they also mention and use this k-nearest neighbor approach.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-22T02:14:28.597Z
Answers.LastActivityDate: 2022-05-26T09:58:40.900Z
Answers.LastEditDate: 2022-05-26T09:58:40.900Z
Answers.UserDisplayName: nbro
Body: <p>I have been reading a lot lately about some very promising work coming out of Uber's AI Labs using mutation algorithms enhanced with <em>novelty search</em> to evolve deep neural nets. See the paper <a href="https://arxiv.org/abs/1712.06563" rel="nofollow noreferrer">Safe Mutations for Deep and Recurrent Neural Networks through Output Gradients</a> (2018) for more details.</p>
  
  <p>In novelty search, are the novel structures or behavior of the neural network rewarded?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-17T05:43:28.233Z
Comments.Text: Hello all.  I have been researching this evening and found that both approaches can be combined to create an optimal solution.  I'm still unclear on 'safe mutation' so am not answering my own question but an leaving a paper here that describes using novelty of both structure and behavior as a fitness function:  https://www.researchgate.net/publication/262373008_Encouraging_Creative_Thinking_in_Robots_Improves_Their_Ability_to_Solve_Challenging_Problems
Comments.UserDisplayName: Mike AI
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-02-19T22:19:17.447Z
Comments.Text: This is from the paper: " Novel individuals are thus determined based on their behavioral distance to current or previously seen individuals. The GA otherwise proceeds as normal, substituting novelty for ﬁtness (reward)." - taken from here: https://arxiv.org/pdf/1712.06567.pdf
Comments.UserDisplayName: Mike AI
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-22T15:38:33.800Z
Comments.Text: safe mutations and novelty search arent dependent on one another ie you could use safe mutations without novelty search and novelty search without safe mutations. If i recall correctly safe mutations runs sgd optimization during evaluation and uses the optimized net's fitness to represent the genome. neat essentially has a search for optimal structure built in and mutations of the structures are driven by config vars so i would suggest doing behavior novelty as searching for novel structures would involve changing the underlying evolution process a substantially.
Comments.UserDisplayName: nickw
Tags: <deep-learning><genetic-algorithms><evolutionary-algorithms><neuroevolution><novelty-search>
Title: In novelty search, are the novel structures or behaviour of the neural network rewarded?
UserDisplayName: Mike AI
ThreadText: # In novelty search, are the novel structures or behaviour of the neural network rewarded?
  
  (Asked by: username_0 on 2018-02-16)
  
  I have been reading a lot lately about some very promising work coming out of Uber's AI Labs using mutation algorithms enhanced with *novelty search* to evolve deep neural nets. See the paper [Safe Mutations for Deep and Recurrent Neural Networks through Output Gradients](https://arxiv.org/abs/1712.06563) (2018) for more details.
  
  In novelty search, are the novel structures or behavior of the neural network rewarded?
  
  **Tags:** deep-learning, genetic-algorithms, evolutionary-algorithms, neuroevolution, novelty-search
  
  > **Comments:**
  > **username_0**: Hello all.  I have been researching this evening and found that both approaches can be combined to create an optimal solution.  I'm still unclear on 'safe mutation' so am not answering my own question but an leaving a paper here that describes using novelty of both structure and behavior as a fitness function:  https://www.researchgate.net/publication/262373008_Encouraging_Creative_Thinking_in_Robots_Improves_Their_Ability_to_Solve_Challenging_Problems  
  > **username_0**: This is from the paper: " Novel individuals are thus determined based on their behavioral distance to current or previously seen individuals. The GA otherwise proceeds as normal, substituting novelty for ﬁtness (reward)." - taken from here: https://arxiv.org/pdf/1712.06567.pdf  
  > **username_1**: safe mutations and novelty search arent dependent on one another ie you could use safe mutations without novelty search and novelty search without safe mutations. If i recall correctly safe mutations runs sgd optimization during evaluation and uses the optimized net's fitness to represent the genome. neat essentially has a search for optimal structure built in and mutations of the structures are driven by config vars so i would suggest doing behavior novelty as searching for novel structures would involve changing the underlying evolution process a substantially.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-11-22. Score: 3
  
  In the paper [Exploiting Open-Endedness to Solve Problems Through the Search for Novelty](http://eplex.cs.ucf.edu/papers/lehman_alife08.pdf) (2008), by Joel Lehman and Kenneth O. Stanley, which introduced the novelty search approach, it is written
  
  > Thus this paper introduces the novelty search algorithm, which searches with no objective other than continually finding **novel behaviors** in the search space.
  
  and
  
  > instead of searching for a final objective, the learning method is rewarded for finding any instance whose **functionality** is significantly different from what has been discovered before
  
  and
  
  > The novelty of a newly generated individual is computed with respect to the **behaviors** (i.e. **not the genotypes**) of an archive of past individuals whose behaviors were highly novel when they originated
  
  Therefore, the goal of a novelty search is to search for novel behavior and not necessarily novel chromosomes (or genotypes).
  
  In the experiments reported in the novelty search paper, the authors use neural networks to represent the [policy](https://stackoverflow.com/q/46260775/3924118) that controls a robot that needs to navigate a maze, while evolving these neural networks with [NEAT](http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf) (a [neuroevolution](https://en.wikipedia.org/wiki/Neuroevolution) method) and a *novelty metric* (rather than a fitness metric, which is used in the original [NEAT](http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf)). In the same experiments section, Lehman and Stanley write
  
  > Thus, for the maze domain, the behavior of a navigator is defined as its ending position. The novelty metric is then the Euclidean distance between the ending positions of two individuals. For example, two robots stuck in the same corner appear similar, while one robot that simply sits at the start position looks very different from one that reaches the goal, though they are both equally viable to the novelty metric.
  
  Therefore, the evolution of the neural networks, which represent the controllers, is not necessarily guided by the novelty of (the architecture of) the neural networks but by the novelty of the behavior generated by the neural networks, even though novel neural networks might correspond or lead to novel behaviors.
  
  > **Comments:**
  > **username_1**: Adding to this just a tad, in the implementation, for determining the novelty of an individual in a population ken states on the users page that an average (euclidean, as username_2 said) distance from the k-nearest neighbors has proven to be an effective measure.  
  > **username_2**: @username_1 Yes, in the paper, they also mention and use this k-nearest neighbor approach.  
  
  ---
  
  