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

Meta-NEAT algorithm progress

Expand Messages
  • Colin Green
    Just a quick update on the meta-neat / parameter search work I ve been doing. I ve had a working version for about a week now and have just started
    Message 1 of 11 , Nov 1, 2004
    • 0 Attachment
      Just a quick update on the meta-neat / parameter search work I've been
      doing.

      I've had a working version for about a week now and have just started
      experimenting with the XOR domain. One concern I've had with SharpNEAT
      so far is that it takes far more generations to solve XOR (on average)
      when compared to the figures reported by others. Therefore I wanted to
      see if this could be attributed to a poor choice of parameters on my
      part or whether it might be something more fundamental.

      So far I have found a set of parameters that find a solution about twice
      as fast as before. So the # of gens required has gone from about 280 to
      about 150. This is still high compared to other's reports, but it does
      demonstrate that the meta-algorithm is working to some degree.

      I have also wrapped up the meta-algorithm work in a rudimentary GUI that
      can be used to track progress, select which parameters you wish to
      search and define a seed NeatParameters object that acts as the starting
      point for the search.

      To keep it simple I have so far only searched on one parameter at a
      time, the theory being that with such a simple search space I can keep
      the population size low - thus keeping duration of searches down. Some
      parameters can also effect evaluation duration a lot, so I have avoided
      these so far.

      So basically it's so far so good. I don't expect the parameters that are
      found for XOR to be applicable to most other problems, since XOR is an
      artificially small and simple problem to solve, but it will still be
      interesting to see how much certain parameters effect a search. So far I
      have found that the rate of asexual reproduction works best at about 90%
      (50/50 before), and that the weight range is best at +-7.5 (+-5 before)
      this latter figure also effects the range of values used when creating
      new connections and also the initial population, therefore by increasing
      the range while keepig the same activation function, the function has
      effectively been steepened towards being a step function.

      Colin.
    • Colin Green
      ... Quick update. I have just got the average number of gens to find a solution for XOR down to about 40, which is a nice result and also means I won t have to
      Message 2 of 11 , Nov 1, 2004
      • 0 Attachment
        Colin Green wrote:

        >So far I have found a set of parameters that find a solution about twice
        >as fast as before. So the # of gens required has gone from about 280 to
        >about 150. This is still high compared to other's reports, but it does
        >demonstrate that the meta-algorithm is working to some degree.
        >
        >
        Quick update. I have just got the average number of gens to find a
        solution for XOR down to about 40, which is a nice result and also means
        I won't have to spend the next fortnight searching for bugs :) On that
        note I think I'll call it a day.

        Colin.
      • Ian Badcoe
        ... Oh? I thought this was just the beginning. At least take your found parameters from XOR and try them on some other problem domains. Ian ... Living@Home -
        Message 3 of 11 , Nov 2, 2004
        • 0 Attachment
          At 22:17 01/11/2004, you wrote:

          >Colin Green wrote:
          >
          > >So far I have found a set of parameters that find a solution about twice
          > >as fast as before. So the # of gens required has gone from about 280 to
          > >about 150. This is still high compared to other's reports, but it does
          > >demonstrate that the meta-algorithm is working to some degree.
          > >
          > >
          >Quick update. I have just got the average number of gens to find a
          >solution for XOR down to about 40, which is a nice result and also means
          >I won't have to spend the next fortnight searching for bugs :) On that
          >note I think I'll call it a day.

          Oh? I thought this was just the beginning.

          At least take your found parameters from XOR and try them on some other
          problem domains.

          Ian

          >Colin.
          >
          >
          >
          >
          >
          >
          >Yahoo! Groups Links
          >
          >
          >
          >



          Living@Home - Open Source Evolving Organisms -
          http://livingathome.sourceforge.net/
        • Mitchell Timin
          Choosing a good set of parameter is a problem for me also. I would be interested in the details of your method. Have you posted any information about that? I
          Message 4 of 11 , Nov 2, 2004
          • 0 Attachment
            Choosing a good set of parameter is a problem for me
            also. I would be interested in the details of your
            method. Have you posted any information about that?
            I don't remember seeing it.

            m

            --- Colin Green <cgreen@...> wrote:

            > Just a quick update on the meta-neat / parameter
            > search work I've been
            > doing.
            >
            > I've had a working version for about a week now and
            > have just started
            > experimenting with the XOR domain. One concern I've
            > had with SharpNEAT
            > so far is that it takes far more generations to
            > solve XOR (on average)
            > when compared to the figures reported by others.
            > Therefore I wanted to
            > see if this could be attributed to a poor choice of
            > parameters on my
            > part or whether it might be something more
            > fundamental.
            >
            > So far I have found a set of parameters that find a
            > solution about twice
            > as fast as before. So the # of gens required has
            > gone from about 280 to
            > about 150. This is still high compared to other's
            > reports, but it does
            > demonstrate that the meta-algorithm is working to
            > some degree.
            >
            > I have also wrapped up the meta-algorithm work in a
            > rudimentary GUI that
            > can be used to track progress, select which
            > parameters you wish to
            > search and define a seed NeatParameters object that
            > acts as the starting
            > point for the search.
            >
            > To keep it simple I have so far only searched on one
            > parameter at a
            > time, the theory being that with such a simple
            > search space I can keep
            > the population size low - thus keeping duration of
            > searches down. Some
            > parameters can also effect evaluation duration a
            > lot, so I have avoided
            > these so far.
            >
            > So basically it's so far so good. I don't expect the
            > parameters that are
            > found for XOR to be applicable to most other
            > problems, since XOR is an
            > artificially small and simple problem to solve, but
            > it will still be
            > interesting to see how much certain parameters
            > effect a search. So far I
            > have found that the rate of asexual reproduction
            > works best at about 90%
            > (50/50 before), and that the weight range is best at
            > +-7.5 (+-5 before)
            > this latter figure also effects the range of values
            > used when creating
            > new connections and also the initial population,
            > therefore by increasing
            > the range while keepig the same activation function,
            > the function has
            > effectively been steepened towards being a step
            > function.
            >
            > Colin.
            >
            >
            >


            =====
            Mitchell Timin
            http://annevolve.sourceforge.net

            __________________________________________________
            Do You Yahoo!?
            Tired of spam? Yahoo! Mail has the best spam protection around
            http://mail.yahoo.com
          • Colin Green
            ... Sorry, I literally meant finish off for the day :) The same code can also be re-used to run one off benchmarks, e.g. how well does this set of parameters
            Message 5 of 11 , Nov 2, 2004
            • 0 Attachment
              Ian Badcoe wrote:

              >At 22:17 01/11/2004, you wrote:
              >
              >
              >>Quick update. I have just got the average number of gens to find a
              >>solution for XOR down to about 40, which is a nice result and also means
              >>I won't have to spend the next fortnight searching for bugs :) On that
              >>note I think I'll call it a day.
              >>
              >>
              >
              >Oh? I thought this was just the beginning.
              >
              >At least take your found parameters from XOR and try them on some other
              >problem domains.
              >
              >

              Sorry, I literally meant finish off for the day :) The same code can
              also be re-used to run one off benchmarks, e.g. how well does this set
              of parameters work on average on this domain, which is something that is
              always going to be useful. And yeh, I'll be looking at applying the
              meta-algorithm to other domains, the trouble is it's a lengthy process
              and thus I suspect it will be a long term investigation that runs
              alongside other investigations.

              Colin.
            • Colin Green
              ... Hi Mitchell, I started out wanting to search for optimal connection weight mutate schemes, and I did post an explanation of how I was going to do that a
              Message 6 of 11 , Nov 2, 2004
              • 0 Attachment
                Mitchell Timin wrote:

                >Choosing a good set of parameter is a problem for me
                >also. I would be interested in the details of your
                >method. Have you posted any information about that?
                >I don't remember seeing it.
                >
                >
                Hi Mitchell,

                I started out wanting to search for optimal connection weight mutate
                schemes, and I did post an explanation of how I was going to do that a
                not long ago. In the end though I decided to expand the idea to search
                for all parameters, e.g. initial population size, initial connection
                proportion, selection proportion, mutation rates, etc.

                The idea is a simple one, create a population of parameters and for each
                one run the NEAT algorithm and average out the performance of each run.
                This gives a fitness that I then use to select the children of the next
                generation of parameters. I also wrapped up the parameters in a seperate
                class that incorporates mutation functions - crossover I haven't yet
                implemented.

                The result is an evolution algorithm that sits on top of NEATs evolution
                algorithm and takes a heck of a long time to run, since each individual
                evaluation is a NEAT run.

                If you're interested in more details then let me know and I'll try and
                put something together on the SharpNEAT web site.

                Colin.
              • Mitchell Timin
                ... ... Yes, Colin I would appreciate that. I don t want to see code, just an explanation of how it works, with enough detail that I might code
                Message 7 of 11 , Nov 3, 2004
                • 0 Attachment
                  --- Colin Green <cgreen@...> wrote:
                  > Mitchell Timin wrote:
                  >
                  > >Choosing a good set of parameter is a problem for
                  > me
                  > >also. I would be interested in the details of your
                  > >method. Have you posted any information about
                  > that?
                  <snip>
                  > If you're interested in more details then let me
                  > know and I'll try and
                  > put something together on the SharpNEAT web site.

                  Yes, Colin I would appreciate that. I don't want to
                  see code, just an explanation of how it works, with
                  enough detail that I might code something similar for
                  myself.

                  m

                  =====
                  Mitchell Timin
                  http://annevolve.sourceforge.net



                  __________________________________
                  Do you Yahoo!?
                  Check out the new Yahoo! Front Page.
                  www.yahoo.com
                • Brian Dexter Allen
                  Hi Colin-- I m curious if you ve looked at the shape of the curves you get from those runs. Do you see nice smooth curves where a small change in a parameter
                  Message 8 of 11 , Nov 3, 2004
                  • 0 Attachment
                    Hi Colin--

                    I'm curious if you've looked at the shape of the curves you get from
                    those runs. Do you see nice smooth curves where a small change in a
                    parameter means a small change in the # of needed generations, or do you
                    get some big jumps? Also, do any of the curves have multiple extrema?
                    I did a series a while back with varying the mutation rate and noticed
                    two local maxima, although with a single run needing a day or so, I lost
                    patience with it quickly once a clearly-best rate emerged.

                    Sounds like interesting stuff.

                    Brian

                    Colin Green wrote:
                    > Mitchell Timin wrote:
                    >
                    > >Choosing a good set of parameter is a problem for me
                    > >also. I would be interested in the details of your
                    > >method. Have you posted any information about that?
                    > >I don't remember seeing it.
                    > >
                    > >
                    > Hi Mitchell,
                    >
                    > I started out wanting to search for optimal connection weight mutate
                    > schemes, and I did post an explanation of how I was going to do that a
                    > not long ago. In the end though I decided to expand the idea to search
                    > for all parameters, e.g. initial population size, initial connection
                    > proportion, selection proportion, mutation rates, etc.
                    >
                    > The idea is a simple one, create a population of parameters and for each
                    > one run the NEAT algorithm and average out the performance of each run.
                    > This gives a fitness that I then use to select the children of the next
                    > generation of parameters. I also wrapped up the parameters in a seperate
                    > class that incorporates mutation functions - crossover I haven't yet
                    > implemented.
                    >
                    > The result is an evolution algorithm that sits on top of NEATs evolution
                    > algorithm and takes a heck of a long time to run, since each individual
                    > evaluation is a NEAT run.
                    >
                    > If you're interested in more details then let me know and I'll try and
                    > put something together on the SharpNEAT web site.
                    >
                    > Colin.
                    >


                    --
                    Brian Dexter Allen
                    http://www.luminousbeings.com/
                  • Colin Green
                    ... Hi Brian, I don t have any graphs but yes I did notice some smooth curves while adjusting some of the parameters manually and noting numbers on scraps of
                    Message 9 of 11 , Nov 4, 2004
                    • 0 Attachment
                      Brian Dexter Allen wrote:

                      >Hi Colin--
                      >
                      >I'm curious if you've looked at the shape of the curves you get from
                      >those runs. Do you see nice smooth curves where a small change in a
                      >parameter means a small change in the # of needed generations, or do you
                      >get some big jumps? Also, do any of the curves have multiple extrema?
                      >I did a series a while back with varying the mutation rate and noticed
                      >two local maxima, although with a single run needing a day or so, I lost
                      >patience with it quickly once a clearly-best rate emerged.
                      >
                      >Sounds like interesting stuff.
                      >
                      >
                      >
                      Hi Brian,

                      I don't have any graphs but yes I did notice some smooth curves while
                      adjusting some of the parameters manually and noting numbers on scraps
                      of paper. For instance the meta-algorithm found that good mutation rates
                      for XOR were:

                      Mutate weights : 0.5 (Normally I use a figure above 0.9)
                      Add Node :0.0005
                      Add Connection: 0.5

                      From this starting point I noticed a steep improvement by increasing
                      the relative rate of 'add node', the gain started to asymptotically
                      level off at between 0.03 and 0.04. Adjusting the balance between weight
                      mutation and 'add connection' caused a gentle drop off in both directions.

                      There was probably a linear improvement in increasing the asexual
                      mutation rate - ultimately this went to 1.0 and the sexual reproduction
                      rate went to 0.0, which perhaps isn't surprising for a problem that
                      requires such a small network.

                      A slightly more subtle benefit was had by tweaking the weight mutation
                      scheme. The Meta-algorithm assigned a high rate to weight resetting, so
                      I tried discarding weight pertubation altogether and this worked well.
                      Also the proportion of weights that are reset per mutation seems to have
                      a plateau between 0.1 and 0.2, higher or lower than this and the
                      improvement starts to drop off slowly.

                      So perhaps nothing really unexpected here, but it's nice to see
                      hard(ish) facts and figures.

                      Oh and no I didn't see any multiple optimal points, but then I didn't
                      perform a detailed analysis so there could well be some hiding in there
                      somewhere.

                      Colin.
                    • Colin Green
                      Forgot to say that those parameters I mentioned brought the average for XOR down to 21 generations in the end, which is actually a lower number than that
                      Message 10 of 11 , Nov 4, 2004
                      • 0 Attachment
                        Forgot to say that those parameters I mentioned brought the average for
                        XOR down to 21 generations in the end, which is actually a lower number
                        than that reported by Ken in his dissertation - I think the number was 32.

                        Colin
                      • Mattias Fagerlund
                        ... For my DelphiNEAT implementation, it takes about 16,45 generations to find a perfect solution (just ran it, averaged over 100 iterations, popsize=150). But
                        Message 11 of 11 , Nov 7, 2004
                        • 0 Attachment
                          > Quick update. I have just got the average number of gens to find a
                          > solution for XOR down to about 40, which is a nice result and also
                          > means
                          > I won't have to spend the next fortnight searching for bugs :) On that
                          > note I think I'll call it a day.

                          For my DelphiNEAT implementation, it takes about 16,45 generations to find
                          a perfect solution (just ran it, averaged over 100 iterations, popsize=150).

                          But your discussion brought back memories of things that went wrong with
                          my initial XOR - my fitness function wasn't identical to Kens; make sure
                          that your fitness function is 100% identical to his!

                          Speficically, each the error for each test is specified as the difference
                          between the correct value (0 or 1) and the the NEAT value [0..1]. But NOT
                          if the NEAT value evaluates to the same binary value as the correct value,
                          then the error is 0!

                          If correct=1 and NEAT = 0.2, Error=0.3
                          If correct=1 and NEAT = 0.49, Error=0.51
                          If correct=1 and NEAT = 0.51, Error=0 (!!)
                          If correct=1 and NEAT = 0.75, Error=0 (!!)
                          If correct=1 and NEAT = 1.0, Error=0 (!!)

                          I had this error and it really hurt my evaluations, and that's because
                          NEAT keeps spending time trying to improve (reduce error of) bit tests
                          that are allready evaluating to the correct binary value.

                          Also make sure that you're not simply summing "hits"/"misses", but instead
                          actual error sums. Because evolution needs a gradient to follow, and
                          discrret fitness levels are hard to find a way across.

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