Mike Mertsock

• March 2006
• Genetic Algorithms

Abstract

Recent advances in our understanding of the immune system of vertebrates has led to the investigation of its computational capabilities. The information-processing capability and the complexity of the immune system is often compared to the brain. A computational model inspired by the immune system, called the artificial immune system (AIS), demonstrates capabilities and uses similar to those of artificial neural networks (ANNs) and genetic algorithms. AIS has applications in security, pattern matching, and other areas. After describing the foundations of AIS, this paper compares the system to both ANNs and genetic algorithms. These comparisons reveal relationships that suggest a definite ordering of the three paradigms within a common theoretical space.

Introduction

The artificial immune system (AIS) is a working computational model of the vertebrate immune system. In a manner similar to artificial neural networks (ANNs) and genetic algorithms (GAs), an AIS uses metaphors of the immune system to produce a practical intelligent system for solving hard problems. It is composed of many simple components (strings representing immune system cells and molecules) that learn the solution to a complex problem, generally in terms of a pattern-recognition problem. Selection, mutation, and communication mechanisms based on corresponding biological models are the forces of change and learning in the AIS; the choice of mechanisms varies among applications. The AIS program evolves a population of strings that collectively know a (possibly large) set of patterns and can classify inputs based on the patterns learned in terms of self and nonself [2].

Though a relatively new idea, artificial immune systems have already been applied in many areas of industry and research. There has been much research in the use of AIS in computer security. Kim and Bentley [9] have explored its use in network intrusion detection. Several authors (see references in [2]) have discussed a distributed AIS for computer security. Dasgupta [1] proposed an “immune agent architecture” for intrusion detection. In other fields, the pattern-recognition capabilities of artificial immune systems have been applied to, for example, aerial image segmentation [10] and clustering problems.

As an intelligent systems paradigm, AIS complements both neural networks and genetic algorithms. At a general level, AIS is used for pattern recognition and learning applications similar to ANNs, and incorporates evolutionary processes [3] such as selection, mutation, and populations of whole individuals. AIS is inspired by and modeled after the immune system in a way similar to ANNs and the human brain. All three paradigms provide effective but probabilistic solutions to hard problems.

The following sections begin with a more thorough examination of the biological foundations of AIS and the information-processing abstractions common to both the biological and artificial immune systems. The remainder of the paper explores the relationships among AIS, ANNs, and GAs, covering three characteristics in detail.

The Immune System as Information Processor

The immune system protects the body’s cells (self) in two ways: the recognition of antigens (self/nonself discrimination [2]), and the immune response. Lymphocytes (B-cells and T-cells) in the immune system recognize antigens (molecules on the surface of recognizable cells) by matching the antigen to receptors on the lymphocyte cell. Each cell has one receptor pattern matching a single antigen or set of similar antigens to some level of affinity. Self antigens (members of the body’s cells) are ignored, and the recognition of nonself antigens (foreign objects/organisms) can trigger the immune response. Each lymphocyte (antibody) is a free object in the body and has one receptor pattern matching the complement of some antigen pattern (epitope), as illustrated above.

Two selection processes, clonal selection and negative selection, affect the proliferation and maturation of B-cells and T-cells, respectively. Clonal selection replicates B-cells when they successfully match antigens. Each clone undergoes a high mutation rate, inversely proportional to the match affinity of the parent. As T-cells mature in an environment free of nonself antigens, negative selection suppresses T-cells that recognize self antigens; T-cells therefore know, and tolerate, self, and will thus respond to nonself antigens—they match the complement of the self-set instead of directly recognizing members of the nonself set [2].

Lymphocytes interact in a variety of ways; they can recognize each other as antigens, support or suppress the immune response, and affect each other during selection. The complex interactions arise even in a stable environment and form a sort of dynamic equilibrium [8]. This immune network theory is debated but still useful for AIS.

