×

Immune programming. (English) Zbl 1092.68042

Summary: This paper describes ‘immune programming’, a paradigm in the field of evolutionary computing taking its inspiration from principles of the vertebrate immune system. These principles are used to derive stack-based computer programs to solve a wide range of problems.
An antigen is used to represent the programming problem to be addressed and may be provided in closed form or as an input/output mapping. An antibody set (a repertoire), wherein each member represents a candidate solution, is generated at random from a gene library representing computer instructions. Affinity, the fit of an antibody (a solution candidate) to the antigen (the problem), is analogous to shape-complementarity evident in biological systems. This measure is used to determine both the fate of individual antibodies, and whether or not the algorithm has successfully completed.
When a repertoire has not yielded affinity relating algorithm completion, individual antibodies are replaced, cloned, or hypermutated. Replacement occurs according to a replacement probability and yields an entirely new randomly generated solution candidate when invoked. This randomness (and that of the initial repertoire) provides diversity sufficient to address a wide range of problems. The chance of antibody cloning, wherein a verbatim copy is placed in the new repertoire, occurs proportionally to its affinity and according to a cloning probability. The chances of an effective (high-affinity) antibody being cloned is high, analogous to replication of effective pathogen-fighting antibodies in biological systems. Hypermutation, wherein probability-based replacement of the gene components within an antibody occurs, is also performed on high-affinity entities. However, the extent of mutation is inversely proportional to the antigenic affinity. The effectiveness of this process lies in the supposition that a candidate showing promise is likely similar to the ideal solution.
This paper describes the paradigm in detail along with the underlying immune theories and their computational models. A set of sample problems are defined and solved using the algorithm, demonstrating its effectiveness and excellent convergent qualities. Further, the speed of convergence with respect to repertoire size limitations and probability parameters is explored and compared to stack-based genetic programming algorithms.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68T05 Learning and adaptive systems in artificial intelligence
68N99 Theory of software

Software:

Genocop
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ada, G.L.; Nossal, G.J.V., The clonal selection theory, Scientific American, 257, 2, 50-57, (1987)
[2] L.N. De Castro, F.J. Von Zuben, The clonal selection algorithm with engineering applications, GECCO’00—Workshop Proceedings (2000) 36-37.
[3] De Castro, L.N.; Von Zuben, F.J., Learning and optimization using the clonal selection principle, IEEE transactions on evolutionary computing, 3, 6, 239-251, (2002)
[4] De Castro, L.N.; Timmis, J.I., Artificial immune systems: A new computational intelligence paradigm, (2002), Springer-Verlag · Zbl 1027.68108
[5] De Castro, L.N.; Timmis, J.I., Artificial immune systems as a novel soft computing paradigm, Soft computing, 7, 526-544, (2003)
[6] Coello, C.A.; Cortés, N.C., Hybridizing a genetic algorithm with an artificial immune system for global optimization, Engineering optimization, 36, 5, 607-634, (2004)
[7] Dasgupta, D.; Ji, A.; González, F., Artificial immune system (AIS) research in the last five years, (), 123-130
[8] Eiben, A.E.; Smith, J.E., Introduction to evolutionary computing, (2003), Springer · Zbl 1028.68022
[9] Fogel, L.J.; Owens, A.J.; Walsh, M.J., Artificial intelligence through simulated evolution, (1966), John Wiley · Zbl 0148.40701
[10] Fogel, D.B., Evolutionary computation: toward a new philosophy of machine intelligence, (1999), IEEE Press Piscataway, NJ · Zbl 0944.68061
[11] Forrest, S.; Hofmeyr, S.; Somayaji, A., Computer immunology, Communications of the ACM, 40, 10, 86-96, (1997)
[12] Forrest, S.; Perelson, A.; Allen, L.; Cherukuri, R., Self-nonself discrimination in a computer, Proceedings of the IEEE symposium on research in security and privacy, 202-212, (1994)
[13] Forrest, S.; Javornik, B.; Smith, R.E.; Perelson, A.S., Using genetic algorithms to explore pattern recognition in the immune system, Evolutionary computation, 1, 3, 191-211, (1993)
[14] Gao, W., Fast immunized evolutionary programming, Proceedings of the congress on evolutionary computation, 1, 666-670, (2004)
[15] Holland, J.H., Adaptation in natural and artificial systems, (1975), University of Michigan Press Ann Arbor, MI
[16] Jerne, N.K., Towards a network theory of the immune system, Annales D immunologie (inst. pasteur), 125C, 373-389, (1974)
[17] Juillé, H.; Pollack, J.B.; Siegel, E.V.; Koza, J.R., Parallel genetic programming on fine-grained SIMD architectures, Working notes of the AAAI-95 fall symposium on genetic programming, (1995), AAAI Press
[18] Koopman, P.J., Stack computers: the new wave, (1989), Ellis Horwood
[19] Koza, J.R., Genetic programming, (1992), MIT Press Cambridge, MA · Zbl 0850.68161
[20] Koza, J.R.; Streeter, M.J.; Keane, M., Routine high-return human-competitive machine learning, (), 6-12
[21] Luger, G.F., Artificial intelligence: structures and strategies for complex problem solving, (2002), Addison-Wesley
[22] Luo, W.; Cao, X.; Wang, X., An immune genetic algorithm based on immune regulation, (), 801-806
[23] McCoy, D.F.; Devaralan, V., Artificial immune systems and aerial image segmentation, Proceedings of the SMC’97, 867-872, (1997)
[24] Michalewicz, Z., Genetic algorithms+data structures=evolution programs, (1996), Springer-Verlag Heidelberg · Zbl 0841.68047
[25] Nikolaev, N.I.; Iba, H.; Slavov, V., Inductive genetic programming with immune network dynamics, (), 355-376
[26] Nossal, G.J.V., Negative selection of lymphocytes, Cell, 76, 229-239, (1994)
[27] Nossal, G.J.V., The molecular and cellular basis of affinity maturation in the antibody response, Cell, 68, 1-2, (1993)
[28] Perelson, A.S.; Oster, G.F., Theoretical studies of clonal selection: minimal antibody repertoire size and reliability of self-non-self discrimination, Journal of theoritical biology, 81, 4, 645-670, (1979)
[29] Perkis, T., Stack-based genetic programming, (), 148-153
[30] Stoffel, K.; Spector, L.; Koza, J.R.; etal., High-performance, parallel, stack-based genetic programming, Genetic programming 1996: Proceedings of the first annual conference, (1996), MIT Press, pp. 224-229
[31] Timmis, J.; Edmonds, C.; Kelsey, J., Assessing the performance of two immune inspired algorithms and a hybrid genetic algorithm for function optimisation, Proceedings of the congress on evolutionary computation, 1, 1044-1051, (2004)
[32] Wierzchoń, S.T., Function optimization by the immune metaphor, Task quarterly, 6, 3, 493-508, (2002)
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.