Category: Science

Summary: Evolving one-dimensional cellular-automaton rules to solve the density-classification task from random initial conditions.

The density-classification task is a classic benchmark for decentralized computation: a cellular automaton should settle to all ones if the initial state contains a majority of ones, and to all zeros otherwise. Simple local rules struggle with this global decision problem, which is why the task has long been used to probe the computational limits of cellular automata.

This experiment uses a genetic algorithm to search the space of radius-3 one-dimensional cellular-automaton rules. Candidate rules are evaluated on many random initial conditions, selected by fitness, and improved through mutation and crossover until the run budget is exhausted.

That approach turns a hard hand-designed-rule problem into an evolutionary search problem. The resulting statistics show not only how well the best rule performs, but also how much better it is than trivial always-zero or always-one strategies and how quickly the population improves.

Method: Genetic-algorithm search over radius-3 lookup-table cellular-automaton rules, evaluated on repeated density-classification trials from random initial conditions.

What is measured: Best validation and final test fitness, generations needed to reach 80% fitness, evolved rule statistics, fitness-history trajectories, and comparison with trivial all-zero and all-one rules.