- 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,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.GregOn 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 - 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. - 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

>>

>>

> - 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