3

I am trying to implement Novelty search; I understand why it can work better than the standard Genetic Algorithm based solution which just rewards according to the objective. I am working on a problem which requires to generate a fixed number of points in a 2d box centered at the origin. In this problem, how can I identify which is a novel configuration of points?

Note: I have thought of one way of doing this: We call the mean of one configuration of points to be the mean of all points in that configuration (let's say this tuple is $(m_x, m_y)$, we store the mean of all configurations generated till now, now for a new configuration it's novelty can be defined as the distance of the mean of this new configuration with $(m_x, m_y)$.
But I think it will not work greatly as some very different configuration of points can also have the same mean.

Vaibhav Thakkar
  • 31
  • 5

1 Answers1

1

You can define different measures in this way:

  1. Maximum distance of the new point with all points of the configuration ($M$)
  2. Minimum distance of the new point with all points of the configuration ($N$)
  3. $\frac{M}{\text{Maximum distance between two points of the configuration(}D)}$: normalize (1) measure
  4. $\frac{N}{D}$:normalize (2) measure

You can get more ideas from distance measures in hierarchical clustering methods. To select a proper one, you need to elaborate on the context of these points.

OmG
  • 1,731
  • 10
  • 19
  • I think in the first or third one, Novelty will be directly proportional to the measure, but not so sure about the second and fourth one, because I think these two won't be very good in differentiating between novel and non novel configuration. – Vaibhav Thakkar Oct 15 '20 at 16:50