How micro-evolution can guide macro-evolution: multi-scale search via evolved modular variation

A divide-and-conquer approach to problem solving can in principle be far more efficient than tackling a problem as a monolithic whole. This type of approach is most appropriate when problems have the type of modular organisation known as near-decomposability, as implicit in many natural and engineered systems. Existing methods create higher scale composite units from non-random combinations of lower-scale units that reflect sub-problem optima. The use of composite units affords search at a higher scale that, when applied recursively, can ultimately lead to optimal top-level solutions. But for this approach to be efficient, we must decompose a problem in a manner that respects its intrinsic modular structure, information which is in general unavailable a priori. Thus, identifying and subsequently exploiting the structure recursively is vital in providing fully automatic problem decomposition.<br/><br/>In this thesis, we define a family of algorithms that probabilistically adapt the scale of decomposition they use to reflect the structure in a problem. By doing so, they can provide optimisation that is provably superior to any single scale of search in nearly decomposable problems. Our proposed framework couples two adaptive processes: a rapid, fine-scale search that guides a slower adaptation of the decomposition. This results in a scaling up of the units used in the rapid search, now operating at a macro-scale. We find that separating the timescales for the fine-scale search and the adaptation of the decomposition is crucial for this kind of scalable optimisation. <br/><br/>Using a simple and general class of problems that have no systematic structure, we demonstrate how our approach can nevertheless exploit the incidental structure present. Furthermore, we use idealised cases that have simple modular structure to demonstrate how our method scales as ?(N log N) (where N is the problem size), despite the fact that single-scale search methods scale as ? (2 ?N) – and support this distinction analytically.<br/><br/>Although our approach is algorithmically superior to single-scale search, the underlying principles that it is constructed from are simple and can operate using only localised feedback. We discuss intriguing parallels between our approach and the significance of associative evolution for ecosystem adaptation. Our results suggest that macro-evolutionary processes might not be merely extended micro-evolution, but that the action of evolutionary processes upon several scales is fundamentally different from the conventional view of (micro-)evolution at a single scale.

Name dc:type.qualificationname

Ph.D.

Level dc:type.qualificationlevel

doctoral

Grantor dc:publisher.institution

University of Southampton

Year dc:date.issued

2010

Author dc:creator

• Mills, Rob

Advisor dc:contributor.advisor

• Watson, Richard