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

Large variability in time to evaluate individuals in sub-populations at different nodes

Expand Messages
  • John Koza
    Hello All: One of the assumptions in the recent discussion on the GP list concerning managing parallel GP runs is that the time it takes to run a generation
    Message 1 of 3 , Oct 2, 2001
      Hello All:

      One of the assumptions in the recent discussion on the GP list concerning
      managing parallel GP runs is that the time it takes to run a generation
      (residing, say, on a node of a parallel computing system) is directly
      proportional to the population size.

      Over a broad range of problems, we have found exactly the opposite.

      For example, we've frequently observed that a tiny handful of individuals in
      one sub-population often take a highly disproportionate amount of computing
      resources. Thus, a parallel processing node (i.e., subpopulation) can fall
      behind the other nodes because of a small number of individuals in that
      particular population. We generally don't get too alarmed if some nodes fall
      behind (in generation number) from other nodes. It isn't clear that this
      discrepancy is even a negative. At various times, we have instituted
      practical triage tests for culling individuals that are overly
      time-consuming.

      It should be remembered that the time it takes to process a generation
      depends on the particular problem's type of fitness measure. There is a
      wide variety of different types of fitness measures out there. Some people
      are running time-consuming simulators of robotic systems, mechanical
      sequences of motions, electrical circuits, control systems, etc. Others are
      matching things to large databases (e.g., molecular biology problems). A
      few lucky people have complex problems with fitness measures that take
      almost no time to evaluate (e.g., many operations research problems fit that
      description).

      On certain problems (e.g., robotic problems with time-out limits, such as
      many of the problems in Jaws-1), the individuals take less and less time to
      evaluate as the individuals become fitter). Generation 0 is often the
      slowest generation.

      In many of the electrical circuit problems that we've done recently, the
      opposite is true. The time to process a generation tends to grow as the
      number of generations increases. For example, very small circuits may have
      just one element of the circuit's desired overall behavior.These smaller
      circuits (on average) simulate quickly. They get the best fitness in the
      early generations (and accordingly propogate) because their partially
      compliant behavior is better than the alternative (i.e., no compliance).
      Then, as the desired overall more complex behavior emerges later in the run,
      everything slows down as the (necessarily) larger circuits predominate.

      By the way, the above phenomena is often misconstrued as bloating. In fact,
      it often just reflects the reality that you walk before you run. Simpler
      and smaller circuits get rewarded early on because of their partially
      compliant behavior. Larger and more complex circuits emerge in later
      generations and they deliver a greater degree of compliance with the
      problem's overall requirements. Depending on the situation, there is no
      particular virtue to program size. In fact, large size may be necessary to
      solve a problem.

      John R. Koza

      Consulting Professor
      Biomedical Informatics
      Department of Medicine
      Medical School Office Building (MC 5479)
      Stanford University
      Stanford, California 94305-5479

      Consulting Professor
      Department of Electrical Engineering
      School of Engineering
      Stanford University

      Phone: 650-941-0336
      Fax: 650-941-9430
      E-Mail: koza@...
      WWW Home Page: http://www.smi.stanford.edu/people/koza

      For information about field of genetic programming in general:
      http://www.genetic-programming.org

      For information about Genetic Programming Inc.:
      http://www.genetic-programming.com

      For information about GECCO-2002 (GP-2002) conference in New York City on
      July 9 - 13, 2002 (Tuesday - Saturday) and the International Society on
      Genetic and Evolutionary Computation visit: http://www.isgec.org/

      For information about the annual Euro-GP-2002 conference on April 3 - 5,
      2002 in Ireland, visit http://evonet.dcs.napier.ac.uk/eurogp2002
    • mjs@tmolp.com
      Building on John s previous message, another thing we have considered in regard to circuits problems is scaling back the population size in later generations
      Message 2 of 3 , Oct 2, 2001
        Building on John's previous message, another thing we have considered
        in regard to circuits problems is scaling back the population size in
        later generations based on some preset time limit on the evaluation of
        each generation at each node. For example, if a node took 3 hours to
        complete a generation and we had set a time limit of 2 hours, the
        population at that node for the next generation would be reduced to
        2/3 its current value. The reduction would be done using tournament
        selection or whatever scheme was being used to select the parents for
        crossover.

        Matt Streeter

        --- In genetic_programming@y..., "John Koza" <koza@s...> wrote:
        > Hello All:
        >
        > One of the assumptions in the recent discussion on the GP list
        concerning
        > managing parallel GP runs is that the time it takes to run a
        generation
        > (residing, say, on a node of a parallel computing system) is
        directly
        > proportional to the population size.
        >
        > Over a broad range of problems, we have found exactly the opposite.
        >
        > For example, we've frequently observed that a tiny handful of
        individuals in
        > one sub-population often take a highly disproportionate amount of
        computing
        > resources. Thus, a parallel processing node (i.e., subpopulation)
        can fall
        > behind the other nodes because of a small number of individuals in
        that
        > particular population. We generally don't get too alarmed if some
        nodes fall
        > behind (in generation number) from other nodes. It isn't clear
        that this
        > discrepancy is even a negative. At various times, we have
        instituted
        > practical triage tests for culling individuals that are overly
        > time-consuming.
        >
        > It should be remembered that the time it takes to process a
        generation
        > depends on the particular problem's type of fitness measure. There
        is a
        > wide variety of different types of fitness measures out there. Some
        people
        > are running time-consuming simulators of robotic systems, mechanical
        > sequences of motions, electrical circuits, control systems, etc.
        Others are
        > matching things to large databases (e.g., molecular biology
        problems). A
        > few lucky people have complex problems with fitness measures that
        take
        > almost no time to evaluate (e.g., many operations research problems
        fit that
        > description).
        >
        > On certain problems (e.g., robotic problems with time-out limits,
        such as
        > many of the problems in Jaws-1), the individuals take less and less
        time to
        > evaluate as the individuals become fitter). Generation 0 is often
        the
        > slowest generation.
        >
        > In many of the electrical circuit problems that we've done recently,
        the
        > opposite is true. The time to process a generation tends to grow as
        the
        > number of generations increases. For example, very small circuits
        may have
        > just one element of the circuit's desired overall behavior.These
        smaller
        > circuits (on average) simulate quickly. They get the best fitness
        in the
        > early generations (and accordingly propogate) because their
        partially
        > compliant behavior is better than the alternative (i.e., no
        compliance).
        > Then, as the desired overall more complex behavior emerges later in
        the run,
        > everything slows down as the (necessarily) larger circuits
        predominate.
        >
        > By the way, the above phenomena is often misconstrued as bloating.
        In fact,
        > it often just reflects the reality that you walk before you run.
        Simpler
        > and smaller circuits get rewarded early on because of their
        partially
        > compliant behavior. Larger and more complex circuits emerge in
        later
        > generations and they deliver a greater degree of compliance with the
        > problem's overall requirements. Depending on the situation, there
        is no
        > particular virtue to program size. In fact, large size may be
        necessary to
        > solve a problem.
        >
        > John R. Koza
        >
        > Consulting Professor
        > Biomedical Informatics
        > Department of Medicine
        > Medical School Office Building (MC 5479)
        > Stanford University
        > Stanford, California 94305-5479
        >
        > Consulting Professor
        > Department of Electrical Engineering
        > School of Engineering
        > Stanford University
        >
        > Phone: 650-941-0336
        > Fax: 650-941-9430
        > E-Mail: koza@s...
        > WWW Home Page: http://www.smi.stanford.edu/people/koza
        >
        > For information about field of genetic programming in general:
        > http://www.genetic-programming.org
        >
        > For information about Genetic Programming Inc.:
        > http://www.genetic-programming.com
        >
        > For information about GECCO-2002 (GP-2002) conference in New York
        City on
        > July 9 - 13, 2002 (Tuesday - Saturday) and the International Society
        on
        > Genetic and Evolutionary Computation visit: http://www.isgec.org/
        >
        > For information about the annual Euro-GP-2002 conference on April 3
        - 5,
        > 2002 in Ireland, visit http://evonet.dcs.napier.ac.uk/eurogp2002
      • Mattias Fagerlund
        [John R. Koza wrote] ... An interesting read, thanks! I was wondering, you having such a huge cluster and all, how do you deal with run boundries? thanks, m
        Message 3 of 3 , Oct 2, 2001
          [John R. Koza wrote]
          > Hello All:
          >
          > One of the assumptions in the recent discussion on the GP list
          > concerning
          > managing parallel GP runs is that the time it takes to run a generation
          > (residing, say, on a node of a parallel computing system) is directly
          > proportional to the population size.

          An interesting read, thanks! I was wondering, you having such a huge
          cluster and all, how do you deal with run boundries?

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