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

Help about crossover point and permutation. (from newbie)

Expand Messages
  • Son Duong Truong
    Dear sir/madame, I am a newbie in GA programming. It comes to me that I want to apply GA to develop an N-gene binary string by two GA operators: crossover and
    Message 1 of 7 , Jan 2, 2004
    • 0 Attachment
      Dear sir/madame,
       
      I am a newbie in GA programming. It comes to me that I want to apply GA to develop an N-gene binary string by two GA operators: crossover and mutation.
      The binary string has character of one of N. (i.e. only one gene in the string has value of 1, all the others has value of 0)
      Crossover operation can be at 1 point or two points in the string. (the point(s) are fixed at a location/locations of the chromosome)
      Mutation is permutation because all that I want to do is that: first I search the entire chromosome to find the genes with value of 1, change it to 0 and randomly choose another gene to change its value to 1.
       
      My question are those:
      1) How to define and choose the location in the chromosome to operate the crossover operation?
      2) How to operate permutation?
       
      I am greatly appriciated your commends and helps about those problems.

      If possible, recommending some sourse code or further reading related would be extremely of usefulness.

      All my best regards and wishes for the New Year 2004,

      Truong Son


      Do you Yahoo!?
      Find out what made the Top Yahoo! Searches of 2003
    • John Koza
      Truong Son: The primary reason to use a GA (or GP) is that you want to conduct a search over individuals in a search space for which you believe that the
      Message 2 of 7 , Jan 3, 2004
      • 0 Attachment

        Truong Son:

        The primary reason to use a GA (or GP) is that you want to conduct a search over individuals in a search space for which you believe that the substructure of the individuals is such that a better individual will often emerge when the substructures of pretty good individuals are combined. 
         
        In this problem, each individual string has one and only one "1".  Crossover is useless because it either (1) leaves a valid individual unchanged, (2) creates an individual with two 1's that must be repaired (i.e., mutated) back to a valid individual with just one 1, or (3) creates an individual with no 1's that must be repaired back to a valid individual with one 1).  There are apparently no substructures that can be combined (raising the question of why you would want to bother with the GA in the first place).
         
        Mutation is the only useful operation. No matter how you define it, it will convert a string with one 1 to a new string with the single "1" elsewhere. 
         
        It might be helpful to say a little more about the motivation for using the genetic algorithm on this particular problem. 
         
        If I understand the problem, one obvious representation is a chromosome string of length 1 over an alphabet of length L. The single value at the single position says where the 1 is located.  This representation encapsulates all the information contained in any of the mere L possible individuals. For a seach in a space represented by a chromosome of length 1, point mutation on the single point is the only useful operator and hence there is no need to bother with the GA in the first place.
         

        John R. Koza

        Consulting Professor
        Biomedical Informatics
        Department of Medicine
        Medical School Office Building (MC 5479)
        Stanford University
        Stanford, California 94305-5479

        Consulting Professor
        Department of Electrical Engineering
        School of Engineering
        Stanford University

        PREFERRED MAILING ADDRESS:
        Post Office Box K
        Los Altos, CA 94023-4011 USA

        Phone: 650-941-0336
        Fax: 650-941-9430
        E-Mail: koza@...
        WWW Home Page: http://www.smi.stanford.edu/people/koza

        For information about field of genetic programming in general:
        http://www.genetic-programming.org

        For information about Genetic Programming Inc.:
        http://www.genetic-programming.com

        For information about the 2003 book "Genetic Programming IV: Routine Human-Competitive Machine Intelligence", visit http://www.genetic-programming.org/gpbook4toc.html

        For the genetic programming bibliography, visit http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

        For information about the Genetic Programming book series from Kluwer Academic Publishers, visit http://www.genetic-programming.org/gpkluwer.html

        For information about the annual Genetic and Evolutionary Computation Conference (GECCO) (which includes the annual Genetic Programming Conference) to be held in Seattle on June 26-30, 2004 (Saturday - Wednesday), visit http://www.isgec.org/gecco-2004/

        For information about the International Society on Genetic and Evolutionary Computation  visit: http://www.isgec.org/

        For information about the annual Euro-Genetic-Programming Conference to be held in April 5-7, 2004 (Monday-Wednesday) at the University of Coimbra in Coimbra Portugal, visit http://www.evonet.info/eurogp2004/

        For information about the annual NASA/DoD Conference on Evolvable Hardware (EH) in Seattle on June 24-26 (Thursday - Saturday), 2004, visit http://ehw.jpl.nasa.gov/events/nasaeh04/

        For information about the Asia-Pacific Workshop on Genetic Programming (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/

        For information about the Genetic Programming Theory and Practice (GPTP) workshop organized by the Center for the Study of Complex Systems of the University of Michigan, visit http://cscs.umich.edu/calendar/conferences/gptp2003/

        For information about the Genetic Programming and Evolvable Hardware journal published by Kluwer Academic Publishers, visit http://www.kluweronline.com/issn/1389-2576

         
         
         
         
         
         -----Original Message-----
        From: Son Duong Truong [mailto:dts8630146@...]
        Sent: Friday, January 02, 2004 10:08 PM
        To: genetic_programming@yahoogroups.com
        Subject: [GP] Help about crossover point and permutation. (from newbie)

        Dear sir/madame,
         
        I am a newbie in GA programming. It comes to me that I want to apply GA to develop an N-gene binary string by two GA operators: crossover and mutation.
        The binary string has character of one of N. (i.e. only one gene in the string has value of 1, all the others has value of 0)
        Crossover operation can be at 1 point or two points in the string. (the point(s) are fixed at a location/locations of the chromosome)
        Mutation is permutation because all that I want to do is that: first I search the entire chromosome to find the genes with value of 1, change it to 0 and randomly choose another gene to change its value to 1.
         
        My question are those:
        1) How to define and choose the location in the chromosome to operate the crossover operation?
        2) How to operate permutation?
         
        I am greatly appriciated your commends and helps about those problems.

        If possible, recommending some sourse code or further reading related would be extremely of usefulness.

        All my best regards and wishes for the New Year 2004,

        Truong Son


        Do you Yahoo!?
        Find out what made the Top Yahoo! Searches of 2003


        Yahoo! Groups Links

      • walid ahmed
        Dear Dr John Koza is there is any rule that says that substructures combination can lead to a better individual. i have seen alot of applications that used
        Message 3 of 7 , Jan 4, 2004
        • 0 Attachment
          Dear Dr John Koza

          is there is any rule that says that substructures
          combination can lead to a better individual.

          i have seen alot of applications that used crosover
          without declaring y they used ga in the first place.
          may be only because the search space was big . it was
          tempting to use GA.however i think in this case we r
          in jusrt a guided random search .???

          thanks

          Walid
          --- John Koza <koza@...> wrote:
          > Truong Son:
          >
          > The primary reason to use a GA (or GP) is that you
          > want to conduct a search
          > over individuals in a search space for which you
          > believe that the
          > substructure of the individuals is such that a
          > better individual will often
          > emerge when the substructures of pretty good
          > individuals are combined.
          >
          > In this problem, each individual string has one and
          > only one "1". Crossover
          > is useless because it either (1) leaves a valid
          > individual unchanged, (2)
          > creates an individual with two 1's that must be
          > repaired (i.e., mutated)
          > back to a valid individual with just one 1, or (3)
          > creates an individual
          > with no 1's that must be repaired back to a valid
          > individual with one 1).
          > There are apparently no substructures that can be
          > combined (raising the
          > question of why you would want to bother with the GA
          > in the first place).
          >
          > Mutation is the only useful operation. No matter how
          > you define it, it will
          > convert a string with one 1 to a new string with the
          > single "1" elsewhere.
          >
          > It might be helpful to say a little more about the
          > motivation for using the
          > genetic algorithm on this particular problem.
          >
          > If I understand the problem, one obvious
          > representation is a chromosome
          > string of length 1 over an alphabet of length L. The
          > single value at the
          > single position says where the 1 is located. This
          > representation
          > encapsulates all the information contained in any of
          > the mere L possible
          > individuals. For a seach in a space represented by a
          > chromosome of length 1,
          > point mutation on the single point is the only
          > useful operator and hence
          > there is no need to bother with the GA in the first
          > place.
          >
          > John R. Koza
          >
          > Consulting Professor
          > Biomedical Informatics
          > Department of Medicine
          > Medical School Office Building (MC 5479)
          > Stanford University
          > Stanford, California 94305-5479
          >
          > Consulting Professor
          > Department of Electrical Engineering
          > School of Engineering
          > Stanford University
          >
          > PREFERRED MAILING ADDRESS:
          > Post Office Box K
          > Los Altos, CA 94023-4011 USA
          >
          > Phone: 650-941-0336
          > Fax: 650-941-9430
          > E-Mail: koza@...
          > WWW Home Page:
          > http://www.smi.stanford.edu/people/koza
          >
          > For information about field of genetic programming
          > in general:
          > http://www.genetic-programming.org
          >
          > For information about Genetic Programming Inc.:
          > http://www.genetic-programming.com
          >
          > For information about the 2003 book "Genetic
          > Programming IV: Routine
          > Human-Competitive Machine Intelligence", visit
          > http://www.genetic-programming.org/gpbook4toc.html
          >
          > For the genetic programming bibliography, visit
          >
          http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html
          >
          > For information about the Genetic Programming book
          > series from Kluwer
          > Academic Publishers, visit
          > http://www.genetic-programming.org/gpkluwer.html
          >
          > For information about the annual Genetic and
          > Evolutionary Computation
          > Conference (GECCO) (which includes the annual
          > Genetic Programming
          > Conference) to be held in Seattle on June 26-30,
          > 2004 (Saturday -
          > Wednesday), visit http://www.isgec.org/gecco-2004/
          >
          > For information about the International Society on
          > Genetic and Evolutionary
          > Computation visit: http://www.isgec.org/
          >
          > For information about the annual
          > Euro-Genetic-Programming Conference to be
          > held in April 5-7, 2004 (Monday-Wednesday) at the
          > University of Coimbra in
          > Coimbra Portugal, visit
          > http://www.evonet.info/eurogp2004/
          >
          > For information about the annual NASA/DoD Conference
          > on Evolvable Hardware
          > (EH) in Seattle on June 24-26 (Thursday - Saturday),
          > 2004, visit
          > http://ehw.jpl.nasa.gov/events/nasaeh04/
          >
          > For information about the Asia-Pacific Workshop on
          > Genetic Programming
          > (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/
          >
          > For information about the Genetic Programming Theory
          > and Practice (GPTP)
          > workshop organized by the Center for the Study of
          > Complex Systems of the
          > University of Michigan, visit
          > http://cscs.umich.edu/calendar/conferences/gptp2003/
          >
          > For information about the Genetic Programming and
          > Evolvable Hardware journal
          > published by Kluwer Academic Publishers, visit
          > http://www.kluweronline.com/issn/1389-2576
          >
          >
          >
          >
          >
          >
          >
          >
          > -----Original Message-----
          > From: Son Duong Truong [mailto:dts8630146@...]
          > Sent: Friday, January 02, 2004 10:08 PM
          > To: genetic_programming@yahoogroups.com
          > Subject: [GP] Help about crossover point and
          > permutation. (from newbie)
          >
          >
          > Dear sir/madame,
          >
          > I am a newbie in GA programming. It comes to me
          > that I want to apply GA to
          > develop an N-gene binary string by two GA operators:
          > crossover and mutation.
          > The binary string has character of one of N. (i.e.
          > only one gene in the
          > string has value of 1, all the others has value of
          > 0)
          > Crossover operation can be at 1 point or two
          > points in the string. (the
          > point(s) are fixed at a location/locations of the
          > chromosome)
          > Mutation is permutation because all that I want to
          > do is that: first I
          > search the entire chromosome to find the genes with
          > value of 1, change it to
          > 0 and randomly choose another gene to change its
          > value to 1.
          >
          > My question are those:
          > 1) How to define and choose the location in the
          > chromosome to operate the
          > crossover operation?
          > 2) How to operate permutation?
          >
          > I am greatly appriciated your commends and helps
          > about those problems.
          > If possible, recommending some sourse code or
          > further reading related
          > would be extremely of usefulness.
          >
          > All my best regards and wishes for the New Year
          > 2004,
          >
          > Truong Son
          >
          >
          >
          >
          ----------------------------------------------------------------------------
          > --
          > Do you Yahoo!?
          > Find out what made the Top Yahoo! Searches of 2003
          > Yahoo! Groups Sponsor
          > ADVERTISEMENT
          >
          >
          >
          >
          >
          >
          === message truncated ===


          __________________________________
          Do you Yahoo!?
          Find out what made the Top Yahoo! Searches of 2003
          http://search.yahoo.com/top2003
        • Son Duong Truong
          Dear Dr John Koza, Thank you very much for your advice and provided related useful websites. I will definitely have a look at those websites for more details.
          Message 4 of 7 , Jan 4, 2004
          • 0 Attachment
            Dear Dr John Koza,
             
            Thank you very much for your advice and provided related useful websites. I will definitely have a look at those websites for more details.
            Actually, I simplify my allocation problems in the previous email. The typical chromosome will have "m" parts of "1 of N" binary string. And i would like to operate the chromosome(s) right between those parts while the permutation (mutation) expected to be done only in each single part of the typical schomosome.
             
            My problem is that since I am not familiar with genetic programming, so I do not know how to code for the crossover and mutation in such the way that I mentioned above. I've found some source codes for GA by C and C++, that seems to be very helpful. However, I haven't utilisied them yet because I have not had a strong enough background. If you and anyone know about any materials that helps, please kindly recommend me.
             
            Thanks very much and wish you have a nice day,
             
            Yours sincerely,
             
            Truong Son

            John Koza <koza@...> wrote:

            Truong Son:

            The primary reason to use a GA (or GP) is that you want to conduct a search over individuals in a search space for which you believe that the substructure of the individuals is such that a better individual will often emerge when the substructures of pretty good individuals are combined. 
             
            In this problem, each individual string has one and only one "1".  Crossover is useless because it either (1) leaves a valid individual unchanged, (2) creates an individual with two 1's that must be repaired (i.e., mutated) back to a valid individual with just one 1, or (3) creates an individual with no 1's that must be repaired back to a valid individual with one 1).  There are apparently no substructures that can be combined (raising the question of why you would want to bother with the GA in the first place).
             
            Mutation is the only useful operation. No matter how you define it, it will convert a string with one 1 to a new string with the single "1" elsewhere. 
             
            It might be helpful to say a little more about the motivation for using the genetic algorithm on this particular problem. 
             
            If I understand the problem, one obvious representation is a chromosome string of length 1 over an alphabet of length L. The single value at the single position says where the 1 is located.  This representation encapsulates all the information contained in any of the mere L possible individuals. For a seach in a space represented by a chromosome of length 1, point mutation on the single point is the only useful operator and hence there is no need to bother with the GA in the first place.
             

            John R. Koza

            Consulting Professor
            Biomedical Informatics
            Department of Medicine
            Medical School Office Building (MC 5479)
            Stanford University
            Stanford, California 94305-5479

            Consulting Professor
            Department of Electrical Engineering
            School of Engineering
            Stanford University

            PREFERRED MAILING ADDRESS:
            Post Office Box K
            Los Altos, CA 94023-4011 USA

            Phone: 650-941-0336
            Fax: 650-941-9430
            E-Mail: koza@...
            WWW Home Page: http://www.smi.stanford.edu/people/koza

            For information about field of genetic programming in general:
            http://www.genetic-programming.org

            For information about Genetic Programming Inc.:
            http://www.genetic-programming.com

            For information about the 2003 book "Genetic Programming IV: Routine Human-Competitive Machine Intelligence", visit http://www.genetic-programming.org/gpbook4toc.html

            For the genetic programming bibliography, visit http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

            For information about the Genetic Programming book series from Kluwer Academic Publishers, visit http://www.genetic-programming.org/gpkluwer.html

            For information about the annual Genetic and Evolutionary Computation Conference (GECCO) (which includes the annual Genetic Programming Conference) to be held in Seattle on June 26-30, 2004 (Saturday - Wednesday), visit http://www.isgec.org/gecco-2004/

            For information about the International Society on Genetic and Evolutionary Computation  visit: http://www.isgec.org/

            For information about the annual Euro-Genetic-Programming Conference to be held in April 5-7, 2004 (Monday-Wednesday) at the University of Coimbra in Coimbra Portugal, visit http://www.evonet.info/eurogp2004/

            For information about the annual NASA/DoD Conference on Evolvable Hardware (EH) in Seattle on June 24-26 (Thursday - Saturday), 2004, visit http://ehw.jpl.nasa.gov/events/nasaeh04/

            For information about the Asia-Pacific Workshop on Genetic Programming (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/

            For information about the Genetic Programming Theory and Practice (GPTP) workshop organized by the Center for the Study of Complex Systems of the University of Michigan, visit http://cscs.umich.edu/calendar/conferences/gptp2003/

            For information about the Genetic Programming and Evolvable Hardware journal published by Kluwer Academic Publishers, visit http://www.kluweronline.com/issn/1389-2576

             
             
             
             
             
             -----Original Message-----
            From: Son Duong Truong [mailto:dts8630146@...]
            Sent: Friday, January 02, 2004 10:08 PM
            To: genetic_programming@yahoogroups.com
            Subject: [GP] Help about crossover point and permutation. (from newbie)

            Dear sir/madame,
             
            I am a newbie in GA programming. It comes to me that I want to apply GA to develop an N-gene binary string by two GA operators: crossover and mutation.
            The binary string has character of one of N. (i.e. only one gene in the string has value of 1, all the others has value of 0)
            Crossover operation can be at 1 point or two points in the string. (the point(s) are fixed at a location/locations of the chromosome)
            Mutation is permutation because all that I want to do is that: first I search the entire chromosome to find the genes with value of 1, change it to 0 and randomly choose another gene to change its value to 1.
             
            My question are those:
            1) How to define and choose the location in the chromosome to operate the crossover operation?
            2) How to operate permutation?
             
            I am greatly appriciated your commends and helps about those problems.

            If possible, recommending some sourse code or further reading related would be extremely of usefulness.

            All my best regards and wishes for the New Year 2004,

            Truong Son


            Do you Yahoo!?
            Find out what made the Top Yahoo! Searches of 2003


            Yahoo! Groups Links



            Yahoo! Groups Links


            Do you Yahoo!?
            Find out what made the Top Yahoo! Searches of 2003

          • John Koza
            Hello: There is definitely no rule or theorem that says that substructure combination [will] lead to a better individual. If the search space of a particular
            Message 5 of 7 , Jan 4, 2004
            • 0 Attachment
              Hello:

              There is definitely no rule or theorem that says that "substructure
              combination [will] lead to a better individual."

              If the search space of a particular problem is such that there is no
              correlation between the payoff (fitness) and some substructure, GA (or GP)
              is simply not going to solve your problem. A good example is the telephone
              pole sitting at the bottom of a crater. All gradients point away from the
              telephone pole and suggest that you should move along the increasing
              gradient towards the (seemingly high) ground level; however, the global
              optimum point is the top of the telephone poll (which rises well above
              ground level).

              Of course, other search methods are also going to fail on this kind of
              cryptographic "needle in a haystack" problem where there is a total
              disconnect between structure and performance.


              John R. Koza

              Consulting Professor
              Biomedical Informatics
              Department of Medicine
              Medical School Office Building (MC 5479)
              Stanford University
              Stanford, California 94305-5479

              Consulting Professor
              Department of Electrical Engineering
              School of Engineering
              Stanford University

              PREFERRED MAILING ADDRESS:
              Post Office Box K
              Los Altos, CA 94023-4011 USA

              Phone: 650-941-0336
              Fax: 650-941-9430
              E-Mail: koza@...
              WWW Home Page: http://www.smi.stanford.edu/people/koza

              For information about field of genetic programming in general:
              http://www.genetic-programming.org

              For information about Genetic Programming Inc.:
              http://www.genetic-programming.com

              For information about the 2003 book "Genetic Programming IV: Routine
              Human-Competitive Machine Intelligence", visit
              http://www.genetic-programming.org/gpbook4toc.html

              For the genetic programming bibliography, visit
              http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

              For information about the Genetic Programming book series from Kluwer
              Academic Publishers, visit http://www.genetic-programming.org/gpkluwer.html

              For information about the annual Genetic and Evolutionary Computation
              Conference (GECCO) (which includes the annual Genetic Programming
              Conference) to be held in Seattle on June 26-30, 2004 (Saturday -
              Wednesday), visit http://www.isgec.org/gecco-2004/

              For information about the International Society on Genetic and Evolutionary
              Computation visit: http://www.isgec.org/

              For information about the annual Euro-Genetic-Programming Conference to be
              held in April 5-7, 2004 (Monday-Wednesday) at the University of Coimbra in
              Coimbra Portugal, visit http://www.evonet.info/eurogp2004/

              For information about the annual NASA/DoD Conference on Evolvable Hardware
              (EH) in Seattle on June 24-26 (Thursday - Saturday), 2004, visit
              http://ehw.jpl.nasa.gov/events/nasaeh04/

              For information about the Asia-Pacific Workshop on Genetic Programming
              (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/

              For information about the Genetic Programming Theory and Practice (GPTP)
              workshop organized by the Center for the Study of Complex Systems of the
              University of Michigan, visit
              http://cscs.umich.edu/calendar/conferences/gptp2003/

              For information about the Genetic Programming and Evolvable Hardware journal
              published by Kluwer Academic Publishers, visit
              http://www.kluweronline.com/issn/1389-2576









              -----Original Message-----
              From: walid ahmed [mailto:welloma@...]
              Sent: Sunday, January 04, 2004 12:12 AM
              To: genetic_programming@yahoogroups.com
              Subject: RE: [GP] Help about crossover point and permutation. (from
              newbie)


              Dear Dr John Koza

              is there is any rule that says that substructures
              combination can lead to a better individual.

              i have seen alot of applications that used crosover
              without declaring y they used ga in the first place.
              may be only because the search space was big . it was
              tempting to use GA.however i think in this case we r
              in jusrt a guided random search .???

              thanks

              Walid
              --- John Koza <koza@...> wrote:
              > Truong Son:
              >
              > The primary reason to use a GA (or GP) is that you
              > want to conduct a search
              > over individuals in a search space for which you
              > believe that the
              > substructure of the individuals is such that a
              > better individual will often
              > emerge when the substructures of pretty good
              > individuals are combined.
              >
              > In this problem, each individual string has one and
              > only one "1". Crossover
              > is useless because it either (1) leaves a valid
              > individual unchanged, (2)
              > creates an individual with two 1's that must be
              > repaired (i.e., mutated)
              > back to a valid individual with just one 1, or (3)
              > creates an individual
              > with no 1's that must be repaired back to a valid
              > individual with one 1).
              > There are apparently no substructures that can be
              > combined (raising the
              > question of why you would want to bother with the GA
              > in the first place).
              >
              > Mutation is the only useful operation. No matter how
              > you define it, it will
              > convert a string with one 1 to a new string with the
              > single "1" elsewhere.
              >
              > It might be helpful to say a little more about the
              > motivation for using the
              > genetic algorithm on this particular problem.
              >
              > If I understand the problem, one obvious
              > representation is a chromosome
              > string of length 1 over an alphabet of length L. The
              > single value at the
              > single position says where the 1 is located. This
              > representation
              > encapsulates all the information contained in any of
              > the mere L possible
              > individuals. For a seach in a space represented by a
              > chromosome of length 1,
              > point mutation on the single point is the only
              > useful operator and hence
              > there is no need to bother with the GA in the first
              > place.
              >
              > John R. Koza
              >
              > Consulting Professor
              > Biomedical Informatics
              > Department of Medicine
              > Medical School Office Building (MC 5479)
              > Stanford University
              > Stanford, California 94305-5479
              >
              > Consulting Professor
              > Department of Electrical Engineering
              > School of Engineering
              > Stanford University
              >
              > PREFERRED MAILING ADDRESS:
              > Post Office Box K
              > Los Altos, CA 94023-4011 USA
              >
              > Phone: 650-941-0336
              > Fax: 650-941-9430
              > E-Mail: koza@...
              > WWW Home Page:
              > http://www.smi.stanford.edu/people/koza
              >
              > For information about field of genetic programming
              > in general:
              > http://www.genetic-programming.org
              >
              > For information about Genetic Programming Inc.:
              > http://www.genetic-programming.com
              >
              > For information about the 2003 book "Genetic
              > Programming IV: Routine
              > Human-Competitive Machine Intelligence", visit
              > http://www.genetic-programming.org/gpbook4toc.html
              >
              > For the genetic programming bibliography, visit
              >
              http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html
              >
              > For information about the Genetic Programming book
              > series from Kluwer
              > Academic Publishers, visit
              > http://www.genetic-programming.org/gpkluwer.html
              >
              > For information about the annual Genetic and
              > Evolutionary Computation
              > Conference (GECCO) (which includes the annual
              > Genetic Programming
              > Conference) to be held in Seattle on June 26-30,
              > 2004 (Saturday -
              > Wednesday), visit http://www.isgec.org/gecco-2004/
              >
              > For information about the International Society on
              > Genetic and Evolutionary
              > Computation visit: http://www.isgec.org/
              >
              > For information about the annual
              > Euro-Genetic-Programming Conference to be
              > held in April 5-7, 2004 (Monday-Wednesday) at the
              > University of Coimbra in
              > Coimbra Portugal, visit
              > http://www.evonet.info/eurogp2004/
              >
              > For information about the annual NASA/DoD Conference
              > on Evolvable Hardware
              > (EH) in Seattle on June 24-26 (Thursday - Saturday),
              > 2004, visit
              > http://ehw.jpl.nasa.gov/events/nasaeh04/
              >
              > For information about the Asia-Pacific Workshop on
              > Genetic Programming
              > (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/
              >
              > For information about the Genetic Programming Theory
              > and Practice (GPTP)
              > workshop organized by the Center for the Study of
              > Complex Systems of the
              > University of Michigan, visit
              > http://cscs.umich.edu/calendar/conferences/gptp2003/
              >
              > For information about the Genetic Programming and
              > Evolvable Hardware journal
              > published by Kluwer Academic Publishers, visit
              > http://www.kluweronline.com/issn/1389-2576
              >
              >
              >
              >
              >
              >
              >
              >
              > -----Original Message-----
              > From: Son Duong Truong [mailto:dts8630146@...]
              > Sent: Friday, January 02, 2004 10:08 PM
              > To: genetic_programming@yahoogroups.com
              > Subject: [GP] Help about crossover point and
              > permutation. (from newbie)
              >
              >
              > Dear sir/madame,
              >
              > I am a newbie in GA programming. It comes to me
              > that I want to apply GA to
              > develop an N-gene binary string by two GA operators:
              > crossover and mutation.
              > The binary string has character of one of N. (i.e.
              > only one gene in the
              > string has value of 1, all the others has value of
              > 0)
              > Crossover operation can be at 1 point or two
              > points in the string. (the
              > point(s) are fixed at a location/locations of the
              > chromosome)
              > Mutation is permutation because all that I want to
              > do is that: first I
              > search the entire chromosome to find the genes with
              > value of 1, change it to
              > 0 and randomly choose another gene to change its
              > value to 1.
              >
              > My question are those:
              > 1) How to define and choose the location in the
              > chromosome to operate the
              > crossover operation?
              > 2) How to operate permutation?
              >
              > I am greatly appriciated your commends and helps
              > about those problems.
              > If possible, recommending some sourse code or
              > further reading related
              > would be extremely of usefulness.
              >
              > All my best regards and wishes for the New Year
              > 2004,
              >
              > Truong Son
              >
              >
              >
              >
              ----------------------------------------------------------------------------
              > --
              > Do you Yahoo!?
              > Find out what made the Top Yahoo! Searches of 2003
              > Yahoo! Groups Sponsor
              > ADVERTISEMENT
              >
              >
              >
              >
              >
              >
              === message truncated ===


              __________________________________
              Do you Yahoo!?
              Find out what made the Top Yahoo! Searches of 2003
              http://search.yahoo.com/top2003



              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/
            • John Koza
              Hello: There are (recently updated) links to a large number of web sites with GA and GP software on the web site of my course at Stanford University at
              Message 6 of 7 , Jan 4, 2004
              • 0 Attachment
                Hello:
                 
                There are (recently updated) links to a large number of web sites with GA and GP software on the web site of my course at Stanford University at http://www.genetic-programming.com/coursemainpage.html 
                 

                John R. Koza

                Consulting Professor
                Biomedical Informatics
                Department of Medicine
                Medical School Office Building (MC 5479)
                Stanford University
                Stanford, California 94305-5479

                Consulting Professor
                Department of Electrical Engineering
                School of Engineering
                Stanford University

                PREFERRED MAILING ADDRESS:
                Post Office Box K
                Los Altos, CA 94023-4011 USA

                Phone: 650-941-0336
                Fax: 650-941-9430
                E-Mail: koza@...
                WWW Home Page: http://www.smi.stanford.edu/people/koza

                For information about field of genetic programming in general:
                http://www.genetic-programming.org

                For information about Genetic Programming Inc.:
                http://www.genetic-programming.com

                For information about the 2003 book "Genetic Programming IV: Routine Human-Competitive Machine Intelligence", visit http://www.genetic-programming.org/gpbook4toc.html

                For the genetic programming bibliography, visit http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

                For information about the Genetic Programming book series from Kluwer Academic Publishers, visit http://www.genetic-programming.org/gpkluwer.html

                For information about the annual Genetic and Evolutionary Computation Conference (GECCO) (which includes the annual Genetic Programming Conference) to be held in Seattle on June 26-30, 2004 (Saturday - Wednesday), visit http://www.isgec.org/gecco-2004/

                For information about the International Society on Genetic and Evolutionary Computation  visit: http://www.isgec.org/

                For information about the annual Euro-Genetic-Programming Conference to be held in April 5-7, 2004 (Monday-Wednesday) at the University of Coimbra in Coimbra Portugal, visit http://www.evonet.info/eurogp2004/

                For information about the annual NASA/DoD Conference on Evolvable Hardware (EH) in Seattle on June 24-26 (Thursday - Saturday), 2004, visit http://ehw.jpl.nasa.gov/events/nasaeh04/

                For information about the Asia-Pacific Workshop on Genetic Programming (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/

                For information about the Genetic Programming Theory and Practice (GPTP) workshop organized by the Center for the Study of Complex Systems of the University of Michigan, visit http://cscs.umich.edu/calendar/conferences/gptp2003/

                For information about the Genetic Programming and Evolvable Hardware journal published by Kluwer Academic Publishers, visit http://www.kluweronline.com/issn/1389-2576

                -----Original Message-----
                From: Son Duong Truong [mailto:dts8630146@...]
                Sent: Sunday, January 04, 2004 3:54 AM
                To: genetic_programming@yahoogroups.com
                Subject: RE: [GP] Help about crossover point and permutation.

                Dear Dr John Koza,
                 
                Thank you very much for your advice and provided related useful websites. I will definitely have a look at those websites for more details.
                Actually, I simplify my allocation problems in the previous email. The typical chromosome will have "m" parts of "1 of N" binary string. And i would like to operate the chromosome(s) right between those parts while the permutation (mutation) expected to be done only in each single part of the typical schomosome.
                 
                My problem is that since I am not familiar with genetic programming, so I do not know how to code for the crossover and mutation in such the way that I mentioned above. I've found some source codes for GA by C and C++, that seems to be very helpful. However, I haven't utilisied them yet because I have not had a strong enough background. If you and anyone know about any materials that helps, please kindly recommend me.
                 
                Thanks very much and wish you have a nice day,
                 
                Yours sincerely,
                 
                Truong Son

                John Koza <koza@...> wrote:

                Truong Son:

                The primary reason to use a GA (or GP) is that you want to conduct a search over individuals in a search space for which you believe that the substructure of the individuals is such that a better individual will often emerge when the substructures of pretty good individuals are combined. 
                 
                In this problem, each individual string has one and only one "1".  Crossover is useless because it either (1) leaves a valid individual unchanged, (2) creates an individual with two 1's that must be repaired (i.e., mutated) back to a valid individual with just one 1, or (3) creates an individual with no 1's that must be repaired back to a valid individual with one 1).  There are apparently no substructures that can be combined (raising the question of why you would want to bother with the GA in the first place).
                 
                Mutation is the only useful operation. No matter how you define it, it will convert a string with one 1 to a new string with the single "1" elsewhere. 
                 
                It might be helpful to say a little more about the motivation for using the genetic algorithm on this particular problem. 
                 
                If I understand the problem, one obvious representation is a chromosome string of length 1 over an alphabet of length L. The single value at the single position says where the 1 is located.  This representation encapsulates all the information contained in any of the mere L possible individuals. For a seach in a space represented by a chromosome of length 1, point mutation on the single point is the only useful operator and hence there is no need to bother with the GA in the first place.
                 

                John R. Koza

                Consulting Professor
                Biomedical Informatics
                Department of Medicine
                Medical School Office Building (MC 5479)
                Stanford University
                Stanford, California 94305-5479

                Consulting Professor
                Department of Electrical Engineering
                School of Engineering
                Stanford University

                PREFERRED MAILING ADDRESS:
                Post Office Box K
                Los Altos, CA 94023-4011 USA

                Phone: 650-941-0336
                Fax: 650-941-9430
                E-Mail: koza@...
                WWW Home Page: http://www.smi.stanford.edu/people/koza

                For information about field of genetic programming in general:
                http://www.genetic-programming.org

                For information about Genetic Programming Inc.:
                http://www.genetic-programming.com

                For information about the 2003 book ! "Genetic Programming IV: Routine Human-Competitive Machine Intelligence", visit http://www.genetic-programming.org/gpbook4toc.html

                For the genetic programming bibliography, visit http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

                For information about the Genetic Programming book series from Kluwer Academic Publishers, visit http://www.genetic-programming.org/gpkluwer.html

                For information about the annual Genetic and Evolutionary Computation Conference (GECCO) (which includes the annual Genetic Programming Conference) to be held in Seattle on June 26-30, 2004 (Saturday - Wednesday), visit http://www.isgec.org/gecco-2004/

                For informat! ion about the International Society on Genetic and Evolutionary Computation  visit: http://www.isgec.org/

                For information about the annual Euro-Genetic-Programming Conference to be held in April 5-7, 2004 (Monday-Wednesday) at the University of Coimbra in Coimbra Portugal, visit http://www.evonet.info/eurogp2004/

                For information about the annual NASA/DoD Conference on Evolvable Hardware (EH) in Seattle on June 24-26 (Thursday - Saturday), 2004, visit http://ehw.jpl.nasa.gov/events/nasaeh04/

                For information about the Asia-Pacific Workshop on Genetic Programming (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/

                For information about the Genetic Programming Theory and Practice (GPTP) workshop organized by the Ce! nter for the Study of Complex Systems of the University of Michigan, visit http://cscs.umich.edu/calendar/conferences/gptp2003/

                For information about the Genetic Programming and Evolvable Hardware journal published by Kluwer Academic Publishers, visit http://www.kluweronline.com/issn/1389-2576

                 
                 
                 
                 
                 
                 -----Original Message-----
                From: Son Duong Truong [mailto:dts8630146@...]
                Sent: Friday, January 02, 2004 10:08 PM
                To: genetic_programming@yahoogroups.com
                Subject: [GP] Help about crossover point and permutation. (from newbie)

                Dear sir/madame,
                 
                I am a newbie in GA programming. It comes to me that I want to apply GA to develop an N-gene binary string by two GA operators: crossover and mutation.
                The binary string has character of one of N. (i.e. only one gene in the string has value of 1, all the others has value of 0)
                Crossover operation can be at 1 point or two points in the string. (the point(s) are fixed at a location/locations of the chromosome)
                Mutation is permutation because all that I want to do is that: first I search the entire chromosome to find the genes with value of 1, change it to 0 and randomly choose another gene to change its value to 1.
                 
                My question are those:
                1) How to define and choose the location in the chromosome to operate the crossover operation?
                2) How to operate permutation?
                 
                I am greatly appriciated your commends and helps about those problems.

                If possible, recommending some sourse code or further reading related would be extremely of usefulness.

                All my best regards and wishes for the New Year 2004,

                Truong Son


                Do you Yahoo!?
                Find out what made the Top Yahoo! Searches of 2003


                Yahoo! Groups Links



                Yahoo! Groups Links


                Do you Yahoo!?
                Find out what made the Top Yahoo! Searches of 2003


                Yahoo! Groups Links

              • walid ahmed
                Dear Dr Koza i am sorry , i did not understand the example of telphone pole... can u plz clarify more Walid ...
                Message 7 of 7 , Jan 5, 2004
                • 0 Attachment
                  Dear Dr Koza

                  i am sorry , i did not understand the example of
                  telphone pole...

                  can u plz clarify more

                  Walid
                  --- John Koza <koza@...> wrote:
                  > Hello:
                  >
                  > There is definitely no rule or theorem that says
                  > that "substructure
                  > combination [will] lead to a better individual."
                  >
                  > If the search space of a particular problem is such
                  > that there is no
                  > correlation between the payoff (fitness) and some
                  > substructure, GA (or GP)
                  > is simply not going to solve your problem. A good
                  > example is the telephone
                  > pole sitting at the bottom of a crater. All
                  > gradients point away from the
                  > telephone pole and suggest that you should move
                  > along the increasing
                  > gradient towards the (seemingly high) ground level;
                  > however, the global
                  > optimum point is the top of the telephone poll
                  > (which rises well above
                  > ground level).
                  >
                  > Of course, other search methods are also going to
                  > fail on this kind of
                  > cryptographic "needle in a haystack" problem where
                  > there is a total
                  > disconnect between structure and performance.
                  >
                  >
                  > John R. Koza
                  >
                  > Consulting Professor
                  > Biomedical Informatics
                  > Department of Medicine
                  > Medical School Office Building (MC 5479)
                  > Stanford University
                  > Stanford, California 94305-5479
                  >
                  > Consulting Professor
                  > Department of Electrical Engineering
                  > School of Engineering
                  > Stanford University
                  >
                  > PREFERRED MAILING ADDRESS:
                  > Post Office Box K
                  > Los Altos, CA 94023-4011 USA
                  >
                  > Phone: 650-941-0336
                  > Fax: 650-941-9430
                  > E-Mail: koza@...
                  > WWW Home Page:
                  > http://www.smi.stanford.edu/people/koza
                  >
                  > For information about field of genetic programming
                  > in general:
                  > http://www.genetic-programming.org
                  >
                  > For information about Genetic Programming Inc.:
                  > http://www.genetic-programming.com
                  >
                  > For information about the 2003 book "Genetic
                  > Programming IV: Routine
                  > Human-Competitive Machine Intelligence", visit
                  > http://www.genetic-programming.org/gpbook4toc.html
                  >
                  > For the genetic programming bibliography, visit
                  >
                  http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html
                  >
                  > For information about the Genetic Programming book
                  > series from Kluwer
                  > Academic Publishers, visit
                  > http://www.genetic-programming.org/gpkluwer.html
                  >
                  > For information about the annual Genetic and
                  > Evolutionary Computation
                  > Conference (GECCO) (which includes the annual
                  > Genetic Programming
                  > Conference) to be held in Seattle on June 26-30,
                  > 2004 (Saturday -
                  > Wednesday), visit http://www.isgec.org/gecco-2004/
                  >
                  > For information about the International Society on
                  > Genetic and Evolutionary
                  > Computation visit: http://www.isgec.org/
                  >
                  > For information about the annual
                  > Euro-Genetic-Programming Conference to be
                  > held in April 5-7, 2004 (Monday-Wednesday) at the
                  > University of Coimbra in
                  > Coimbra Portugal, visit
                  > http://www.evonet.info/eurogp2004/
                  >
                  > For information about the annual NASA/DoD Conference
                  > on Evolvable Hardware
                  > (EH) in Seattle on June 24-26 (Thursday - Saturday),
                  > 2004, visit
                  > http://ehw.jpl.nasa.gov/events/nasaeh04/
                  >
                  > For information about the Asia-Pacific Workshop on
                  > Genetic Programming
                  > (ASPGP03), visit http://www.cs.adfa.edu.au/~cec_gp/
                  >
                  > For information about the Genetic Programming Theory
                  > and Practice (GPTP)
                  > workshop organized by the Center for the Study of
                  > Complex Systems of the
                  > University of Michigan, visit
                  > http://cscs.umich.edu/calendar/conferences/gptp2003/
                  >
                  > For information about the Genetic Programming and
                  > Evolvable Hardware journal
                  > published by Kluwer Academic Publishers, visit
                  > http://www.kluweronline.com/issn/1389-2576
                  >
                  >
                  >
                  >
                  >
                  >
                  >
                  >
                  >
                  > -----Original Message-----
                  > From: walid ahmed [mailto:welloma@...]
                  > Sent: Sunday, January 04, 2004 12:12 AM
                  > To: genetic_programming@yahoogroups.com
                  > Subject: RE: [GP] Help about crossover point and
                  > permutation. (from
                  > newbie)
                  >
                  >
                  > Dear Dr John Koza
                  >
                  > is there is any rule that says that substructures
                  > combination can lead to a better individual.
                  >
                  > i have seen alot of applications that used crosover
                  > without declaring y they used ga in the first place.
                  > may be only because the search space was big . it
                  > was
                  > tempting to use GA.however i think in this case we
                  > r
                  > in jusrt a guided random search .???
                  >
                  > thanks
                  >
                  > Walid
                  > --- John Koza <koza@...> wrote:
                  > > Truong Son:
                  > >
                  > > The primary reason to use a GA (or GP) is that you
                  > > want to conduct a search
                  > > over individuals in a search space for which you
                  > > believe that the
                  > > substructure of the individuals is such that a
                  > > better individual will often
                  > > emerge when the substructures of pretty good
                  > > individuals are combined.
                  > >
                  > > In this problem, each individual string has one
                  > and
                  > > only one "1". Crossover
                  > > is useless because it either (1) leaves a valid
                  > > individual unchanged, (2)
                  > > creates an individual with two 1's that must be
                  > > repaired (i.e., mutated)
                  > > back to a valid individual with just one 1, or (3)
                  > > creates an individual
                  > > with no 1's that must be repaired back to a valid
                  > > individual with one 1).
                  > > There are apparently no substructures that can be
                  > > combined (raising the
                  > > question of why you would want to bother with the
                  > GA
                  > > in the first place).
                  > >
                  > > Mutation is the only useful operation. No matter
                  > how
                  > > you define it, it will
                  > > convert a string with one 1 to a new string with
                  > the
                  > > single "1" elsewhere.
                  > >
                  > > It might be helpful to say a little more about the
                  > > motivation for using the
                  > > genetic algorithm on this particular problem.
                  > >
                  > > If I understand the problem, one obvious
                  > > representation is a chromosome
                  > > string of length 1 over an alphabet of length L.
                  > The
                  > > single value at the
                  > > single position says where the 1 is located. This
                  > > representation
                  > > encapsulates all the information contained in any
                  > of
                  > > the mere L possible
                  > > individuals. For a seach in a space represented by
                  > a
                  > > chromosome of length 1,
                  > > point mutation on the single point is the only
                  >
                  === message truncated ===


                  __________________________________
                  Do you Yahoo!?
                  Find out what made the Top Yahoo! Searches of 2003
                  http://search.yahoo.com/top2003
                Your message has been successfully submitted and would be delivered to recipients shortly.