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

Re: quasi-random numbers

Expand Messages
  • Bob McKay
    I think the bottom line in this is, what do we really need from the number generator for EAs (I won t use the term RNG here, because I think that presumes the
    Message 1 of 3 , May 1, 2010
    • 0 Attachment
      I think the bottom line in this is, what do we really need from the number generator for EAs (I won't use the term RNG here, because I think that presumes the answer). And is it the same as statisticians require from RNGs?

      I think the answer to the latter is clear from a variety of sources. Meysenburg, Foster et al. showed that statistical tests were not a good indicator of RNG perfromance; but even more strongly, the experiments of Teytaud, our own, and a number of other people have shown that randomised low-discrepancy sequences give substantially better performance - particularly in initialisation - than more random-appearing sequences. Halton, Foure etc. sequences (even when randomised) are nothing like uniform samples; they are far too regularly spaced - which is exactly why they work better. But they fail the simplest statistical tests for randomness.

      So it sounds like we have contradictory requirements - randomness, but even spread. But I think this might be resolvable. Why do we really require randomness? It seems to me that this is mainly so the EA can't cheat, optimising for regularities in the RNG rather than for the solution space. On the other hand, we want evenness to reduce the effects of sample bias in search.

      So our requirement for randomness is closer to that of the cryptographer than the statistician. I think it's probably something like, generator A is better than generator B if the K complexity of an algorithm that could better-than-random predict the results of algorithm A is higher than that for algorithm B ( a proper definition would need to be relativised somewhat like in PAC learning - i.e. predict within epsilon, and with a bound on the probability that it would be this correct after seeing some given amount of the sequence).

      But then we also have the desire for evenness. I strongly suspect that these are in conflict, and that the trade-off changes both through the evolutionary process (evenness is more important earlier in the run), and also with problem difficulty (i.e. better RNG quality is more important with tougher problems). This might be why a lot of the work comparing low-discrepancy sequences has concentrated on initialisation, while comparisons of RNGs has generally looked at performance throughout the run.

          Best Wishes
          Bob
    • David vun Kannon
      Resending to the list address. From: dvunkannon@hotmail.com To: urilabob@gmail.com Subject: RE: [GP] Re: quasi-random numbers Date: Sun, 2 May 2010 13:13:11
      Message 2 of 3 , May 3, 2010
      • 0 Attachment
        Resending to the list address.
         

        From: dvunkannon@...
        To: urilabob@...
        Subject: RE: [GP] Re: quasi-random numbers
        Date: Sun, 2 May 2010 13:13:11 -0400

        Bob,
         
        My question that started this discussion was in fact driven by concerns with initializing an EA. I assume that if the genome has 40 real numbers, I would use a QR sequence that was good in 40 dimensions.
         
        I'm not clear on using a QR sequence later as part of a mutation operator. A mutation operator that looks at each real and decides to mutate it - does that use the same 40-dimension sequence as the initialization, or a one dimensional sequence? Do I need to work backward from the expected number of function evaluatons to the expected number of calls to the mutation operator, and then generate a seqence with that number of items? I'm not sure that I can just substitute a call to a QR function for a call to a PRNG.
         
        Cheers,
        David vun Kannon
         

        To: genetic_programming@yahoogroups.com
        From: urilabob@...
        Date: Sat, 1 May 2010 19:30:56 +0900
        Subject: [GP] Re: quasi-random numbers



        I think the bottom line in this is, what do we really need from the number generator for EAs (I won't use the term RNG here, because I think that presumes the answer). And is it the same as statisticians require from RNGs?

        I think the answer to the latter is clear from a variety of sources. Meysenburg, Foster et al. showed that statistical tests were not a good indicator of RNG perfromance; but even more strongly, the experiments of Teytaud, our own, and a number of other people have shown that randomised low-discrepancy sequences give substantially better performance - particularly in initialisation - than more random-appearing sequences. Halton, Foure etc. sequences (even when randomised) are nothing like uniform samples; they are far too regularly spaced - which is exactly why they work better. But they fail the simplest statistical tests for randomness.

        So it sounds like we have contradictory requirements - randomness, but even spread. But I think this might be resolvable. Why do we really require randomness? It seems to me that this is mainly so the EA can't cheat, optimising for regularities in the RNG rather than for the solution space. On the other hand, we want evenness to reduce the effects of sample bias in search.

        So our requirement for randomness is closer to that of the cryptographer than the statistician. I think it's probably something like, generator A is better than generator B if the K complexity of an algorithm that could better-than-random predict the results of algorithm A is higher than that for algorithm B ( a proper definition would need to be relativised somewhat like in PAC learning - i.e. predict within epsilon, and with a bound on the probability that it would be this correct after seeing some given amount of the sequence).

        But then we also have the desire for evenness. I strongly suspect that these are in conflict, and that the trade-off changes both through the evolutionary process (evenness is more important earlier in the run), and also with problem difficulty (i.e. better RNG quality is more important with tougher problems). This might be why a lot of the work comparing low-discrepancy sequences has concentrated on initialisation, while comparisons of RNGs has generally looked at performance throughout the run.

            Best Wishes
            Bob


      • Bob McKay
        Hi David, sorry, I was previously commenting more on the general discussion than on your original question. I agree that you need to tailor the sequence
        Message 3 of 3 , May 4, 2010
        • 0 Attachment
          Hi David, sorry, I was previously commenting more on the general discussion than on your original question. I agree that you need to tailor the sequence dimensionality to the problem.

          I haven't worked on using LD sequences after initialisation, but I would imagine it might be again appropriate to consider our overall goal. At least in comma algorithms, where we assume all information is held in the current population, I think we would probably want to restart sampling each generation. But maybe it's a bit more complex than that. For example, if we were wanting a Gaussian bias for mutation in a GA, we should presumably use something ike a Gaussian transformation of an LD sequence, similarly for crossover. However I'm less clear on how this might appropriately work in GP. Not too sure that it is easy to define what it is we want GP to do "even sampling" over.

                 Best Wishes
                 Bob


          Bob,

          My question that started this discussion was in fact driven by concerns with initializing an EA. I assume that if the genome has 40 real numbers, I would use a QR sequence that was good in 40 dimensions.

          I'm not clear on using a QR sequence later as part of a mutation operator. A mutation operator that looks at each real and decides to mutate it - does that use the same 40-dimension sequence as the initialization, or a one dimensional sequence? Do I need to work backward from the expected number of function evaluatons to the expected number of calls to the mutation operator, and then generate a seqence with that number of items? I'm not sure that I can just substitute a call to a QR function for a call to a PRNG.

          Cheers,
          David vun Kannon

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