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

Limiting execution time of fitness function

Expand Messages
  • deluxenewandimproved
    Are there any genetic programming packages (or papers) that deal with limiting the execution time of a fitness function? I m trying to find a way to deal with
    Message 1 of 9 , Feb 27, 2005
    • 0 Attachment
      Are there any genetic programming packages (or papers) that deal with
      limiting the execution time of a fitness function? I'm trying to
      find a way to deal with infinite loops.

      Any help will be greatly appreciated.
      -Deluxe
    • Brock
      In my systems I just use the *nix signal mechanism to trigger an Alarm signal (which then raises an exception in the evaluation loop. My genotypes then provide
      Message 2 of 9 , Mar 1 6:23 AM
      • 0 Attachment
        In my systems I just use the *nix signal mechanism to trigger an Alarm
        signal (which then raises an exception in the evaluation loop.

        My genotypes then provide 'eval' and 'timed_eval'.

        --Brock

        On 2005.02.28.00.57, deluxenewandimproved wrote:
        |
        | Are there any genetic programming packages (or papers) that deal with
        | limiting the execution time of a fitness function? I'm trying to
        | find a way to deal with infinite loops.
        |
        | Any help will be greatly appreciated.
        | -Deluxe
      • Peter Day
        I ve also used this system and it works well. ... -- No virus found in this outgoing message. Checked by AVG Anti-Virus. Version: 7.0.300 / Virus Database:
        Message 3 of 9 , Mar 1 10:02 AM
        • 0 Attachment
          I've also used this system and it works well.


          Brock wrote:

          >
          > In my systems I just use the *nix signal mechanism to trigger an Alarm
          > signal (which then raises an exception in the evaluation loop.
          >
          > My genotypes then provide 'eval' and 'timed_eval'.
          >
          > --Brock
          >
          > On 2005.02.28.00.57, deluxenewandimproved wrote:
          > |
          > | Are there any genetic programming packages (or papers) that deal with
          > | limiting the execution time of a fitness function? I'm trying to
          > | find a way to deal with infinite loops.
          > |
          > | Any help will be greatly appreciated.
          > | -Deluxe
          >
          > *Yahoo! Groups Sponsor*
          > ADVERTISEMENT
          > click here
          > <http://us.ard.yahoo.com/SIG=1297m24f7/M=298184.6018725.7038619.3001176/D=groups/S=1705948923:HM/EXP=1109773432/A=2593423/R=0/SIG=11el9gslf/*http://www.netflix.com/Default?mqso=60190075>
          >
          >
          >
          > ------------------------------------------------------------------------
          > *Yahoo! Groups Links*
          >
          > * To visit your group on the web, go to:
          > http://groups.yahoo.com/group/genetic_programming/
          >
          > * To unsubscribe from this group, send an email to:
          > genetic_programming-unsubscribe@yahoogroups.com
          > <mailto:genetic_programming-unsubscribe@yahoogroups.com?subject=Unsubscribe>
          >
          > * Your use of Yahoo! Groups is subject to the Yahoo! Terms of
          > Service <http://docs.yahoo.com/info/terms/>.
          >
          >


          --
          No virus found in this outgoing message.
          Checked by AVG Anti-Virus.
          Version: 7.0.300 / Virus Database: 266.5.3 - Release Date: 01/03/2005
        • Bob MacCallum
          FWIW, that s also how it s done in PerlGP (set an alarm which breaks a Perl eval ) Although unfortunately in Perl, for reasons beyond me, sometimes the signal
          Message 4 of 9 , Mar 2 8:30 AM
          • 0 Attachment
            FWIW, that's also how it's done in PerlGP (set an alarm which breaks a
            Perl 'eval')
            Although unfortunately in Perl, for reasons beyond me, sometimes the
            signal can't
            be caught cleanly. This problem is taken care of by storing the
            population on disk
            and restarting automatically :-)

            On Tue, 1 Mar 2005 07:23:34 -0700, Brock <rbw3@...> wrote:
            > In my systems I just use the *nix signal mechanism to trigger an Alarm
            > signal (which then raises an exception in the evaluation loop.
          • Lee Spector
            Deluxe, The implementation strategy for terminating the fitness test will depend to some extent on the structure and implementation language of your program
            Message 5 of 9 , Mar 3 9:20 AM
            • 0 Attachment
              Deluxe,

              The implementation strategy for terminating the fitness test will
              depend to some extent on the structure and implementation language of
              your program interpreter. If you are recursively interpreting program
              trees or using your programming language's built-in interpreter then it
              is usually simplest to use a non-local exit, whether based on OS
              signals or (probably better) language-specific mechanisms (I usually
              use Lisp's THROW and CATCH, but more modern programmers probably prefer
              more modern exception mechanisms). With some program representations,
              however (e.g. many linear-program representations), you can instead use
              an iterative interpreter structure and simply stop iterating when
              you've hit a limit.

              More interesting (to me, anyway) is the decision of what to do after
              you've terminated interpretation. Here your options are constrained by
              your program representation and problem encoding. If, for example, you
              are doing something like symbolic regression with the standard
              functional program representation then it's hard to say what you should
              use as the value of the overall expression when one of the
              sub-expressions has no value (because its interpretation was terminated
              early). So you probably just want to give the non-terminating program a
              disqualifying fitness penalty. If, however, your program computes its
              value as a side effect of instructions that operate on registers or
              stacks, then early termination can be treated as normal termination --
              simply get the values from the registers or stacks after termination,
              whether that termination was normal or not. One could then choose
              either to impose or not to impose a penalty for the abnormal
              termination.

              The effects of all of these options on evolutionary dynamics are, as
              far as I know, open questions (though you might want to poke around
              http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html to
              see what you can find). I believe that Koza has results showing that
              non-terminators-treated-as-invalid (along with other kinds of
              "pathological individuals") tend to drop to low levels after a few
              generations. But I don't know anything about work exploring
              penalties/non-penalties for non-terminators-treated-as-valid. I and
              others have played with many of the options in GP using my Push
              language -- which computes everything by side-effects and stacks -- but
              I don't think we have any definitive advice on this to offer, and I
              doubt that there is much to say that would generalize. (Push
              implementations and related papers can be found at
              http://hampshire.edu/lspector/push.html)

              -Lee



              On Mar 2, 2005, at 11:30 AM, Bob MacCallum wrote:

              > FWIW, that's also how it's done in PerlGP (set an alarm which breaks a
              > Perl 'eval')
              > Although unfortunately in Perl, for reasons beyond me, sometimes the
              > signal can't
              > be caught cleanly.  This problem is taken care of by storing the
              > population on disk
              > and restarting automatically :-)
              >
              > On Tue, 1 Mar 2005 07:23:34 -0700, Brock <rbw3@...> wrote:
              > > In my systems I just use the *nix signal mechanism to trigger an
              > Alarm
              > > signal (which then raises an exception in the evaluation loop.
              >
              >
              On Feb 27, 2005, at 7:57 PM, deluxenewandimproved wrote:

              >
              > Are there any genetic programming packages (or papers) that deal with
              > limiting the execution time of a fitness function?  I'm trying to
              > find a way to deal with infinite loops.
              >
              > Any help will be greatly appreciated.
              > -Deluxe
              >
              --
              Lee Spector
              Dean, Cognitive Science + Professor, Computer Science
              Cognitive Science, Hampshire College
              893 West Street, Amherst, MA 01002-3359
              lspector@..., http://hampshire.edu/lspector/
              Phone: 413-559-5352, Fax: 413-559-5438
            • Lee Spector
              P.S. One other increasingly common problem encoding strategy for which the options of what-to-do-after-termination remain open involves the use of
              Message 6 of 9 , Mar 3 9:35 AM
              • 0 Attachment
                P.S. One other increasingly common problem encoding strategy for which
                the options of what-to-do-after-termination remain open involves the
                use of "developmental" instructions that augment an "embryo" when
                executed. Koza has written a lot about this recently, but many others
                use the same basic strategy. If you terminate a program because it hits
                a limit there's probably still a partially-developed structure
                (circuit, network, controller, creature, whatever) hanging around that
                you could still evaluate (or not) with (or without) a penalty for the
                abnormal termination.

                -Lee


                On Mar 3, 2005, at 12:20 PM, Lee Spector wrote:

                >
                > Deluxe,
                >
                > The implementation strategy for terminating the fitness test will
                > depend to some extent on the structure and implementation language of
                > your program interpreter. If you are recursively interpreting program
                > trees or using your programming language's built-in interpreter then
                > it
                > is usually simplest to use a non-local exit, whether based on OS
                > signals or (probably better) language-specific mechanisms (I usually
                > use Lisp's THROW and CATCH, but more modern programmers probably
                > prefer
                > more modern exception mechanisms). With some program representations,
                > however (e.g. many linear-program representations), you can instead
                > use
                > an iterative interpreter structure and simply stop iterating when
                > you've hit a limit.
                >
                > More interesting (to me, anyway) is the decision of what to do after
                > you've terminated interpretation. Here your options are constrained by
                > your program representation and problem encoding. If, for example, you
                > are doing something like symbolic regression with the standard
                > functional program representation then it's hard to say what you
                > should
                > use as the value of the overall expression when one of the
                > sub-expressions has no value (because its interpretation was
                > terminated
                > early). So you probably just want to give the non-terminating program
                > a
                > disqualifying fitness penalty. If, however, your program computes its
                > value as a side effect of instructions that operate on registers or
                > stacks, then early termination can be treated as normal termination --
                > simply get the values from the registers or stacks after termination,
                > whether that termination was normal or not. One could then choose
                > either to impose or not to impose a penalty for the abnormal
                > termination.
                >
                > The effects of all of these options on evolutionary dynamics are, as
                > far as I know, open questions (though you might want to poke around
                > http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html to
                > see what you can find). I believe that Koza has results showing that
                > non-terminators-treated-as-invalid (along with other kinds of
                > "pathological individuals") tend to drop to low levels after a few
                > generations. But I don't know anything about work exploring
                > penalties/non-penalties for non-terminators-treated-as-valid. I and
                > others have played with many of the options in GP using my Push
                > language -- which computes everything by side-effects and stacks --
                > but
                > I don't think we have any definitive advice on this to offer, and I
                > doubt that there is much to say that would generalize. (Push
                > implementations and related papers can be found at
                > http://hampshire.edu/lspector/push.html)
                >
                >   -Lee
                >
                >
                >
                > On Mar 2, 2005, at 11:30 AM, Bob MacCallum wrote:
                >
                > > FWIW, that's also how it's done in PerlGP (set an alarm which
                > breaks a
                > >  Perl 'eval')
                > >  Although unfortunately in Perl, for reasons beyond me, sometimes
                > the
                > >  signal can't
                > >  be caught cleanly.  This problem is taken care of by storing the
                > >  population on disk
                > >  and restarting automatically :-)
                > >
                > >  On Tue, 1 Mar 2005 07:23:34 -0700, Brock <rbw3@...> wrote:
                > >  > In my systems I just use the *nix signal mechanism to trigger an
                > > Alarm
                > >  > signal (which then raises an exception in the evaluation loop.
                > >
                > >
                > On Feb 27, 2005, at 7:57 PM, deluxenewandimproved wrote:
                >
                > >
                > >  Are there any genetic programming packages (or papers) that deal
                > with
                > >  limiting the execution time of a fitness function?  I'm trying to
                > >  find a way to deal with infinite loops.
                > >
                > >  Any help will be greatly appreciated.
                > >  -Deluxe
                > >
                > --
                > Lee Spector
                > Dean, Cognitive Science + Professor, Computer Science
                > Cognitive Science, Hampshire College
                > 893 West Street, Amherst, MA 01002-3359
                > lspector@..., http://hampshire.edu/lspector/
                > Phone: 413-559-5352, Fax: 413-559-5438
                >
                >
                >
                >
                > Yahoo! Groups Sponsor
                >
                > ADVERTISEMENT
                > <22305_0205_016_b_300250_a.gif>
                > <l.gif>
                >
                > Yahoo! Groups Links
                >
                > • To visit your group on the web, go to:
                > http://groups.yahoo.com/group/genetic_programming/
                >  
                > • To unsubscribe from this group, send an email to:
                > genetic_programming-unsubscribe@yahoogroups.com
                >  
                > • Your use of Yahoo! Groups is subject to the Yahoo! Terms of
                > Service.
                >
                >
                --
                Lee Spector
                Dean, Cognitive Science + Professor, Computer Science
                Cognitive Science, Hampshire College
                893 West Street, Amherst, MA 01002-3359
                lspector@..., http://hampshire.edu/lspector/
                Phone: 413-559-5352, Fax: 413-559-5438
              • Langdon W B
                Possibly of interest are: Experiments with a Coroutine Model for Genetic Programming icec94:maxwell Genetic Programming, Indexed memory, the Halting
                Message 7 of 9 , Mar 3 9:51 AM
                • 0 Attachment
                  Possibly of interest are:
                  "Experiments with a Coroutine Model for Genetic Programming" icec94:maxwell
                  "Genetic Programming, Indexed memory, the Halting problem, and other curiosities" fairs94:teller

                  Bill
                  W. B. Langdon, Phone +44-1206-873291
                  Computer Science, Fax: +44-1206-872788
                  University of Essex
                  Wivenhoe Park,
                  Colchester CO4 3SQ, UK
                  http://www.cs.essex.ac.uk/staff/W.Langdon/

                  Foundations of Genetic Programming
                  http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP
                  Evolving L-systems http://www.cs.ucl.ac.uk/staff/W.Langdon/pfeiffer.html
                  EuroGP Lausanne 2005 http://www.evonet.info/eurogp2005
                  GP Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
                  >
                  >
                  > P.S. One other increasingly common problem encoding strategy for which=20
                  > the options of what-to-do-after-termination remain open involves the=20
                  > use of "developmental" instructions that augment an "embryo" when=20
                  > executed. Koza has written a lot about this recently, but many others=20
                  > use the same basic strategy. If you terminate a program because it hits=20
                  > a limit there's probably still a partially-developed structure=20
                  > (circuit, network, controller, creature, whatever) hanging around that=20
                  > you could still evaluate (or not) with (or without) a penalty for the=20
                  > abnormal termination.
                  >
                  > -Lee
                  >
                  >
                  > On Mar 3, 2005, at 12:20 PM, Lee Spector wrote:
                  >
                  > >
                  > > Deluxe,
                  > >
                  > > The implementation strategy for terminating the fitness test will
                  > > depend to some extent on the structure and implementation language of
                  > > your program interpreter. If you are recursively interpreting program
                  > > trees or using your programming language's built-in interpreter then=20
                  > > it
                  > > is usually simplest to use a non-local exit, whether based on OS
                  > > signals or (probably better) language-specific mechanisms (I usually
                  > > use Lisp's THROW and CATCH, but more modern programmers probably=20
                  > > prefer
                  > > more modern exception mechanisms). With some program representations,
                  > > however (e.g. many linear-program representations), you can instead=20
                  > > use
                  > > an iterative interpreter structure and simply stop iterating when
                  > > you've hit a limit.
                  > >
                  > > More interesting (to me, anyway) is the decision of what to do after
                  > > you've terminated interpretation. Here your options are constrained by
                  > > your program representation and problem encoding. If, for example, you
                  > > are doing something like symbolic regression with the standard
                  > > functional program representation then it's hard to say what you=20
                  > > should
                  > > use as the value of the overall expression when one of the
                  > > sub-expressions has no value (because its interpretation was=20
                  > > terminated
                  > > early). So you probably just want to give the non-terminating program=20
                  > > a
                  > > disqualifying fitness penalty. If, however, your program computes its
                  > > value as a side effect of instructions that operate on registers or
                  > > stacks, then early termination can be treated as normal termination --
                  > > simply get the values from the registers or stacks after termination,
                  > > whether that termination was normal or not. One could then choose
                  > > either to impose or not to impose a penalty for the abnormal
                  > > termination.
                  > >
                  > > The effects of all of these options on evolutionary dynamics are, as
                  > > far as I know, open questions (though you might want to poke around
                  > > http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html to
                  > > see what you can find). I believe that Koza has results showing that
                  > > non-terminators-treated-as-invalid (along with other kinds of
                  > > "pathological individuals") tend to drop to low levels after a few
                  > > generations. But I don't know anything about work exploring
                  > > penalties/non-penalties for non-terminators-treated-as-valid. I and
                  > > others have played with many of the options in GP using my Push
                  > > language -- which computes everything by side-effects and stacks --=20
                  > > but
                  > > I don't think we have any definitive advice on this to offer, and I
                  > > doubt that there is much to say that would generalize. (Push
                  > > implementations and related papers can be found at
                  > > http://hampshire.edu/lspector/push.html)
                  > >
                  > > =A0 -Lee
                  > >
                  > >
                  > >
                  > > On Mar 2, 2005, at 11:30 AM, Bob MacCallum wrote:
                  > >
                  > > > FWIW, that's also how it's done in PerlGP (set an alarm which=20
                  > > breaks a
                  > > >=A0 Perl 'eval')
                  > > >=A0 Although unfortunately in Perl, for reasons beyond me, sometimes=20
                  > > the
                  > > >=A0 signal can't
                  > > >=A0 be caught cleanly.=A0 This problem is taken care of by storing the
                  > > >=A0 population on disk
                  > > >=A0 and restarting automatically :-)
                  > > >
                  > > >=A0 On Tue, 1 Mar 2005 07:23:34 -0700, Brock <rbw3@...> wrote:
                  > > >=A0 > In my systems I just use the *nix signal mechanism to trigger an
                  > > > Alarm
                  > > >=A0 > signal (which then raises an exception in the evaluation loop.
                  > > >
                  > > >
                  > > On Feb 27, 2005, at 7:57 PM, deluxenewandimproved wrote:
                  > >
                  > > >
                  > > >=A0 Are there any genetic programming packages (or papers) that deal=20
                  > > with
                  > > >=A0 limiting the execution time of a fitness function?=A0 I'm trying to
                  > > >=A0 find a way to deal with infinite loops.
                  > > >
                  > > >=A0 Any help will be greatly appreciated.
                  > > >=A0 -Deluxe
                  > > >
                • Peter Day
                  If you re not alerady using a package and are comfortable with java then ecj ((http://cs.gmu.edu/~eclab/projects/ecj/) is very comprehensive and limiting
                  Message 8 of 9 , Mar 4 4:51 AM
                  • 0 Attachment
                    If you're not alerady using a package and are comfortable with java then
                    ecj ((http://cs.gmu.edu/~eclab/projects/ecj/) is very comprehensive and
                    limiting execution time can be done by simply stoping the evaluation
                    thread after a preset time.

                    deluxenewandimproved wrote:

                    >
                    >Are there any genetic programming packages (or papers) that deal with
                    >limiting the execution time of a fitness function? I'm trying to
                    >find a way to deal with infinite loops.
                    >
                    >Any help will be greatly appreciated.
                    >-Deluxe
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >Yahoo! Groups Links
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                    >
                  • deluxenewandimproved
                    Thanks for the responses to this question, everyone. I ll let you know if I make any intresting progress along this path. Best, Deluxe
                    Message 9 of 9 , Mar 16 4:52 AM
                    • 0 Attachment
                      Thanks for the responses to this question, everyone. I'll let you
                      know if I make any intresting progress along this path.

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