2014_421_Vasilenko_Mutation_Crossing_The Clonal Selection Algorithm with Engineering Applications (Задание 5), страница 2
Файл "2014_421_Vasilenko_Mutation_Crossing_The Clonal Selection Algorithm with Engineering Applications" внутри архива находится в следующих папках: Задание 5, ответ. PDF-файл из архива "Задание 5", который расположен в категории "лабораторные работы". Всё это находится в предмете "надёжность программного обеспечения" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
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. Figure 2 illustrates thisidea by considering all possible antigen-binding sitesdepicted in the x-axis, with the most similar ones adjacentto each other. The Ag-Ab affinity is shown on the y-axis.If it is taken a particular antibody (A) selected during aprimary response, then point mutations allow the immunesystem to explore local areas around A by making smallsteps towards an antibody with higher affinity, leading toa local optima (A1).
Because mutations with loweraffinity are lost, the Ab can not go down the hill.Receptor editing allows an antibody to take large stepsthrough the landscape, landing in a locale where theaffinity might be lower (B). However, occasionally theleap will lead to an antibody on the side of a hill wherethe climbing region is more promising (C), reaching theglobal optimum. From this locale, point mutations candrive the Ab to the top of the hill (C1). In conclusion,point mutations are good for exploring local regions,while editing may rescue immune responses stuck onunsatisfactory local optima.In addition to somatic hypermutation and receptor editing,a fraction of newcomer cells from the bone marrow isadded to the lymphocyte pool in order to maintain thediversity of the population. According to Jerne (1984),from 5-8% of the least stimulated lymphocytes is replacedper cell generation, joining the pool of available antigenrecognizing cells.
This may yield the same result as theprocess of receptor editing, i.e., a broader search for theglobal optimum of the antigen-binding site.2.3THE REGULATION OF THEHYPERMUTATION MECHANISMA rapid accumulation of mutations is necessary for a fastmaturation of the immune response, but the majority ofthe changes will lead to poorer or non-functionalantibodies.
If a cell that has just picked up a usefulmutation continues to be mutated at the same rate duringthe next immune responses, then the accumulation ofdeleterious changes may cause the loss of theAN EVOLUTIONARY SYSTEMThe clonal selection functioning of the immune systemcan be interpreted as a remarkable microcosm of CharlesDarwin’s law of evolution, with the three major principlesof diversity, variation and natural selection (Cziko, 1995).The two central processes involved in the production ofantibodies, genetic recombination and mutation, are thesame ones responsible for the biological evolution ofsexually reproducing species. In these species, the sametwo processes are involved in providing the variations onwhich natural selection can work to fit the organism to theenvironment (Holland, 1995).
As a consequence,cumulative blind variation and natural selection, whichover many millions of years resulted in the emergence ofmammalian species, remain crucial in the day-by-dayceaseless battle to survival of these species.Whereas adaptive biological evolution proceeds bycumulative natural selection among organisms, researchon the immune system has now provided the first clearevidence that ontogenetic adaptive changes can beachieved by cumulative blind variation and selectionwithin organisms. The clonal selection algorithm, to bedescribed further in the text, aims at demonstrating thatthis cumulative blind variation can generate high qualitysolutions to complex problems.4THE SHAPE-SPACE MODELThe shape-space model (S) aims at quantitativelydescribing the interactions among antigens and antibodies(Ag-Ab).
The set of features that characterize a moleculeis called its generalized shape. The Ag-Ab representation(binary or real-valued) determines a distance measure tobe used to calculate the degree of interaction betweenthese molecules. Mathematically, the generalized shape ofa molecule (m), either an antibody or an antigen, can berepresented by a set of coordinates m = <m1, m2,..., mL>,which can be regarded as a point in an L-dimensionalreal-valued shape-space (m ∈ SL). Here, the precisephysical meaning of each parameter is not relevant. In thiswork, we used binary (or integer) strings to represent themolecules.
Antigens and antibodies were considered ofthe same length L. The length and cell representationdepends upon the problem.5THE PROPOSED ALGORITHMAfter discussing the clonal selection principle and theaffinity maturation process, the development of the clonalselection algorithm (CSA) is straightforward.
The mainimmune aspects taken into account were: maintenance ofthe memory cells functionally disconnected from therepertoire, selection and cloning of the most stimulatedcells, death of non-stimulated cells, affinity maturationand re-selection of the clones with higher affinity,generation and maintenance of diversity, hypermutationproportional to the cell affinity.Nd(6)Pr(1)M6ENGINEERING APPLICATIONS(2)To evaluate the clonal selection algorithm (CSA), weconsidered three different problems:(3)1. a binary character recognition task will be used to testits learning and memory acquisition capabilities;2. a multi-modal optimization task; and3. a 30 cities instance of the Travelling SalesmanProblem (TSP).SelectPn(5)Re-select(3) Reproduce (Clone) these n best individuals of thepopulation, giving rise to a temporary population ofclones (C). The clone size is an increasing functionof the affinity with the antigen;(4) Submit the population of clones to a hypermutationscheme, where the hypermutation is proportional tothe affinity of the antibody with the antigen.
Amaturated antibody population is generated (C*);(5) Re-select the improved individuals from C* tocompose the memory set M. Some members of P canbe replaced by other improved members of C*;(6) Replace d antibodies by novel ones (diversityintroduction). The lower affinity cells have higherprobabilities of being replaced.CloneC6.1Maturate(4)C*Figure 3: Block diagram of the clonal selection algorithm.The algorithm works as in Figure 3 (after each six stepswe have one cell generation):(1) Generate a set (P) of candidate solutions, composedof the subset of memory cells (M) added to theremaining (Pr) population (P = Pr + M);(2) Determine (Select) the n best individuals of thepopulation (Pn), based on an affinity measure;BINARY CHARACTER RECOGNITIONThe learning and memory acquisition of the CSA isverified through its application to a binary characterrecognition problem.
Our goal is to demonstrate that acumulative blind variation together with selection canproduce individuals with increasing affinities (maturationof the immune response). In this case, we assume that theantigen population is represented by a set of eight binarycharacters to be learned.
These characters are the sameones originally proposed by Lippman (1987), in adifferent context. Each character is represented by abitstring (Hamming shape-space, briefly discussed inSection 4) of length L = 120. The antibody repertoire iscomposed of 10 individuals, 8 of them in the memory setM.(a) Input patterns(b) 0 generations(c) 50 generations(d) 100 generations(e) 200 generationsFigure 4: (a) Patterns to be learned, or input patterns (antigens). (b) Initial memory set. (c) Memory set after 50 cellgenerations. (d) Memory set after 100 cell generations. (e) Memory set after 200 cell generations.The original characters (antigens) are depicted in Figure4(a).
Figure 4(b) illustrates the initial memory set, andFigures 4(b) to 4(e) represent the maturation of thememory set (immune response) through cell generations.The affinity measure takes into account the Hammingdistance (D) between antigens and antibodies, accordingto Equation (1):L1 if abi ≠ ag iD = ∑ / where / = 0 otherwisei =1Global optimum(1)Notice that an exact matching is not necessary to obtain asuccessful character recognition. A partial matching isenough in most applications. The algorithm convergedafter 250 cell generations.6.2MULTI-MODAL OPTIMIZATIONFigure 5: Function to be maximized by the CSA.The CSA reproduces those individuals with higheraffinities and selects their improved maturated progenies.This strategy suggests that the algorithm performs agreedy search, where single members will be locallyoptimized (exploitation of the surrounding space), and thenewcomers yield a broader exploration of the searchspace.
This characteristic makes the CSA very suitable forsolving multi-modal optimization tasks and, as anillustration, consider the case of maximizing the functionf(x,y) = x.sin(4πx)−y.sin(4πy+π)+1, depicted in Figure 5.Notice that this function is composed of many localoptima and a single global optimum.We employed the Hamming shape-space, with binarystrings representing real values for x and y. The chosenbitstring length was L = 22, corresponding to a precisionof six decimal places.
The variables x and y are definedover the range [−1, 2], and the mapping from a binarystring m = <mL,..., m2, m1> into a real number z iscompleted in two steps:•convert the binary string m = <mL,..., m2, m1> frombase 2 to base 10:(< mL ,..., m2 , m1 >)2 = (∑)21m .2 ii =0 i10= z'Figure 6: Optimized population after 100 cell generations.•find the corresponding real value for z:−zzz = z min + z '.