2014_421_Vasilenko_Mutation_Crossing_The Clonal Selection Algorithm with Engineering Applications (Задание 5), страница 3

max22 min , where zmax = 2 and2 −1zmin = −1.The affinity measure corresponds to the evaluation of thefunction f(x,y) after decoding x and y, as described above.Figure 6 presents the optimized population after 100generations. Notice that the solutions (stars) covers mostof the peaks, including the global optimum. The solutioncan be directly extracted by means of a sorting procedure.6.3 TRAVELLING SALESMAN PROBLEM (TSP)Simply stated, the travelling salesman must visit everycity in his territory, exactly once, and then return to thestarting city. The question is: given the cost of travelbetween all pairs of cities, which is the tour with thesmallest cost? In this work, the cost of the tour is basicallythe length of the itinerary traveled by the salesman.The TSP is a kind of combinatorial optimization problemand arises in numerous applications, from VLSI circuitdesign, to fast food delivery. In this case, the use of anInteger shape-space might be appropriate, where integervalued vectors of length L, composed of permutations ofelements in the set C = {1,2,...,L}, represent the possibletours.

Each component of the integer vector indexes acity. The total length of each tour gives the affinitymeasure of the corresponding vector.Figure 7 presents the best solution determined by theCSA, which corresponds to the global optimum (Moscato& Fontanari, 1990). The population size is 300individuals, with a rate of 20% of newcomers. In thiscase, low affinity individuals are allowed to be replacedafter each 20 generations. This scheduling is supposed toleave a breathing time to allow the achievement of localoptima, followed by the replacement of the poorerindividuals.By comparing the proposed algorithm, called CSA, withthe standard genetic algorithm (GA), we can notice thatthe CSA can reach a diverse set of local optima solutions,while the GA tends to polarize the whole population ofindividuals towards the best candidate solution.Essentially, their coding schemes and evaluationfunctions are not different, but their evolutionary searchprocesses differ from the viewpoint of inspiration,vocabulary and sequence of steps.

We do not advocatethat the CSA performs better than the GA, on average, inall applications. Instead, we demonstrate that theproposed algorithm is also derived from a biologicallyinspired approach, which performs learning and multimodal search. Like the GA, the clonal selection algorithmis highly parallel and presents a fine tractability in termsof computational cost.AcknowledgmentsLeandro Nunes de Castro would like to thank FAPESP(Proc.

n. 98/11333-9) for the financial support. FernandoVon Zuben would like to thank FAPESP (Proc. n.98/09939-6) and CNPq (Proc. n. 300910/96-7) for theirfinancial support.References174271112inserted in order to improve its performance in solvingparticular tasks, like the travelling salesman problem.302313Allen, D. et al. (1987), “Timing, Genetic Requirementsand Functional Consequences of Somatic Hypermutationduring B-cell Development”, Imm. Rev., 96, 5-22.36169152Berek, C. & Ziegner, M.

(1993), “The Maturation of theImmune Response”, Imm. Today, 14(8): 400-402.261910514 18Burnet, F. M. (1978), “Clonal Selection and After”, InTheoretical Immunology, (Eds.) G. I. Bell, A. S. Perelson& G. H. Pimbley Jr., Marcel Dekker Inc., 63-85.18212420292272528Figure 7: Best tour determined by the CSA after 300generations.7CONCLUSIONSIn this paper, we proposed a general-purpose algorithminspired in the clonal selection principle and affinitymaturation of the immune response.

The algorithm wasverified to be capable of performing learning andmaintenance of high quality memory and, it was alsocapable of solving complex problems, like multi-modaland combinatorial optimization.The algorithm introduced constitutes a crude version ofthe clonal selection principle. Many heuristics could beCoutinho, A. (1989), “Beyond Clonal Selection andNetwork”, Immun. Rev., 110, 63-87.Cziko, G. (1995), “The Immune System: Selectionby the Enemy”, In Without Miracles, G. Cziko, ABradford Book, The MIT Press, 39-48.Dasgupta, D., (1999), Artificial Immune Systems andTheir Applications, Ed., Springer-Verlag.George, A. J.

T. & Gray, D. (1999), “Receptor Editingduring Affinity Maturation”, Imm. Today, 20(4): 196.Hofmeyr S. A. & Forrest, S. (1999), “Immunity byDesign: An Artificial Immune System”, Proc. ofGECCO’99, 1289-1296.Holland, J. H. (1995), Adaptation in Natural andArtificial Systems, 4th Ed., MIT Press.Hunt, J. E. & Cooke, D. E. (1996), “Learning Using anArtificial Immune System”, Journal of Network andComputer Applications, 19, 189-212.Moscato, P. & Fontanari, J. F. (1990), “Stochastic VersusDeterministic Update in Simulated Annealing, PhysicsLetters A, 146(4): 204-208.Ishida, Y. (1996), “The Immune System as a SelfIdentification Process: A Survey and a Proposal”, In Proc.of the IMBS’96.Nussenzweig, M.

C. (1998), “Immune Receptor Editing;Revise and Select”, Cell, 95, 875-878.Jerne, N. K. (1984), “Idiotypic Networks and OtherPreconceived Ideas”, Imm. Rev., 79, 5-24.Smith, D. J., Forrest, S., Hightower, R. R. & Perelson, S.A. (1997), “Deriving Shape Space Parameters fromImmunological Data”, J. Theor. Biol., 189, 141-150.Lippmann, R. P. (1987), “An Introduction to Computingwith Neural Nets”, IEEE ASSP Magazine, 4-22.Sutton, R. S. & Barto, A. G.

(1998), ReinforcementLearning: An Introduction, A Bradford Book.Tonegawa, S. (1983), “Somatic Generation of AntibodyDiversity”, Nature, 302, 575-581..