Devising New AlgorithmsThis 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:
Adaptive SystemsMany 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. Adaptive Systems FormalismThis 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$.
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$).
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)).
Some ExamplesHolland provides a series of illustrations rephrasing common adaptive systems in the context of the formalism [Holland1975] (pages 3536). 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 159160):
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 onetoone, 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 representationsolution 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 (componentwise) 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 betterperforming 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. Complex Adaptive SystemsAdaptive strategies are typically complex because they result in irreducible emergent behaviors that occur as a result of the nonlinear interactions of system components. The study of Complex Adaptive Systems (CAS) is the study of highlevel abstractions of natural and artificial systems that are generally impervious to traditional analysis techniques. Macroscopic patterns emerge from the dynamic and nonlinear interactions of the system's lowlevel (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 'bottomup' 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 problemsolving 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 GellMann [GellMann1994] and Arthur [Arthur1997]. Biologically Inspired AlgorithmsExplicit 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). Conceptual FrameworkAlthough 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:
Immunology as Information ProcessingForrest 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 spatiotemporal 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 fourstep 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. Modeling a New StrategyOnce 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 tradeoff's in modeling an adaptive technique. Engineers and MathematiciansGoldberg 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 counterproductive 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 tradeoff that distinguishes 'model description' (mathematicianscientists) that is concerned with model fidelity, and model prescription (engineerinventor) 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 mathematicianscientist 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 tradeoff between highcost highaccuracy models and lowcost lowfidelity 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 blindprototyping 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". MethodologyThe methodology has been referred to as postmodern 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 socalled 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 facetwise models. These are midrange 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:
Facetwise 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 highorder 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 highdimensional and nonlinear. 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 socalled 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 patchquilt 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):
Bibliography

Free CourseGet one algorithm per week...
Own A CopyThis 438page ebook has...


Please Note: This content was automatically generated from the book content and may contain minor differences. 

Do you like Clever Algorithms? Buy the book now. 