Standard Complexity Measures

Does selection favor more complex forms? The answer is yes. As indicated by figure 3.25, the complexity of the average Tron agent has been increasing over time.

We have taken three straightforward software complexity measures and applied them to the s-expressions governing Tron agents: depth (of the expression tree), size (number of tokens) and cyclomatic number (irreducible loops -- see page 3). As time and selection go by, the average complexity of the surviving agents' code goes up. depth variable has reached a ceiling; most surviving agents have the maximum depth of 17.

But expression complexity is an abstract measure. Are we evolving complex behaviors? The present section analyzes the behavioral characteristics of evolved Tron robots.

  

Figure 3.25: Evolution of Complexity in Tron Agents. The horizontal axis is the time scale. Three complexity measures are plotted: expression depth, size and cyclomatic number (depth is on the right-hand y axis). All three complexity measures increase with evolutionary time. Depth has reached an internal limit (17) whereas size could still grow (the maximum is 512).