In several of the talks here at GECCO, the issue of complexity has come up. In one talk I just listened to, the speaker discussed three general measures of complexity:
1) Shannon Entropy, or degree of uncertainty
2) Kolmogorov complexity, or the amount of description needed to fully specify something
3) Functional complexity, or how complex its interactions with the environment are
He argued that functional complexity should be kept separate from other measures.
But here's one strange example. Let's say you take a mouse. It has a high degree of regularity in its morphology. It's bilaterally symmetric, hierarchical, and highly modular. Now, if you took that mouse and dropped it in a blender, so that its molecules were distributed randomly in space, by the first two measures above, that blended mouse would be more complex than the intact mouse. However, its functional complexity would be much lower (i.e., a live mouse can run around and do lots of things that a blended mouse can't).
For the things we're interested in either understanding or engineering, I think excluding functional complexity is probably wrong.