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

Delphi NEAT

Expand Messages
  • Kenneth Stanley
    Hey Mattias, I noticed you posted a new version of Delphi NEAT. I was curious what s in the update? ken
    Message 1 of 6 , Feb 3 1:20 AM
    • 0 Attachment
      Hey Mattias, I noticed you posted a new version of Delphi NEAT. I was
      curious what's in the update?

      ken
    • Mattias Fagerlund
      ... Nothing major, I don t even remember what it was ;) Oh, now I recall, I had to change the way I find a innovation because I used to keep innovation in an
      Message 2 of 6 , Feb 3 1:47 AM
      • 0 Attachment
        > Hey Mattias, I noticed you posted a new version of Delphi NEAT. I was
        > curious what's in the update?

        Nothing major, I don't even remember what it was ;)

        Oh, now I recall, I had to change the way I find a innovation because I
        used to keep innovation in an unsorted list which meant that finding
        matching innovations was a case of searching unsorted lists O(m * n).
        When I tried with LARGE genotypes, the process became very expensive, so
        I changed the innovation list to a sorted list so I could match them in O
        (m * ln(n)) instead.

        It doesn't improve the performance of neat, nor does it speed up the
        regular cases of neat (where m and n are small). But for large very
        genotypes, it's a good speed increase.

        cheers,
        m
      • Kenneth Stanley
        ... I was ... because I ... finding ... n). ... expensive, so ... in O ... the ... Do you keep the list of innovations around forever or do you delete it after
        Message 3 of 6 , Feb 3 11:41 AM
        • 0 Attachment
          --- In neat@yahoogroups.com, "Mattias Fagerlund" <mattias@c...> wrote:
          > > Hey Mattias, I noticed you posted a new version of Delphi NEAT.
          I was
          > > curious what's in the update?
          >
          > Nothing major, I don't even remember what it was ;)
          >
          > Oh, now I recall, I had to change the way I find a innovation
          because I
          > used to keep innovation in an unsorted list which meant that
          finding
          > matching innovations was a case of searching unsorted lists O(m *
          n).
          > When I tried with LARGE genotypes, the process became very
          expensive, so
          > I changed the innovation list to a sorted list so I could match them
          in O
          > (m * ln(n)) instead.
          >
          > It doesn't improve the performance of neat, nor does it speed up
          the
          > regular cases of neat (where m and n are small). But for large very
          > genotypes, it's a good speed increase.
          >

          Do you keep the list of innovations around forever or do you delete it
          after each generation?

          ken
        • Mattias Fagerlund
          ... I m sorry, I was referring to genes (they re identified by their innovation id). Genes (both nodes and connections) are sorted by their innovation id. When
          Message 4 of 6 , Feb 3 11:56 AM
          • 0 Attachment
            > Do you keep the list of innovations around forever or do you delete it
            > after each generation?

            I'm sorry, I was referring to genes (they're identified by their
            innovation id). Genes (both nodes and connections) are sorted by their
            innovation id. When determining species / unrelatedness, the process of
            comparing nodes and connections is time consuming for large genomes.
            This improvement came about when I was testing OCR - about 100 inputs
            and 26 outputs => 2600 genes to compare to determine species.

            I outlined a simple method that's O(m * ln(n)), where m is the number of
            genes in genome 1 and n is the number of genes in genome 2. Now, this is
            obviously (?) still wasteful, since both lists are sorted.

            I actually run down gene list 1 and gene list 2, making sure they're in
            synch, and then I compare away. Which is O(m+n) - vastly superior to the
            previous O(m * n) for large genomes. For smaller genomes, the work of
            keeping the gene list sorted cancels out the performance boost of having
            a sorted list during the comparison.

            With the original method, O(m * n) = O( 2600 * 2600) => very slow. New
            method = O(m + n) = O(2600 + 2600) => much better.

            Perhaps this is the way original NEAT always behaved, but DelphiNEAT
            didn't.

            cheers,
            m
          • Derek James
            Just wondering if anybody d done any sort of ablation testing with elitism. Last night we inadvertently disabled the elitism functionality in our
            Message 5 of 6 , Feb 3 12:18 PM
            • 0 Attachment
              Just wondering if anybody'd done any sort of ablation
              testing with elitism.

              Last night we inadvertently disabled the elitism
              functionality in our implementation and we were trying
              to figure out why it wasn't working (several runs in a
              row could not solve XOR and the overall population was
              bloating badly). Philip found the problem, enabled
              elitism, and it worked like a dream...solved for XOR
              in 20-30 generations, with very small topologies.

              So we sort of inadvertantly did an ablation test for
              elitism. :)

              So I'm wondering how crucial an aspect of NEAT in
              particular and GAs in general, elitism is. It
              certainly seems incredibly important, at least with
              XOR...so much so that removing it effectively broke
              the algorithm.

              I was also wondering if anyone had implemented elitism
              differently than the original NEAT study (the fittest
              members of species due to produce 5 or more offspring
              in the next generation are copied over unchanged), and
              what their experiences/thoughts might have been.

              Derek

              __________________________________
              Do you Yahoo!?
              Yahoo! SiteBuilder - Free web site building tool. Try it!
              http://webhosting.yahoo.com/ps/sb/
            • Kenneth Stanley
              The steeper the hill you re climbing, the more important elitism is. It s an intuitive concept in search: you don t want to forget the highest point you ve
              Message 6 of 6 , Feb 3 11:50 PM
              • 0 Attachment
                The steeper the hill you're climbing, the more important
                elitism is. It's an intuitive concept in search:
                you don't want to forget the highest point you've been to
                because then you'll have to find it all over again.
                On a steep hill in particular, it's less likely you'll
                be able to find the high point you were last at.
                It makes sense that allowing your algorithm to forget
                it's best-so-far solution would have a big impact on
                performance.

                I haven't tried alternate elitism schemes. Although the
                "babies stolen" parameter in my C++ NEAT is a kind of
                super-elitism, where champions of top species get to
                have disproportionately many babies, although they are
                not clones.

                ken


                --- In neat@yahoogroups.com, Derek James <blue5432@y...> wrote:
                > Just wondering if anybody'd done any sort of ablation
                > testing with elitism.
                >
                > Last night we inadvertently disabled the elitism
                > functionality in our implementation and we were trying
                > to figure out why it wasn't working (several runs in a
                > row could not solve XOR and the overall population was
                > bloating badly). Philip found the problem, enabled
                > elitism, and it worked like a dream...solved for XOR
                > in 20-30 generations, with very small topologies.
                >
                > So we sort of inadvertantly did an ablation test for
                > elitism. :)
                >
                > So I'm wondering how crucial an aspect of NEAT in
                > particular and GAs in general, elitism is. It
                > certainly seems incredibly important, at least with
                > XOR...so much so that removing it effectively broke
                > the algorithm.
                >
                > I was also wondering if anyone had implemented elitism
                > differently than the original NEAT study (the fittest
                > members of species due to produce 5 or more offspring
                > in the next generation are copied over unchanged), and
                > what their experiences/thoughts might have been.
                >
                > Derek
                >
                > __________________________________
                > Do you Yahoo!?
                > Yahoo! SiteBuilder - Free web site building tool. Try it!
                > http://webhosting.yahoo.com/ps/sb/
              Your message has been successfully submitted and would be delivered to recipients shortly.