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

Re: [GP] Re: Question About GP

Expand Messages
  • 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 1 of 19 , Oct 23, 2006
      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 2 of 19 , Oct 23, 2006
        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 3 of 19 , Oct 30, 2006
          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 4 of 19 , Oct 31, 2006
            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 5 of 19 , Nov 5, 2006
              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 6 of 19 , Nov 8, 2006
                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 7 of 19 , Nov 9, 2006
                  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 8 of 19 , Nov 9, 2006
                    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 9 of 19 , Nov 9, 2006
                      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.