Self assembly is a vital and ubiquitous mechanism in biological systems. In recent years, we have investigated its evolutionary potential and discovered that the inherent property of self assembling systems to form extended regular structures from locally interacting components enables one to construct scalable digital circuitry by inductive generalization [1].
Among other case studies, we scrutinized in depth the evolution of scalable multipliers. Scalability here means that the genetically encoded components can assemble into logical circuitry of any desired size, capable of multiplying arbitrarily large numbers.
The demand for scalability poses a conceptual problem to genetic algorithms: The solutions to a potentially infinite number of problem instances (pairs of number to multiply) must be learned from only a finite number of test cases. The evolving system must be able to represent not only individual solutions to specific problem instances but to capture the logical structure underlying the problem under consideration.
Self assembled structures of building blocks equipped with logical functionality enable the representation of the inductive structures behind problems such as multiplication by pattern formation: logical patterns are mapped onto geometrical ones. Enabling the realization of circuits which exploit the deeper structures of a given problem is not however sufficient to allow self-organizing evolution. We developed a genetic algorithm which makes such generalizable circuits also sufficiently beneficial, which is less trivial than it may look. This is achieved while still evaluating the results of a limited set of test problems, without referring to structural insight into the nature of the problem.
A central observation we made is the existence of an “inductive hill”. In most attempts to evolve digital multipliers (constrained or unconstrained), the time one needs to get an n by n multiplier (n-1 referring to the number of bits) grows monotonically and very fast with n. With evolving self assembled structures, however, this growth stops at a finite value of n. With only very few exceptions, evolved self-assembled multipliers capable of calculating correctly 4bit x 4bit products can also multiply arbitrarily large numbers (when assembled to the according size). This is especially interesting because the inductive barrier occurring for 3 to 4 bit multipliers is similar to the transition between table look up (10x10 multiplication tables) and rule based multiplication for human learners.