# Fitness Landscape Of The Cellular Automata Majority Problem: View From The "Olympus" S. Verel A**, P. Collard** A**, M. Tomassini** B **And L. Vanneschi** C

a**Laboratoire I3S, CNRS-University of Nice Sophia Antipolis, France**
b**Information Systems Department, University of Lausanne, Switzerland**
c**Dipartimento di Informatica Sistemistica e Comunicazione, University of**
Milano-Bicocca, Italy

## Abstract

In this paper we study cellular automata (CAs) that perform the computational Majority task. This task is a good example of what the phenomenon of emergence in complex systems is. We take an interest in the reasons that **make this particular**
fitness landscape a difficult one. The first goal is to study landscape as such, and thus it is ideally independent from the actual heuristics used to search the space. However, a second goal is to understand the features a good search technique for this particular problem space should possess. We statistically **quantify in various ways** the degree of difficulty of searching this landscape. Due to neutrality, investigations based on sampling techniques on the whole landscape are difficult to conduct. So, we go exploring the landscape from the top**. Although it has been proved that no**
CA can perform the task perfectly, several efficient CAs for this task have been found. Exploiting similarities between these CAs and symmetries in the landscape, we define the Olympus **landscape which is regarded as the "heavenly home" of** the best local optima known **(blok). Then we measure several properties of this**
subspace. Although it is easier to find relevant CAs in this subspace than in the overall landscape, there are structural reasons that prevents a searcher from finding overfitted CAs in the Olympus. Finally, we study dynamics and **performances of**
genetic algorithms on the Olympus **in order to confirm our analysis and to find**
efficient CAs for the Majority problem with low computational **cost.**
Key words: **Fitness landscapes, Correlation analysis, Neutrality, Cellular**
automata, AR models arXiv:0709.3974v1 [cs.AI] 25 Sep 2007