3

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 (2018) for more details.

In novelty search, are the novel structures or behavior of the neural network rewarded?

nbro
  • 39,006
  • 12
  • 98
  • 176
Mike AI
  • 145
  • 2
  • 8
  • 1
    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 – Mike AI Feb 17 '18 at 05:43
  • 1
    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 fitness (reward)." - taken from here: https://arxiv.org/pdf/1712.06567.pdf – Mike AI Feb 19 '18 at 22:19
  • 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. – nickw Nov 22 '19 at 15:38

1 Answers1

3

In the paper Exploiting Open-Endedness to Solve Problems Through the Search for Novelty (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 that controls a robot that needs to navigate a maze, while evolving these neural networks with NEAT (a neuroevolution method) and a novelty metric (rather than a fitness metric, which is used in the original NEAT). 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.

nbro
  • 39,006
  • 12
  • 98
  • 176
  • 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. – nickw Nov 22 '19 at 15:18
  • 1
    @nickw Yes, in the paper, they also mention and use this k-nearest neighbor approach. – nbro Nov 22 '19 at 15:21