Interdependencies, nearly-decomposability and adaptation

Abstract: In this paper we discuss some limitations that selection mechanisms face when the entities subject to selection are complex systems of interdependent elements. We briefly present Kauffman’s NK model which addresses this problem in biological systems. It is argued that, contrary to the myopic search behaviour underlying biological fitness landscapes, social organisations are not bound in their search dynamics. This amounts to say that the problem of finding optima on a fitness landscape can be decomposed in many different ways. Following work by Page (1996), we present a measure of the complexity of a fitness landscape in terms of the complexity (size) of the algorithm that decomposes the problem most accurately, while still being able to locate the global optima with full certainty. We then extend this measures to allow for near-decomposability in a sense of Simon (1969). Finally we study some evolutionary properties of populations of agents characterised by different decompositions of the same given problem. It is shown that search strategies capable of finding the global optimum with full certainty generally do not survive due to their large amount of time required. Instead, search strategies that only approximately map the struture of interdependencies do better as the amount of time required is much smaller, while the fitness of solutions that are found, are close to the fitness of the globally optimal solution.