The Clonal Selection Algorithm with Engineering Applications (Задание 5)

The Clonal Selection Algorithm with Engineering Applications 1Leandro Nunes de CastroFernando J. Von Zubenlnunes@dca.fee.unicamp.brSchool of Electrical and Computer Engineering (FEEC)State University of Campinas (UNICAMP)Campinas-SP – Brazilvonzuben@dca.fee.unicamp.brSchool of Electrical and Computer Engineering (FEEC)State University of Campinas (UNICAMP)Campinas-SP – BrazilAbstractThe clonal selection algorithm is used by thenatural immune system to define the basicfeatures of an immune response to an antigenicstimulus. It establishes the idea that only thosecells that recognize the antigens are selected toproliferate.

The selected cells are subject to anaffinity maturation process, which improves theiraffinity to the selective antigens. In this paper,we propose a powerful computationalimplementation of the clonal selection principlethat explicitly takes into account the affinitymaturation of the immune response. Thealgorithm is shown to be an evolutionarystrategy capable of solving complex machinelearning tasks, like pattern recognition and multimodal optimization.1INTRODUCTIONOver the last few years, there has been an ever increasinginterest in the area of artificial immune systems (AIS) andtheir applications.

Among the many works in this newfield of research, we can detach those of Ishida (1996);Hunt & Cook (1996); Dasgupta (1999) and Hofmeyr &Forrest (1999). The AIS aim at using ideas gleaned fromimmunology in order to develop systems capable ofperforming different tasks in various areas of research.In this work, we will review the clonal selection concept,together with the affinity maturation process, anddemonstrate that these biological principles can lead tothe development of powerful computational tools.

Thealgorithm to be presented focus on a systemic view of theimmune system and does not take into account cell-cellinteractions. It is not our goal to model exactly anyphenomenon, but to show that some basic immuneprinciples can help us not only to better understand theimmune system itself, but also to solve complexengineering tasks.1First, we are going to apply the clonal selection algorithmto binary character recognition to verify its ability toperform tasks such as learning and memory acquisition.Then it will be shown that the same algorithm is suitablefor solving multi-modal and combinatorial optimization.This work is concluded with a brief discussion relatingthe proposed clonal selection algorithm with the wellknown genetic algorithms introduced by Holland (1995).2THE CLONAL SELECTION THEORYWhen an animal is exposed to an antigen, somesubpopulation of its bone marrow derived cells (Blymphocytes) respond by producing antibodies (Ab).Each cell secretes only one kind of antibody, which isrelatively specific for the antigen.

By binding to theseantibodies (receptors), and with a second signal fromaccessory cells, such as the T-helper cell, the antigenstimulates the B cell to proliferate (divide) and matureinto terminal (non-dividing) antibody secreting cells,called plasma cells. The various cell divisions (mitosis)generate a clone, i.e., a set of cells that are the progeny ofa single cell. While plasma cells are the most activeantibody secretors, large B lymphocytes, which dividerapidly, also secrete Ab, albeit at a lower rate. While Bcells secrete Ab, T cells play a central role in theregulation of the B cell response and are preeminent incell mediated immune responses.Lymphocytes, in addition to proliferating and/ordifferentiating into plasma cells, can differentiate intolong-lived B memory cells.

Memory cells circulatethrough the blood, lymph and tissues, and when exposedto a second antigenic stimulus commence to differentiateinto large lymphocytes capable of producing high affinityantibodies, pre-selected for the specific antigen that hadstimulated the primary response. Figure 1 depicts theclonal selection principle.The main features of the clonal selection theory, that willbe explored in this paper, are (Burnet, 1978):• generation of new random genetic changes,subsequently expressed as diverse antibody patternsby a form of accelerated somatic mutation;In Workshop Proceedings of GECCO, pp. 36-37, Workshop on Artificial Immune Systems and Their Applications, Las Vegas, USA, July 2000.Barto, 1998), where the system is continuously improvingits capability to perform its task.One important characteristic of the immune memory isthat it is associative: B cells adapted to a certain type ofantigen A1 presents a faster and more efficient secondaryresponse not only to A1, but also to any structurallyrelated antigen A2.

