

![0_image_0.png](0_image_0.png)

$$n s c=\sum_{i=1}^{m-1}c_{i},\ \ {\mathrm{where:}}\ \forall i\in[1,m)\ \ c_{i}=m i n(P_{i},0)$$

We hypothesize that nsc **can give some indication of problem difficulty in the** following sense: if nsc= 0, the problem is easy, if nsc< **0 the problem is difficult**
and the value of nsc **quantifies this difficulty: the smaller its value, the more** difficult the problem. In other words, according to our hypothesis, **a problem**
is difficult if at least one of the segments S1, S2, . . . , Sm−1 **has a negative slope**
and the sum of all the negative slopes gives a measure of problem hardness. The idea is that the presence of a segment with negative slope indicates a bad evolvability for individuals having fitness values contained in that segment.

## 4 Analysis Of The Majority Problem Fitness Landscape

4.1 Definition of the fitness landscape
As in Mitchell [4], we use CA of radius r **= 3 and configurations of length** N = 149. The set S **of potential solutions of the Majority Fitness Landscape** is the set of binary string which represent the possible CA rules. The **size of**
S **is 2**2 2r+1 = 2128**, and each automaton should be tested on the 2**149 **possible**
different ICs. This gives 2277 possibilities, a size far too large to be searched exhaustively. Since performance can be defined in several ways, the **consequence**
is that for each feasible CA in the search space, the associated fitness can be