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

Re: [neat] Re: Combining NSGA-II and NEAT speciated fitness sharing

Expand Messages
  • Drew Kirkpatrick
    Josh, As far as behavioral diversity goes, there s been some interesting papers on using information distance. I used a normalized compression distance (really
    Message 1 of 14 , Jun 14, 2013
    • 0 Attachment

      Josh,

      As far as behavioral diversity goes, there's been some interesting papers on using information distance. I used a normalized compression distance (really general method) measure to drive novelty search, with ok-ish results, although it wasn't a particularly deceptive task.

      I like the idea of a general method for measuring behavioral novelty, even if they can be computationally expensive.

      -Drew

      On Jun 14, 2013 10:25 AM, "Joshua Auerbach" <joshua.auerbach@...> wrote:
       

      Hi everyone,

      I just want to chime in and say that in some recent work (currently under review) I did basically the same thing as you have described in these two papers (even though I was not aware of them).  I replaced NEAT's speciation mechanism with a genotypic diversity metric computed as the distance to the k-nearest neighbors calculated using NEAT's genomic distance measure.  This seemed to work well enough.  Though, as Stephane mentioned, based on his and Jean-Baptiste's work it is quite likely that using a behavioral diversity metric would be even more effective.  However, in some domains it is not clear how behavioral distance should be characterized.

      Ken/Joel, I do have a question for you:  In my NSGA-II / CPPN-NEAT hybrid I did not use any crossover and just relied on asexual reproduction.  Did  you incorporate sexual reproduction in your implementation?  If so, how did you determine which individuals were allowed to mate if speciation was not employed?

      Best,
      Josh




      On 06/13/2013 10:37 PM, Oliver Coleman wrote:
       
      "Effective Diversity Maintenance in Deceptive Domains" (J. Lehman, K. Stanley, R. Miikkulainen. 2013)
      Disables speciation and uses explicit genetic diversity objective (Handles it in the same way as the first one you linked).


      On 14 June 2013 08:07, Ken <kstanley@...> wrote:
       

      Our group recently has tried simply replacing NEAT-style speciation with a "genetic diversity objective." The benefit of that approach is that you don't have to worry about the interaction between speciation and the pareto front while you still get some protection for genetic diversity; the downside of course is it's not certain that the dynamics will be exactly like fitness sharing. But you can see an example of this approach in this paper:

      http://eplex.cs.ucf.edu/papers/lehman_ab13.pdf

      The genetic diversity objective is defined there as: "In particular, the genomic diversity of a given genome is quantifi ed as the average distance to its k-nearest neighbors in genotype space as measured by NEAT's genomic distance measure."


      -- 
      Dr. Joshua E. Auerbach
      Morphology, Evolution and Cognition Lab
      Dept of Computer Science / Vermont Complex Systems Center
      University of Vermont 
    • Joshua Auerbach
      Drew, (changed the subject, since this is branching off into a separate topic) I actually have played some with NCD (using gzip) but found it to be
      Message 2 of 14 , Jun 14, 2013
      • 0 Attachment
        Drew,

        (changed the subject, since this is branching off into a separate topic)

        I actually have played some with NCD (using gzip) but found it to be prohibitively slow for comparing expressive vectors with any decently large population size.  Though I agree that it is conceptually quite appealing: especially its ability to compare vectors of different sizes.

        Stephane and Jean-Baptiste have shown that even simple distance measures such as Hamming distance between binary sensory-motor vectors can work well.  But, if an individual is a robot with an evolving morphology and it does not have a fixed set of sensors or motors it becomes less clear what the vector characterizing its behavior should be.  You could still use vectors of sensory motor signals and have vectors of different sizes, in which case you would need something like NCD.  Or, you could use some other behavioral characterization that would always have a fixed dimension in which you would be losing a lot of information about the individual's behavior.

        Do you have some way of approximating NCD that is more computationally feasible?

        Best,
        Josh


        On 06/14/2013 10:35 AM, Drew Kirkpatrick wrote:
         

        Josh,

        As far as behavioral diversity goes, there's been some interesting papers on using information distance. I used a normalized compression distance (really general method) measure to drive novelty search, with ok-ish results, although it wasn't a particularly deceptive task.

        I like the idea of a general method for measuring behavioral novelty, even if they can be computationally expensive.

        -Drew

        On Jun 14, 2013 10:25 AM, "Joshua Auerbach" <joshua.auerbach@...> wrote:
         

        Hi everyone,

        I just want to chime in and say that in some recent work (currently under review) I did basically the same thing as you have described in these two papers (even though I was not aware of them).  I replaced NEAT's speciation mechanism with a genotypic diversity metric computed as the distance to the k-nearest neighbors calculated using NEAT's genomic distance measure.  This seemed to work well enough.  Though, as Stephane mentioned, based on his and Jean-Baptiste's work it is quite likely that using a behavioral diversity metric would be even more effective.  However, in some domains it is not clear how behavioral distance should be characterized.

        Ken/Joel, I do have a question for you:  In my NSGA-II / CPPN-NEAT hybrid I did not use any crossover and just relied on asexual reproduction.  Did  you incorporate sexual reproduction in your implementation?  If so, how did you determine which individuals were allowed to mate if speciation was not employed?

        Best,
        Josh




        On 06/13/2013 10:37 PM, Oliver Coleman wrote:
         
        "Effective Diversity Maintenance in Deceptive Domains" (J. Lehman, K. Stanley, R. Miikkulainen. 2013)
        Disables speciation and uses explicit genetic diversity objective (Handles it in the same way as the first one you linked).


        On 14 June 2013 08:07, Ken <kstanley@...> wrote:
         

        Our group recently has tried simply replacing NEAT-style speciation with a "genetic diversity objective." The benefit of that approach is that you don't have to worry about the interaction between speciation and the pareto front while you still get some protection for genetic diversity; the downside of course is it's not certain that the dynamics will be exactly like fitness sharing. But you can see an example of this approach in this paper:

        http://eplex.cs.ucf.edu/papers/lehman_ab13.pdf

        The genetic diversity objective is defined there as: "In particular, the genomic diversity of a given genome is quantifi ed as the average distance to its k-nearest neighbors in genotype space as measured by NEAT's genomic distance measure."


        -- 
        Dr. Joshua E. Auerbach
        Morphology, Evolution and Cognition Lab
        Dept of Computer Science / Vermont Complex Systems Center
        University of Vermont 


        -- 
        Dr. Joshua E. Auerbach
        Morphology, Evolution and Cognition Lab
        Dept of Computer Science / Vermont Complex Systems Center
        University of Vermont 
      • Drew Kirkpatrick
        Josh, I tried a number of methods to speed up the speed of NCD in my second M.S. thesis. Some of the approaches I used do deviate from the more general
        Message 3 of 14 , Jun 14, 2013
        • 0 Attachment

          Josh,

          I tried a number of methods to speed up the speed of NCD in my second M.S. thesis. Some of the approaches I used do deviate from the more general approach, but I was just trying to see what worked.

          Don't have the paper handy, but it and all my source code are on the list from last year. If you search for novelty search and competitive coevolution you should find it.

          I really wanted to try out another task that was more deceptive, but weekend warrior-ing grad school didn't leave me time to add more to the project.

          Maybe something in that paper might give you some ideas.

          -Drew

          On Jun 14, 2013 11:09 AM, "Joshua Auerbach" <joshua.auerbach@...> wrote:
           

          Drew,

          (changed the subject, since this is branching off into a separate topic)

          I actually have played some with NCD (using gzip) but found it to be prohibitively slow for comparing expressive vectors with any decently large population size.  Though I agree that it is conceptually quite appealing: especially its ability to compare vectors of different sizes.

          Stephane and Jean-Baptiste have shown that even simple distance measures such as Hamming distance between binary sensory-motor vectors can work well.  But, if an individual is a robot with an evolving morphology and it does not have a fixed set of sensors or motors it becomes less clear what the vector characterizing its behavior should be.  You could still use vectors of sensory motor signals and have vectors of different sizes, in which case you would need something like NCD.  Or, you could use some other behavioral characterization that would always have a fixed dimension in which you would be losing a lot of information about the individual's behavior.

          Do you have some way of approximating NCD that is more computationally feasible?

          Best,
          Josh


          On 06/14/2013 10:35 AM, Drew Kirkpatrick wrote:
           

          Josh,

          As far as behavioral diversity goes, there's been some interesting papers on using information distance. I used a normalized compression distance (really general method) measure to drive novelty search, with ok-ish results, although it wasn't a particularly deceptive task.

          I like the idea of a general method for measuring behavioral novelty, even if they can be computationally expensive.

          -Drew

          On Jun 14, 2013 10:25 AM, "Joshua Auerbach" <joshua.auerbach@...> wrote:
           

          Hi everyone,

          I just want to chime in and say that in some recent work (currently under review) I did basically the same thing as you have described in these two papers (even though I was not aware of them).  I replaced NEAT's speciation mechanism with a genotypic diversity metric computed as the distance to the k-nearest neighbors calculated using NEAT's genomic distance measure.  This seemed to work well enough.  Though, as Stephane mentioned, based on his and Jean-Baptiste's work it is quite likely that using a behavioral diversity metric would be even more effective.  However, in some domains it is not clear how behavioral distance should be characterized.

          Ken/Joel, I do have a question for you:  In my NSGA-II / CPPN-NEAT hybrid I did not use any crossover and just relied on asexual reproduction.  Did  you incorporate sexual reproduction in your implementation?  If so, how did you determine which individuals were allowed to mate if speciation was not employed?

          Best,
          Josh




          On 06/13/2013 10:37 PM, Oliver Coleman wrote:
           
          "Effective Diversity Maintenance in Deceptive Domains" (J. Lehman, K. Stanley, R. Miikkulainen. 2013)
          Disables speciation and uses explicit genetic diversity objective (Handles it in the same way as the first one you linked).


          On 14 June 2013 08:07, Ken <kstanley@...> wrote:
           

          Our group recently has tried simply replacing NEAT-style speciation with a "genetic diversity objective." The benefit of that approach is that you don't have to worry about the interaction between speciation and the pareto front while you still get some protection for genetic diversity; the downside of course is it's not certain that the dynamics will be exactly like fitness sharing. But you can see an example of this approach in this paper:

          http://eplex.cs.ucf.edu/papers/lehman_ab13.pdf

          The genetic diversity objective is defined there as: "In particular, the genomic diversity of a given genome is quantifi ed as the average distance to its k-nearest neighbors in genotype space as measured by NEAT's genomic distance measure."


          -- 
          Dr. Joshua E. Auerbach
          Morphology, Evolution and Cognition Lab
          Dept of Computer Science / Vermont Complex Systems Center
          University of Vermont 


          -- 
          Dr. Joshua E. Auerbach
          Morphology, Evolution and Cognition Lab
          Dept of Computer Science / Vermont Complex Systems Center
          University of Vermont 
        • Ken
          Hi Stef, I changed the subject again just to make it easier to keep track as the conversation branches. Thanks for pointing out these insights and your work on
          Message 4 of 14 , Jun 14, 2013
          • 0 Attachment
            Hi Stef,

            I changed the subject again just to make it easier to keep track as the conversation branches.

            Thanks for pointing out these insights and your work on behavioral vs. genetic diversity. It does appear that behavioral diversity and novelty are emerging through recent research such as your own as more critical factors in maintaining healthy diversity than genetic diversity, in particular when the diversity is in service of achieving a traditional objective (i.e. when one of the multiple objectives is some kind of task-specific performance measure).

            However, genetic diversity may still play a useful role in combination with behavioral diversity or novelty, which I want to illustrate here. Recall that the original motivation in NEAT for maintaining genetic diversity was to ensure that genetic innovations (i.e. additions of structure) are not eliminated prematurely. That is, the point is to ensure that individuals with new structure are not eliminated before they have a chance to show their potential by optimizing their weights over several more generations. Placing them in protected species gives them that opportunity to optimize further.

            However, recent results such as yours suggest that when you have a target objective, protecting behavioral diversity is so effective (most likely because it help avoid deception) that a system with only behavioral diversity will likely come closer to the objective than one with only genetic diversity.

            But that leaves open the possibility that genetic diversity can complement behavioral diversity or novelty. One interesting question is whether in the "Encouraging Behavioral Diversity in Evolutionary Robotics" paper the results would be even better if *both* behavioral diversity/novelty and genetic diversity were combined (as our group has done in recent papers). Going back to the motivation in NEAT for genetic diversity, the logic for why it would still matter when combined with behavioral diversity/novelty can be seen:

            Just as we do not know at first for any structural innovation whether that innovation might lead to higher fitness in an objective-based problem, we also do not know initially whether a particular structural innovation might lead later to more *novelty*. Often structural additions in neuroevolution lead to a complete collapse in behavior, which obviously hurts fitness, but also hurts novelty because degenerate behaviors are not considered novel (except at the very beginning of the run). Therefore, if you are not protecting genetic diversity when novelty/behavioral diversity are one of the objectives, then you are risking prematurely eliminating genotypes before their potential for novelty has been explored.

            However, perhaps more significant in magnitude than even that scenario is whether novelty alone (as in novelty search) can drive a search as effectively without genetic diversity than it can with it. When you are searching for a specific objective target, deception is the overriding pathology, which is why behavioral diversity is such a potent antidote. However, if you are searching only for novelty, then obviously deception is no longer the issue (since you are not looking for any one thing), which means that now other pathologies (such as prematurely losing structural innovations from the population) would become more important. Therefore, the impact of forgoing genetic diversity might be more evident in that context.

            Furthermore, even if this issue is most evident in pure novelty search, it may still appear to some extent in any search where behavioral diversity is important, since genetic diversity ultimately drives behavioral diversity.

            This issue probably merits further study. I only mean to raise the question, not to argue that the answer is conclusive. I'm guessing the real answer is probably nuanced. For example, it may be that genetic diversity is more important early in a run when small structural changes tend to have the most dramatic effects on behavior. Perhaps in later generations because the effect tends to be less the need for genotypic protection might reduce. But my guess is that ultimately genetic diversity and behavioral diversity both play a role in healthy evolution, and in fact complement each other (because genetic diversity helps foster behavioral diversity). I would also guess the effect would be more pronounced the more a search relies on novelty as its primary driver (with pure novelty search being the most extreme such case). Of course these are currently just speculations on my part.

            Best,

            ken


            --- In neat@yahoogroups.com, Stéphane Doncieux <stephane.doncieux@...> wrote:
            >
            > Hi Oliver,
            >
            > we are using NSGA-II for neuroevolution for quite a while now, and in
            > the same situation, we have actually chosen to use a simplified version
            > of NEAT. We have discarded the innovation numbers and thus the
            > speciation and crossover and kept only the idea of starting simple. We
            > have actually replaced all of it with an objective that rewards the
            > behavioral diversity of the robot we were evolving. We made some
            > comparisons with NEAT in this paper: "Mouret, J.-B. and Doncieux, S.
            > (2012). Encouraging Behavioral Diversity in Evolutionary Robotics: an
            > Empirical Study. Evolutionary Computation. Vol 20 No 1 Pages 91-133", cf
            > http://www.isir.upmc.fr/files/2011ACLI2061.pdf
            > It revealed to be more efficient than NEAT on the different setups that
            > we did consider.
            >
            > Since then, if we don't have a reason to use something else, we use this
            > simple encoding either with a behavioral diversity objective or with a
            > novelty objective. It gives not bad results, see
            > http://www.youtube.com/watch?feature=player_embedded&v=Trj0_A1ZfNo, for
            > instance. It has at least the advantage of being simple. If you want
            > some source code and/or look at the work we have done on this topic, you
            > can have a look at http://pages.isir.upmc.fr/evorob_db/.
            >
            > I know that it does not directly answer your question, but my advice
            > would be at least to test such an approach with a simpler encoding and
            > some helper objectives. It is quite straightforward to implement and
            > will give you some reference points with which to compare the
            > performance of more complex algorithms. The other advantage is that the
            > day researchers in multi-objective evolutionary algorithms come up with
            > a new and more efficient algorithm, it should be simple to use it. By
            > the way, if you experience problem with that, I would be happy to
            > discuss it with you.
            >
            > Hope it helps,
            >
            > Best,
            >
            > stephane
            >
          • Stéphane Doncieux
            Hi, we have also tried NCD with gzip and it was really too slow. If someone knows how to estimate it in a reasonable time, I am interested... By the way, a
            Message 5 of 14 , Jun 15, 2013
            • 0 Attachment
              Hi,

              we have also tried NCD with gzip and it was really too slow. If someone knows how to estimate it in a reasonable time, I am interested... By the way, a generic measure would be nice, but there is an alternative that we have tested in a paper that I will present at CEC next week. We have just used several different behavioral measures in a single run. Actually, it gives better results than using a single behavioral diversity measure. The intuition is that it is actually difficult to capture with a single measure all the different aspects of a behavior. Thus by considering several measures, we have the opportunity to take into account multiple aspects of the behavior. We have more chance to find differences between behaviors and we thus better keep behavioral diversity and foster exploration. In practice it is often easy to think about several different behavior distances and more difficult to choose one. See " S. Doncieux, J.-B. Mouret. Behavioral Diversity with Multiple Behavioral Distances. IEEE Congress on Evolutionary Computation, 2013 (CEC 2013). " available for download from http://pages.isir.upmc.fr/evorob_db

              best,

              stephane

              > Josh,
              >
              > I tried a number of methods to speed up the speed of NCD in my
              second M.S.
              > thesis. Some of the approaches I used do deviate from the more
              general
              > approach, but I was just trying to see what worked.
              >
              > Don't have the paper handy, but it and all my source code are
              on the list
              > from last year. If you search for novelty search and
              competitive
              > coevolution you should find it.
              >
              > I really wanted to try out another task that was more
              deceptive, but
              > weekend warrior-ing grad school didn't leave me time to add
              more to the
              > project.
              >
              > Maybe something in that paper might give you some ideas.
              >
              > -Drew
              > On Jun 14, 2013 11:09 AM, "Joshua Auerbach"
              <joshua.auerbach@...> wrote:
              >
              > > **
              > >
              > >
              > > Drew,
              > >
              > > (changed the subject, since this is branching off into a
              separate topic)
              > >
              > > I actually have played some with NCD (using gzip) but
              found it to be
              > > prohibitively slow for comparing expressive vectors with
              any decently large
              > > population size. Though I agree that it is conceptually
              quite appealing:
              > > especially its ability to compare vectors of different
              sizes.
              > >
              > > Stephane and Jean-Baptiste have shown that even simple
              distance measures
              > > such as Hamming distance between binary sensory-motor
              vectors can work
              > > well. But, if an individual is a robot with an evolving
              morphology and it
              > > does not have a fixed set of sensors or motors it becomes
              less clear what
              > > the vector characterizing its behavior should be. You
              could still use
              > > vectors of sensory motor signals and have vectors of
              different sizes, in
              > > which case you would need something like NCD. Or, you
              could use some other
              > > behavioral characterization that would always have a fixed
              dimension in
              > > which you would be losing a lot of information about the
              individual&#39;s
              > > behavior.
              > >
              > > Do you have some way of approximating NCD that is more
              computationally
              > > feasible?
              > >
              > > Best,
              > > Josh
              > >
              > >
              > > On 06/14/2013 10:35 AM, Drew Kirkpatrick wrote:
              > >
              > >
              > >
              > > Josh,
              > >
              > > As far as behavioral diversity goes, there's been some
              interesting papers
              > > on using information distance. I used a normalized
              compression distance
              > > (really general method) measure to drive novelty search,
              with ok-ish
              > > results, although it wasn't a particularly deceptive task.
              > >
              > > I like the idea of a general method for measuring
              behavioral novelty, even
              > > if they can be computationally expensive.
              > >
              > > -Drew
              > > On Jun 14, 2013 10:25 AM, "Joshua Auerbach"
              <joshua.auerbach@...>
              > > wrote:
              > >
              > >>
              > >>
              > >> Hi everyone,
              > >>
              > >> I just want to chime in and say that in some recent
              work (currently under
              > >> review) I did basically the same thing as you have
              described in these two
              > >> papers (even though I was not aware of them). I
              replaced NEAT's speciation
              > >> mechanism with a genotypic diversity metric computed
              as the distance to the
              > >> k-nearest neighbors calculated using NEAT's genomic
              distance measure. This
              > >> seemed to work well enough. Though, as Stephane
              mentioned, based on his
              > >> and Jean-Baptiste&#39;s work it is quite likely
              that using a behavioral
              > >> diversity metric would be even more effective.
              However, in some domains it
              > >> is not clear how behavioral distance should be
              characterized.
              > >>
              > >> Ken/Joel, I do have a question for you: In my NSGA-II
              / CPPN-NEAT hybrid
              > >> I did not use any crossover and just relied on asexual
              reproduction. Did
              > >> you incorporate sexual reproduction in your
              implementation? If so, how did
              > >> you determine which individuals were allowed to mate
              if speciation was not
              > >> employed?
              > >>
              > >> Best,
              > >> Josh
              > >>
              > >>
              > >>
              > >>
              > >> On 06/13/2013 10:37 PM, Oliver Coleman wrote:
              > >>
              > >>
              > >> "Effective Diversity Maintenance in Deceptive Domains"
              (J. Lehman, K.
              > >> Stanley, R. Miikkulainen. 2013)
              > >> http://eplex.cs.ucf.edu/papers/lehman_gecco13.pdf
              > >> Disables speciation and uses explicit genetic
              diversity
              > >> objective (Handles it in the same way as the first one
              you linked).
              > >>
              > >>
              > >> On 14 June 2013 08:07, Ken
              <kstanley@...> wrote:
              > >>
              > >>>
              > >>>
              > >>> Our group recently has tried simply replacing
              NEAT-style speciation with
              > >>> a "genetic diversity objective." The benefit of
              that approach is that you
              > >>> don't have to worry about the interaction between
              speciation and the pareto
              > >>> front while you still get some protection for
              genetic diversity; the
              > >>> downside of course is it's not certain that the
              dynamics will be exactly
              > >>> like fitness sharing. But you can see an example
              of this approach in this
              > >>> paper:
              > >>>
              > >>> http://eplex.cs.ucf.edu/papers/lehman_ab13.pdf
              > >>>
              > >>> The genetic diversity objective is defined there
              as: "In particular, the
              > >>> genomic diversity of a given genome is quantifi ed
              as the average distance
              > >>> to its k-nearest neighbors in genotype space as
              measured by NEAT's genomic
              > >>> distance measure."
              > >>>
              > >>
              > >> --
              > >> Dr. Joshua E. Auerbach
              > >> Morphology, Evolution and Cognition Lab
              > >> Dept of Computer Science / Vermont Complex Systems
              Center
              > >> University of Vermont
              > >>
              > >>
              > >
              > > --
              > > Dr. Joshua E. Auerbach
              > > Morphology, Evolution and Cognition Lab
              > > Dept of Computer Science / Vermont Complex Systems Center
              > > University of Vermont
              > >
              > >
              > >

            • Stéphane Doncieux
              Hi Ken, I certainly did not want to say that genetic diversity is not important. I just wanted to say that behavioral diversity should not be neglected and
              Message 6 of 14 , Jun 15, 2013
              • 0 Attachment
                Hi Ken,

                I certainly did not want to say that genetic diversity is not important.
                I just wanted to say that behavioral diversity should not be neglected
                and that genotypic diversity, in my opinion, should not be preferred
                over behavioral diversity if one only is to be used. I have the feeling
                that genotypic diversity is not the main bottleneck, but I do also think
                that it is important (and the performance of NEAT prove it). The thing
                is that keeping a good diversity in the genotype space is not enough to
                guarantee a good diversity in the behavioral space, as many different
                neural networks may have the same behavior (think about neurons that are
                not connected to outputs or neural network parts connected to sensors
                that are not activated for a while) and likewise very close neural
                networks may result in very different behaviors.

                By the way, I completely agree with you, Ken, genotypic and behavioral
                diversity are very probably complimentary. Combining both will certainly
                lead to better results and it would be interesting to further
                investigate it.

                Best,

                stef

                >
                > Hi Stef,
                >
                > I changed the subject again just to make it easier to keep track as
                the conversation branches.
                >
                > Thanks for pointing out these insights and your work on behavioral vs.
                genetic diversity. It does appear that behavioral diversity and novelty
                are emerging through recent research such as your own as more critical
                factors in maintaining healthy diversity than genetic diversity, in
                particular when the diversity is in service of achieving a traditional
                objective (i.e. when one of the multiple objectives is some kind of
                task-specific performance measure).
                >
                > However, genetic diversity may still play a useful role in combination
                with behavioral diversity or novelty, which I want to illustrate here.
                Recall that the original motivation in NEAT for maintaining genetic
                diversity was to ensure that genetic innovations (i.e. additions of
                structure) are not eliminated prematurely. That is, the point is to
                ensure that individuals with new structure are not eliminated before
                they have a chance to show their potential by optimizing their weights
                over several more generations. Placing them in protected species gives
                them that opportunity to optimize further.
                >
                > However, recent results such as yours suggest that when you have a
                target objective, protecting behavioral diversity is so effective (most
                likely because it help avoid deception) that a system with only
                behavioral diversity will likely come closer to the objective than one
                with only genetic diversity.
                >
                > But that leaves open the possibility that genetic diversity can
                complement behavioral diversity or novelty. One interesting question is
                whether in the "Encouraging Behavioral Diversity in Evolutionary
                Robotics" paper the results would be even better if *both* behavioral
                diversity/novelty and genetic diversity were combined (as our group has
                done in recent papers). Going back to the motivation in NEAT for genetic
                diversity, the logic for why it would still matter when combined with
                behavioral diversity/novelty can be seen:
                >
                > Just as we do not know at first for any structural innovation whether
                that innovation might lead to higher fitness in an objective-based
                problem, we also do not know initially whether a particular structural
                innovation might lead later to more *novelty*. Often structural
                additions in neuroevolution lead to a complete collapse in behavior,
                which obviously hurts fitness, but also hurts novelty because degenerate
                behaviors are not considered novel (except at the very beginning of the
                run). Therefore, if you are not protecting genetic diversity when
                novelty/behavioral diversity are one of the objectives, then you are
                risking prematurely eliminating genotypes before their potential for
                novelty has been explored.
                >
                > However, perhaps more significant in magnitude than even that scenario
                is whether novelty alone (as in novelty search) can drive a search as
                effectively without genetic diversity than it can with it. When you are
                searching for a specific objective target, deception is the overriding
                pathology, which is why behavioral diversity is such a potent antidote.
                However, if you are searching only for novelty, then obviously deception
                is no longer the issue (since you are not looking for any one thing),
                which means that now other pathologies (such as prematurely losing
                structural innovations from the population) would become more important.
                Therefore, the impact of forgoing genetic diversity might be more
                evident in that context.
                >
                > Furthermore, even if this issue is most evident in pure novelty
                search, it may still appear to some extent in any search where
                behavioral diversity is important, since genetic diversity ultimately
                drives behavioral diversity.
                >
                > This issue probably merits further study. I only mean to raise the
                question, not to argue that the answer is conclusive. I'm guessing the
                real answer is probably nuanced. For example, it may be that genetic
                diversity is more important early in a run when small structural changes
                tend to have the most dramatic effects on behavior. Perhaps in later
                generations because the effect tends to be less the need for genotypic
                protection might reduce. But my guess is that ultimately genetic
                diversity and behavioral diversity both play a role in healthy
                evolution, and in fact complement each other (because genetic diversity
                helps foster behavioral diversity). I would also guess the effect would
                be more pronounced the more a search relies on novelty as its primary
                driver (with pure novelty search being the most extreme such case). Of
                course these are currently just speculations on my part.
                >
                > Best,
                >
                > ken
              • Ken
                Oops I had forgotten that we actually do have experimental results supporting the idea that genetic diversity can be important for maintaining behavioral
                Message 7 of 14 , Jun 15, 2013
                • 0 Attachment
                  Oops I had forgotten that we actually do have experimental results supporting the idea that genetic diversity can be important for maintaining behavioral diversity. So I was mistaken to say in the previous post that it was just speculation. The publication (with Joel Lehman and Risto Miikkulainen) will appear at this year's GECCO:

                  http://eplex.cs.ucf.edu/papers/lehman_gecco13.pdf

                  The key results are in figure 5 and figure 7, which show "N" (novelty alone) and "N+S" (novelty+speciation) comparisons in a range of biped walking variant domains (figure 5) and a range of maze navigation variant domains (figure 7). These ranges mean the combinations were tested at varying levels of problem difficulty. What you can see is that overall, N+S (i.e. with genetic diversity) outperforms novelty alone.

                  In the biped task, the gap is even bigger, which makes intuitive sense if you think about: The biped tends to be a brittle task that requires precise weight tuning. In a situation like that, new neural network structure is likely to destabilize delicately tuned behaviors, leading to degenerate behaviors. Therefore, some kind of genetic diversity protection is very helpful to make it possible to explore new structural possibilities and hence the behaviors they may later enable.

                  However, even in maze navigation variants the advantage of adding speciation is seen. In fact, one other important result is that in maze navigation, N+S does better than a combination of F+N (fitness plus novelty), which shows that in some cases novelty is the ideal driver for the search, and when that is true, genetic diversity provides an additional boost.

                  So indeed I think it would be premature to throw away genetic diversity from NEAT systems too soon, especially when novelty or behavioral diversity are already in the mix. It's still an interesting topic for further investigation though.

                  Best,

                  ken

                  --- In neat@yahoogroups.com, "Ken" <kstanley@...> wrote:
                  >
                  >
                  >
                  > Hi Stef,
                  >
                  > I changed the subject again just to make it easier to keep track as the conversation branches.
                  >
                  > Thanks for pointing out these insights and your work on behavioral vs. genetic diversity. It does appear that behavioral diversity and novelty are emerging through recent research such as your own as more critical factors in maintaining healthy diversity than genetic diversity, in particular when the diversity is in service of achieving a traditional objective (i.e. when one of the multiple objectives is some kind of task-specific performance measure).
                  >
                  > However, genetic diversity may still play a useful role in combination with behavioral diversity or novelty, which I want to illustrate here. Recall that the original motivation in NEAT for maintaining genetic diversity was to ensure that genetic innovations (i.e. additions of structure) are not eliminated prematurely. That is, the point is to ensure that individuals with new structure are not eliminated before they have a chance to show their potential by optimizing their weights over several more generations. Placing them in protected species gives them that opportunity to optimize further.
                  >
                  > However, recent results such as yours suggest that when you have a target objective, protecting behavioral diversity is so effective (most likely because it help avoid deception) that a system with only behavioral diversity will likely come closer to the objective than one with only genetic diversity.
                  >
                  > But that leaves open the possibility that genetic diversity can complement behavioral diversity or novelty. One interesting question is whether in the "Encouraging Behavioral Diversity in Evolutionary Robotics" paper the results would be even better if *both* behavioral diversity/novelty and genetic diversity were combined (as our group has done in recent papers). Going back to the motivation in NEAT for genetic diversity, the logic for why it would still matter when combined with behavioral diversity/novelty can be seen:
                  >
                  > Just as we do not know at first for any structural innovation whether that innovation might lead to higher fitness in an objective-based problem, we also do not know initially whether a particular structural innovation might lead later to more *novelty*. Often structural additions in neuroevolution lead to a complete collapse in behavior, which obviously hurts fitness, but also hurts novelty because degenerate behaviors are not considered novel (except at the very beginning of the run). Therefore, if you are not protecting genetic diversity when novelty/behavioral diversity are one of the objectives, then you are risking prematurely eliminating genotypes before their potential for novelty has been explored.
                  >
                  > However, perhaps more significant in magnitude than even that scenario is whether novelty alone (as in novelty search) can drive a search as effectively without genetic diversity than it can with it. When you are searching for a specific objective target, deception is the overriding pathology, which is why behavioral diversity is such a potent antidote. However, if you are searching only for novelty, then obviously deception is no longer the issue (since you are not looking for any one thing), which means that now other pathologies (such as prematurely losing structural innovations from the population) would become more important. Therefore, the impact of forgoing genetic diversity might be more evident in that context.
                  >
                  > Furthermore, even if this issue is most evident in pure novelty search, it may still appear to some extent in any search where behavioral diversity is important, since genetic diversity ultimately drives behavioral diversity.
                  >
                  > This issue probably merits further study. I only mean to raise the question, not to argue that the answer is conclusive. I'm guessing the real answer is probably nuanced. For example, it may be that genetic diversity is more important early in a run when small structural changes tend to have the most dramatic effects on behavior. Perhaps in later generations because the effect tends to be less the need for genotypic protection might reduce. But my guess is that ultimately genetic diversity and behavioral diversity both play a role in healthy evolution, and in fact complement each other (because genetic diversity helps foster behavioral diversity). I would also guess the effect would be more pronounced the more a search relies on novelty as its primary driver (with pure novelty search being the most extreme such case). Of course these are currently just speculations on my part.
                  >
                  > Best,
                  >
                  > ken
                  >
                  >
                  > --- In neat@yahoogroups.com, Stéphane Doncieux <stephane.doncieux@> wrote:
                  > >
                  > > Hi Oliver,
                  > >
                  > > we are using NSGA-II for neuroevolution for quite a while now, and in
                  > > the same situation, we have actually chosen to use a simplified version
                  > > of NEAT. We have discarded the innovation numbers and thus the
                  > > speciation and crossover and kept only the idea of starting simple. We
                  > > have actually replaced all of it with an objective that rewards the
                  > > behavioral diversity of the robot we were evolving. We made some
                  > > comparisons with NEAT in this paper: "Mouret, J.-B. and Doncieux, S.
                  > > (2012). Encouraging Behavioral Diversity in Evolutionary Robotics: an
                  > > Empirical Study. Evolutionary Computation. Vol 20 No 1 Pages 91-133", cf
                  > > http://www.isir.upmc.fr/files/2011ACLI2061.pdf
                  > > It revealed to be more efficient than NEAT on the different setups that
                  > > we did consider.
                  > >
                  > > Since then, if we don't have a reason to use something else, we use this
                  > > simple encoding either with a behavioral diversity objective or with a
                  > > novelty objective. It gives not bad results, see
                  > > http://www.youtube.com/watch?feature=player_embedded&v=Trj0_A1ZfNo, for
                  > > instance. It has at least the advantage of being simple. If you want
                  > > some source code and/or look at the work we have done on this topic, you
                  > > can have a look at http://pages.isir.upmc.fr/evorob_db/.
                  > >
                  > > I know that it does not directly answer your question, but my advice
                  > > would be at least to test such an approach with a simpler encoding and
                  > > some helper objectives. It is quite straightforward to implement and
                  > > will give you some reference points with which to compare the
                  > > performance of more complex algorithms. The other advantage is that the
                  > > day researchers in multi-objective evolutionary algorithms come up with
                  > > a new and more efficient algorithm, it should be simple to use it. By
                  > > the way, if you experience problem with that, I would be happy to
                  > > discuss it with you.
                  > >
                  > > Hope it helps,
                  > >
                  > > Best,
                  > >
                  > > stephane
                  > >
                  >
                • Ken
                  Hi Stef, It looks like we just posted at the same time. I think we are in agreement that if only one is to be used, behavioral diversity is the priority. The
                  Message 8 of 14 , Jun 15, 2013
                  • 0 Attachment
                    Hi Stef,

                    It looks like we just posted at the same time. I think we are in agreement that if only one is to be used, behavioral diversity is the priority. The way I look at it, behavioral diversity is a way to mitigate deception, which is such a profound problem for evolution that it is almost essential to do something about it. On the other hand, genetic diversity is mainly a way to protect structural innovation, which can help with achieving behavioral diversity, but on its own is not enough to deal with the profound problem of deception. So we seem to be pretty much in agreement overall.

                    Best,

                    ken

                    --- In neat@yahoogroups.com, Stéphane Doncieux <stephane.doncieux@...> wrote:
                    >
                    > Hi Ken,
                    >
                    > I certainly did not want to say that genetic diversity is not important.
                    > I just wanted to say that behavioral diversity should not be neglected
                    > and that genotypic diversity, in my opinion, should not be preferred
                    > over behavioral diversity if one only is to be used. I have the feeling
                    > that genotypic diversity is not the main bottleneck, but I do also think
                    > that it is important (and the performance of NEAT prove it). The thing
                    > is that keeping a good diversity in the genotype space is not enough to
                    > guarantee a good diversity in the behavioral space, as many different
                    > neural networks may have the same behavior (think about neurons that are
                    > not connected to outputs or neural network parts connected to sensors
                    > that are not activated for a while) and likewise very close neural
                    > networks may result in very different behaviors.
                    >
                    > By the way, I completely agree with you, Ken, genotypic and behavioral
                    > diversity are very probably complimentary. Combining both will certainly
                    > lead to better results and it would be interesting to further
                    > investigate it.
                    >
                    > Best,
                    >
                    > stef
                    >
                    > >
                    > > Hi Stef,
                    > >
                    > > I changed the subject again just to make it easier to keep track as
                    > the conversation branches.
                    > >
                    > > Thanks for pointing out these insights and your work on behavioral vs.
                    > genetic diversity. It does appear that behavioral diversity and novelty
                    > are emerging through recent research such as your own as more critical
                    > factors in maintaining healthy diversity than genetic diversity, in
                    > particular when the diversity is in service of achieving a traditional
                    > objective (i.e. when one of the multiple objectives is some kind of
                    > task-specific performance measure).
                    > >
                    > > However, genetic diversity may still play a useful role in combination
                    > with behavioral diversity or novelty, which I want to illustrate here.
                    > Recall that the original motivation in NEAT for maintaining genetic
                    > diversity was to ensure that genetic innovations (i.e. additions of
                    > structure) are not eliminated prematurely. That is, the point is to
                    > ensure that individuals with new structure are not eliminated before
                    > they have a chance to show their potential by optimizing their weights
                    > over several more generations. Placing them in protected species gives
                    > them that opportunity to optimize further.
                    > >
                    > > However, recent results such as yours suggest that when you have a
                    > target objective, protecting behavioral diversity is so effective (most
                    > likely because it help avoid deception) that a system with only
                    > behavioral diversity will likely come closer to the objective than one
                    > with only genetic diversity.
                    > >
                    > > But that leaves open the possibility that genetic diversity can
                    > complement behavioral diversity or novelty. One interesting question is
                    > whether in the "Encouraging Behavioral Diversity in Evolutionary
                    > Robotics" paper the results would be even better if *both* behavioral
                    > diversity/novelty and genetic diversity were combined (as our group has
                    > done in recent papers). Going back to the motivation in NEAT for genetic
                    > diversity, the logic for why it would still matter when combined with
                    > behavioral diversity/novelty can be seen:
                    > >
                    > > Just as we do not know at first for any structural innovation whether
                    > that innovation might lead to higher fitness in an objective-based
                    > problem, we also do not know initially whether a particular structural
                    > innovation might lead later to more *novelty*. Often structural
                    > additions in neuroevolution lead to a complete collapse in behavior,
                    > which obviously hurts fitness, but also hurts novelty because degenerate
                    > behaviors are not considered novel (except at the very beginning of the
                    > run). Therefore, if you are not protecting genetic diversity when
                    > novelty/behavioral diversity are one of the objectives, then you are
                    > risking prematurely eliminating genotypes before their potential for
                    > novelty has been explored.
                    > >
                    > > However, perhaps more significant in magnitude than even that scenario
                    > is whether novelty alone (as in novelty search) can drive a search as
                    > effectively without genetic diversity than it can with it. When you are
                    > searching for a specific objective target, deception is the overriding
                    > pathology, which is why behavioral diversity is such a potent antidote.
                    > However, if you are searching only for novelty, then obviously deception
                    > is no longer the issue (since you are not looking for any one thing),
                    > which means that now other pathologies (such as prematurely losing
                    > structural innovations from the population) would become more important.
                    > Therefore, the impact of forgoing genetic diversity might be more
                    > evident in that context.
                    > >
                    > > Furthermore, even if this issue is most evident in pure novelty
                    > search, it may still appear to some extent in any search where
                    > behavioral diversity is important, since genetic diversity ultimately
                    > drives behavioral diversity.
                    > >
                    > > This issue probably merits further study. I only mean to raise the
                    > question, not to argue that the answer is conclusive. I'm guessing the
                    > real answer is probably nuanced. For example, it may be that genetic
                    > diversity is more important early in a run when small structural changes
                    > tend to have the most dramatic effects on behavior. Perhaps in later
                    > generations because the effect tends to be less the need for genotypic
                    > protection might reduce. But my guess is that ultimately genetic
                    > diversity and behavioral diversity both play a role in healthy
                    > evolution, and in fact complement each other (because genetic diversity
                    > helps foster behavioral diversity). I would also guess the effect would
                    > be more pronounced the more a search relies on novelty as its primary
                    > driver (with pure novelty search being the most extreme such case). Of
                    > course these are currently just speculations on my part.
                    > >
                    > > Best,
                    > >
                    > > ken
                    >
                  • Drew Kirkpatrick
                    Stephane, As promising as NCD is, I think the only realistic approach to speeding it up is to use faster and faster compression algorithms (or more hardware).
                    Message 9 of 14 , Jun 17, 2013
                    • 0 Attachment
                      Stephane,

                      As promising as NCD is, I think the only realistic approach to speeding it up is to use faster and faster compression algorithms (or more hardware). It seems to me the general trend in NCD is that the faster the compression algorithm, the smaller the set of data it's capable of successfully performing NCD comparisons on. I'd imagine that's particularly problematic in your approach of multiple measures of behavior. 

                      I used zlib for my NCD calculations, it was much faster than the LZMA algorithm that the CompLearn NCD implementation is moving towards (LZMA is slower, but with fewer limitations to zlib). I also had 48 cpu's on nights and weekends all to myself to throw at the project, which certainly helped. Still took a few weeks to run through all my conditions. 


                      -Drew


                      On Sat, Jun 15, 2013 at 2:38 PM, Stéphane Doncieux <stephane.doncieux@...> wrote:
                       

                      Hi,

                      we have also tried NCD with gzip and it was really too slow. If someone knows how to estimate it in a reasonable time, I am interested... By the way, a generic measure would be nice, but there is an alternative that we have tested in a paper that I will present at CEC next week. We have just used several different behavioral measures in a single run. Actually, it gives better results than using a single behavioral diversity measure. The intuition is that it is actually difficult to capture with a single measure all the different aspects of a behavior. Thus by considering several measures, we have the opportunity to take into account multiple aspects of the behavior. We have more chance to find differences between behaviors and we thus better keep behavioral diversity and foster exploration. In practice it is often easy to think about several different behavior distances and more difficult to choose one. See " S. Doncieux, J.-B. Mouret. Behavioral Diversity with Multiple Behavioral Distances. IEEE Congress on Evolutionary Computation, 2013 (CEC 2013). " available for download from http://pages.isir.upmc.fr/evorob_db

                      best,

                      stephane



                      > Josh,
                      >
                      > I tried a number of methods to speed up the speed of NCD in my second M.S.
                      > thesis. Some of the approaches I used do deviate from the more general
                      > approach, but I was just trying to see what worked.
                      >
                      > Don't have the paper handy, but it and all my source code are on the list
                      > from last year. If you search for novelty search and competitive
                      > coevolution you should find it.
                      >
                      > I really wanted to try out another task that was more deceptive, but
                      > weekend warrior-ing grad school didn't leave me time to add more to the
                      > project.
                      >
                      > Maybe something in that paper might give you some ideas.
                      >
                      > -Drew
                      > On Jun 14, 2013 11:09 AM, "Joshua Auerbach" <joshua.auerbach@...> wrote:
                      >
                      > > **

                      > >
                      > >
                      > > Drew,
                      > >
                      > > (changed the subject, since this is branching off into a separate topic)
                      > >
                      > > I actually have played some with NCD (using gzip) but found it to be
                      > > prohibitively slow for comparing expressive vectors with any decently large
                      > > population size. Though I agree that it is conceptually quite appealing:
                      > > especially its ability to compare vectors of different sizes.
                      > >
                      > > Stephane and Jean-Baptiste have shown that even simple distance measures
                      > > such as Hamming distance between binary sensory-motor vectors can work
                      > > well. But, if an individual is a robot with an evolving morphology and it
                      > > does not have a fixed set of sensors or motors it becomes less clear what
                      > > the vector characterizing its behavior should be. You could still use
                      > > vectors of sensory motor signals and have vectors of different sizes, in
                      > > which case you would need something like NCD. Or, you could use some other
                      > > behavioral characterization that would always have a fixed dimension in
                      > > which you would be losing a lot of information about the individual&#39;s

                      > > behavior.
                      > >
                      > > Do you have some way of approximating NCD that is more computationally
                      > > feasible?
                      > >
                      > > Best,
                      > > Josh
                      > >
                      > >
                      > > On 06/14/2013 10:35 AM, Drew Kirkpatrick wrote:
                      > >
                      > >
                      > >
                      > > Josh,
                      > >
                      > > As far as behavioral diversity goes, there's been some interesting papers
                      > > on using information distance. I used a normalized compression distance
                      > > (really general method) measure to drive novelty search, with ok-ish
                      > > results, although it wasn't a particularly deceptive task.
                      > >
                      > > I like the idea of a general method for measuring behavioral novelty, even
                      > > if they can be computationally expensive.
                      > >
                      > > -Drew
                      > > On Jun 14, 2013 10:25 AM, "Joshua Auerbach" <joshua.auerbach@...>
                      > > wrote:
                      > >
                      > >>
                      > >>
                      > >> Hi everyone,
                      > >>
                      > >> I just want to chime in and say that in some recent work (currently under
                      > >> review) I did basically the same thing as you have described in these two
                      > >> papers (even though I was not aware of them). I replaced NEAT's speciation
                      > >> mechanism with a genotypic diversity metric computed as the distance to the
                      > >> k-nearest neighbors calculated using NEAT's genomic distance measure. This
                      > >> seemed to work well enough. Though, as Stephane mentioned, based on his
                      > >> and Jean-Baptiste&#39;s work it is quite likely that using a behavioral

                      > >> diversity metric would be even more effective. However, in some domains it
                      > >> is not clear how behavioral distance should be characterized.
                      > >>
                      > >> Ken/Joel, I do have a question for you: In my NSGA-II / CPPN-NEAT hybrid
                      > >> I did not use any crossover and just relied on asexual reproduction. Did
                      > >> you incorporate sexual reproduction in your implementation? If so, how did
                      > >> you determine which individuals were allowed to mate if speciation was not
                      > >> employed?
                      > >>
                      > >> Best,
                      > >> Josh
                      > >>
                      > >>
                      > >>
                      > >>
                      > >> On 06/13/2013 10:37 PM, Oliver Coleman wrote:
                      > >>
                      > >>
                      > >> "Effective Diversity Maintenance in Deceptive Domains" (J. Lehman, K.
                      > >> Stanley, R. Miikkulainen. 2013)
                      > >> http://eplex.cs.ucf.edu/papers/lehman_gecco13.pdf
                      > >> Disables speciation and uses explicit genetic diversity
                      > >> objective (Handles it in the same way as the first one you linked).
                      > >>
                      > >>
                      > >> On 14 June 2013 08:07, Ken <kstanley@...> wrote:
                      > >>
                      > >>>
                      > >>>
                      > >>> Our group recently has tried simply replacing NEAT-style speciation with
                      > >>> a "genetic diversity objective." The benefit of that approach is that you
                      > >>> don't have to worry about the interaction between speciation and the pareto
                      > >>> front while you still get some protection for genetic diversity; the
                      > >>> downside of course is it's not certain that the dynamics will be exactly
                      > >>> like fitness sharing. But you can see an example of this approach in this
                      > >>> paper:
                      > >>>
                      > >>> http://eplex.cs.ucf.edu/papers/lehman_ab13.pdf
                      > >>>
                      > >>> The genetic diversity objective is defined there as: "In particular, the
                      > >>> genomic diversity of a given genome is quantifi ed as the average distance
                      > >>> to its k-nearest neighbors in genotype space as measured by NEAT's genomic
                      > >>> distance measure."
                      > >>>
                      > >>
                      > >> --
                      > >> Dr. Joshua E. Auerbach
                      > >> Morphology, Evolution and Cognition Lab
                      > >> Dept of Computer Science / Vermont Complex Systems Center
                      > >> University of Vermont
                      > >>
                      > >>
                      > >
                      > > --
                      > > Dr. Joshua E. Auerbach
                      > > Morphology, Evolution and Cognition Lab
                      > > Dept of Computer Science / Vermont Complex Systems Center
                      > > University of Vermont
                      > >
                      > >
                      > >


                    Your message has been successfully submitted and would be delivered to recipients shortly.