×

Theoretical advances in artificial immune systems. (English) Zbl 1155.68087

Summary: Artificial immune systems (AIS) constitute a relatively new area of bio-inspired computing. Biological models of the natural immune system, in particular the theories of clonal selection, immune networks and negative selection, have provided the inspiration for AIS algorithms. Moreover, such algorithms have been successfully employed in a wide variety of different application areas. However, despite these practical successes, until recently there has been a dearth of theory to justify their use. In this paper, the existing theoretical work on AIS is reviewed. After the presentation of a simple example of each of the three main types of AIS algorithm (that is, clonal selection, immune network and negative selection algorithms respectively), details of the theoretical analysis for each of these types are given. Some of the future challenges in this area are also highlighted.

MSC:

68W05 Nonnumerical algorithms
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] de Castro, L.N.; Timmis, J., Artificial immune systems: A new computational intelligence approach, (2002), Springer · Zbl 1027.68108
[2] Hart, E.; Timmis, J., Application areas of AIS: the past, the present and the future, Applied soft computing, 8, 1, 191-201, (2008)
[3] Hart, E.; Ross, P., Studies on the implications of shape – space models for idiotypic networks, (), 413-426
[4] Hart, E., Not all balls are round, ()
[5] E. Hart, Analysis of a growth model for idiotypic networks, in: H. Bersini, J. Carneiro (Eds.), 5th International Conference on Artificial Immune Systems, ICARIS, vol. 4163, 2006, pp. 66-80
[6] E. Hart, H. Bersini, F. Santos, Tolerance vs intolerance: How affinity defines topology in an idiotypic network, in: H. Bersini, J. Carneiro (Eds.), 5th International Conference on Artificial Immune Systems, ICARIS, vol. 4163, 2006, pp. 109-121
[7] Cohen, I.R., Tending adam’s garden: evolving the cognitive immune self, (2000), Elsevier Academic Press
[8] Janeway, C.A.; Medzhitov, R., Innate immune recognition, Annual review of immunology, 20, 197-216, (2002)
[9] Janeway, Charles A.; Paul, Travers, Immunobiology: the immune system in health and disease, (1997), Garland Publishing New York
[10] Germain, R.N., An innately interesting decade of research in immunology, Nature medicine, 10, 12, 1307-1320, (2004)
[11] Burnet, F.M., The clonal selection theory of acquired immunity, (1959), Cambridge University Press
[12] Forrest, S.; Perelson, A.S.; Allen, L.; Cherukuri, R., Self-nonself discrimination in a computer, ()
[13] F. Esponda, Negative representations of information, Ph.D. Thesis, University of New Mexico, 2005
[14] Jerne, N.K., Towards a network theory of the immune system, Ann. immunol. (inst. pasteur), 125C, 373-389, (1974)
[15] Farmer, J.D.; Packard, N.H.; Perelson, A.S., The immune system, adaptation, and machine learning, Physica D, 22, 187-204, (1986)
[16] Perelson, A.S., Immune network theory, Immunological reviews, 110, 5-36, (1989)
[17] Langman, R.E.; Cohn, M., The ‘complete’ idiotype network is an absurd immune system, Immunology today, 7, 4, 100-101, (1986)
[18] Varela, F.; Coutinho, A.; Dupire, B.; Vaz, N., Cognitive networks: immune, neural and otherwise, Theoretical immunology, 2, 359-375, (1988)
[19] Holland, J.H., Adaptation in natural and artificial systems, (1975), The University of Michigan Press Ann Arbor, MI
[20] Bersini, H.; Varela, F.J., Hints for adaptive problem solving gleaned from immune network, (), 343-354
[21] Bersini, H.; Varela, F., The immune learning mechansims: recruitment, reinforcement and their applications, (1994), Chapman Hall
[22] S. Forrest, A.S. Perelson, L. Allen, R. Cherukuri, Self – nonself discrimination in a computer, in: Proc. IEEE Symposium on Research Security and Privacy, 1994, pp. 202-212
[23] Hightower, R.R.; Forrest, S.A.; Perelson, A.S., The evolution of emergent organization in immune system gene libraries, (), 344-350
[24] Forrest, S.; Hofmeyr, S.; Somayaji, A., Computer immunology, Communications of the ACM, 40, 10, 88-96, (1997)
[25] Hofmeyr, S.; Forrest, S., Architecture for an artificial immune system, Evolutionary computation, 7, 1, 1289-1296, (2000)
[26] Y. Ishida, Fully distributed diagnosis by pdp learning algorithm: Towards immune network pdp model, in: Proc. of the Int. Joint Conf. on Neural Networks, 1990, pp. 777-782
[27] Ishida, Y., An immune network model and its applications to process diagnosis, Systems and computers in Japan, 24, 6, 646-651, (1993)
[28] Ishida, Y., Active diagnosis by self-organisation: an approach by the immune network metaphor, (), 1084-1089
[29] Ishida, Y., Immunity-based systems: A design perspective, (2004), Springer-Verlag Heidelberg, Germany
[30] Cooke, D.; Hunt, J., Recognising promoter sequences using an artificial immune system, (), 89-97
[31] Hunt, J.; Cooke, D., Learning using an artificial immune system, Journal of network and computer applications, 19, 189-212, (1996)
[32] Hunt, J.; Timmis, J.; Cooke, D.; Neal, M.; King, C., JISYS: development of an artificial immune system for real-world applications, (), 157-186 · Zbl 1059.68607
[33] J. Timmis, Artificial immune systems: A novel data analysis technique inspired by the immune system, Ph.D. Thesis, University of Wales, Aberystwyth, 2000
[34] de Castro, L.N.; Von Zuben, F.J., Learning and optimization using the clonal selection principle, IEEE transactions on evolutionary computation, 6, 3, 239-251, (2002)
[35] de Castro, L.N.; Von Zuben, F.J., Ainet: an artificial immune network for data analysis, (2001), Idea Group Publishing USA, 231-259
[36] Wierzchon, S.; Kuzelewska, U., Stable clusters formation in an artificial immune system, (), 68-75
[37] Neal, M., An artificial immune system for continuous analysis of time-varying data, (), 76-85
[38] Hart, E.; Ross, P., Exploiting the analogy between immunology and sparse distributed memories: A system for clustering non-stationary data, (), 49-58
[39] A. Watkins, An artificial immune recognition system, M.Sc. Thesis, Mississippi State University, 2001
[40] Watkins, A.; Timmis, J.; Boggess, L., Artificial immune recognition system (AIRS): an immune inspired supervised machine learning algorithm, Genetic programming and evolvable machines, 5, 3, 291-318, (2004)
[41] Goodman, D.; Boggess, L.; Watkins, A., An investigation into the source of power for airs, an artificial immune classification system, (), 1678-1683
[42] Goodman, D.; Boggess, L.; Watkins, A., Artificial immune system classification of multiple-class problems, (), 179-184
[43] J. Greensmoth, New frontiers for an artificial immune system, M.Sc. Thesis, School of Computing, University of Leeds, 2003
[44] A. Watkins, Exploiting immunological metaphors in the development of serial, parallel and distributed learning algorithms, Ph.D. Thesis, University of Kent, Computing Laboratory, 2005
[45] Dasgupta, D., An overview of artificial immune systems and their applications, (), 1-21, (Chapter 1) · Zbl 0923.92005
[46] Timmis, J.; Knight, T., Artificial immune systems: using the immune system as inspiration for data mining, (), 209-230
[47] Garrett, S., How do we evaluate artificial immune systems?, Evolutionary computation, 13, 2, 145-177, (2005)
[48] Timmis, J.; Bentley, P., Proc. of the 1st international conference on artificial immune systems, (2002), University of Kent Printing Unit
[49] Timmis, J.; Bentley, P.; Hart, E., ()
[50] Nicosia, G.; Cutello, V.; Bentley, P.; Timmis, J., ()
[51] Jacob, C.; Pilat, M.; Bentley, P.; Timmis, J., ()
[52] H. Bersini, J. Carneiro (Eds.), Proceedings of the 5th International Conference on Artificial Immune Systems, vol. 4163, Springer, 2006
[53] ()
[54] Freitas, A.; Timmis, J., Revisiting the foundations of artificial immune systems for data mining, IEEE transactions on evolutionary computation, 11, 4, 521-540, (2007)
[55] A.S. Perelson, G.F. Oster, Theoretical studies of clonal selection: Minimal antibody repertoire size and reliability of self-nonself discrimination, 81 (1979) 645-670
[56] Segal, L.A.; Perelson, A.S., Computations in shape – space: A new approach to immune network theory, ()
[57] Perelson, Alan S.; Weisbuch, G., Immunology for physicists, Reviews of modern physics, 69, 4, 1219-1267, (1997)
[58] Percus, J.K.; Percus, O.E.; Perelson, A.S., Predicting the size of the T-cell receptor and antibody combining region from consideration of efficient self-nonself discrimination, Proceedings of national Academy of sciences USA, 90, 1691-1695, (1993)
[59] G. Nicosia, Immune algorithms for optimisation and protein structure prediction, Ph.D. Thesis, Department of Mathematics and Computer Science, University of Catania, Italy, 2004
[60] Kelsey, J.; Timmis, J., Immune inspired somatic contiguous hypermutation for function optimisation, (), 207-218 · Zbl 1028.68801
[61] Coello Coello, C.A.; Cruz Cortes, N., An approach to solve multiobjective optimization problems based on an artificial immune system, () · Zbl 1028.68714
[62] N. Cruz Cortes, C. Coello Coello, Multiobjective optimisation using ideas from the clonal selection principle, in: E. Cantu-Paz (Ed.), Genetic and Evolutionary Computation (GECCO), vol. 1, 2003, pp. 158-170 · Zbl 1028.68714
[63] Mitchell, M., An introduction to genetic algorithms, (1999), The MIT Press
[64] Clark, E.; Hone, A.; Timmis, J., A Markov chain model of the B-cell algorithm, (), 318-330
[65] de Castro, L.N.; von Zuben, F.J., An evolutionary immune network for data clustering, (), 84-89
[66] de Castro, L.N.; von Zuben, F.J., Ainet: an artificial immune network for data analysis, (), 231-259, (Chapter 12)
[67] Grimmett, G.R.; Stirzaker, D.R., Probability and random processes, (1982), Oxford University Press · Zbl 0759.60002
[68] Villalobos-Arias, M.; Coello Coello, C.A.; Hernandez-Lerma, O., Convergence analysis of a multiobjective artificial immune system algorithm, Lecture notes in computer science, 3239, 226-235, (2004)
[69] Nix, A.E.; Vose, M.D., Modeling genetic algorithms with Markov chains, Annals of mathematics and artificial intelligence, 5, 79-88, (1992) · Zbl 1034.68534
[70] Vose, M.D., Modeling simple genetic algorithms, ()
[71] Rudolph, G., Finite Markov chain results in evolutionary computation: A tour d’horizon, Fundamenta informaticae, 35, 1-4, 67-89, (1998) · Zbl 0943.68060
[72] V. Cutello, G. Nicosia, P. Oliveto, M. Romeo, On the convergence of immune algorithms, in: Proc.of Foundations of Computational Intelligence, 2007, pp. 409-416
[73] Seneta, E., Non-negative matrices and Markov chains, (1981), Springer-Verlag New York · Zbl 0471.60001
[74] Robert, F., LES systèmes dynamiques discrets, (1995), Springer-Verlag Berlin · Zbl 0843.93005
[75] Jordan, D.W.; Smith, P., Nonlinear ordinary differential equations, (1999), Oxford University Press Oxford · Zbl 0955.34001
[76] Elaydi, S., Discrete chaos, (2000), Chapman and Hall/CRC Boca Raton · Zbl 0945.37010
[77] Hone, A.; Kelsey, J., Optima, extrema and artificial immune systems, (), 89-98
[78] Goncharova, Larisa B.; Tarakanov, Alexander O.; Melnikov, Yuri, Biomolecular immunocomputing, (), 102-110
[79] Tarakanov, A.O.; Skormin, V.A.; Sokolova, S.P., Immunocomputing: principles and applications, (2003), Springer-Verlag New York, NY · Zbl 1040.68063
[80] Feller, William, An introduction to probability theory and its applications, vol. 1, (1968), John Wiley & Sons · Zbl 0077.12201
[81] M.T. Ranang, An artificial immune system approach to preserving security in computer networks, Master’s Thesis, Norges Teknisk-Naturvitenskapelige Universitet, 2002
[82] Uspensky, James Victor, Introduction to mathematical probability, (1937), McGraw-Hill
[83] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C., Introduction to algorithms, (2002), MIT Press
[84] Robinson, J.A., A machine-oriented logic based on the resolution principle, Journal of the association for computing machinery (JACM), 12, 1, 23-41, (1965) · Zbl 0139.12303
[85] Welzl, E., Boolean satisfiability — combinatorics and algorithms, ()
[86] Brueggemann, T.; Kern, W., An improved deterministic local search algorithm for 3-SAT, Theoretical computer science, 329, 1-3, 303-313, (2004) · Zbl 1086.68051
[87] Hofmeister, T.; Schöning, U.; Schuler, R.; Watanabe, O., A probabilistic 3-SAT algorithm further improved, (), 192-202 · Zbl 1054.68138
[88] Schöning, U., A probabilistic algorithm for \(k\)-SAT and constraint satisfaction problems, (), 410-414
[89] Langdon, W.B.; Poli, R., Foundations of genetic programming, (2002), Springer-Verlag Berlin · Zbl 0993.68039
[90] Hone, A.; van den Berg, H., Mathematical analysis of artificial immune system dynamics and performance, (), 351-374
[91] Stepney, S.; Smith, R.; Timmis, J.; Tyrrell, A.; Neal, M.; Hone, A., Conceptual frameworks for artificial immune systems, International journal of unconventional computing, 1, 3, 315-338, (2005)
[92] Timmis, J., Artificial immune systems: today and tommorow, Natural computing, 6, 1, (2007) · Zbl 1116.68068
[93] J. Greensmith, U. Aickelin, J. Twycross, Articulation and clarification of the dendritic cell algorithm, in: H. Bersini, J. Carneiro (Eds.), Proceedings of the 5th International Conference on Artificial Immune Systems, vol. 4163, 2006, pp. 404-417
[94] P.J. Bentley, J. Greensmith, S. Ujjin, Two ways to grow tissue for Artificial Immune Systems, In Jacob et al. [51], pp. 139-152
[95] Sieburg, H.B.; Clay, O.K., The cellular device machine development system for modeling biology on the computer, Complex systems, 5, 575-601, (1991) · Zbl 0781.92003
[96] C. Kuttler, J. Niehren, R. Blossey, Gene regulation in the pi calculus: Simulating cooperativity at the lambda switch, in: Proc Concurrent Models in Molecular Biology, Bioconcur 04, 2004
[97] A. Phillips, L. Cardelli, A correct abstract machine for the stochastic pi-calculus, in: Proc Concurrent Models in Molecular Biology, Bioconcur’04, ENTCS, 2004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.