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

Question About GP

Expand Messages
  • Agus Iskandar
    Hello, guys. I m just newbie in this GP field but I m curious about this field and I want to learn more. In my campus, I don t get this lesson about GP. I just
    Message 1 of 19 , Oct 3, 2006
    • 0 Attachment
      Hello, guys. I'm just newbie in this GP field but I'm curious about this
      field and I want to learn more. In my campus, I don't get this lesson
      about GP. I just taught only about Evolutionary Computation for
      common. And there is only one book about GP ("GP An Introduction by
      Wolfgang Banzhaf) which I was still reading it till now.

      Can anyone help me? I have some questions about GP.
      1. Please tell me, what is the difference between GA and GP actually?
      2. Anyone have good reference sites about the implementation of GP?
      3. Can I make GP not only in LISP or C but other programming languanges
      like Delphi or Java?
      4. I'm interested in Developmental Genetic Programing (DGP) because it
      is very similar to GA, because it use kind of binary representation
      for the function and terminals. Can anyone tell me more about this
      DGP?

      I'm sorry if i ask too many and maybe the questions are too easy for u
      all but I really2 appreciate any kind of answers
      for my questions.
      Thx very much.
    • Douglas Mota
      A nice first approach would be wikipedia: http://en.wikipedia.org/wiki/Evolutionary_computing http://en.wikipedia.org/wiki/Genetic_algorithms
      Message 2 of 19 , Oct 3, 2006
      • 0 Attachment
        A nice first approach would be wikipedia:

        http://en.wikipedia.org/wiki/Evolutionary_computing
        http://en.wikipedia.org/wiki/Genetic_algorithms
        http://en.wikipedia.org/wiki/Genetic_programming (there's a list of tools and implementations)

        Regards,
        Douglas Mota Dias

        Agus Iskandar <isk_gust@...> escreveu:
        Hello, guys. I'm just newbie in this GP field but I'm curious about this
        field and I want to learn more. In my campus, I don't get this lesson
        about GP. I just taught only about Evolutionary Computation for
        common. And there is only one book about GP ("GP An Introduction by
        Wolfgang Banzhaf) which I was still reading it till now.

        Can anyone help me? I have some questions about GP.
        1. Please tell me, what is the difference between GA and GP actually?
        2. Anyone have good reference sites about the implementation of GP?
        3. Can I make GP not only in LISP or C but other programming languanges
        like Delphi or Java?
        4. I'm interested in Developmental Genetic Programing (DGP) because it
        is very similar to GA, because it use kind of binary representation
        for the function and terminals. Can anyone tell me more about this
        DGP?

        I'm sorry if i ask too many and maybe the questions are too easy for u
        all but I really2 appreciate any kind of answers
        for my questions.
        Thx very much.






        Douglas Mota Dias, MSc
        Researcher
        email: douglasm@...-rio.br

        ICA: Applied Computational Intelligence Laboratory
        Electrical Engineering Department
        Pontifícia Universidade Católica do Rio de Janeiro - PUC-Rio
        Brazil
        phone: +55 21 3114-1221 / fax: +55 21 3114-1634
        http://www.ica.ele.puc-rio.br

        ---------------------------------
        Yahoo! Search
        Música para ver e ouvir: You're Beautiful, do James Blunt

        [Non-text portions of this message have been removed]
      • Martin Sewell
        ... GP generalizes GAs, but Woodward (2003) argues that the two are effectively equivalent and it is the representation that is important. Regards Martin
        Message 3 of 19 , Oct 3, 2006
        • 0 Attachment
          At 07:47 03/10/2006 +0000, Agus Iskandar wrote:

          >1. Please tell me, what is the difference between GA and GP actually?

          GP generalizes GAs, but Woodward (2003) argues that the two are
          effectively equivalent and it is the representation that is important.

          Regards

          Martin
        • Candida Ferreira
          ... There are several differences, but fundamentally they both are what Richard Dawkins calls simple replicators. See my discussion of this in the GEP book at:
          Message 4 of 19 , Oct 4, 2006
          • 0 Attachment
            Agus Iskandar wrote:

            > 1. Please tell me, what is the difference between GA and GP actually?

            There are several differences, but fundamentally they both are what Richard
            Dawkins calls simple replicators. See my discussion of this in the GEP book
            at:

            http://www.gene-expression-programming.com/GepBook/Chapter1/Section4.htm

            http://www.gene-expression-programming.com/GepBook/Chapter1/Section5.htm


            Best wishes,
            Candida

            ---
            Candida Ferreira, Ph.D.
            Founder and Director, Gepsoft
            http://www.gene-expression-programming.com/author.asp

            GEP: Mathematical Modeling by an Artificial Intelligence
            2nd Edition, Springer-Verlag 2006
            http://www.gene-expression-programming.com/Books/index.asp

            Modeling Software:
            http://www.gepsoft.com/
          • Norman Paterson
            ... GA searches for the optimal instance of a data structure, which represents a solution to a particular probblem. For example: the best shape of a jet
            Message 5 of 19 , Oct 5, 2006
            • 0 Attachment
              > Agus Iskandar wrote:
              >
              >> 1. Please tell me, what is the difference between GA and GP actually?
              >

              GA searches for the optimal instance of a data structure, which
              represents a solution to a particular probblem.
              For example: the best shape of a jet fighter wing, where "best" is
              defined in terms of cost, performance, or whatever.

              GP searches for the optimal instance of a data structure, which
              represents an executable program that solves a particular class of
              problems.
              For example: the best program to reverse an articulated lorry, where
              "best" is defined in terms of efficiency, correctness, brevity, or
              whatever.

              Norman Paterson
              norman@...-andrews.ac.uk
            • Agus Iskandar
              Thx for all the informations. Now i kinda get the picture now. But please,Can i ask again? This time is about the fitness cases and fitness measure in GP. Can
              Message 6 of 19 , Oct 6, 2006
              • 0 Attachment
                Thx for all the informations.
                Now i kinda get the picture now.

                But please,Can i ask again?
                This time is about the fitness cases and fitness measure in GP.

                Can I say that you need to know first what is the correct output from
                the problem that you want to implement GP with, and that is the
                fitness cases.
                For example one kind of problem like arithmatic function, the fitness
                cases in some sample cases of input with their correct output of the
                function.

                Different from GP, in GA, you dont need to know the correct output for
                the fitness measure, all you need is to make a measure of for
                example how costly is the solution found so far, or is the schedule
                given by the GA system fit your satisfaction(GA in scheduling problem).

                Can somebody help me to make a clear view about this fitness cases and
                measure in GP.
                An answer with example of the implementation of the GP fitness cases
                and measure will be nice.

                Thx and once again I am sorry if I ask an easy question but thx for
                sharing your time and knowledge to me.

                Regards,

                Agus Iskandar
              • Luis Guillermo RESTREPO RIVAS
                In both, GA and GP, from the point of view of fitness, all that is necessary is: Given the two fitness values of two candidate solutions, to be able to compare
                Message 7 of 19 , Oct 6, 2006
                • 0 Attachment
                  In both, GA and GP, from the point of view of fitness, all that is necessary
                  is: Given the two fitness values of two candidate solutions, to be able to
                  compare them and decide which one is better.

                  Luis Guillermo Restrepo Rivas

                  > -----Mensaje original-----
                  > De: genetic_programming@yahoogroups.com
                  > [mailto:genetic_programming@yahoogroups.com] En nombre de
                  > Agus Iskandar
                  > Enviado el: viernes, 06 de octubre de 2006 2:27
                  > Para: genetic_programming@yahoogroups.com
                  > Asunto: [GP] Re: Question About GP
                  >
                  > Thx for all the informations.
                  > Now i kinda get the picture now.
                  >
                  > But please,Can i ask again?
                  > This time is about the fitness cases and fitness measure in GP.
                  >
                  > Can I say that you need to know first what is the correct
                  > output from the problem that you want to implement GP with,
                  > and that is the fitness cases.
                  > For example one kind of problem like arithmatic function, the
                  > fitness cases in some sample cases of input with their
                  > correct output of the function.
                  >
                  > Different from GP, in GA, you dont need to know the correct
                  > output for the fitness measure, all you need is to make a
                  > measure of for example how costly is the solution found so
                  > far, or is the schedule given by the GA system fit your
                  > satisfaction(GA in scheduling problem).
                  >
                  > Can somebody help me to make a clear view about this fitness
                  > cases and measure in GP.
                  > An answer with example of the implementation of the GP
                  > fitness cases and measure will be nice.
                  >
                  > Thx and once again I am sorry if I ask an easy question but
                  > thx for sharing your time and knowledge to me.
                  >
                  > Regards,
                  >
                  > Agus Iskandar
                • Agus Iskandar
                  Hello everyone. Thx for the reply till now. I really appreciate it. This time i want to ask about the representation of the individual in GP. I want to know
                  Message 8 of 19 , Oct 10, 2006
                  • 0 Attachment
                    Hello everyone.
                    Thx for the reply till now. I really appreciate it.
                    This time i want to ask about the representation of the individual in
                    GP.

                    I want to know which one from tree,array,linked list is the one that
                    people usually used for their GP system.
                    What are the plus and minus for each kind representations and how you
                    deal with the flaw?
                    And if you could, can you give me a reference which one I should use
                    for a newbie like me?

                    Thx again.

                    Regards,
                    Agus Iskandar
                  • Langdon W B
                    You could look at fast implementations where the tree is linearised eg... @InCollection{kinnear:keith, author = Mike J. Keith and Martin C. Martin ,
                    Message 9 of 19 , Oct 12, 2006
                    • 0 Attachment
                      You could look at fast implementations where the tree is linearised
                      eg...

                      @InCollection{kinnear:keith,
                      author = "Mike J. Keith and Martin C. Martin",
                      title = "Genetic Programming in {C}++: Implementation Issues",
                      booktitle = "Advances in Genetic Programming",
                      publisher = "MIT Press",
                      editor = "Kenneth E. {Kinnear, Jr.}",
                      year = "1994",
                      pages = "285--310",
                      chapter = "13",
                      keywords = "genetic algorithms, genetic programming",
                      size = "25 pages",
                      URL = "http://www.frc.ri.cmu.edu/~mcm/chapt.html",
                      URL = "http://www.metahuman.org/martin/papers/GeneticProgrammingInC++AdvancesInGP_KeithMartin.pdf",
                      URL = "http://citeseer.ist.psu.edu/568531.html",
                      abstract = "The purpose of our current research is to investigate
                      the design and implementation of a Genetic Programming
                      platform in C++, with primary focus on efficiency and
                      flexibility. In this chapter we consider the lower
                      level implementation aspects of such a platform,
                      specifically, the Genome Interpreter. The fact that
                      Genetic Programming is a computationally expensive task
                      means that the overall efficiency of the platform in
                      both memory and time is crucial. In particular, the
                      node representation is the key part of the
                      implementation in which the overhead will be magnified.
                      We first compare a number of ways of storing the
                      topology of the tree. The most efficient representation
                      overall is one in which the program tree is a linear
                      array of nodes in prefix order as opposed to a pointer
                      based tree structure. We consider trade-offs with other
                      linear representations, namely postfix and arbitrary
                      positioning of functions and their arguments. We then
                      consider how to represent which function or terminal
                      each node represents, and demonstrate a very efficient
                      one to two byte representation. Finally, we integrate
                      these approaches and offer a prefix/jump-table (PJT)
                      approach which results in a very small overhead per
                      node in both time and space compared to the other
                      approaches we investigated. In addition to being
                      efficient, our interpreter is also very flexible.
                      Finally, we discuss approaches for handling flow
                      control, encapsulation, recursion, and simulated
                      parallel programming.",
                      notes = "Contrasts 5 different genome interpreters (postfix,
                      prefix, Mixfix). Code based on C and C++. Population of
                      trees.

                      check later 1995 for postscript on GP ftp site",
                      }

                      Or savings by avoiding reexecution of parts of trees not changed by
                      crossover using caches. Eg:

                      @InProceedings{Handley:1994:DAGpcp,
                      author = "S. Handley",
                      title = "On the use of a directed acyclic graph to represent a
                      population of computer programs",
                      booktitle = "Proceedings of the 1994 IEEE World Congress on
                      Computational Intelligence",
                      year = "1994",
                      pages = "154--159",
                      volume = "1",
                      address = "Orlando, Florida, USA",
                      month = "27-29 " # jun,
                      publisher = "IEEE Press",
                      keywords = "genetic algorithms, genetic programming, DAG",
                      doi = "doi:10.1109/ICEC.1994.350024",
                      size = "6 pages",
                      abstract = "This paper demonstrates a technique that reduces the
                      time and space requirements of genetic programming. The
                      population of parse trees is stored as a directed
                      acyclic graph (DAG), rather than as a forest of trees.
                      This saves space by not duplicating structurally
                      identical subtrees. Also, the value computed by each
                      subtree for each fitness case is cached, which saves
                      computation both by not recomputing subtrees that
                      appear more than once in a generation and by not
                      recomputing subtrees that are copied from one
                      generation to the next. I have implemented this
                      technique for a number of problems and have seen a 15-
                      to 28-fold reduction in the number of nodes extant per
                      generation and an 11- to 30-fold reduction in the
                      number of nodes evaluated per run (for populations of
                      size 500).",
                      notes = "Converts whole GP population to a directed Acyclic
                      Graph, which is functionally equivelent. With
                      primatives that have NO SIDE EFFECTS is able to cache
                      earlier sub tree evaluations so they donot have to be
                      re-evaluated, even if occur in a different individual.
                      Claims speed ups of 11-30 fold.",
                      }


                      Bill

                      W. B. Langdon,
                      Computer Science,
                      Essex Institute of Technology
                      University of Essex
                      Wivenhoe Park,
                      Colchester CO4 3SQ, UK
                      http://www.cs.essex.ac.uk/staff/W.Langdon/
                      Spam blocking gmail
                      Foundations of Genetic Programming
                      http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP
                      EuroGP-2007 http://evonet.lri.fr/TikiWiki/tiki-index.php?page=EuroGP
                      GECCO 2007 http://www.sigevo.org/gecco-2007
                      GP EM http://springerlink.metapress.com/link.asp?id=104755
                      GP Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/


                      > Hello everyone.
                      > Thx for the reply till now. I really appreciate it.
                      > This time i want to ask about the representation of the individual in
                      > GP.
                      >
                      > I want to know which one from tree,array,linked list is the one that
                      > people usually used for their GP system.
                      > What are the plus and minus for each kind representations and how you
                      > deal with the flaw?
                      > And if you could, can you give me a reference which one I should use
                      > for a newbie like me?
                      >
                      > Thx again.
                      >
                      > Regards,
                      > Agus Iskandar
                      >
                      >
                      >
                      >
                      >
                      >
                      >
                      > Yahoo! Groups Links
                      >
                      >
                      >
                      >
                      >
                    • Agus Iskandar
                      Thx Mr. Langdon, for the information. I just starting to read it and if there is something that i dont understand, please give me ur guidance :) I have this
                      Message 10 of 19 , Oct 17, 2006
                      • 0 Attachment
                        Thx Mr. Langdon, for the information.
                        I just starting to read it and if there is something that i dont
                        understand, please give me ur guidance :)

                        I have this one question that been bugging me.
                        There is this one article that said that one flaw that GP system had
                        is the individual solution (program) that being evolved by GP,usually
                        too complicated for us (human) to understand. It is true? Have
                        somebody do anything about this?
                        Pls give me ur comments. Thx
                      • Langdon W B
                        Dear Agus Iskandar, Hmm. On the one hand, Evolution in Biology does not tend to produce systems which are easily understood by people. Just considering the
                        Message 11 of 19 , Oct 23, 2006
                        • 0 Attachment
                          Dear Agus Iskandar,
                          Hmm.

                          On the one hand, Evolution in Biology does not tend to produce
                          systems which are easily understood by people.
                          Just considering the genetic material. Even today something like 98%
                          of it has no known function.
                          On the other hand, if you think of evolutionary computation as an
                          optimisation technique you might get some distance by thinking about
                          what makes a program understandable in general or for you in
                          particular. Then instructing evolution to go in that direction.
                          This may not be easy and simplistic mechanism may cause evolution to
                          go in the direction your fitness function tells it to, rather than the
                          way you really wanted.
                          Another way to go is to simplify the program after it has been
                          evolved. There are tools about which claim to do this. You can even
                          use GP to shorten its own solutions.

                          Bill

                          W. B. Langdon, Phone +44-1206-873291
                          Computer Science, Fax: +44-1206-872788
                          Essex Institute of Technology
                          University of Essex
                          Wivenhoe Park,
                          Colchester CO4 3SQ, UK
                          http://www.cs.essex.ac.uk/staff/W.Langdon/
                          Spam blocking gmail
                          Foundations of Genetic Programming
                          http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP
                          EuroGP-2007 http://evonet.lri.fr/TikiWiki/tiki-index.php?page=EuroGP
                          GECCO 2007 http://www.cs.ucl.ac.uk/external/W.Langdon/gecco
                          GP EM http://springerlink.metapress.com/link.asp?id=104755
                          GP Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
                        • Martin Sewell
                          ... 1) In some problems it is important that the solution is easily understood, whilst in others it is not. 2) If the solution was that simple, it is likely
                          Message 12 of 19 , Oct 23, 2006
                          • 0 Attachment
                            At 08:23 17/10/2006 +0000, Agus Iskandar wrote:

                            >Thx Mr. Langdon, for the information.
                            >I just starting to read it and if there is something that i dont
                            >understand, please give me ur guidance :)
                            >
                            >I have this one question that been bugging me.
                            >There is this one article that said that one flaw that GP system had
                            >is the individual solution (program) that being evolved by GP,usually
                            >too complicated for us (human) to understand. It is true? Have
                            >somebody do anything about this?
                            >Pls give me ur comments. Thx

                            1) In some problems it is important that the solution is easily
                            understood, whilst in others it is not.

                            2) If the solution was that simple, it is likely that GP would not be
                            required in the first place.

                            3) If you wish to show the explanatory ability of GP in a favourable
                            light, compare GP with neural networks. :-)

                            Regards

                            Martin
                          • Agus Iskandar
                            Thx Mr. Langdon and Mr. Martin for the answers. It really help a lot for me to make a clear view about GP. But I have a question again: 1.Can i have a summary
                            Message 13 of 19 , Oct 30, 2006
                            • 0 Attachment
                              Thx Mr. Langdon and Mr. Martin for the answers.
                              It really help a lot for me to make a clear view about GP.

                              But I have a question again:
                              1.Can i have a summary about GP like this?

                              I want to know the solutions of some kind of problems and i dont
                              know the suitable program or functions for making it.
                              So I make GP system to find it and make the program that gives
                              solutions according to my fitness function.
                              So in the end GP give me solutions in the shape of some kind of
                              program codes that combine my defined functions and terminals.
                              So I use the output of GP,the program solutions for my problem.

                              2.What about GP in game playing strategy for example in chess game?
                              Can somebody explain about this?
                              I wonder how to implement GP in a game because we can't wait for too
                              long just for waiting the computer done making the calculation for
                              the next move,right? Coz GP (and also GA) are known for its long time
                              for doing a fitness evaluation. Or do I wrong,pls correct me? Or if
                              anyone in this mailing list have been made it,pls share your
                              experiences. To be honest, i kinda interested in implementing GP in a
                              game playing strategy.:)

                              Thx for ur time and your kindness for replying me. :)

                              Regards,

                              Agus Iskandar
                            • Agus Iskandar
                              Thx Mr. Langdon and Mr. Martin for the answers. Recently I read about this article by Mr. Gleich (2003) about implementing GP in chess endgame. In Mr. Gleich
                              Message 14 of 19 , Oct 31, 2006
                              • 0 Attachment
                                Thx Mr. Langdon and Mr. Martin for the answers.

                                Recently I read about this article by Mr. Gleich (2003) about
                                implementing GP in chess endgame. In Mr. Gleich case, he used the
                                KRK(King,Rook,King) position dataset for his system.(have anyone read
                                this?)

                                For me,it is a really interesting field to implement GP in game
                                playing strategy. But unfortunately I am still really blind about this
                                field.

                                1.Please, anyone who have made project about this or know something
                                about GP implementation in game playing strategy especially in chess
                                game, please share me your knowledge or you could give me a link where
                                i can start to learn about that.

                                2.One question that i have in mind is :
                                GP is known for a great amount of time that it takes for fitness
                                evaluation. So when we used GP for game playing strategy for example
                                in chess, the individual programs in the population,each of them must
                                be tested for fitness evaluation by running the individual program in
                                a chess game with random position.
                                Because of that i'm started to think that we must wait for a really
                                long time just for evaluating one individual program. Because we must
                                wait for the individual program done playing the game.

                                Are my arguments above true or actually that is not the only way to
                                evaluate the fitness of GP system in game playing strategy?
                                Pls give your comments.

                                I'm in the middle of making a proposal for my final project right
                                now. I am really interested in GP but knowing how blind i was about
                                this field, i feel that i must really learn a lot about this.

                                Thx for your kindness for sharing your time and knowledge for a newbie
                                like me.

                                Regards,

                                Agus
                              • Adil Raja
                                Agus, I hope that u r fine. Ur queries are genuine and I hope that I might be able to help. Please read my response below. want to know the solutions of some
                                Message 15 of 19 , Nov 5, 2006
                                • 0 Attachment
                                  Agus,
                                  I hope that u r fine. Ur queries are genuine and I hope that I might be
                                  able to help. Please read my response below.

                                  want to know the solutions of some kind of problems and i dont know the
                                  suitable program or functions for making it.
                                  So I make GP system to find it and make the program that gives solutions
                                  according to my fitness function.
                                  So in the end GP give me solutions in the shape of some kind of program
                                  codes that combine my defined functions and terminals.
                                  So I use the output of GP,the program solutions for my problem.

                                  If we say that there are to steps for doing mathematical modeling then these
                                  would be.
                                  1) To find the right model first for instance in the form of ax^2-by^3+cz
                                  (where x,y,z are some input variables and a, b, c are the coefficients of
                                  the model.
                                  2) The second step would be to find the values of the coefficients.

                                  So it is the first step at which GP is good at. Sometimes one never knows
                                  (or never wants to work out) the form of the model for various reasons (the
                                  problem could be formidable). For the second step one normally has to
                                  integrate a parameter tuning engine with GP. This could be based on anything
                                  (for instance any line-search methods or other soft computing approach).
                                  (All this is very much true for the symbolic regression domain in which I
                                  work).

                                  Now GP can give u as many solutions (u may also call them individuals or
                                  programs or models) as much as the size of the population. Each of these are
                                  potential solutions to the problem at hand. Obviously, the one that would
                                  suit you would be the one that has a better fitness.

                                  2.What about GP in game playing strategy for example in chess game?
                                  Can somebody explain about this?
                                  I wonder how to implement GP in a game because we can't wait for too
                                  long just for waiting the computer done making the calculation for
                                  the next move,right? Coz GP (and also GA) are known for its long time
                                  for doing a fitness evaluation. Or do I wrong,pls correct me? Or if
                                  anyone in this mailing list have been made it,pls share your
                                  experiences. To be honest, i kinda interested in implementing GP in a
                                  game playing strategy.:)

                                  For a better answer on this I would suggest that you'd better read Koza et
                                  als. Genetic Programming IV: Routine Human-Competitve Machine Intelligence.
                                  Chapter 1 http://www.genetic-programming.org/gp4chapter1.pdf . In this
                                  chapter Koza et. al. briefly discuss the fierce chess combat between Garry
                                  Kasparov and deep-blue, which the former ultimately lost. The authors use
                                  this as an example to illustrate the A-to-I ratio i.e. Artificial to
                                  Intelligence ratio. It is believed that the deep-blue chess system presented
                                  highly human competitive (as it defeated Garry Kasparov) and delivered a
                                  high degree of "A" (artificiality in some meaningful sense) but the project
                                  had low returns when measured in terms of A-2-I ratio (I stands for the
                                  intelligence which was provided by the humans). The major reason being that
                                  the humans (the development team) spent years in developing chips and
                                  software that could evaluate a large number of alternative moves in
                                  parallel. Maybe a great deal of human intelligence was also invested in
                                  articulating chess moves at a tactical level.
                                  The crux of the story is that: one has to take two things into
                                  consideration. 1) How much is the artificial intelligence intelligence
                                  algorithm delivering. 2) And how much are the humans themselves involved in
                                  the whole process.

                                  Moreover, this might also give u hint that developing a good chess playing
                                  machine would involve a great deal of work (not by the GP only:)).

                                  I hope it all helps. My input is not thorough. But maybe we could prolong
                                  the discussion.

                                  Regards,
                                  A

                                  On 10/30/06, Agus Iskandar <isk_gust@...> wrote:
                                  >
                                  > Thx Mr. Langdon and Mr. Martin for the answers.
                                  > It really help a lot for me to make a clear view about GP.
                                  >
                                  > But I have a question again:
                                  > 1.Can i have a summary about GP like this?
                                  >
                                  > I want to know the solutions of some kind of problems and i dont
                                  > know the suitable program or functions for making it.
                                  > So I make GP system to find it and make the program that gives
                                  > solutions according to my fitness function.
                                  > So in the end GP give me solutions in the shape of some kind of
                                  > program codes that combine my defined functions and terminals.
                                  > So I use the output of GP,the program solutions for my problem.
                                  >







                                  2.What about GP in game playing strategy for example in chess game?
                                  > Can somebody explain about this?
                                  > I wonder how to implement GP in a game because we can't wait for too
                                  > long just for waiting the computer done making the calculation for
                                  > the next move,right? Coz GP (and also GA) are known for its long time
                                  > for doing a fitness evaluation. Or do I wrong,pls correct me? Or if
                                  > anyone in this mailing list have been made it,pls share your
                                  > experiences. To be honest, i kinda interested in implementing GP in a
                                  > game playing strategy.:)
                                  >
                                  > Thx for ur time and your kindness for replying me. :)
                                  >
                                  > Regards,
                                  >
                                  > Agus Iskandar
                                  >
                                  >
                                  >


                                  [Non-text portions of this message have been removed]
                                • Agus Iskandar
                                  First of all i want to make an apologize because i am sending two similar reply to the mailing list because the first mail i sent,i thought it was failed so i
                                  Message 16 of 19 , Nov 8, 2006
                                  • 0 Attachment
                                    First of all i want to make an apologize because i am sending two
                                    similar reply to the mailing list because the first mail i sent,i
                                    thought it was failed so i send a new one.

                                    Thanks Mr.Adil Raja for your reply.
                                    To be honest when using GP in symbolic regression or like the one
                                    example you give me or in this one book about GP that i read, i
                                    understand about the concept of GP but when i try to think how to
                                    implement GP in other field, i am getting a little confused or maybe
                                    it is me who must learn more about GP :p

                                    And about Deep Blue, Yeah i have read about that also but thx for your
                                    clearer explanation.
                                    And it is true that what you said about implement GP in chess game
                                    playing but i have read that you can also implement GP in chess
                                    endgame. So the search space is not as great when you implement GP in
                                    chess game from the start. But still, it need a lot of work to do.

                                    Now i have some question again :
                                    1.Is GP an online or offline Machine Learning system?
                                    According my opinion GP is an offline ML system but i am not sure.

                                    2.Have anyone replace a system that using GA with GP? Can you give me
                                    the link of the article which make that?

                                    Regards,

                                    Agus Iskandar
                                  • Adil Raja
                                    Agus, I hope that u r fine and in the best of health. Here u go with the comments: 1.Is GP an online or offline Machine Learning system? According my opinion
                                    Message 17 of 19 , Nov 9, 2006
                                    • 0 Attachment
                                      Agus,
                                      I hope that u r fine and in the best of health. Here u go with the
                                      comments:

                                      1.Is GP an online or offline Machine Learning system?
                                      According my opinion GP is an offline ML system but i am not sure.

                                      This is a very nice question. But this also confuses sometimes and a clear
                                      distinction has to be made as to what doe one mean by the term "on-line".
                                      There are two notions around this term.

                                      1) Given the training data an ML evolves as it sees any new training sample
                                      (i.e. input/output n-tuple for instance). This happen in Neural networks for
                                      instance, as proposed by Mitchell in his very nice book known as "Machine
                                      Learning" (McGraw Hill). So the online gradient descent algorithm adapts the
                                      weights (the coefficients) of the network as it sees a new training example
                                      (as opposed to the whole training data which is the case with off-line
                                      training). Now the question is that whether GP would do such a thing? That
                                      given a single training data it would evolve new individuals (i.e. conduct
                                      crossover and mutation to form new individuals). Before answering this
                                      question another question has to be answered: Can GP afford to do this type
                                      of on-line training? This type of online training definitely helps in making
                                      gradient descent faster since the error start skiing down the slope quickly.
                                      In GP this means that u are making the evolutionary process much more
                                      compute intensive: u are going though the cumbersome process of reproduction
                                      once every training sample as opposed to once the whole training data has
                                      been seen. However, this type of on-line training has been used with GP for
                                      tuning the the parameters of the evolving model using gradient descent.
                                      Please follow the link to the paper "Applying Online Gradient Descent Search
                                      to Genetic Programming for Object Recognition" to read the scheme presented
                                      therein by Will Smart and Mengjie Zhang. It seems that these guys are quite
                                      adroit at integrating gradient descent with GP. I have now read a couple of
                                      papers by these guys and I do like their work.

                                      The Link: http://crpit.com/confpapers/CRPITV32Smart.pdf

                                      2) The second notion around on-line learning, well I shall also call it
                                      laypersons notion since it is my own terminology. But I do believe that the
                                      notion exists and is well established. It is just that it might have a
                                      different name. So the notion is, that once u have trained your ML model and
                                      that u have deployed it in actual real-life scenario, then how would you
                                      adapt the model to any (radical) changes of the system. In my view it can be
                                      done in two ways with GP. First off, u append the new input/output
                                      n-tuple(s) to the already existing data. Then the first option is to train
                                      the wole GP from the scratch. The other option could be to use the new data
                                      to start the evolution from where it was previously stopped. i.e. where ur
                                      GP run ended. However, there could be more subtleties which I don't know of.
                                      In that case you can I would be grateful to anyone on the mailing list to
                                      help refine our (your's and mine) concepts and views.


                                      2.Have anyone replace a system that using GA with GP? Can you give me
                                      the link of the article which make that?

                                      I am not sure of this as I am not into GAs. But GAs and GP still do
                                      different types of works in some ways. For instance, from my previous mail.
                                      It would be good to find a mathematical model using GP. With GA u can find
                                      the right vales of coefficients of this model.

                                      On 11/8/06, Agus Iskandar <isk_gust@...> wrote:
                                      >
                                      > First of all i want to make an apologize because i am sending two
                                      > similar reply to the mailing list because the first mail i sent,i
                                      > thought it was failed so i send a new one.
                                      >
                                      > Thanks Mr.Adil Raja for your reply.
                                      > To be honest when using GP in symbolic regression or like the one
                                      > example you give me or in this one book about GP that i read, i
                                      > understand about the concept of GP but when i try to think how to
                                      > implement GP in other field, i am getting a little confused or maybe
                                      > it is me who must learn more about GP :p
                                      >
                                      > And about Deep Blue, Yeah i have read about that also but thx for your
                                      > clearer explanation.
                                      > And it is true that what you said about implement GP in chess game
                                      > playing but i have read that you can also implement GP in chess
                                      > endgame. So the search space is not as great when you implement GP in
                                      > chess game from the start. But still, it need a lot of work to do.
                                      >
                                      > Now i have some question again :
                                      > 1.Is GP an online or offline Machine Learning system?
                                      > According my opinion GP is an offline ML system but i am not sure.
                                      >
                                      > 2.Have anyone replace a system that using GA with GP? Can you give me
                                      > the link of the article which make that?
                                      >
                                      > Regards,
                                      >
                                      > Agus Iskandar
                                      >
                                      >
                                      >


                                      [Non-text portions of this message have been removed]
                                    • David vun Kannon
                                      Agus, I ve made the suggestion (many years ago on this list) that GP could be used to try to create the evaluation function that scores board positions. If GP
                                      Message 18 of 19 , Nov 9, 2006
                                      • 0 Attachment
                                        Agus,

                                        I've made the suggestion (many years ago on this list) that GP could be used
                                        to try to create the evaluation function that scores board positions. If GP
                                        is used to do this, then the clock time used to evaluate each member of the
                                        population does not have to be excessive.

                                        You could use a book of positions that have already been scored via another
                                        algorithm or by humans as one way to calculate fitness (how close is the
                                        individual's output score for that position to the precalculated score,
                                        summed over all positions in the book). Once you have some reasonable
                                        scoring functions in the population, you could switch to playing complete
                                        games with one side using one function and the other side using another. You
                                        can apply these ideas to just the end game, if desired.

                                        Of course, this leads to a question of what are the best functions and
                                        terminals to use to create a board evaluation function. Terminals might be
                                        the set of pieces and the set of locations (a1..h8), functions might be
                                        attacks(x, y), defends(x, y), exists(x), occupied(x), and combinatorics and,
                                        or, not. (Just speculating here, I'm not a chess eval function expert by any
                                        means!)

                                        I wouldn't try to force a GP system to re-invent the whole framework of game
                                        trees with alpha-beta pruning etc.

                                        Cheers,
                                        David vun Kannon

                                        >From: "Agus Iskandar" <isk_gust@...>
                                        >Reply-To: genetic_programming@yahoogroups.com
                                        >To: genetic_programming@yahoogroups.com
                                        >Subject: [GP] Re: Question About GP
                                        >Date: Mon, 30 Oct 2006 10:08:48 -0000
                                        >
                                        >Thx Mr. Langdon and Mr. Martin for the answers.
                                        >It really help a lot for me to make a clear view about GP.
                                        >
                                        >But I have a question again:
                                        >1.Can i have a summary about GP like this?
                                        >
                                        >I want to know the solutions of some kind of problems and i dont
                                        >know the suitable program or functions for making it.
                                        >So I make GP system to find it and make the program that gives
                                        >solutions according to my fitness function.
                                        >So in the end GP give me solutions in the shape of some kind of
                                        >program codes that combine my defined functions and terminals.
                                        >So I use the output of GP,the program solutions for my problem.
                                        >
                                        >2.What about GP in game playing strategy for example in chess game?
                                        >Can somebody explain about this?
                                        >I wonder how to implement GP in a game because we can't wait for too
                                        >long just for waiting the computer done making the calculation for
                                        >the next move,right? Coz GP (and also GA) are known for its long time
                                        >for doing a fitness evaluation. Or do I wrong,pls correct me? Or if
                                        >anyone in this mailing list have been made it,pls share your
                                        >experiences. To be honest, i kinda interested in implementing GP in a
                                        >game playing strategy.:)
                                        >
                                        >Thx for ur time and your kindness for replying me. :)
                                        >
                                        >Regards,
                                        >
                                        >Agus Iskandar
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >
                                        >Yahoo! Groups Links
                                        >
                                        >
                                        >
                                        >
                                      • R. Muhammad Atif Azad
                                        I agree with the notion that it would have more merit to not to use GP from scratch. Alternatively a step wise approach may be used such as introduced by Ryan
                                        Message 19 of 19 , Nov 9, 2006
                                        • 0 Attachment
                                          I agree with the notion that it would have more merit to not to use GP
                                          from scratch. Alternatively a step wise approach may be used such as
                                          introduced by Ryan et. al. [1] termed Run Transferrable Libraries. The
                                          purpose
                                          behind such approach is to transfer the knowledge gained in one run over
                                          to the next. This knowledge is encapsulated in the form of libraries of
                                          functions instead of the simplistic approach of seeding the next
                                          population with the selected individuals of the previous runs.

                                          They have shown it to work on a selection of problem domains and not just
                                          the problems.

                                          [1] look for run transferrable libraries at GP bibliography.

                                          This can have implications because a recently published article in
                                          Scientific American tried to look into what makes a Grand Master with an
                                          ambitious title "how to become a genius" or something along those lines.
                                          According to the research shown there, the same old adage of working hard
                                          remains the key to become extra ordinary in a domain - especially chess.
                                          The study showed that the grand masters do not look at the intricacies of
                                          the game but they are great at finding patterns in the game which are
                                          instantaneously matched with the corresponding successful game plans that
                                          they have tried and experienced before. This was demonstrated in a game
                                          between a Grand master vs about 15/30 novices at the same time. He was
                                          standing in the middle while they were all sitting around and he would
                                          circle around to play with all of them.

                                          I think GP can utilise such an approach. Initially, the library can come
                                          from a knowledge base and can be improved upon over time.

                                          ==

                                          As far as the online learning with GP is concerned, systems that deal with
                                          dynamically changing environments will be useful. Grad Descent can work
                                          well as a local search algorith with GP - but it would do only so much
                                          with an already converged system.

                                          Higher order genomes and work done by the likes of O'Neill and Brabazon
                                          has shown that Grammatical Evolution with the dynamically evolving
                                          grammars can be useful.

                                          Implementing it in real time would have issues specific to the problem
                                          environment and demands. These will determine paramters such as population
                                          sizes, the interval of introduction of new data - and such things may
                                          have a huge bearing on the results. Time permitting you can re-run the
                                          system from scratch but then it won't be termed online introduction of new
                                          data - it would be a typical offline GP run.

                                          Atif



                                          On Thu, 9 Nov 2006, David vun Kannon wrote:

                                          > Agus,
                                          >
                                          > I've made the suggestion (many years ago on this list) that GP could be used
                                          > to try to create the evaluation function that scores board positions. If GP
                                          > is used to do this, then the clock time used to evaluate each member of the
                                          > population does not have to be excessive.
                                          >
                                          > You could use a book of positions that have already been scored via another
                                          > algorithm or by humans as one way to calculate fitness (how close is the
                                          > individual's output score for that position to the precalculated score,
                                          > summed over all positions in the book). Once you have some reasonable
                                          > scoring functions in the population, you could switch to playing complete
                                          > games with one side using one function and the other side using another. You
                                          > can apply these ideas to just the end game, if desired.
                                          >
                                          > Of course, this leads to a question of what are the best functions and
                                          > terminals to use to create a board evaluation function. Terminals might be
                                          > the set of pieces and the set of locations (a1..h8), functions might be
                                          > attacks(x, y), defends(x, y), exists(x), occupied(x), and combinatorics and,
                                          > or, not. (Just speculating here, I'm not a chess eval function expert by any
                                          > means!)
                                          >
                                          > I wouldn't try to force a GP system to re-invent the whole framework of game
                                          > trees with alpha-beta pruning etc.
                                          >
                                          > Cheers,
                                          > David vun Kannon
                                          >
                                          >> From: "Agus Iskandar" <isk_gust@...>
                                          >> Reply-To: genetic_programming@yahoogroups.com
                                          >> To: genetic_programming@yahoogroups.com
                                          >> Subject: [GP] Re: Question About GP
                                          >> Date: Mon, 30 Oct 2006 10:08:48 -0000
                                          >>
                                          >> Thx Mr. Langdon and Mr. Martin for the answers.
                                          >> It really help a lot for me to make a clear view about GP.
                                          >>
                                          >> But I have a question again:
                                          >> 1.Can i have a summary about GP like this?
                                          >>
                                          >> I want to know the solutions of some kind of problems and i dont
                                          >> know the suitable program or functions for making it.
                                          >> So I make GP system to find it and make the program that gives
                                          >> solutions according to my fitness function.
                                          >> So in the end GP give me solutions in the shape of some kind of
                                          >> program codes that combine my defined functions and terminals.
                                          >> So I use the output of GP,the program solutions for my problem.
                                          >>
                                          >> 2.What about GP in game playing strategy for example in chess game?
                                          >> Can somebody explain about this?
                                          >> I wonder how to implement GP in a game because we can't wait for too
                                          >> long just for waiting the computer done making the calculation for
                                          >> the next move,right? Coz GP (and also GA) are known for its long time
                                          >> for doing a fitness evaluation. Or do I wrong,pls correct me? Or if
                                          >> anyone in this mailing list have been made it,pls share your
                                          >> experiences. To be honest, i kinda interested in implementing GP in a
                                          >> game playing strategy.:)
                                          >>
                                          >> Thx for ur time and your kindness for replying me. :)
                                          >>
                                          >> Regards,
                                          >>
                                          >> Agus Iskandar
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >>
                                          >> Yahoo! Groups Links
                                          >>
                                          >>
                                          >>
                                          >>
                                          >
                                          >
                                          >
                                        Your message has been successfully submitted and would be delivered to recipients shortly.