Clever Algorithms: Nature-Inspired Programming Recipes

By Jason Brownlee PhD

Home | Free Course | Read Online



This is the ad-supported version of the book. Buy it now if you like it.

Immune Algorithms

Overview

This chapter describes Immune Algorithms.

Immune System

Immune Algorithms belong to the Artificial Immune Systems field of study concerned with computational methods inspired by the process and mechanisms of the biological immune system.

A simplified description of the immune system is an organ system intended to protect the host organism from the threats posed to it from pathogens and toxic substances. Pathogens encompass a range of micro-organisms such as bacteria, viruses, parasites and pollen. The traditional perspective regarding the role of the immune system is divided into two primary tasks: the detection and elimination of pathogen. This behavior is typically referred to as the differentiation of self (molecules and cells that belong to the host organisms) from potentially harmful non-self. More recent perspectives on the role of the system include a maintenance system [Cohen2001a], and a cognitive system [Varela1994].

The architecture of the immune system is such that a series of defensive layers protect the host. Once a pathogen makes it inside the host, it must contend with the innate and acquired immune system. These interrelated immunological sub-systems are comprised of many types of cells and molecules produced by specialized organs and processes to address the self-nonself problem at the lowest level using chemical bonding, where the surfaces of cells and molecules interact with the surfaces of pathogen.

The adaptive immune system, also referred to as the acquired immune system, is named such because it is responsible for specializing a defense for the host organism based on the specific pathogen to which it is exposed. Unlike the innate immune system, the acquired immune system is present only in vertebrates (animals with a spinal column). The system retains a memory of exposures which it has encountered. This memory is recalled on reinfection exhibiting a learned pathogen identification. This learning process may be divided into two types of response. The first or primary response occurs when the system encounters a novel pathogen. The system is slow to respond, potentially taking a number of weeks to clear the infection. On re-encountering the same pathogen again, the system exhibits a secondary response, applying what was learned in the primary response and clearing up the infection rapidly. The memory the system acquires in the primary response is typically long lasting, providing pathogenic immunity for the lifetime of the host, two common examples of which are the chickenpox and measles. White blood cells called lymphocytes (or leukocytes) are the most important cell in the acquired immune system. Lymphocytes are involved in both the identification and elimination of pathogen, and recirculate within the host organisms body in the blood and lymph (the fluid that permeates tissue).

Artificial Immune Systems

Artificial Immune Systems (AIS) is a sub-field of Computational Intelligence motivated by immunology (primarily mammalian immunology) that emerged in the early 1990s (for example [Bersini1990] [Ishida1990]), based on the proposal in the late 1980s to apply theoretical immunological models to machine learning and automated problem solving (such as [Hoffmann1986] [Farmer1986]). The early works in the field were inspired by exotic theoretical models (immune network theory) and were applied to machine learning, control and optimization problems. The approaches were reminiscent of paradigms such as Artificial Neural Networks, Genetic Algorithms, Reinforcement Learning, and Learning Classifier Systems. The most formative works in giving the field an identity were those that proposed the immune system as an analogy for information protection systems in the field of computer security. The classical examples include Forrest et al.'s Computer Immunity [Forrest1994] [Forrest1997a] and Kephart's Immune Anti-Virus [Kephart1994] [Kephart1995]. These works were formative for the field because they provided an intuitive application domain that captivated a broader audience and assisted in differentiating the work as an independent sub-field.

Modern Artificial Immune systems are inspired by one of three sub-fields: clonal selection, negative selection and immune network algorithms. The techniques are commonly used for clustering, pattern recognition, classification, optimization, and other similar machine learning problem domains.

The seminal reference for those interested in the field is the text book by de Castro and Timmis "Artificial Immune Systems: A New Computational Intelligence Approach" [Castro2002]. This reference text provides an introduction to immunology with a level of detail appropriate for a computer scientist, followed by a summary of the state of the art, algorithms, application areas, and case studies.

Algorithms

Extensions

