Fitness landscape of the cellular automata majority problem: View from the Olympus

Details Fitness landscape of the cellular automata majority problem: View from the Olympus Fitness landscape of the cellular automata majority problem: View from the Olympus

2007-09-25

arxiv.org/abs/0709.3974v1

Theoretical Computer Science 378, 1 (2007) 54-77

Computer Science

Artificial Intelligence

Scientific paper

10.1016/j.tcs.2007.01.001

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 the 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 prevent a searcher from finding overfitted CAs in the Olympus. Finally, we study dynamics and performance 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.

Affiliated with

Also associated with

No associations

Rating

Fitness landscape of the cellular automata majority problem: View from the Olympus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fitness landscape of the cellular automata majority problem: View from the Olympus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fitness landscape of the cellular automata majority problem: View from the Olympus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-626377