The immune system is often compared in its complexity and information-processing roles to the brain [2]. Because it recognizes and responds to stimuli (microorganisms and cells) beyond the reach of sensory perception and thus conscious awareness, it “performs an accessory role to human cognition.” [5] One of the first major breakthroughs in immunology was the discovery that the immune system is not controlled by a central organ [6] but is a self-regulating distributed network of lymphocytes. This concept is the foundation for the diversity of antigens the system recognizes and the adaptability of the system, and is at the core of any variety of AIS. Each lymphocyte computes a decision problem by matching certain antigens. They are both the agents that can communicate and recognize patterns, and are themselves the patterns that compose the knowledge of the system; they can “can recognize as well as be recognized.” [8]

Artificial Immune Systems

Artificial immune systems evolve a population of strings, representing the patterns known by individual lymphocytes, to solve a particular pattern-recognition problem. Patterns are usually represented as strings of bits. In general, each pattern string exists as a vector in a Hamming shape-space [11] of D dimensions that encodes D properties of the (biological or metaphorical) antigen. Pattern recognition involves measuring the Hamming distance between an antigen and the bitwise complement of each pattern in the population (see above), resulting in a match whenever the distance is within a specified affinity threshold. Note that the lymphocyte patterns and the antigen patterns share the same representation scheme.

The general form of any AIS algorithm is to determine a representation scheme, generate a random population of pattern strings, and then perform clonal or negative selection to learn the self or nonself set, respectively; the system is then ready to use. Note that an AIS has a training/learning phase similar to ANNs, and has selection and mutation mechanisms similar to GAs. Clonal selection is usually implemented as a close model of the biological process. CLONALG [4] is a well-known implementation of clonal selection. Forrest et. al. state that a genetic algorithm with no crossover can provide an approximation of clonal selection [6].

AIS applications use various combinations of one or more of the clonal selection, negative selection, and network theory concepts. For example, an AIS discussed in [7] learns the self-behavior of a computer system through negative selection in order to identify anomalies. By matching the complement of self rather than directly matching nonself strings, the system would be able to detect anomalies that had never before been observed. This is quite different from the operation of most antivirus programs.

Comparing AIS to Other Paradigms

Intuitively, artificial immune systems lie on a middle ground between artificial neural networks and genetic algorithms. This has been implied by much of the discussion thus far. A more thorough analysis of the components, knowledge representation, and interaction of each paradigm will suggest more precisely how they are related. In addition to the areas covered below, de Castro and Timmis [2] compare several other aspects.

Components

All three paradigms are based on a collection of small, more or less homogeneous components. The artificial neuron is the unit component of an ANN. The neuron processes its input, which may or may not be the original input signal, and responds with an output signal based on connection weights, an activation function, and a threshold. The artificial neuron is a reactive element, a data processor whose input and output are of primary concern, and the information stored within a single neuron is in itself of less importance. Representation of knowledge is implicit and distributed, and information processing, though it acts as a unit, is distributed among the set of homogeneous (in terms of the signal processing algorithm) artificial neurons.

The genetic algorithm works with a population of chromosomes. Each chromosome is pure representation, the complement of an artificial neuron: it passively stores data and by itself has no knowledge of how the data is processed. The fitness function, which is external to the chromosome, is responsible for interpreting the chromosome. Thus, the information processing component is explicit, external to the data representation, and a single unit.

The AIS is composed of shape-space strings that are both descriptive and reactive. Each string is both a pattern that recognizes antigens and influences other components, and a pattern that can be recognized by others. Information processing and representation are thus distributed through the system, and are both explicit and visible. Figure 1 illustrates the comparison of ANN, AIS, and GA components in terms of internal/external and implicit/explicit data representation and data processing.

Knowledge and Memory

Chromosomes in genetic algorithms store individual genotypes. However, as the goal is to find one or a few optimal points within the search space, redundancy actually increases over time as individuals converge upon the optimal points. The final output is an optimal subset of the population. Schemata in GAs relate the information represented by chromosomes in a generic, horizontal way. The schemata operate on fragments of chromosomes and relate members of the same population. Similarly, crossover maps chromosomes to chromosomes, but does not require domain-specific knowledge to work properly; the chromosomes are nothing more than strings from the perspective of crossover.

