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

Re: [GP] Majority Classification Problem

Expand Messages
  • Greg Hornby
    Sean, Hugues Juille worked on this several years ago and I m under the impression he got very good results. Check out: Juillé, H.
    Message 1 of 5 , Jan 2, 2013
    • 0 Attachment
      Sean,

      Hugues Juille worked on this several years ago and I'm under the impression he got very good results.  Check out:

      Juillé, H. and Pollack, J. B. (1998). Coevolving the "Ideal" Trainer: Application to the Discovery of Cellular Automata Rules
      Proceedings of the Third Annual Genetic Programming Conference , Madison, Wisconsin, July 22 - 25, 1998.

      This paper is online at:

      Table 1 of that paper suggests he might have achieved an 86% success rate on 149 bits.  Hugues's dissertation came out in '99 and it might be more clear on this.

      Greg



      On Wed, Jan 2, 2013 at 12:10 PM, Sean Luke <sean@...> wrote:
       

      Hi all. For an EC experiment we're doing I'm poking around at reimplementing the Majority Classification Problem, where the objective is to construct a 7-neighborhood 1-dimensional cellular automaton rule which classifies whether the initial automata values are majority 0's or majority 1's.

      The first GA work on this problem was "Evolving Globally Synchronized Cellular Automata" by Das, Crutchfield, Mitchell, and Hanson, which yielded a 76.9% accuracy. After this, the record was improved to 82.326% in "Discovery by Genetic Programming of a Cellular Automata Rule that is Better than any Known Rule for the Majority Classification Problem" by Andre, Bennett, and Koza, using GP.

      Is this where the record stands now? In the back of my mind I recall that another GA paper had beaten this record a few years later but for the life of me I cannot find anything. I am aware of Back's paper on *multi-dimensional* CA but that's it. Can anyone guide me here?

      Sean


    • Sean Luke
      Thanks guys. That was just what I was looking for. BTW, someone needs to update Wikipedia about this, all it points to is the Das results. Sean
      Message 2 of 5 , Jan 2, 2013
      • 0 Attachment
        Thanks guys. That was just what I was looking for. BTW, someone needs to update Wikipedia about this, all it points to is the Das results.

        Sean

        On Jan 2, 2013, at 3:14 PM, moshe sipper wrote:

        > Sean -- Having done quite a bit myself [http://www.moshesipper.com/pcm/%5d
        > check out
        > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.7665

        On Jan 2, 2013, at 3:23 PM, Greg Hornby wrote:

        > Hugues Juille worked on this several years ago and I'm under the impression he got very good results. Check out:
        >
        > Juillé, H. and Pollack, J. B. (1998). Coevolving the "Ideal" Trainer: Application to the Discovery of Cellular Automata Rules.
        > Proceedings of the Third Annual Genetic Programming Conference , Madison, Wisconsin, July 22 - 25, 1998.
        >
        > This paper is online at:
        > http://demo.cs.brandeis.edu/papers/long.html#gp98
        > http://demo.cs.brandeis.edu/papers/gp98.pdf
        >
        > Table 1 of that paper suggests he might have achieved an 86% success rate on 149 bits. Hugues's dissertation came out in '99 and it might be more clear on this.
      • w langdon
        Dear Sean, This is indeed mentioned in his PhD thesis http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/hugues_thesis.html eg chapters 4 and 6. Bill
        Message 3 of 5 , Jan 3, 2013
        • 0 Attachment
          Dear Sean,
          This is indeed mentioned in his PhD thesis
          http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/hugues_thesis.html
          eg chapters 4 and 6.
          Bill

          On 1/2/13, Greg Hornby <ghornby@...> wrote:
          > Sean,
          >
          > Hugues Juille worked on this several years ago and I'm under the impression
          > he got very good results. Check out:
          >
          > Juillé, H. <http://demo.cs.brandeis.edu/papers/author.html#juille> and
          > Pollack,
          > J. B. <http://demo.cs.brandeis.edu/papers/author.html#pollack> (1998).
          > *Coevolving
          > the "Ideal" Trainer: Application to the Discovery of Cellular Automata
          > Rules
          > *.
          > *Proceedings of the Third Annual Genetic Programming Conference* , Madison,
          > Wisconsin, July 22 - 25, 1998.
          >
          > This paper is online at:
          > http://demo.cs.brandeis.edu/papers/long.html#gp98
          > http://demo.cs.brandeis.edu/papers/gp98.pdf
          >
          > Table 1 of that paper suggests he might have achieved an 86% success rate
          > on 149 bits. Hugues's dissertation came out in '99 and it might be more
          > clear on this.
          >
          > Greg
          >
          >
          >
          > On Wed, Jan 2, 2013 at 12:10 PM, Sean Luke <sean@...> wrote:
          >
          >> **
          >>
          >>
          >> Hi all. For an EC experiment we're doing I'm poking around at
          >> reimplementing the Majority Classification Problem, where the objective
          >> is
          >> to construct a 7-neighborhood 1-dimensional cellular automaton rule which
          >> classifies whether the initial automata values are majority 0's or
          >> majority
          >> 1's.
          >>
          >> The first GA work on this problem was "Evolving Globally Synchronized
          >> Cellular Automata" by Das, Crutchfield, Mitchell, and Hanson, which
          >> yielded
          >> a 76.9% accuracy. After this, the record was improved to 82.326% in
          >> "Discovery by Genetic Programming of a Cellular Automata Rule that is
          >> Better than any Known Rule for the Majority Classification Problem" by
          >> Andre, Bennett, and Koza, using GP.
          >>
          >> Is this where the record stands now? In the back of my mind I recall that
          >> another GA paper had beaten this record a few years later but for the
          >> life
          >> of me I cannot find anything. I am aware of Back's paper on
          >> *multi-dimensional* CA but that's it. Can anyone guide me here?
          >>
          >> Sean
          >>
          >>
          >
        • Bob McKay
          Hi Sean; you might find this article useful for a recent summary: http://link.springer.com/article/10.1007%2Fs12293-012-0093-z# @article{Enzan2012,
          Message 4 of 5 , Jan 3, 2013
          • 0 Attachment
            Hi Sean; you might find this article useful for a recent summary:
            http://link.springer.com/article/10.1007%2Fs12293-012-0093-z#

            @article{Enzan2012,
            year={2012},
            issn={1865-9284},
            journal={Memetic Computing},
            doi={10.1007/s12293-012-0093-z},
            title={Cell state change dynamics in cellular automata},
            url={http://dx.doi.org/10.1007/s12293-012-0093-z},
            publisher={Springer-Verlag},
            keywords={Cellular automata; Density classification; Evolutionary algorithms},
            author={Iclănzan, David and Gog, Anca and Chira, Camelia},
            pages={1-9},
            language={English}
            }

                Cheers
                Bob McKay
          Your message has been successfully submitted and would be delivered to recipients shortly.