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

Types of mutation?

Expand Messages
  • Ian Badcoe
    Hi, How many types of mutation have people generally considered? I ask because I ve already got six, and there s three more I really think I should have... I m
    Message 1 of 21 , Jan 27, 2004
      Hi,
      How many types of mutation have people generally considered?

      I ask because I've already got six, and there's three more I really think
      I should have...

      I'm considering cross-over as a special class of mutation for this. It's
      not a hard philosophical position, it's just handy for terminology.

      Also, in a typed system, some of these mutations (marked *) can be
      imagined as having type-changing and type-preserving alternatives --
      obviously the former might always fail in some contexts...

      OK, these are the types I have:

      Delete : A(BCD) -> A(BD)
      Duplicate : A(BCD) -> A(BCCD)
      Insert(*) : A(BCD) -> A(BCXD) (this does crossover if X is from a
      different parent)
      Substitute(*) : A(BCD) -> A(BXD) (this does crossover if X is from a
      different parent)
      ConstChange : A(1) -> A(2) (I know many implementations don't create new
      constants, but I do...)
      Reorder : A(BCD) -> A(BDC)

      And the three types I think I should add are:

      SubstituteNew : A(BCD) -> A(BQD) (where Q is a new random subtree, not
      from any parent)
      Wrap : A(BCD) -> A(BX(C)D) (X must have an arity of 1 and not change the
      type (e.g. negate, sin, not, ...))
      Unwrap : A(B) -> B

      I know this may an unusual different view of mutation, and I could spout a
      lot of hand-waving theory, but I'll wait and see if anybody comments.

      Ian Badcoe
      Free transport into the future - while you wait.
    • Tim Gordon
      ... I seem to remember that this idea was discussed in : W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone. Genetic Programming: An Introduction. Morgan
      Message 2 of 21 , Jan 27, 2004
        > I'm considering cross-over as a special class of mutation for this. It's
        > not a hard philosophical position, it's just handy for terminology.

        I seem to remember that this idea was discussed in :

        W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone. Genetic
        Programming: An Introduction. Morgan Kaufmann, Inc., San Francisco, USA,
        1998.
      • Bill LANGDON
        ... Genetic Programming and Data Structures http://www.amazon.com/exec/obidos/ASIN/0792381351/qid%3D916137667/sr%3D1-8/104-4357421-7447951 includes a survey
        Message 3 of 21 , Jan 27, 2004
          > Hi,
          > How many types of mutation have people generally considered?

          "Genetic Programming and Data Structures"

          http://www.amazon.com/exec/obidos/ASIN/0792381351/qid%3D916137667/sr%3D1-8/104-4357421-7447951

          includes a survey of published mutation operators.


          Bill

          W. B. Langdon, Phone +44 20 7679 4436
          Computer Science, Fax +44 20 7387 1397
          University College, London,
          Gower Street,
          London, WC1E 6BT, UK
          http://www.cs.ucl.ac.uk/staff/W.Langdon

          Foundations of Genetic Programming
          http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP
          EuroGP Portugal 5-7 April 2004 http://www.evonet.info/eurogp2004/
          GECCO Seattle 26-30 June 2004 http://www.isgec.org/
          GP Bibliography http://www.cs.bham.ac.uk/~wbl/biblio/
        • Ian Badcoe
          ... Hi, Thanks for the info, but unfortunately £113 is a little more than I was thinking of spending on a casual enquiry. Can you not persuade the publisher
          Message 4 of 21 , Jan 27, 2004
            At 12:50 27/01/2004 +0000, you wrote:
            >"Genetic Programming and Data Structures"
            >
            >http://www.amazon.com/exec/obidos/ASIN/0792381351/qid%3D916137667/sr%3D1-8/104-4357421-7447951

            Hi,
            Thanks for the info, but unfortunately £113 is a little more than
            I was thinking of spending on a casual enquiry.

            Can you not persuade the publisher that a paperback would be
            useful? :-)

            Ian Badcoe


            Free transport into the future - while you wait.
          • Martin C. Martin
            ... What about a trip to the library? - Martin
            Message 5 of 21 , Jan 27, 2004
              Ian Badcoe wrote:

              > At 12:50 27/01/2004 +0000, you wrote:
              >
              > Thanks for the info, but unfortunately £113 is a little more than
              > I was thinking of spending on a casual enquiry.

              What about a trip to the library?

              - Martin
            • Ian Badcoe
              ... Not everybody works in an University... Now, I could get on to my friends at the local University and put an afternoon aside to go over there and read the
              Message 6 of 21 , Jan 27, 2004
                At 09:41 27/01/2004 -0500, you wrote:
                >Ian Badcoe wrote:
                >
                > > At 12:50 27/01/2004 +0000, you wrote:
                > >
                > > Thanks for the info, but unfortunately £113 is a little more than
                > > I was thinking of spending on a casual enquiry.
                >
                >What about a trip to the library?

                Not everybody works in an University...

                Now, I could get on to my friends at the local University and put an
                afternoon aside to go over there and read the relevant chapters, but what I
                was really hoping for here was some interesting discussion, personal
                opinions, gut-feelings and nice wild speculation...

                >- Martin

                Ian Badcoe


                Free transport into the future - while you wait.
              • Luis Felipe Strano Moraes
                ... I think types of mutation just suck. :) --lf
                Message 7 of 21 , Jan 27, 2004
                  On Tue, Jan 27, 2004 at 02:56:36PM +0000, Ian Badcoe wrote:
                  > At 09:41 27/01/2004 -0500, you wrote:
                  > >Ian Badcoe wrote:
                  > >
                  > > > At 12:50 27/01/2004 +0000, you wrote:
                  > > >
                  > > > Thanks for the info, but unfortunately £113 is a little more than
                  > > > I was thinking of spending on a casual enquiry.
                  > >
                  > >What about a trip to the library?
                  >
                  > Not everybody works in an University...
                  >
                  > Now, I could get on to my friends at the local University and put an
                  > afternoon aside to go over there and read the relevant chapters, but what I
                  > was really hoping for here was some interesting discussion, personal
                  > opinions, gut-feelings and nice wild speculation...
                  I think types of mutation just suck. :)

                  --lf

                  >
                  > >- Martin
                  >
                  > Ian Badcoe
                  >
                  >
                  > Free transport into the future - while you wait.
                  >
                  >
                  >
                  >
                  >
                  > Yahoo! Groups Links
                  >
                  > To visit your group on the web, go to:
                  > http://groups.yahoo.com/group/genetic_programming/
                  >
                  > To unsubscribe from this group, send an email to:
                  > genetic_programming-unsubscribe@yahoogroups.com
                  >
                  > Your use of Yahoo! Groups is subject to:
                  > http://docs.yahoo.com/info/terms/
                  >
                • Ian Badcoe
                  ... Free transport into the future - while you wait.
                  Message 8 of 21 , Jan 27, 2004
                    > > was really hoping for here was some interesting discussion, personal
                    > > opinions, gut-feelings and nice wild speculation...
                    >I think types of mutation just suck. :)

                    :) first time a post here made me laugh!


                    Free transport into the future - while you wait.
                  • Martin Sewell
                    ... That s a bit harsh, almost half the staff and even some of the students do. Cheers Martin ;-)
                    Message 9 of 21 , Jan 27, 2004
                      At 14:56 27/01/2004 +0000, Ian Badcoe wrote:
                      >Not everybody works in an University...
                      >
                      >[...]

                      That's a bit harsh, almost half the staff and even some of the students do.

                      Cheers

                      Martin ;-)
                    • Lucas, Simon M
                      ... Not sure what you mean by this. In many cases a random mutation hill-climber performs as well as or better than a more complex GA that uses crossover - see
                      Message 10 of 21 , Jan 27, 2004
                        Re:

                        >> I think types of mutation just suck. :)
                        >>
                        >> --lf

                        Not sure what you mean by this.

                        In many cases a random mutation hill-climber
                        performs as well as or better than a
                        more complex GA that uses crossover -
                        see for example:

                        @INCOLLECTION{Mitchell1994,
                        AUTHOR = "Mitchell, M. and Holland, J. and Forrest, S.",
                        EDITOR = "Cowan, J. and Tesauro, G. and Alspector, J.",
                        TITLE = "When Will a Genetic Algorithm Outperform Hill Climbing?",
                        BOOKTITLE = "Advances in Neural Information Processing Systems 6",
                        YEAR = "1994",
                        PAGES = "51 -- 58",
                        PUBLISHER = "Morgan Kaufman",
                        ADDRESS = "San Mateo, CA"}
                        (paper available from citeseer, I think)

                        Random mutation hill-climbers are easier to analyse than GAs,
                        and on some problems benefit enormously from careful
                        design of the variation (mutation) operator -
                        note the use of 2-opt (and others) with the TSP
                        for example.

                        It sometimes seems like a near religious belief
                        of the GP community that recombination is
                        wonderful. I'd be interested to know of your
                        favourite papers showing clear cases of crossover
                        outperforming random mutation hill climbers.

                        Note that although an RMHC is a simple algorithm,
                        there is still some skill in applying it successfully -
                        and so if more effort goes in to tuning the GA than the
                        RMHC, you can get misleading results. One common
                        mistake is to run the hill-climber without restarts -
                        in which case it can easily get stuck and perform poorly.

                        Cheers,

                        Simon Lucas


                        --------------------------------------------------
                        Dr. Simon Lucas
                        Department of Computer Science
                        University of Essex
                        Colchester CO4 3SQ
                        United Kingdom
                        Email: sml@...
                        http://cswww.essex.ac.uk/staff/lucas/lucas.htm
                        --------------------------------------------------



                        -----Original Message-----
                        From: Luis Felipe Strano Moraes [mailto:ra016681@...]
                        Sent: 27 January 2004 15:00
                        To: genetic_programming@yahoogroups.com


                        Subject: Re: [GP] Types of mutation?


                        On Tue, Jan 27, 2004 at 02:56:36PM +0000, Ian Badcoe wrote:
                        > At 09:41 27/01/2004 -0500, you wrote:
                        > >Ian Badcoe wrote:
                        > >
                        > > > At 12:50 27/01/2004 +0000, you wrote:
                        > > >
                        > > > Thanks for the info, but unfortunately £113 is a little more than
                        > > > I was thinking of spending on a casual enquiry.
                        > >
                        > >What about a trip to the library?
                        >
                        > Not everybody works in an University...
                        >
                        > Now, I could get on to my friends at the local University and put an
                        > afternoon aside to go over there and read the relevant chapters, but what I
                        > was really hoping for here was some interesting discussion, personal
                        > opinions, gut-feelings and nice wild speculation...
                        I think types of mutation just suck. :)

                        --lf

                        >
                        > >- Martin
                        >
                        > Ian Badcoe
                        >
                        >
                        > Free transport into the future - while you wait.
                        >
                        >
                        >
                        >
                        >
                        > Yahoo! Groups Links
                        >
                        > To visit your group on the web, go to:
                        > http://groups.yahoo.com/group/genetic_programming/
                        >
                        > To unsubscribe from this group, send an email to:
                        > genetic_programming-unsubscribe@yahoogroups.com
                        >
                        > Your use of Yahoo! Groups is subject to:
                        > http://docs.yahoo.com/info/terms/
                        >



                        Yahoo! Groups Links

                        To visit your group on the web, go to:
                        http://groups.yahoo.com/group/genetic_programming/

                        To unsubscribe from this group, send an email to:
                        genetic_programming-unsubscribe@yahoogroups.com

                        Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
                      • Bill LANGDON
                        ... Dear Ian, From colleagues in industry I know that Genetic Programming and Data Structures is also available via non-academic libraries. Bill
                        Message 11 of 21 , Jan 27, 2004
                          > > >What about a trip to the library?
                          > >
                          > > Not everybody works in an University...

                          Dear Ian,
                          From colleagues in industry I know that
                          "Genetic Programming and Data Structures" is also available via
                          non-academic libraries.

                          Bill
                        • Lucas, Simon M
                          ... Not sure what you mean by this. In many cases a random mutation hill-climber performs as well as or better than a more complex GA that uses crossover - see
                          Message 12 of 21 , Jan 27, 2004
                            Re:

                            >> I think types of mutation just suck. :)
                            >>
                            >> --lf

                            Not sure what you mean by this.

                            In many cases a random mutation hill-climber
                            performs as well as or better than a
                            more complex GA that uses crossover -
                            see for example:

                            @INCOLLECTION{Mitchell1994,
                            AUTHOR = "Mitchell, M. and Holland, J. and Forrest, S.",
                            EDITOR = "Cowan, J. and Tesauro, G. and Alspector, J.",
                            TITLE = "When Will a Genetic Algorithm Outperform Hill Climbing?",
                            BOOKTITLE = "Advances in Neural Information Processing Systems 6",
                            YEAR = "1994",
                            PAGES = "51 -- 58",
                            PUBLISHER = "Morgan Kaufman",
                            ADDRESS = "San Mateo, CA"}
                            (paper available from citeseer, I think)

                            Random mutation hill-climbers are easier to
                            analyse than GAs, and on some problems benefit
                            enormously from careful design of the variation
                            (mutation) operator - note the use of 2-opt
                            (and others) with the TSP for example.

                            It sometimes seems like a near religious belief
                            of the GP community that recombination is
                            wonderful. I'd be interested to know of your
                            favourite papers showing clear cases of crossover
                            outperforming random mutation hill climbers.

                            Note that although an RMHC is a simple algorithm,
                            there is still some skill in applying it successfully -
                            and so if more effort goes in to tuning the GA than the
                            RMHC, you can get misleading results. One common
                            mistake is to run the hill-climber without restarts -
                            in which case it can easily get stuck and perform poorly.

                            Cheers,

                            Simon Lucas


                            --------------------------------------------------
                            Dr. Simon Lucas
                            Department of Computer Science
                            University of Essex
                            Colchester CO4 3SQ
                            United Kingdom
                            Email: sml@... http://cswww.essex.ac.uk/staff/lucas/lucas.htm
                            --------------------------------------------------



                            -----Original Message-----
                            From: Luis Felipe Strano Moraes [mailto:ra016681@...]
                            Sent: 27 January 2004 15:00
                            To: genetic_programming@yahoogroups.com


                            Subject: Re: [GP] Types of mutation?


                            On Tue, Jan 27, 2004 at 02:56:36PM +0000, Ian Badcoe wrote:
                            > At 09:41 27/01/2004 -0500, you wrote:
                            > >Ian Badcoe wrote:
                            > >
                            > > > At 12:50 27/01/2004 +0000, you wrote:
                            > > >
                            > > > Thanks for the info, but unfortunately £113 is a little
                            > > > more than I was thinking of spending on a casual enquiry.
                            > >
                            > >What about a trip to the library?
                            >
                            > Not everybody works in an University...
                            >
                            > Now, I could get on to my friends at the local University and put an
                            > afternoon aside to go over there and read the relevant chapters, but what I
                            > was really hoping for here was some interesting discussion, personal
                            > opinions, gut-feelings and nice wild speculation...
                            I think types of mutation just suck. :)

                            --lf

                            >
                            > >- Martin
                            >
                            > Ian Badcoe
                            >
                            >
                            > Free transport into the future - while you wait.
                            >
                            >
                            >
                            >
                            >
                            > Yahoo! Groups Links
                            >
                            > To visit your group on the web, go to:
                            > http://groups.yahoo.com/group/genetic_programming/
                            >
                            > To unsubscribe from this group, send an email to:
                            > genetic_programming-unsubscribe@yahoogroups.com
                            >
                            > Your use of Yahoo! Groups is subject to:
                            > http://docs.yahoo.com/info/terms/
                            >
                          • Mats Andrén
                            ... I find it a bit unclear what kind of feedback to give on your original post. After all, the number of possible transformations that could in some way or
                            Message 13 of 21 , Jan 27, 2004
                              >but what I
                              >was really hoping for here was some interesting discussion, personal
                              >opinions, gut-feelings and nice wild speculation...

                              I find it a bit unclear what kind of feedback to give on your original
                              post. After all, the number of possible transformations that could in some
                              way or another loosely be called "mutation" is a very large. One could
                              easily think of many more than those that you list. Is this a question
                              weather having lots of operators is better than having just a few? Or is it
                              a question if some of these operators are somehow better than others in
                              general? Is it even a question at all? :)

                              /Mats Andrén, Linköping, Sweden
                            • Son Duong Truong
                              Hi Ian, I am studying with some kind of (should I say) conditional mutation inwhich mutating one gene may lead to the change of other genes. A small example
                              Message 14 of 21 , Jan 27, 2004
                                Hi Ian,
                                 
                                I am studying with some kind of (should I say) "conditional mutation" inwhich mutating one gene may lead to the change of other genes. A small example may be in the Travel sale man problem with the conditions that all cities has been only visitted once. I wonder if we may consider it a type of mutation? I think, whatever we define the mutation, provided that it serves as a chance of randomly pick in the search space, then it ensures the principle of GA.
                                 
                                By the way, Is there anyone can tell me the backward of "conditional mutation"? I might recognize that it may take longer time depended on the situation.
                                 
                                Thanks and regards,
                                 
                                Duong Truong Son
                                Meng student.
                                Civil Engineering Department
                                National University of Singapore
                                http://www.nus.edu.sg

                                Ian Badcoe <ian_badcoe@...> wrote:
                                Hi,
                                      How many types of mutation have people generally considered?

                                      I ask because I've already got six, and there's three more I really think
                                I should have...

                                      I'm considering cross-over as a special class of mutation for this.  It's
                                not a hard philosophical position, it's just handy for terminology.

                                      Also, in a typed system, some of these mutations (marked *) can be
                                imagined as having type-changing and type-preserving alternatives --
                                obviously the former might always fail in some contexts...

                                      OK, these are the types I have:

                                Delete : A(BCD) -> A(BD)
                                Duplicate : A(BCD) -> A(BCCD)
                                Insert(*) : A(BCD) -> A(BCXD)                  (this does crossover if X is from a
                                different parent)
                                Substitute(*) : A(BCD) -> A(BXD)            (this does crossover if X is from a
                                different parent)
                                ConstChange : A(1) -> A(2)                  (I know many implementations don't create new
                                constants, but I do...)
                                Reorder : A(BCD) -> A(BDC)

                                      And the three types I think I should add are:

                                SubstituteNew : A(BCD) -> A(BQD)            (where Q is a new random subtree, not
                                from any parent)
                                Wrap : A(BCD) -> A(BX(C)D)                  (X must have an arity of 1 and not change the
                                type (e.g. negate, sin, not, ...))
                                Unwrap : A(B) -> B

                                      I know this may an unusual different view of mutation, and I could spout a
                                lot of hand-waving theory, but I'll wait and see if anybody comments.

                                      Ian Badcoe
                                Free transport into the future - while you wait.





                                Yahoo! Groups Links


                                Do you Yahoo!?
                                Yahoo! SiteBuilder - Free web site building tool. Try it!

                              • Ian Badcoe
                                ... I should have explained that in these C etc represent entire sub-trees, not just terminal nodes, and: A(BCD) - A(BXD) Means swapping the whole subtree C
                                Message 15 of 21 , Jan 28, 2004
                                  >Delete : A(BCD) -> A(BD)
                                  >Duplicate : A(BCD) -> A(BCCD)
                                  >Insert(*) : A(BCD) -> A(BCXD) (this does crossover if X
                                  >is from a
                                  >different parent)
                                  >Substitute(*) : A(BCD) -> A(BXD) (this does crossover if X
                                  >is from a
                                  >different parent)
                                  >ConstChange : A(1) -> A(2) (I know many
                                  >implementations don't create new
                                  >constants, but I do...)
                                  >Reorder : A(BCD) -> A(BDC)

                                  I should have explained that in these "C" etc represent entire sub-trees,
                                  not just terminal nodes, and:

                                  A(BCD) -> A(BXD)

                                  Means swapping the whole subtree C for subtree X. You can also have a
                                  point mutation operator:

                                  A(b(C)) -> A(x(C))

                                  Where b and x are single nodes and not subtrees. I didn't try this yet,
                                  however.

                                  Ian B
                                  Free transport into the future - while you wait.
                                • Ian Badcoe
                                  ... Probably I should have asked which types of mutation have people considered? , rather than how many . I expected at least one person to come back with
                                  Message 16 of 21 , Jan 28, 2004
                                    At 23:36 27/01/2004 +0100, you wrote:

                                    > >but what I
                                    > >was really hoping for here was some interesting discussion, personal
                                    > >opinions, gut-feelings and nice wild speculation...
                                    >
                                    >I find it a bit unclear what kind of feedback to give on your original
                                    >post.

                                    Probably I should have asked "which types of mutation have people
                                    considered?", rather than "how many".

                                    I expected at least one person to come back with experiences of having
                                    approached the same problem using different sets of mutation operators. I
                                    expected some comment on how my set compared with other people's sets.

                                    >Is this a question
                                    >weather having lots of operators is better than having just a few?

                                    I am interested in that.

                                    >Or is it
                                    >a question if some of these operators are somehow better than others in
                                    >general?

                                    This also...

                                    >Is it even a question at all? :)

                                    Only if your reply is an answer. :)

                                    It's an invitation to discuss the matter.

                                    - Does adding more mutation operators (increasing the connectivity of the
                                    search-space) help or hinder search speed or success rate?

                                    - Obviously the answer to that depends on which operators -- what makes
                                    operators good? (How much does it depend on other implementation details?)

                                    - Can one suppose that "smart" mutation operators will work "in sympathy"
                                    with the semantics of the tree? e.g. at the simplest level you can respect
                                    any type information you have. Beyond that, "Wrap" seems a sympathetic
                                    change, how often have you negated an expression when editing a program,
                                    its a "sensible" thing to try... Obviously these two examples merely
                                    scratch the surface.

                                    - And I guess then the whole thing also comes back to questions about how
                                    to do crossover and different ways of deciding which piece of "foreign DNA"
                                    to take from a parent...? Although this wasn't the main thrust of my
                                    thought at this time.

                                    Putting it another way, your statements:

                                    > After all, the number of possible transformations that could in some
                                    >way or another loosely be called "mutation" is a very large. One could
                                    >easily think of many more than those that you list.

                                    Are true, and obviously most of them would not be useful. So how do people
                                    choose? What properties make a mutation operation useful?

                                    Did anybody consider having a "superset" of mutation operators, and
                                    dynamically adjusting their probabilities according to how useful they
                                    proved over the last N generations...?

                                    Ian Badcoe

                                    Free transport into the future - while you wait.
                                  • C. Setzkorn
                                    Dear Ian, IMHO sophisticated/complex representation schemes (such as GP’s) require several genetic operators (GOs). However, I don’t think one could
                                    Message 17 of 21 , Jan 28, 2004
                                      Dear Ian,

                                      IMHO sophisticated/complex representation schemes (such as GP’s) require
                                      several genetic operators (GOs). However, I don’t think one could
                                      exhaustively list those operators. I believe that the operators depend
                                      on many things:

                                      - Representation scheme
                                      - Problem domain
                                      - Problem itself (emphasising the fact that they should be adaptable)

                                      Hence each problem requires problem specific GOs.

                                      I am aware of some papers that empirically show that several GOs are
                                      beneficial. I have written a paper where I investigate this issue using
                                      factorial analysis of variance. I could send it to you if you like.

                                      HTH,
                                      Christian
                                    • Ian Badcoe
                                      ... This would certainly be my idea. ... These, I would say are true -- in those cases where your GP is customized to the problem -- but if you wanted your GP
                                      Message 18 of 21 , Jan 28, 2004
                                        At 12:50 28/01/2004 +0000, C. Setzkorn wrote:
                                        >Dear Ian,
                                        >
                                        >IMHO sophisticated/complex representation schemes (such as GP's) require
                                        >several genetic operators (GOs). However, I don't think one could
                                        >exhaustively list those operators. I believe that the operators depend
                                        >on many things:
                                        >
                                        >- Representation scheme

                                        This would certainly be my idea.

                                        >- Problem domain
                                        >- Problem itself (emphasising the fact that they should be adaptable)

                                        These, I would say are true -- in those cases where your GP is customized
                                        to the problem -- but if you wanted your GP to be a more "out of the box"
                                        problem solver, then you want to _define_ these as untrue and abstract the
                                        operators to the point where they had some hope of general
                                        applicability. Like I said, they would still be tuned to the representation...

                                        >Hence each problem requires problem specific GOs.
                                        >
                                        >I am aware of some papers that empirically show that several GOs are
                                        >beneficial. I have written a paper where I investigate this issue using
                                        >factorial analysis of variance. I could send it to you if you like.

                                        Really deep stats may be a little beyond me but yes please.

                                        >HTH,
                                        >Christian

                                        Ian Badcoe

                                        Free transport into the future - while you wait.
                                      • Osman Erol
                                        Hi All, I would first give some comments on the listed 6 mutation types and add another macro-mutation operator I have used in my studies: The first 3 mutation
                                        Message 19 of 21 , Jan 28, 2004

                                          Hi All,

                                           

                                          I would first give some comments on the listed 6 mutation types and add another macro-mutation operator I have used in my studies:

                                           

                                          The first 3 mutation types (eg: delete, duplicate, insert) can be replaced by only one mutation that means all. This can be summarized as :

                                          Delete one node and write instead of this star-closure of the node alphabet. Star closure contains by definition empty character (delete mutation), any node (insertion), same as previous node (special case of insertion – duplication).

                                           

                                          All of the listed mutations are in-chromosome operators. Why not to exagerate its role and modify any chromosome totally. This the generational mutation and replaces one chromosome by another random one. As far as I undestand, random mutation hill climbing uses this technique.

                                           

                                          An important adventage of the crossover over Hill Climbing techniques is that it does not require the derivation information. Even if the system is a black-box and is not modeled, you may carry the crossover.

                                           

                                          Regards,

                                           

                                          Osman

                                           

                                           

                                           

                                           

                                          -----Özgün İleti-----
                                          Kimden: Ian Badcoe [mailto:ian_badcoe@...]
                                          Tarih: 28 Ocak 2004 Çarşamba 15:45
                                          Kime: genetic_programming@yahoogroups.com
                                          Konu: Re: [GP] Types of mutation?

                                           

                                          At 12:50 28/01/2004 +0000, C. Setzkorn wrote:
                                          >Dear Ian,
                                          >
                                          >IMHO sophisticated/complex representation schemes (such as GP's) require
                                          >several genetic operators (GOs). However, I don't think one could
                                          >exhaustively list those operators. I believe that the operators depend
                                          >on many things:
                                          >
                                          >- Representation scheme

                                          This would certainly be my idea.

                                          >- Problem domain
                                          >- Problem itself (emphasising the fact that they should be adaptable)

                                          These, I would say are true -- in those cases where your GP is customized
                                          to the problem -- but if you wanted your GP to be a more "out of the box"
                                          problem solver, then you want to _define_ these as untrue and abstract the
                                          operators to the point where they had some hope of general
                                          applicability.  Like I said, they would still be tuned to the representation...

                                          >Hence each problem requires problem specific GOs.
                                          >
                                          >I am aware of some papers that empirically show that several GOs are
                                          >beneficial. I have written a paper where I investigate this issue using
                                          >factorial analysis of variance. I could send it to you if you like.

                                          Really deep stats may be a little beyond me but yes please.

                                          >HTH,
                                          >Christian

                                                   Ian Badcoe

                                          Free transport into the future - while you wait.



                                          Yahoo! Groups Links

                                          ·         To visit your group on the web, go to:
                                          http://groups.yahoo.com/group/genetic_programming/
                                           

                                          ·         To unsubscribe from this group, send an email to:
                                          genetic_programming-unsubscribe@yahoogroups.com
                                           

                                          ·         Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.

                                        • bobmaccallum@spamcop.net
                                          ... A bit late into the fray as usual (as a casual digest reader) but here s my input for what it s worth. Note that I haven t read everyone s comments in
                                          Message 20 of 21 , Jan 28, 2004
                                            Ian Badcoe writes:
                                            > Probably I should have asked "which types of mutation have people
                                            > considered?", rather than "how many".
                                            >
                                            > I expected at least one person to come back with experiences of having
                                            > approached the same problem using different sets of mutation operators. I
                                            > expected some comment on how my set compared with other people's sets.

                                            A bit late into the fray as usual (as a casual digest reader)
                                            but here's my input for what it's worth. Note that I haven't
                                            read everyone's comments in detail - so sorry if I repeat or
                                            ignore something important.

                                            A few years ago I did an "overexpression study" using my tree-based GP
                                            system. Basically there is one type of "point mutation" (a leaf biased point
                                            mutation) and a bunch of "macro mutation" types which
                                            are usually chosen with equal probability:

                                            * deep point mutation (biased more to internal nodes)
                                            * swap two subtrees
                                            * replace subtree (with random new subtree)
                                            * internal deletion (remove some internal edges of a subtree)
                                            * internal insertion (add some nodes inside a subtree)
                                            * copy subtree (to another node - deleting the subtree that was there)

                                            Oh I guess I'd better give a bit of a plug, because these
                                            operators are described in more detail here...
                                            http://perlgp.org/docs/manual/manual/node17.html
                                            These operators were designed based on my understanding of real genetics
                                            and not much reading of the GP literature.

                                            Anyway, the experiment was to do 30 runs with one of the operators
                                            given roughly 3 times more chance of being picked than usual.
                                            That's 6x30 runs in total for a fixed amount of wallclock time.
                                            The problem/task was some kind of protein secondary structure prediction.
                                            Looking at mean final fitness, the runs with extra deep point mutation, swap
                                            subtrees and copy subtrees did a bit worse. Of course the run with
                                            more internal deletions made smaller programs and completed more
                                            tournaments. There are presumably even more side-effects and interactions
                                            between operators. All six operators in equal proportions gave good
                                            results and I've used that ever since... (Self-adaptation? Tried
                                            it, seemed a bit unstable, should try it again, but you know how things are...)

                                            Didn't publish it of course... :-)
                                            Happy to explain if anything doesn't make sense.

                                            Good to see lots of discussion on the list again.
                                            cheers
                                            Bob.
                                            [ stockholm bioinformatics center ]
                                          • bobmaccallum@spamcop.net
                                            After some off-list discussion with Ian, it became clear that my internal insertion mechanism was a bit unclear - and perhaps is of interest and worth
                                            Message 21 of 21 , Jan 29, 2004
                                              After some off-list discussion with Ian, it became clear that
                                              my "internal insertion" mechanism was a bit unclear - and perhaps
                                              is of interest and worth explaining more.

                                              Ian has already mentioned:
                                              wrap : +(2, 3) -> +(sin(2), 3)
                                              unwrap : sin(3) -> 3

                                              The "internal insertion" is a bit more general, can be applied
                                              between any two nodes of the same type but requires new subtrees
                                              to fill out any unfinished branches:

                                              An example (graphical version below)
                                              Starting with this:
                                              +(-(1, 2), *(3, 4))
                                              Wrap an add around the subtract
                                              +(+(-(1, 2)), *(3, 4))
                                              But this syntactically requires another child to be added to the add, either:
                                              +(?, -(1, 2)) or
                                              +(-(1, 2), ?)
                                              Choose one at random and put a random subtree (e.g. *(x, y)) there
                                              +(+(*(x, y), -(1, 2)), *(3, 4))

                                              + +
                                              / \ -insert-> ___/ \
                                              - * + *
                                              / \ / \ <-delete- / \ / \
                                              1 2 3 4 * | 3 4
                                              / \ |
                                              x y |
                                              -
                                              / \
                                              1 2

                                              This is all assuming fixed arity, note.
                                            Your message has been successfully submitted and would be delivered to recipients shortly.