Home | Read Online | Amazon | GoodReads | Google Books | PDF (code) | GitHub
This section provides a discussion of some of the approaches that may be used to devise new algorithms and systems inspired by biological systems for addressing mathematical and engineering problems. This discussion covers:
Many algorithms, such as the Genetic Algorithm have come from the study and models of complex and adaptive systems. Adaptive systems research provides a methodology by which these systems can be systematically investigated resulting in adaptive plans or strategies that can provide the basis for new and interesting algorithms.
Holland proposed a formalism in his seminal work on adaptive systems that provides a general manner in which to define an adaptive system [Holland1975]. Phrasing systems in this way provides a framework under which adaptive systems may be evaluated and compared relative to each other, the difficulties and obstacles of investigating specific adaptive systems are exposed, and the abstracted principles of different system types may be distilled. This section provides a summary of the Holland's seminal adaptive systems formalism and considers clonal selection as an example of an adaptive plan.
This section presents a brief review of Holland's adaptive systems formalism described in [Holland1975] (Chapter 2). This presentation focuses particularly on the terms and their description, and has been hybridized with the concise presentation of the formalism by De Jong [Jong1975] (page 6). The formalism is divided into sections: 1) Primary Objects summarized in Table (below), and 2) Secondary Objects summarized in Table (below). Primary Objects are the conventional objects of an adaptive system: the environment $e$, the strategy or adaptive plan that creates solutions in the environment $s$, and the utility assigned to created solutions $U$.
| Term | Object | Description |
| $e$ | Environment | The environment of the system undergoing adaptation. |
| $s$ | Strategy | The adaptive plan which determines successive structural modifications in response to the environment. |
| $U$ | Utility | A measure of performance or payoff of different structures in the environment. Maps a given solution ($A$) to a real number evaluation. |
Secondary Objects extend beyond the primary objects providing the detail of the formalism. These objects suggest a broader context than that of the instance specific primary objects, permitting the evaluation and comparison of sets of objects such as plans ($S$), environments ($E$), search spaces ($A$), and operators ($O$).
| Term | Object | Description |
| $A$ | Search Space | The set of attainable structures, solutions, and the domain of action for an adaptive plan. |
| $E$ | Environments | The range of different environments, where $e$ is an instance. It may also represent the unknowns of the strategy about the environment. |
| $O$ | Operators | Set of operators applied to an instance of $A$ at time $t$ ($A_t$) to transform it into $A_{t+1}$. |
| $S$ | Strategies | Set of plans applicable for a given environment (where $s$ is an instance), that use operators from the set $O$. |
| $X$ | Criterion | Used to compare strategies (in the set $S$), under the set of environments ($E$). Takes into account the efficiency of a plan in different environments. |
| $I$ | Feedback | Set of possible environmental inputs and signals providing dynamic information to the system about the performance of a particular solution $A$ in a particular environment $E$. |
| $M$ | Memory | The memory or retained parts of the input history ($I$) for a solution ($A$). |
A given adaptive plan acts in discrete time $t$, which is a useful simplification for analysis and computer simulation. A framework for a given adaptive system requires the definition of a set of strategies $S$, a set of environments $E$, and criterion for ranking strategies $X$. A given adaptive plan is specified within this framework given the following set of objects: a search space $A$, a set of operators $O$, and feedback from the environment $I$. Holland proposed a series of fundamental questions when considering the definition for an adaptive system, which he rephrases within the context of the formalism (see Table (below)).
| Question | Formal |
| To what parts of its environment is the organism (system, organization) adapting? | What is $E$? |
| How does the environment act upon the adapting organism (system, organization)? | What is $I$? |
| What structures are undergoing adaptation? | What is $A$? |
| What are the mechanisms of adaptation? | What is $O$? |
| What part of the history of its interaction with the environment does the organism (system, organization) retain in addition to that summarized in the structure tested? | What is $M$? |
| What limits are there to the adaptive process? | What is $S$? |
| How are different (hypotheses about) adaptive processes to be compared? | What is $X$? |
Holland provides a series of illustrations rephrasing common adaptive systems in the context of the formalism [Holland1975] (pages 35-36). Examples include: genetics, economics, game playing, pattern recognition, control, function optimization, and the central nervous system. The formalism is applied to investigate his schemata theorem, reproductive plans, and genetic plans. These foundational models became the field of Evolutionary Computation (Evolutionary Algorithms Chapter).
From working within the formalism, Holland makes six observations regarding obstacles that may be encountered whilst investigating adaptive systems [Holland1975] (pages 159-160):
Cavicchio provides perhaps one of the first applications of the formalism (after Holland) in his dissertation investigating Holland's reproductive plans [Cavicchio1970] (and to a lesser extent in [Cavicchio1972]). The work summarizes the formalism, presenting essentially the same framework, although he provides a specialization of the search space $A$. The search space is broken down into a representation (codes), solutions (devices), and a mapping function from representation to solutions. The variation highlights the restriction the representation and mapping have on the designs available to the adaptive plan. Further, such mappings may not be one-to-one, there may be many instances in the representation space that map to the same solution (or the reverse).
Although not explicitly defined, Holland's specification of structures $A$ is clear in pointing out that the structures are not bound to a level of abstraction; the definition covers structures at all levels. Nevertheless, Cavicchio's specialization for a representation-solution mapping was demonstrated to be useful in his exploration of reproductive plans (early Genetic Algorithms). He proposed that an adaptive system is first order if the utility function $U$ for structures on an environment encompasses feedback $I$.
Cavicchio described the potential independence (component-wise) and linearity of the utility function with respect to the representation used. De Jong also employed the formalism to investigate reproductive plans in his dissertation research [Jong1975]. He indicated that the formalism covers the essential characteristics of adaptation, where the performance of a solution is a function of its characteristics and its environment. Adaptation is defined as a strategy for generating better-performing solutions to a problem by reducing initial uncertainty about the environment via feedback from the evaluation of individual solutions. De Jong used the formalism to define a series of genetic reproductive plans, which he investigated in the context of function optimization.
Adaptive strategies are typically complex because they result in irreducible emergent behaviors that occur as a result of the non-linear interactions of system components. The study of Complex Adaptive Systems (CAS) is the study of high-level abstractions of natural and artificial systems that are generally impervious to traditional analysis techniques. Macroscopic patterns emerge from the dynamic and non-linear interactions of the system's low-level (microscopic) adaptive agents. The emergent patterns are more than the sum of their parts. As such, traditional reductionist methodologies fail to describe how the macroscopic patterns emerge. Holistic and totalistic investigatory approaches are applied that relate the simple rules and interactions of the simple adaptive agents to their emergent effects in a 'bottom-up' manner.
Some relevant examples of CAS include: the development of embryos, ecologies, genetic evolution, thinking and learning in the brain, weather systems, social systems, insect swarms, bacteria becoming resistant to an antibiotic, and the function of the adaptive immune system.
The field of CAS was founded at the Santa Fe Institute (SFI), in the late 1980s by a group of physicists, economists, and others interested in the study of complex systems in which the agents of those systems change [Anderson1988]. One of the most significant contributors to the inception of the field from the perspective of adaptation was Holland. He was interested in the question of how computers could be programmed so that problem-solving capabilities are built up by specifying: "what is to be done" (inductive information processing) rather than "how to do it" (deductive information processing). In the 1992 reprint of his book he provided a summary of CAS with a computational example called ECHO [Holland1975]. His work on CAS was expanded in a later book which provided an in depth study of the topic [Holland1995].
There is no clear definition of a Complex Adaptive System, rather sets of parsimonious principles and properties, many different researches in the field defining their own nomenclature. Popular definitions beyond Holland's work include that of Gell-Mann [Gell-Mann1994] and Arthur [Arthur1997].
Explicit methodologies have been devised and used for investigating natural systems with the intent of devising new computational intelligence techniques. This section introduces two such methodologies taken from the field of Artificial Immune Systems (Immune Algorithms Chapter).
Although the progression from an inspiring biological system to an inspired computation system may appear to be an intuitive process, it can involve problems of standardization of nomenclature, effective abstraction and departure from biology, and rigor. Stepney, et al. caution that by following a process that lacks the detail of modeling, one may fall into the trap of reasoning by metaphor [Twycross2005] [Stepney2004] [Stepney2005].
Besides the lack of rigor, the trap suggests that such reasoning and lack of objective analysis limits and biases the suitability and applicability of resultant algorithms. They propose that many algorithms in the field of Artificial Immune Systems (and beyond) have succumbed to this trap. This observation resulted in the development and application of a conceptual framework to provide a general process that may be applied in the field of Biological Inspired Computation toward realizing Biological Inspired Computational Intelligence systems.
The conceptual framework is comprised of the following actors and steps:
Forrest and Hofmeyr summarized their AIS research efforts at the University of New Mexico and the Santa Fe Institute as "immunology as information processing" [Forrest2001]. They define information as spatio-temporal patterns that can be abstracted and described independent of the biological system and information processing as computation with these patterns. They proposed that such patterns are encoded in the proteins and other molecules of the immune system, and that they govern the behavior of the biological system. They suggest that their information processing perspective can be contrasted with the conventional structural perspective of cellular interactions as mechanical devices. They consider a simple four-step procedure for the investigation of immunology as information processing, transitioning from the biological system to a usable computational tool:
The procedure is similar to the outlined in the conceptual framework for Biologically Inspired Algorithms in that in addition to identifying biological mechanisms (input) and demonstrating a resultant algorithms (output), the procedure 1) highlights the need for abstraction involving modeling the identified mechanism, and 2) highlights the need to analyze the models and abstractions. The procedure of Forrest and Hofmeyr can be used to specialize the conceptual framework of Stepney et al. by clearly specifying the immunological information processing focus.
Once an abstract information processing system is devised it must be investigated in a systematic manner. There are a range of modeling techniques for such a system from weak and rapid to realize to strong and slow to realize. This section considers the trade-off's in modeling an adaptive technique.
Goldberg describes the airplane and other products of engineering as material machines, and distinguishes them from the engineering of genetic algorithms and other adaptive systems as conceptual machines. He argues the methodological distinction between the two is counter-productive and harmful from the perspective of conceptual machines, specifically that the methodology of the material is equally applicable to that of the conceptual [Goldberg1999a].
The obsession of mathematical rigor in computer science, although extremely valuable, is not effective in the investigation of adaptive systems given their complexity. Goldberg sites the airplane as an example where the engineering invention is used and trusted without a formal proof that the invention works (that an airplane can fly). (Goldberg is quick to point out that sets of equations do exist for various aspects of flight, although no integrated mathematical proof for airplane flight exists.)
This defense leads to what Goldberg refers to the economy of design, which is demonstrated with a trade-off that distinguishes 'model description' (mathematician-scientists) that is concerned with model fidelity, and model prescription (engineer-inventor) that is concerned with a working product. In descriptive modeling the model is the thing whereas in 'prescriptive modeling', the object is the thing. In the latter, the model (and thus its utility) serves the object, in the former model accuracy may be of primary concern. This economy of modeling provides a perspective that distinguishes the needs of the prescriptive and descriptive fields of investigation.
The mathematician-scientist is interested in increasing model accuracy at the expense of speed (slow), whereas the engineer may require a marginally predictive (less accurate) model relatively quickly. This trade-off between high-cost high-accuracy models and low-cost low-fidelity models is what may be referred to as the modeling spectrum that assists in selecting an appropriate level of modeling. Goldberg proposes that the field of Genetic Algorithms expend too much effort at either ends of this spectrum. There is much work where there is an obsession with blind-prototyping many different tweaks in the hope of striking it lucky with the right mechanism, operator, or parameter. Alternatively, there is also an obsession with detailed mathematical models such as differential equations and Markov chains. The middle ground of the spectrum, what Goldberg refers to as little models is a valuable economic modeling consideration for the investigation of conceptual machines to "do good science through good engineering".
The methodology has been referred to as post-modern systems engineering and is referred to by Goldberg as a methodology of innovation [Goldberg2004]. The core principles of the process are as follows:
Decomposition Problem decomposition and decomposition design is an axiom of reductionism and is at the very heart of problem solving in computer science. In the context of adaptive systems, one may consider the base or medium on which the system is performing its computation mechanisms the so-called building blocks of information processing. A structural decomposition may involve the architecture and data structures of the system. Additionally, one may also consider a functional breakdown of mechanisms such as the operators applied at each discrete step of an algorithmic process. The reductions achieved provide the basis of investigation and modeling.
Small Models Given the principle of the economy of modeling presented as a spectrum, one may extend the description of each of the five presented model types. Small Models refers to the middle of the spectrum, specifically to the application of dimensional and facet-wise models. These are mid-range quantitative models that make accurate prediction over a limited range of states at moderate cost. Once derived, this class of models generally require a small amount of formal manipulation and large amounts of data for calibration and verification. The following summarizes the modeling spectrum:
Facet-wise models are an exercise in simple mathematics that may be used to investigate a decomposition element of a model in relative isolation. They are based on the idea of bracketing high-order phenomena by simplifying or making assumptions about the state of the system. An example used by Goldberg from fluid mechanics is a series of equations that simplify the model by assuming that a fluid or gas has no viscosity, which matches no known substance. A common criticism of this modeling approach is "system X doesn't work like that, the model is unrealistic." The source of such concerns with adaptive systems is that their interactions are typically high-dimensional and non-linear. Goldberg's response is that for a given poorly understood area of research, any 'useful' model is better than no model. Dimensional analysis or the so-called dimensional reasoning and scaling laws are another common conceptual tool in engineering and the sciences. Such models may be used to investigate dimensionless parameters of the system, which may be considered the formalization of the systemic behaviors.
Integration Integration is a unification process of combining the findings of various models together to form a patch-quilt coherent theory of the system. Integration is not limited to holistic unification, and one may address specific hypothesis regarding the system resulting in conclusions about existing systems and design decisions pertaining to the next generation of systems.
Application In addition to elucidating the methodology, Goldberg specifies a series of five useful heuristics for the application of the methodology (taken from [Goldberg1999a], page 8):
| [Anderson1988] | P. W. Anderson and K. J. Arrow and D. Pines, "Proceedings of The Santa Fe Institute Studies in the Sciences of\n\tComplexity - Economy As an Evolving Complex System", Addison Wesley Publishing Company, 1988. |
| [Arthur1997] | W. B. Arthur, "Introduction: Process and Emergence in the Economy", in The Economy as an Evolving Complex System II, 1997. |
| [Cavicchio1970] | D. J. Cavicchio Jr., "Adaptive Search Using Simulated Evolution", [PhD Thesis] The University of Michigan, 1970. |
| [Cavicchio1972] | D. J. Cavicchio Jr., "Reproductive adaptive plans", in Proceedings of the ACM annual conference, 1972. |
| [Forrest2001] | S. Forrest and S. A. Hofmeyr, "Immunology as Information Processing", in Design Principles for the Immune System and Other Distributed Autonomous\n\tSystems, 2001. |
| [Gell-Mann1994] | M. Gell–Mann, "Complex Adaptive Systems", in Complexity: metaphors, models, and reality, 1994. |
| [Goldberg1999a] | D. E. Goldberg, "From Genetic and Evolutionary Optimization to the Design of Conceptual\n\tMachines", Evolutionary Optimization, 1999. |
| [Goldberg2004] | D. E. Goldberg, "The Design of Innovating Machines: A Fundamental Discipline for a\n\tPostmodern Systems Engineering", in Engineering Systems Symposium, 2004. |
| [Holland1975] | J. H. Holland, "Adaptation in natural and artificial systems: An introductory analysis\n\twith applications to biology, control, and artificial intelligence", University of Michigan Press, 1975. |
| [Holland1995] | J. H. Holland, "Hidden Order: How Adaptation Builds Complexity", Addison Wesley Publishing Company, 1995. |
| [Jong1975] | K. A. De Jong, "An analysis of the behavior of a class of genetic adaptive systems", [PhD Thesis] University of Michigan Ann Arbor, MI, USA, 1975. |
| [Stepney2004] | S. Stepney and R. E. Smith and J. Timmis and A. M. Tyrrell, "Towards a Conceptual Framework for Artificial Immune Systems", in Lecture Notes in Computer Science, 2004. |
| [Stepney2005] | S. Stepney and R. E. Smith and J. Timmis and A. M. Tyrrell and M. J. Neal and A. N. W. Hone, "Conceptual Frameworks for Artificial Immune Systems", International Journal of Unconventional Computing, 2005. |
| [Twycross2005] | J. Twycross and U. Aickelin, "Towards a Conceptual Framework for Innate Immunity", in Lecture Notes in Computer Science, 2005. |
Please Note: This content was automatically generated from the book content and may contain minor differences.