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

Random seeds and other persistent data in GP individuals.

Expand Messages
  • Ian Badcoe
    Hi, I m working on some prototypes towards the Living@Home GP engine. It s a very simple test case, where each individual is a single gene, gets run for some
    Message 1 of 3 , Sep 2, 2003
    • 0 Attachment
      Hi,
      I'm working on some prototypes towards the Living@Home GP engine.

      It's a very simple test case, where each individual is a single gene, gets
      run for some number of ticks, and scored on it's ability to output numbers
      with certain properties. Pretty trivial really, and I'm planning to score
      them for producing prime numbers at first (it's a problem too difficult for
      them to find trivial solutions, but there are plenty of simple heuristics
      they can discover to improve their chances, such as making all their output
      odd, or a*b*c...*z + 1).

      I didn't put any variables in yet (still don't know what we need) but they
      do have a couple of other pieces of "state data":

      i) a count of how many numbers they already emitted
      ii) a random number stream

      The first is pretty-obviously local to one-only run of the individual, and
      not a problem.

      In implementing the latter, I've actually given them two streams, a
      "Master" stream (for off-line events, such as mutation) and an "Execution"
      stream (for use during the individuals lifetime). Now, I've run into a
      catch, which is this: the Execution Stream, must be re-seeded back to a
      constant value each time the individual is run, because it's an important
      principle that individuals always live the same life under the same
      conditions. That's straightforward enough, but as I come to handle the
      Master Stream, it's making less sense to me. e.g. my plan was that one of
      the individuals acting as a parent, would contribute the random numbers for
      the cross-over of the child. But that means that an individual in any
      "elite" would either be changed in the next generation (master random
      stream advanced), or else would run the risk of producing precisely the
      same child again in the future.

      If the Master stream does advance from generation to generation, then it
      has to be saved back to disk, for restarting purposes. But should that
      happen, when the individual is not strictly "changing"? Maybe that's OK,
      since we can make it a principle that the individual's fitness cannot
      change as a result of advancing the Master stream (that's why the Execute
      stream is separate, after all). But I wonder if, long-term, it makes
      issues for distributed working. If I scatter copies of an individual onto
      remote machines, do they become different individuals as they breed and
      their master-streams advance? By one definition they do, because they will
      no longer have identical effects if injected into a "standard" simulation:
      they'll produce different offspring.

      It seems to me that the behaviour of a population, _should_ be a property
      of only the population's overall state. But, there can be other random
      numbers required, e.g. for parent selection, which implies the existence of
      a further "External" random number stream. The External stream could be
      constructed as a hash of one random number taken from each individual (I
      was going to do this), but then it falls foul of the same paradox as the
      Master Streams themselves, e.g. if they don't change neither does it, and
      every generation is the same.

      Can anybody help me out here? Maybe there's no choice but to treat all
      "Master" random numbers as coming from the environment and not the
      individual? Does anybody know of general approaches that people have
      taken? For example, I've seen discussions where cross-over/mutation
      conditions are allowed to evolve between individuals, which is only a small
      step from granting them full control of their reproductive strategy. And
      that might require them for have, for e.g. knowledge of how many offspring
      they already produced, or even a perception of how successful their
      previous children have been (obviously we're getting more into the study of
      evolution, and less into optimisation strategies).

      Ian Badcoe
      Free transport into the future - while you wait.
    • Pierre Collet
      ... engine. ... single gene, gets ... numbers ... treat all ... have ... Dear Ian, Some years ago, Evelyne Lutton, Marc Schoenauer, Frederic Raynal and I have
      Message 2 of 3 , Sep 2, 2003
      • 0 Attachment
        --- In genetic_programming@yahoogroups.com, Ian Badcoe
        <ian_badcoe@y...> wrote:
        > Hi,
        > I'm working on some prototypes towards the Living@Home GP
        engine.
        >
        > It's a very simple test case, where each individual is a
        single gene, gets
        > run for some number of ticks, and scored on it's ability to output
        numbers
        > with certain properties.
        > ...
        > ...
        > Can anybody help me out here? Maybe there's no choice but to
        treat all
        > "Master" random numbers as coming from the environment and not the
        > individual? Does anybody know of general approaches that people
        have
        > taken?
        > ...

        Dear Ian,

        Some years ago, Evelyne Lutton, Marc Schoenauer, Frederic Raynal and
        I have published a paper on what we had called the "Parisian
        approach" in reference to the Michigan approach of Classifier Systems.

        The idea seems to be related to what you describe, i.e. each
        individual of the population only represents a part of the global
        solution.
        A first paper was presented at GECCO'99 (P. Collet, E. Lutton, F.
        Raynal, M. Schoenauer, ``Individual GP : An Alternative Viewpoint for
        the Resolution of Complex Problems,'' GECCO99, Orlando, Florida, Jul
        1999) and another one was published on Wolfgang Banzhaf's GPEM
        journal in 2000 (P. Collet, E. Lutton, F. Raynal, M. Schoenauer,
        ``Polar IFS + Parisian Genetic Programming = Efficient IFS Inverse
        Problem Solving,'' Genetic Programming and Evolvable Machines
        Journal, vol 1 Number 4, pp 339-361, Oct 2000)
        (http://lil.univ-littoral.fr/~collet/publications-en.html#GPEM00).

        Jean Louchet has also used this approach for his "fly" algorithm for
        3D obstacle detection. In this case, the solution is made of
        thousands of individuals (flies) that are sitting on solid objects of
        the scene. The paper was also published in GPEM :
        "J. Louchet, Using an Individual Evolution Strategy for Stereovision,
        Genetic Programming and Evolvable Machines, Vol. 2, No. 2, March
        2001, Kluwer Academic Publishers, 101-109."

        Hope this helps.

        Pierre Collet
      • Ian Badcoe
        Hi Pierre, Thanks for these. The first I ll study. The second I don t have access to, and it doesn t seem to be on-line anywhere. I m not sure these are
        Message 3 of 3 , Sep 3, 2003
        • 0 Attachment
          Hi Pierre,
          Thanks for these. The first I'll study. The second I don't have
          access to, and it doesn't seem to be on-line anywhere.

          I'm not sure these are quite in the same area I was trying to ask
          about, however. Could you explain some more about what issues came up for
          you, and how you tackled them. If it's too complex, maybe we should go to
          private email and I'll summarize back to the group later.

          In case it helps, I've thought of a better explanation of my question:

          --

          You have a population of individuals who have state data, which changes
          during their lifetime (run-time). Each individual can be considered in two
          contexts: (i) the "ideal" individual, as first created and still in its
          initial state, or, (ii) "living" individuals, such as might be pulled from
          the middle of a simulation run, and who therefore have different state data
          -- you could imagine that the latter might have been "knocked about a bit"
          by life in the big bad simulation.

          In a totally conventional GP approach, living individuals will have
          relevance only during simulation (done only for fitness calculation). And
          all breeding will be done with ideal individuals.

          However, we want to take the scope of the GP away from abstract problem
          solving and look at biological-style simulations. Now breeding events
          cannot be abstracted away from the simulation. Any breeding in this
          context has to take place at some point inside it. Two individuals must
          have met, negotiated an exchange of genomic information, and one of them
          (the "mother") must create the new genome, whist she is running.

          Which is where the contradiction creeps in, because cross-over requires a
          random number stream (RStream). Since the process is (conceptually)
          contained within the mother, it doesn't seem to make sense that it should
          rely on any data from anywhere else. So the RStream should come from the
          mother...

          On the other hand, if we have archived individuals, we presumably stored
          either their ideal states, or else their states at some arbitrary moment in
          time. And, if we retrieve two archived individuals and do the same
          breeding event, we'd expect the same result, which we won't get if the
          mother's RStream is in a different state. Yet we have to let that stream's
          state advance during her life, or any repeated breedings will produce clones.

          --

          It's not technically difficult, as one could simply create a single RStream
          for each breed event -- seeding it, for example, from the environment
          tick-count, or the mother's age in simulation cycles, or any other
          determinate factor. Reproducing a breed event would then carry the proviso
          that this seed factor must also be duplicated.

          However, I feel that in highlighting this living individual vs. ideal
          individual dichotomy, I've hit on a real weak area in the theory of what
          I'm doing. And I'd really rather understand it a bit better before I much
          commit too much to code and data

          Ian Badcoe

          At 17:36 9/2/2003 +0000, you wrote:
          >--- In genetic_programming@yahoogroups.com, Ian Badcoe
          ><ian_badcoe@y...> wrote:
          > > Hi,
          > > I'm working on some prototypes towards the Living@Home GP
          >engine.
          > >
          > > It's a very simple test case, where each individual is a
          >single gene, gets
          > > run for some number of ticks, and scored on it's ability to output
          >numbers
          > > with certain properties.
          > > ...
          > > ...
          > > Can anybody help me out here? Maybe there's no choice but to
          >treat all
          > > "Master" random numbers as coming from the environment and not the
          > > individual? Does anybody know of general approaches that people
          >have
          > > taken?
          > > ...
          >
          >Dear Ian,
          >
          >Some years ago, Evelyne Lutton, Marc Schoenauer, Frederic Raynal and
          >I have published a paper on what we had called the "Parisian
          >approach" in reference to the Michigan approach of Classifier Systems.
          >
          >The idea seems to be related to what you describe, i.e. each
          >individual of the population only represents a part of the global
          >solution.
          >A first paper was presented at GECCO'99 (P. Collet, E. Lutton, F.
          >Raynal, M. Schoenauer, ``Individual GP : An Alternative Viewpoint for
          >the Resolution of Complex Problems,'' GECCO99, Orlando, Florida, Jul
          >1999) and another one was published on Wolfgang Banzhaf's GPEM
          >journal in 2000 (P. Collet, E. Lutton, F. Raynal, M. Schoenauer,
          >``Polar IFS + Parisian Genetic Programming = Efficient IFS Inverse
          >Problem Solving,'' Genetic Programming and Evolvable Machines
          >Journal, vol 1 Number 4, pp 339-361, Oct 2000)
          >(http://lil.univ-littoral.fr/~collet/publications-en.html#GPEM00).
          >
          >Jean Louchet has also used this approach for his "fly" algorithm for
          >3D obstacle detection. In this case, the solution is made of
          >thousands of individuals (flies) that are sitting on solid objects of
          >the scene. The paper was also published in GPEM :
          >"J. Louchet, Using an Individual Evolution Strategy for Stereovision,
          >Genetic Programming and Evolvable Machines, Vol. 2, No. 2, March
          >2001, Kluwer Academic Publishers, 101-109."
          >
          >Hope this helps.
          >
          >Pierre Collet
          >
          >
          >
          >To unsubscribe from this group, send an email to:
          >genetic_programming-unsubscribe@yahoogroups.com
          >
          >
          >
          >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

          Free transport into the future - while you wait.
        Your message has been successfully submitted and would be delivered to recipients shortly.