There are many other algorithms and classes of algorithm that were not described from the field of Artificial Immune Systems, not limited to:

  • Clonal Selection Algorithms: such as the B-Cell Algorithm [Kelsey2003], the Multi-objective Immune System Algorithm (MSIRA) [Coello2002] [Cortes2003] and the the Optimization Immune Algorithm (opt-IA, opt-IMMALG) [Cutello2002a] [Cutello2002] and the Simple Immunological Algorithm [Cutello2005b].
  • Immune Network Algorithms: such as the approach by Timmis used for clustering called the Artificial Immune Network (AIN) [Timmis2000] (later extended and renamed the Resource Limited Artificial Immune System [Timmis2001] [Timmis2000a].
  • Negative Selection Algorithms: such as an adaptive framework called the ARTificial Immune System (ARTIS), with the application to intrusion detection renamed the Lightweight Intrusion Detection System (LISYS) [Hofmeyr1999] [Hofmeyr2000].

Bibliography

[Bersini1990] H. Bersini and F. Varela, "Hints for Adaptive Problem Solving Gleaned from Immune Networks", in Lecture Notes In Computer Science, 1990.
[Castro2002] L. N. de Castro and J. Timmis, "Artificial Immune Systems: A New Computational Intelligence Approach", Springer, 2002.
[Coello2002] C. A. Coello Coello and N. C. Cortés, "An Approach to Solve Multiobjective Optimization Problems Based on an Artificial Immune System", in First International Conference on Artificial Immune Systems, 2002.
[Cohen2001a] I. R. Cohen, "Tending Adam's Garden: Evolving the Cognitive Immune Self", Academic Press, 2001.
[Cortes2003] N. C. Cortés and C. A. Coello Coello, "Multiobjective Optimization Using Ideas from the Clonal Selection Principle", in Lecture Notes in Computer Science, 2003.
[Cutello2002] V. Cutello and G. Nicosia, "Multiple learning using immune algorithms", in Proceedings of 4th International Conference on Recent Advances in Soft Computing, RASC 2002, 2002.
[Cutello2002a] V. Cutello and G. Nicosia, "An Immunological Approach to Combinatorial Optimization Problems", in Lecture Notes In Computer Science, 2002.
[Cutello2005b] V. Cutello and G. Nicosia, "Chapter VI. The Clonal Selection Principle for In Silico and In Vivo Computing", in Recent Developments in Biologically Inspired Computing, 2005.
[Farmer1986] J. D. Farmer and N. H. Packard and Alan S. Perelson, "The immune system, adaptation, and machine learning", Physica D, 1986.
[Forrest1994] S. Forrest and A. S. Perelson and L. Allen and R. Cherukuri, "Self-Nonself Discrimination in a Computer", in Proceedings of the 1992 IEEE Symposium on Security and Privacy, 1994.
[Forrest1997a] S. Forrest and S. A. Hofmeyr and A. Somayaji, "Computer immunology", Communications of the ACM, 1997.
[Hoffmann1986] G. W. Hoffmann, "A Neural Network Model Based on the Analogy with the Immune System", Journal of Theorectical Immunology, 1986.
[Hofmeyr1999] S. Hofmeyr and S. Forrest, "Immunity by Design: An Artificial Immune System", in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 1999.
[Hofmeyr2000] S. A. Hofmeyr and S. Forrest, "Architecture for an Artificial Immune System", Evolutionary Computation, 2000.
[Ishida1990] Y. Ishida, "Fully distributed diagnosis by PDP learning algorithm: towards immune network PDP models", in IJCNN International Joint Conference on Neural Networks, 1990.
[Kelsey2003] J. Kelsey and J. Timmis, "Immune Inspired Somatic Contiguous Hypermutation for Function Optimisation", in Lecture Notes in Computer Science, 2003.
[Kephart1994] J. O. Kephart, "A Biologically Inspired Immune System for Computers", in Artificial Life IV, 1994.
[Kephart1995] J. O. Kephart and G. B. Sorkin and W. C. Arnold and D. M. Chess and G. J. Tesauro and S. R. White, "Biologically inspired defences against computer viruses", in Proceedings of the 14th International Joint Conference on Artificial Intelligence, 1995.
[Timmis2000] J. Timmis and M. Neal and J. Hunt, "An Artificial Immune System for Data Analysis", Biosystems, 2000.
[Timmis2000a] J. Timmis and M. Neal, "Investigating the evolution and stability of a resource limited artificial immune system", in Workshop Program, 2000.
[Timmis2001] J. Timmis and M. J. Neal, "A resource limited artificial immune system for data analysis", Knowledge Based Systems Journal: Special Issue, 2001.
[Varela1994] F. J. Varela, "A cognitive view of the immune system", World Futures, 1994.
Clever Algorithms: Nature-Inspired Programming Recipes

Free Course

Get one algorithm per week...
  • ...delivered to your inbox
  • ...described in detail
  • ...to read at your own pace
Sign-up Now












Own A Copy

This 438-page ebook has...
  • ...45 algorithm descriptions
  • ...best practice usage
  • ...pseudo code
  • ...Ruby code
  • ...primary sources
Buy Now




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

Clever Algorithms: Nature-Inspired Programming Recipes



Do you like Clever Algorithms?
Buy the book now.


© Copyright 2014. All Rights Reserved. | About | Contact | Privacy