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

6379Re: [neat] Multiobjective NEAT/HyperNEAT papers

Expand Messages
  • kenstanley01
    Jul 18, 2014
    • 0 Attachment
      Hi Jared and Josh,

      There are a number of different ways that NEAT or HyperNEAT can be integrated into a multiobjective framework.  The trickiest part usually involves what to do about speciation when multiobjective algorithms like NSGA-II want to control the main loop and do selection themselves.  What Josh describes is probably the most common solution: adding a genetic diversity objective in lieu of the conventional NEAT style of fitness adjustment from speciation.   You can see that technique also used in some of our recent publications that use multiobjective versions of NEAT or HyperNEAT.  For example:



      This idea is often used also if a novelty objective is being combined with other objectives in NEAT.  It is important to note that novelty (which is calculated over behavior) is different from genetic diversity (which is calculated through NEAT-style genotypic differences based on historical markings).  So usually when we've done multiobjective optimization with novelty as an objective we've also included genetic diversity, as in the first paper above.  

      Josh also mentions that he uses the NEAT compatibility metric to do the genetic diversity, and that's a useful point to highlight:  you can still use historical markings and compute genotypic distances as in the original NEAT, even in a multiobjective framework.  In fact, it is important to do that - any other way of measuring diversity is likely to have unintended consequences (like simply rewarding being bigger, which is not the intent).

      Although this advice and the precedent for it sounds simple enough, it's important to note that the right way to go about multiobjectivizing NEAT is still not a settled issue.  The genetic diversity objective is easy enough to include, but it is *not* equivalent to NEAT-style speciation, and in some domains there may be a cost to that.  This subtlety is not widely recognized and not published but we have unpublished evidence that a genetic diversity objective can actually be damaging whereas NEAT-style speciation may not be (if one is swapped with the other and all else remains equal).  The reason is that an objective that rewards genetic diversity rewards genomes that are completely useless yet crazy, pushing up bloat (an important side effect) and wasting evaluations on junk.  This problem arises because it is extremely easy to dominate on genetic diversity simply by adding more genetic bloat - and dominating on one objective is enough to get offspring allocated in a multiobjective setting.  In regular NEAT-style speciation, on the other hand, genetic diversity merely *adjusts* fitness, which means that being completely horrible tempers the advantage of being genetically unique.  This difference is a real concern as people (including our own group) swap one for the other as if they are equivalent.

      Perhaps an alternative that we should consider is to forego having an explicit genetic diversity objective and instead adjust all the fitness values for all the objectives prior to NSGA-II ranking in the usual way the NEAT-style speciation adjusts fitnesses, and then hand everything back to NSGA-II.  Or something like that.  Like I said, unfortunately there is almost nothing published about these subtleties but unpublished experimental results have me worried that we are replacing NEAT with something not as healthy as NEAT when we go to multiobjectivize NEAT and think they're the same thing.  The subject deserves more thought.  It's worth noting though that for some problems simply adding the genetic diversity objectives works fine enough (which is why people have been using it), so it is obviously a practical option in some cases, but I think it is ultimately flawed.

      On the other hand, there is a strain of thought in the community that you don't even need genetic diversity anymore now that novelty (i.e. behavioral diversity) has been shown so powerful.  Some believe that the use of such novelty now eclipses the need for genetic diversity.  Once again, for some problems that may be true, but also once again I have seen experimental results in some domains that suggest that genetic diversity is still important, even if you also have novelty, and I believe we would be throwing it away at our long-term peril (especially for runs that are intended to go for very many generations).  Genetic diversity in my view (and based on experimental results) complements novelty because sometimes a new kind of genotype has the *potential* to do something novel but needs several generations to get there.  Without speciation (or some kind of protection) such a genotype will be lost, and the potential novelty it could have yielded lost with it.

      As you can see, the issues here are more complex than they may initially seem, and there are basically two ways to approach it:  One is just to do what has been done before and not think about it too much.  Another is to really pursue trying to do it the best possible way and think about the subtleties of the particular way genetic diversity is interleaved into multiobjective NEAT or HyperNEAT.  Both are legitimate depending on the domain and purpose of the empirical research.

      Best,

      ken

    • Show all 5 messages in this topic