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

Efficiency (was: Re: [GP] Many or few functions?)

Expand Messages
  • Howard A. Landman
    ... You consider me the young apprentice caught between your Scylla and Charybdis - Sting, Wrapped Around Your Finger Well, that depends. The basic
    Message 1 of 7 , Nov 19, 2005
      > Do people find that it's better to use a minimal set of functions or a
      > very large one?

      "You consider me the young apprentice
      caught between your Scylla and Charybdis"
      - Sting, "Wrapped Around Your Finger"

      Well, that depends. The basic dilemma is: as you add more functions your
      search space explodes dramatically, so if you have too many you may never
      find a good solution in reasonable time. But if you FAIL to include a
      function that is needed, you may never find a solution at all.

      Finding the perfect balance - the "right encoding" - is still a bit of a
      black art.

      And as long as we're on the topic of efficiency ...

      Note that the lack of reconvergent fanout in tree-GP automatically forces
      some size inefficiency (e.g. to build XOR2 out of NAND2 requires 5 gates
      in a tree but only 4 in a minimal (directed acyclic graph) circuit), and
      the search space is exponential in the minimum solution size. For some
      applications, evolving graphs rather than trees can make a huge
      difference. Other mechanisms for inducing out-of-the-tree communication,
      such as memory operations, can often be interpreted as just a way of
      escaping this inefficiency; that is, as "wires" connecting different
      points in the function tree's "space" rather than as "memory" connecting
      different points in the computation's "time". (The ideas in this
      paragraph are more fully explored in a paper I started writing a few years
      ago but never finished; maybe I'll dig it up and try to complete it now.)

      Koza-style GP only allows fanout at the very bottom, i.e. terminals may be
      repeated. The introduction of ADFs improves this slightly (terminals may
      be repeated in an ADF as well), but does not give a general solution.
      Thus, from the viewpoint of evolving large circuits which *require* a lot
      of reconvergence, it's inherently crippled.

      Further, there was a student poster at DAC within the last couple of years
      that showed that even adhering to *acyclic* graphs causes some
      inefficiency; in some cases circuits containing the dreaded "asynchrounous
      feedback loops" can actually be smaller and/or faster than the best ones
      which don't! Unidirectional (acyclic) data flow is thus provably
      suboptimal in and of itself, even if it includes a mechanism enabling
      fully general reconvergent fanout.

      Howard A. Landman
      Ageia Technlogies
    • Colin Green
      ... I wonder if a general solution to this problem exists whereby the set of functions in use in a given solution instance (genome) is also defined within the
      Message 2 of 7 , Nov 19, 2005
        Howard A. Landman wrote:

        > > Do people find that it's better to use a minimal set of functions or a
        > > very large one?
        >
        >
        >Well, that depends. The basic dilemma is: as you add more functions your
        >search space explodes dramatically, so if you have too many you may never
        >find a good solution in reasonable time. But if you FAIL to include a
        >function that is needed, you may never find a solution at all.
        >
        >
        I wonder if a general solution to this problem exists whereby the set of
        functions in use in a given solution instance (genome) is also defined
        within the genome - it evolves along with the tree/graph of operations.

        >Finding the perfect balance - the "right encoding" - is still a bit of a
        >black art.
        >
        >And as long as we're on the topic of efficiency ...
        >
        >Note that the lack of reconvergent fanout in tree-GP automatically forces
        >some size inefficiency (e.g. to build XOR2 out of NAND2 requires 5 gates
        >in a tree but only 4 in a minimal (directed acyclic graph) circuit), and
        >the search space is exponential in the minimum solution size. For some
        >applications, evolving graphs rather than trees can make a huge
        >difference.
        >
        This is something that has been discussed occassionally on the NEAT
        yahoo group, only there we use the ANN terms of feed-forward and
        recurrent networks.

        > Other mechanisms for inducing out-of-the-tree communication,
        >such as memory operations, can often be interpreted as just a way of
        >escaping this inefficiency; that is, as "wires" connecting different
        >points in the function tree's "space" rather than as "memory" connecting
        >different points in the computation's "time". (The ideas in this
        >paragraph are more fully explored in a paper I started writing a few years
        >ago but never finished; maybe I'll dig it up and try to complete it now.)
        >
        >
        It's an area I'm very interested in right now. I've been thinking about
        a fusion between graph based GP and NEAT, which basically just means
        extending NEAT to use GP operators at each node instead of the single
        neuron activation function it uses right now (in most publicly available
        implementations anyhow). I wonder if anyone could point me in the
        direction of any graph based GP research papers and/or software. My
        attempts at searching via google and citeseer have been patchy so far -
        maybe I'm missing some critical key word that I'm unaware of.

        Regards,

        Colin Green
        (http://sharpneat.sourceforge.net) <http://sharpneat.sourceforge.net/>
      • Terence Soule
        Hi, A student of my addressed some of these questions in a paper at EuroGP. He found that functions could be divided into equivilency sets and one function
        Message 3 of 7 , Nov 20, 2005
          Hi,

          A student of my addressed some of these questions in a paper at EuroGP.
          He found that functions could be divided into equivilency sets and one
          function from each set was generally sufficient. The equivilency sets
          were pretty much what would be expected, e.g. sin, cos, and tan are in the
          same set. Including any one function from an equivilency set is
          equivilent to including any other one. Including too many functions
          from the same set seemed to result in slightly poorer results. Presumably
          because of the larger search space created.

          The paper citation:
          Gang Wang and Terence Soule
          "How to Choose Appropriate Function Sets for Genetic Programming"
          EuroGP 2004
          pp. 198-207
          Springer Lecture Notes in Computer Science Vol. 303

          Hope this helps,
          Terry Soule
          Department of Computer Science
          University of Idaho
          tsoule@...

          On Sun, 20 Nov 2005, Colin Green wrote:

          > Howard A. Landman wrote:
          >
          > > > Do people find that it's better to use a minimal set of functions or a
          > > > very large one?
          > >
          > >
          > >Well, that depends. The basic dilemma is: as you add more functions your
          > >search space explodes dramatically, so if you have too many you may never
          > >find a good solution in reasonable time. But if you FAIL to include a
          > >function that is needed, you may never find a solution at all.
          > >
          > >
          > I wonder if a general solution to this problem exists whereby the set of
          > functions in use in a given solution instance (genome) is also defined
          > within the genome - it evolves along with the tree/graph of operations.
          >
          > >Finding the perfect balance - the "right encoding" - is still a bit of a
          > >black art.
          > >
          > >And as long as we're on the topic of efficiency ...
          > >
          > >Note that the lack of reconvergent fanout in tree-GP automatically forces
          > >some size inefficiency (e.g. to build XOR2 out of NAND2 requires 5 gates
          > >in a tree but only 4 in a minimal (directed acyclic graph) circuit), and
          > >the search space is exponential in the minimum solution size. For some
          > >applications, evolving graphs rather than trees can make a huge
          > >difference.
          > >
          > This is something that has been discussed occassionally on the NEAT
          > yahoo group, only there we use the ANN terms of feed-forward and
          > recurrent networks.
          >
          > > Other mechanisms for inducing out-of-the-tree communication,
          > >such as memory operations, can often be interpreted as just a way of
          > >escaping this inefficiency; that is, as "wires" connecting different
          > >points in the function tree's "space" rather than as "memory" connecting
          > >different points in the computation's "time". (The ideas in this
          > >paragraph are more fully explored in a paper I started writing a few years
          > >ago but never finished; maybe I'll dig it up and try to complete it now.)
          > >
          > >
          > It's an area I'm very interested in right now. I've been thinking about
          > a fusion between graph based GP and NEAT, which basically just means
          > extending NEAT to use GP operators at each node instead of the single
          > neuron activation function it uses right now (in most publicly available
          > implementations anyhow). I wonder if anyone could point me in the
          > direction of any graph based GP research papers and/or software. My
          > attempts at searching via google and citeseer have been patchy so far -
          > maybe I'm missing some critical key word that I'm unaware of.
          >
          > Regards,
          >
          > Colin Green
          > (http://sharpneat.sourceforge.net) <http://sharpneat.sourceforge.net/>
          >
          >
          >
          >
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
          >
          >
        • Michael Lones
          On 20 Nov 2005, at 01:26, Colin Green wrote: [...] ... The two best known ones are Poli s Parallel Distributed Genetic Programming [1997] and Miller s
          Message 4 of 7 , Nov 21, 2005
            On 20 Nov 2005, at 01:26, Colin Green wrote:

            [...]

            > I wonder if anyone could point me in the
            > direction of any graph based GP research papers and/or software. My
            > attempts at searching via google and citeseer have been patchy so
            > far -
            > maybe I'm missing some critical key word that I'm unaware of.

            The two best known ones are Poli's Parallel Distributed Genetic
            Programming [1997] and Miller's Cartesian Genetic Programming [2000].
            Other ones with graph-based elements include Genetic Network
            Programming [Katagiri et al, 2000], PADO [Teller and Veloso, 1996],
            Multiple Interacting Programs [Angeline, 1998] and Genetically
            Programmed Networks [Silva et al, 1999]. You can find references at:
            http://www-users.york.ac.uk/~mal503/common/thesis/b.html

            Hope this helps!
            Mic


            Michael Lones
            Intelligent Systems Research Group
            University of York
            http://www-users.york.ac.uk/~mal503/
          • Mario Giacobini
            Hi! I ve worked quite a lot on graph based EAs, and even if I don t directly discuss GP issues, I think thet some of my group s papers could be interesting for
            Message 5 of 7 , Nov 29, 2005
              Hi!
              I've worked quite a lot on graph based EAs, and even if
              I don't directly discuss GP issues, I think thet some of my
              group's papers could be interesting for you. You can look
              on my publication's web page:
              http://www-iis.unil.ch/~mgiacobi/publications.php
              Hope this will help you, regards
              Mario




              On Nov 21, 2005, at 10:52 AM, Michael Lones wrote:

              >
              > On 20 Nov 2005, at 01:26, Colin Green wrote:
              >
              > [...]
              >
              > > I wonder if anyone could point me in the
              > > direction of any graph based GP research papers and/or software. My
              > > attempts at searching via google and citeseer have been patchy so 
              > > far -
              > > maybe I'm missing some critical key word that I'm unaware of.
              >
              > The two best known ones are Poli's Parallel Distributed Genetic 
              > Programming [1997] and Miller's Cartesian Genetic Programming [2000]. 
              > Other ones with graph-based elements include Genetic Network 
              > Programming [Katagiri et al, 2000], PADO [Teller and Veloso, 1996], 
              > Multiple Interacting Programs [Angeline, 1998] and Genetically 
              > Programmed Networks [Silva et al, 1999]. You can find references at: 
              > http://www-users.york.ac.uk/~mal503/common/thesis/b.html
              >
              > Hope this helps!
              > Mic
              >
              >
              > Michael Lones
              > Intelligent Systems Research Group
              > University of York
              > http://www-users.york.ac.uk/~mal503/
              >
              >
              >
              >
              > YAHOO! GROUPS LINKS
              >
              > ▪  Visit your group "genetic_programming" on the web.
              >  
              > ▪  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.
              >
              >
              >
              ------------------------------------------------------------------------
              ---------------
              The exhausting search for the wisdom is our second heaven.

              [Paracelsus]
              ------------------------------------------------------------------------
              ---------------
              Mario Giacobini

              Research Assistant & Invited Lecturer
              Information Systems Department School of Multimedia and Art
              UNIL-Sorge, Amphipole University of Torino
              University of Lausanne Italy
              1015 Lausanne
              Switzerland

              tel: +41-21-6923586
              fax: +41-21-6923585
              e-mail: mario.giacobini@...
              http://www-iis.unil.ch/~mgiacobi
              ------------------------------------------------------------------------
              ---------------


              [Non-text portions of this message have been removed]
            • Colin Green
              ... Thanks everyone for the references. Genetic Network Programming in particular looks to be exactly the sort of scheme I was thinking about, although
              Message 6 of 7 , Nov 30, 2005
                --- In genetic_programming@yahoogroups.com, Mario Giacobini
                <mario.giacobini@u...> wrote:
                >
                > Hi!
                > I've worked quite a lot on graph based EAs, and even if
                > I don't directly discuss GP issues, I think thet some of my
                > group's papers could be interesting for you. You can look
                > on my publication's web page:
                > http://www-iis.unil.ch/~mgiacobi/publications.php
                > Hope this will help you, regards
                > Mario
                >

                Thanks everyone for the references. Genetic Network Programming in
                particular looks to be exactly the sort of scheme I was thinking
                about, although searching on this phrase didn't give a lot of results.
                For anyone else interested in this particular topic I did find this
                paper freely available for starters:

                "Genetic Network Programming with Reinforcement Learning and its
                Performance Evaluation", Shingo Mabu, Kotaro Hirasaw and Jinglu Hu.
                http://www.cs.bham.ac.uk/~wbl/biblio/gecco2004/LBP036.pdf

                Thanks,

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