The strings of an AIS “constitute most of the knowledge contained in an artificial immune system.” [2] Each string is a somewhat independent unit that is meaningful in itself (as a single pattern within the repertoire of an AIS). However, the whole is greater than the sum of its parts, not only because a greater number of unique patterns may be represented in the strings, but the presence of more self-strings can improve the accuracy of an existing system. Because each string pattern is a meaningful unit of information, techniques such natural death rates are used to prune the population, encourage more diversity, etc. The knowledge of the system is only complete with the full set of patterns. In the AIS, a schema concept operates on whole patterns: the coverage of an antibody’s pattern matches number of patterns determined by the affinity threshold ɛ [5]. For example, an affinity threshold 2 allows an antibody to match (bind) any pattern whose complement has a Hamming distance of no more than 2 from the antibody’s pattern. Figure 2 illustrates this concept in the shape space S: the value of ɛ determines the coverage of an antibody pattern.

The only domain-meaningful knowledge stored in ANNs is the network itself; the whole is greater than the sum of its parts. Knowledge about the classification of its input is only available through the behavior of the entire system—the network is a black box. The memory of the system is distributed and holistic, so the information (connection weights, aggregation function, and threshold) at an individual neuron is meaningless in isolation. ANNs have no clear concept of schemata, for two reasons: (1) an artificial neuron is (usually) connected with real-valued weights to every neuron in the layers above and below it, so this total connectedness makes it difficult to describe the relationships among specific subsets of neurons, and (2) the only meaningful unit of knowledge representation is the ANN as a whole.

Structure and Interaction

Most ANNs have a relatively static physical structure: artificial neurons are organized into layers, and each neuron in layer k connects to every neuron in layer k + 1. This structure is determined at design time and typically does not change; only the weights and thresholds of particular neurons may change. Neurons only know about the neurons to which they are connected. Both forward- and back-propagation send information specifically along these connections. The structure, therefore, is just as important as its elements.

A population of genetic algorithm chromosomes is generally unstructured, except for a usually-constant population size. Chromosomes may appear in any order and duplicates can and do appear, without degrading the behavior of the system. The only time that any order is imposed upon the population is externally, by the fitness function or specialized selection operators.

AIS strings are not placed in a physical structure; they are free to interact with any and all antigens and epitopes. The immune network theory discusses various ways in which immune cells form chains of pattern recognition and other such associations dynamically. These dynamic structures appear in response to the environment and influence the final behavior of the AIS.

The three paradigms also interact differently with their environments (inputs); see Figure 3. Neural networks act as external observers of the environment, processing the input in a structure separate in location and encoding from the environment. AIS antibodies are metaphorically situated within the environment; their encoding is the same as the environment’s inputs, and antibodies can recognize both their inputs and other antibodies within this context. In genetic algorithms, the situation is reversed. The environment (fitness function) is the information processor and acts upon the data (chromosomes).

Summary

At a highly subjective level, the three paradigms represent expanding scopes of intelligent system metaphors: ANNs represent the mind’s cognition, AIS represent the body’s cognition, and GAs represent the species’ cognition. This theme is quite apparent in the discussion of the three aspects above, and can be seen when comparing many other aspects of these paradigms.

Conclusion

Artificial immune systems show the potential to provide capable solutions in a wide variety of pattern recognition problems. They use simplified models of the vertebrate immune system to learn a collection of self and nonself patterns; the system can then be applied to pattern recognition tasks such as intrusion detection, clustering, image segmentation, and others. The mechanics of AIS use specialized evolutionary principles such as selection and mutation, which are applied to units (pattern strings) that both store the patterns to recognize and affect the behavior of the system by reacting to recognized patterns.

Comparing artificial immune systems, artificial neural networks, and genetic algorithms reveals many common threads among the paradigms. After studying their relationships in three specific areas, a continuum from ANNs to AIS to GAs is apparent. A more formal investigation of these paradigms in terms of information processing theory may lead to an intelligent system model that unifies the three paradigms as a spectrum of models within one parameter space. Such a model could allow for making more confident and objective design decisions about a specific ANN/AIS/GA implementation.

The similarities of the three paradigms suggests the possibility of building hybrid systems using two or more of the paradigms. In fact, descriptions of several ANN/AIS and AIS/GA hybrid systems have already been published.