This phenomenon is calledimmunological cross-reaction, or cross-reactive response(Smith et al., 1997). This kind of associative memory ispart of the process of vaccination and is calledgeneralization capability, or simply generalization, inother artificial intelligence fields, like neural networks.SelectionAntigens(Cloning)ProliferationDifferentiationSome authors (Allen et al., 1987; Coutinho, 1989)suggested that long-lived B memory cells aredisconnected, at least functionally, from the other cells.Memory cellsMM2.2SOMATIC HYPERMUTATION, RECEPTOREDITING AND REPERTOIRE DIVERSITYPlasma cellsFigure 1: The clonal selection principle.••2.1phenotypic restriction and retention of one pattern toone differentiated cell (clone);proliferation and differentiation on contact of cellswith antigens.REINFORCEMENT LEARNING ANDMEMORYLearning in the immune system involves raising thepopulation size and affinity of those lymphocytes thathave proven themselves to be valuable by havingrecognized any antigen.

While doing technology, it’sone’s desire to solve any kind of problem using a minimalamount of resources. Hence, we need the engineeringtools to seek high quality and parsimonious solutions. Inour model, we do not intend to maintain a large clone foreach candidate solution, but to keep the single bestindividual. A clone will be temporarily created, accordingto the clonal selection theory, and those progeny with lowaffinity will be discarded.In the normal course of the immune system evolution, anorganism would be expected to encounter a given antigenrepeatedly during its life time. The initial exposure to anantigen that stimulates an adaptive immune response ishandled by a spectrum of small clones of B cells eachproducing antibody of different affinity. The effectivenessof the immune response to secondary encounters isconsiderably enhanced by storing some high affinityantibody producing cells from the first infection (memorycells), so as to form a large initial improved clone forsubsequent encounters.

Rather than ‘starting from scratch’every time, such a strategy ensures that both the speedand accuracy of the immune response becomessuccessively greater after each infection. This scheme isintrinsic of a reinforcement learning strategy (Sutton &In a T cell dependent immune response, the repertoire ofantigen-activated B cells is diversified basically by twomechanisms: hypermutation and receptor editing(Tonegawa, 1983; Berek & Ziegner, 1993; Nussenzweig,1998; George & Gray, 1999).Antibodies present in a memory response have, onaverage, a higher affinity than those of the early primaryresponse. This phenomenon, which is restricted to T-celldependent responses, is referred to as the maturation ofthe immune response.

This maturation requires theantigen-binding sites of the antibody molecules, in thematured response, to be structurally different from thosepresent in the primary response.Random changes are introduced into the genesresponsible for the Ag-Ab interactions and occasionallyone such change will lead to an increase in the affinity ofthe antibody. It is these high-affinity variants which arethen selected to enter the pool of memory cells. Not onlythe repertoire is diversified through a hypermutationmechanism, but also mechanisms must exist such that rareB cells with high affinity mutant receptors can be selectedto dominate the response.

Those cells with low affinityreceptors must be efficiently eliminated, become anergicor be edited, so that they do not significantly contribute tothe pool of memory cells (Berek & Ziegner, 1993;Nussensweig, 1998; George & Gray, 1999).Recent results suggest that the immune system practicesmolecular selection of receptors in addition to clonalselection of lymphocytes. Instead of the expected clonaldeletion of all self-reactive cells, occasionally Blymphocytes were found that had undergone receptorediting: these B cells had deleted their low affinityreceptors and developed entirely new ones through V(D)Jrecombination (Nussenzweig, 1998).C1A1AffinityCAB1Badvantageous mutation.

The selection mechanism mayprovide a means by which the regulation of thehypermutation process is made dependent on receptoraffinity. Cells with low affinity receptors may be furthermutated and, as a rule, die if they do not become higheraffinity cells. In cells with high-affinity antibodyreceptors however, hypermutation may be inactivated(Berek & Ziegner, 1993).3Antigen-binding sitesFigure 2: Schematic representation of shape-space forantigen-binding sites. Somatic mutations guide to localoptima, while receptor editing introduce diversity, leadingto possibly better candidate receptors.Receptor editing offers the ability to escape from localoptima on an affinity landscape.