Loading ...
Sorry, an error occurred while loading the content.

Re: Novelty search in a generational GA

Expand Messages
  • joel278
    Hi Oliver, Keith, The 0.05% probability of adding new individuals to the archive was applied in the GP experiments described in
    Message 1 of 9 , Jul 5, 2013
    • 0 Attachment
      Hi Oliver, Keith,

      The 0.05% probability of adding new individuals to the archive was applied in the GP experiments described in http://eplex.cs.ucf.edu/publications/2010/lehman-gecco10b.
      Although 0.05% seems small, the archive still grows in those experiments to encompass on average 500 individuals (1000 individuals x 1000 generations*1/5000 chance of being added). It worked well in practice in the domains explored in that paper, and is likely robust to some variation.

      Increasing or decreasing the probability effectively changes the amount of pressure driving the current population away from previously discovered points. This seems easier to interpret than how the choice of the threshold (and/or rules for the threshold to adjust dynamically) affect search. So the more direct implications of changing the probability may be another benefit for the random sampling approach to adding to the archive (also if the probability remains constant over the run, which is how I usually implement it, then you have an easy-to-calculate expectation for the size of the archive over time).

      Keith, thanks for providing the code to your automatic method for calculating a reasonable sample probability, it sounds like an interesting approach. Your experiments with test behaviors also sound illustrative and support the idea that randomly sampling the space may better approximate what is really novel at a given time in the search.

      Joel

      --- In neat@yahoogroups.com, Oliver Coleman <oliver.coleman@...> wrote:
      >
      > Hi Joel,
      >
      > I've been experimenting with novelty search and have decided to try the
      > probabilistic approach to determine if an individual is added to the
      > permanent archive. You said *"in new implementations I've tended to remove
      > the threshold and instead add any new individual to the archive (at the end
      > of a generation) with fixed probability (e.g. 0.05%)."* I'm just wondering
      > if you really meant 0.05% or you actually meant 5% (p = 0.05)? One seems a
      > bit large and the other a bit small!
      >
      > Cheers,
      > Oliver
      >
      >
      > T: 0421 972 953 | E: oliver.coleman@... | W: http://ojcoleman.com
      >
      >
      >
      > On 12 June 2013 13:32, joel278 <lehman.154@...> wrote:
      >
      > > **
      > >
      > >
      > > Hi Oliver,
      > >
      > > I don't believe there have been any direct empirical comparisons between
      > > the probabilistic and novelty score threshold methods of adding individuals
      > > to the archive. In my informal experiments it didn't seem to have a large
      > > effect on the overall effectiveness of search. But, the probabilistic
      > > method is simpler to implement and I like how it directly samples where
      > > search is spending most time in the space of phenotypic behaviors -- which
      > > is the underlying motivation for the archive.
      > >
      > > I think you are right, that the threshold version also approximates this
      > > sampling process over time, and that the slight repulsive force of adding a
      > > highly-novel individual to the archive in that version may be mitigated by
      > > averaging over many nearest-neighbors. So overall this implementation
      > > detail might not be a determining factor in novelty search's success or
      > > failure in most domains. So, all other things being almost equal, the
      > > simpler implementation is the one I tend to favor :)
      > >
      > > Best,
      > > Joel
      > >
      > > --- In neat@yahoogroups.com, Oliver Coleman <oliver.coleman@> wrote:
      > > >
      > > > ​Hi Joel,
      > >
      > > >
      > > > Clicked the send button before I was finished... in addition to previous
      > > > email:
      > > > ​
      > > > *
      > > > "​
      > >
      > > > That said, the simpler algorithm you suggest is interesting. It seems a
      > > bit
      > > > more greedy in nature and may work well sometimes in practice. One
      > > slightly
      > > > strange thing about it is that the evaluation order of individuals
      > > within a
      > > > generation may matter; that is, the novelty of an individual evaluated
      > > > later in the population may be affected by archive additions earlier. I
      > > am
      > > > not sure if that is bad or good. "*
      > >
      > > >
      > > > It should definitely be the case that a later evaluation of an individual
      > > > may be affected by archive additions from earlier in the current
      > > > generation: that is how it takes into account the current population.
      > > But I
      > > > agree that it is in some sense more greedy and will give a less accurate
      > > > signal about where the search currently is, and so will presumably not
      > > > maintain population diversity quite as well. As well as having the
      > > possibly
      > > > undesirable fact that the order of evaluation will have some impact
      > > (though
      > > > I don't see this as a major issue).
      > > >
      > > > ​Thanks for the tips on creating a smoother gradient in a generational
      > >
      > > > setting, makes perfect sense. :)
      > > >
      > > > I'm ambivalent about the deterministic and probabilistic methods of
      > > > determining whether to add an individual to the archive. Is there any
      > > > experimental evidence to show one is better than the other (at least for
      > > > some tasks)? ​In the paper you linked ("Efï¬ ciently Evolving Programs
      > >
      > > > through the Search for Novelty") it says:
      > > > *"adding a highly novel individual to the archive has the disadvantage
      > > that
      > >
      > > > it penalizes an area of the behavior space that may merit further ex
      > > > ploration."*
      > >
      > > > But I wonder if the average distance to the k-nearest-neighbours metric
      > > > isn't enough to avoid this issue for most practical purposes? I suppose
      > > KNN
      > > > can mitigate it (more so as K is increased), but won't do away with it
      > > > completely like the probabilistic approach will tend to (apart from the
      > > > hopefully rare occasions when a new highly novel individual is added to
      > > the
      > > > archive).
      > > >
      > > > On the other hand, perhaps the probabilistic approach might tend to
      > > result
      > > > in the search revisiting the same behaviours many times because they
      > > > weren't added to the archive the first time they were discovered? Again,
      > > > this is just an intuition, I have no idea if this is likely in practice.
      > > > Perhaps a combination of both methods is the safest bet. :)
      > > >
      > > > ​Cheers,
      > > > Oliver​
      > > >
      > > >
      > > > T: 0421 972 953 | E: oliver.coleman@ | W: http://ojcoleman.com
      > >
      > > >
      > > >
      > > >
      > > > On 11 June 2013 08:55, Oliver Coleman <oliver.coleman@> wrote:
      > > >
      > > > > Hi Joel,
      > > > >
      > > > > Thanks for your advice!
      > > > >
      > > > > Creating pressure for diversity within the population by comparing
      > > novelty
      > > > > among all current members certainly seems like a good idea and makes
      > > > > intuitive sense. In "Novelty-based Multiobjectivization" (J. Mouret,
      > > > > 2009) it was found that ignoring the current population resulted in
      > > much
      > > > > slower convergence on the solution to a deceptive T-maze task, though
      > > I'm
      > > > > not entirely sure if this is due to higher diversity in the population.
      > > > >
      > > > > "
      > > > > That said, the simpler algorithm you suggest is interesting. It seems a
      > > > > bit more greedy in nature and may work well sometimes in practice. One
      > > > > slightly strange thing about it is that the evaluation order of
      > > individuals
      > > > > within a generation may matter; that is, the novelty of an individual
      > > > > evaluated later in the population may be affected by archive additions
      > > > > earlier. I am not sure if that is bad or good. "
      > > > >
      > > > > Yes,
      > > > >
      > > > >
      > > > > T: 0421 972 953 | E: oliver.coleman@ | W: http://ojcoleman.com
      > > > >
      > > > >
      > > > >
      > > > > On 10 June 2013 00:51, joel278 <lehman.154@> wrote:
      > > > >
      > > > >> **
      > >
      > > > >>
      > > > >>
      > > > >> Oliver,
      > > > >>
      > > > >> Also related to the simplifying the novelty search algorithm is the
      > > idea
      > > > >> of adding to the archive probabilistically instead of using a
      > > threshold.
      > > > >> That is, in the original C++ implementation individuals are added to
      > > the
      > > > >> archive when their novelty is greater than an experimenter-specified
      > > > >> threshold (which an also vary dynamically). However, in new
      > > implementations
      > > > >> I've tended to remove the threshold and instead add any new
      > > individual to
      > > > >> the archive (at the end of a generation) with fixed probability (e.g.
      > > > >> 0.05%).
      > > > >>
      > > > >> Note that this approach is also described in a paper applying novelty
      > > > >> search to genetic programming (
      > > > >> http://eplex.cs.ucf.edu/publications/2010/lehman-gecco10b).
      > > > >>
      > > > >> One nice thing about this approach is that it is easier to understand
      > > how
      > > > >> changing the probability will influence archive growth than the
      > > novelty
      > > > >> threshold. That is, the expectation of growth per generation is just
      > > the
      > > > >> probability of addition (which is a parameter to be chosen by the
      > > > >> experimenter) times the population size. In contrast, the novelty
      > > threshold
      > > > >> is specified in terms of a more abstract quantity (i.e. novelty
      > > scores),
      > > > >> and while this threshold can also be adjusted dynamically to add one
      > > or two
      > > > >> individuals per generation on average, it can add some complication
      > > to the
      > > > >> implementation.
      > > > >>
      > > > >> Adding to the archive probabilistically (i.e. each new individual has
      > > > >> some fixed chance of being added to the archive regardless of how
      > > novel
      > > > >> they are) may also be more principled than the threshold method. In
      > > effect,
      > > > >> adding probabilistically samples uniformly where search has been and
      > > > >> creates an accumulating force away from behaviors search has been
      > > spending
      > > > >> most effort exploring. In contrast, adding new individuals to the
      > > archive
      > > > >> when they are greater than the threshold tends to create a small
      > > repulsive
      > > > >> force exactly where things are most novel. Of course, over time it
      > > also
      > > > >> approximates where search has been, but the probabilistic approach
      > > does so
      > > > >> more directly.
      > > > >>
      > > > >> In any case, I thought I'd mention this slightly nuanced
      > > implementation
      > > > >> detail because it also relates to interactions between the archive and
      > > > >> population, and is perhaps a simpler and more principled way to
      > > accumulate
      > > > >> an archive of past behaviors to encourage search to diverge from
      > > behaviors
      > > > >> explored in the past.
      > > > >>
      > > > >> Best,
      > > > >> Joel
      > > > >>
      > > > >>
      > > > >> --- In neat@yahoogroups.com, "joel278" <lehman.154@> wrote:
      > > > >> >
      > > > >> >
      > > > >> >
      > > > >> > Hi Oliver,
      > > > >> >
      > > > >> > Thanks for raising this interesting question relating to pairing
      > > > >> novelty search with generational evolutionary algorithms. Whether
      > > novelty
      > > > >> search is performed generationally or in a steady-state algorithm, I
      > > think
      > > > >> that taking the population into account in some way or another when
      > > > >> calculating the novelty of new individuals can often be very helpful.
      > > > >> >
      > > > >> > In particular, the motivation for measuring novelty against the
      > > current
      > > > >> population as well as the archive is to take all available
      > > information into
      > > > >> account. While it is true that the archive alone provides some
      > > information
      > > > >> about where in the space of behaviors has *previously* been searched,
      > > the
      > > > >> population gives additional information about where is *currently*
      > > being
      > > > >> searched.
      > > > >> >
      > > > >> > In other words, it is likely desirable to have the population itself
      > > > >> spread over the space of previously unexplored behaviors. If only the
      > > > >> archive is taken into account, it is possible that the population
      > > itself
      > > > >> may converge to searching one novel area of the behavior space (where
      > > there
      > > > >> are few archive points), which could potentially lead down blind
      > > alleys.
      > > > >> When the population is taken into account there is some repulsive
      > > force
      > > > >> within the population to maintain diversity and explore different
      > > novel
      > > > >> areas of the behavior space -- which may in general benefit exploring
      > > the
      > > > >> overall search for novelty.
      > > > >> >
      > > > >> >
      > > > >> ​​
      > >
      > > > >> That said, the simpler algorithm you suggest is interesting. It seems
      > > a
      > > > >> bit more greedy in nature and may work well sometimes in practice. One
      > > > >> slightly strange thing about it is that the evaluation order of
      > > individuals
      > > > >> within a generation may matter; that is, the novelty of an individual
      > > > >> evaluated later in the population may be affected by archive additions
      > > > >> earlier. I am not sure if that is bad or good.
      > > > >> >
      > > > >> > In a generational novelty search in particular, it may be wise to
      > > > >> reduce selection pressure or increase the number of nearest neighbors
      > > > >> considered in calculated novelty. The reason is that unlike in the
      > > steady
      > > > >> state variation, where the novelty of an individual will smoothly
      > > vary over
      > > > >> time (as individuals are replaced individually), in a generational
      > > model,
      > > > >> the novelty of an individual can change abruptly over generations
      > > (what is
      > > > >> novel one generation may not be novel even the next generation). To
      > > provide
      > > > >> a smoother gradient, it may thus be important to reduce novelty
      > > pressure
      > > > >> (e.g. by decreasing the greediness of the search through the survival
      > > > >> threshold or however you are applying pressure, or by increasing the
      > > size
      > > > >> of the neighborhood considered for calculating novelty, which may also
      > > > >> smooth novelty calculations).
      > > > >> >
      > > > >> > I hope you find this response informative, while novelty search is
      > > > >> viable whether it is generational or steady-state, there are some
      > > factors
      > > > >> that may increase its performance when specializing the algorithm to
      > > > >> generational or steady-state evolutionary algorithms in particular.
      > > > >> >
      > > > >> > Best,
      > > > >> > Joel
      > > > >> >
      > > > >> > --- In neat@yahoogroups.com, Oliver Coleman <oliver.coleman@>
      > > wrote:
      > > > >> > >
      > > > >> > > Hi all,
      > > > >> > >
      > > > >> > > I have a question about implementing novelty search in a
      > > generational
      > > > >> GA.
      > > > >> > > In "Abandoning Objectives: Evolution through the
      > > > >> > > Search for Novelty Alone" (Lehman and Stanley, 2011, pg 13), it
      > > > >> suggests
      > > > >> > > that it's necessary (or at least a good idea) to determine the
      > > > >> novelty of
      > >
      > > > >> > > an individual against the archive and the (entire) current
      > > population.
      > > > >> > >
      > > > >> > > I'm wondering why this is better than the following approach:
      > > > >> > > for (individual I in population)
      > > > >> > > N = novelty of I measured against archive
      > > > >> > > if (N > threshold)
      > > > >> > > add I to archive
      > > > >> > >
      > > > >> > > That is, if you iterate through the population, adding
      > > individuals to
      > > > >> the
      > > > >> > > archive as you go, then is this equivalent (or a reasonable
      > > > >> approximation)
      > > > >> > > to checking each individual against the entire population and the
      > > > >> archive?
      > > > >> > > If not, why not?
      > > > >> > >
      > > > >> > > Thanks in advance for any assistance! :)
      > > > >> > >
      > > > >> > > Cheers,
      > > > >> > > Oliver
      > > > >> > >
      > >
      > > > >> > > T: 0421 972 953 | E: oliver.coleman@ | W: http://ojcoleman.com
      > > > >> > >
      > > > >> >
      > > > >>
      > > > >>
      > > > >>
      > > > >
      > > > >
      > > >
      > >
      > >
      > >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.