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

Majority Classification Problem

Expand Messages
  • Sean Luke
    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
    Message 1 of 5 , Jan 2, 2013
    • 0 Attachment
      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
    • 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 2 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 3 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 4 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 5 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.