Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Clonal selection: an immunological algorithm for global optimization over continuous spaces

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In this research paper we present an immunological algorithm (IA) to solve global numerical optimization problems for high-dimensional instances. Such optimization problems are a crucial component for many real-world applications. We designed two versions of the IA: the first based on binary-code representation and the second based on real values, called opt-IMMALG01 and opt-IMMALG, respectively. A large set of experiments is presented to evaluate the effectiveness of the two proposed versions of IA. Both opt-IMMALG01 and opt-IMMALG were extensively compared against several nature inspired methodologies including a set of Differential Evolution algorithms whose performance is known to be superior to many other bio-inspired and deterministic algorithms on the same test bed. Also hybrid and deterministic global search algorithms (e.g., DIRECT, LeGO, PSwarm) are compared with both IA versions, for a total 39 optimization algorithms.The results suggest that the proposed immunological algorithm is effective, in terms of accuracy, and capable of solving large-scale instances for well-known benchmarks. Experimental results also indicate that both IA versions are comparable, and often outperform, the state-of-the-art optimization algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aiex R.M., Resende M.G.C., Ribeiro C.C.: TTTPLOTS: a perl program to create time-to-target plots. Optim. Lett. 1, 355–366 (2007)

    Article  Google Scholar 

  2. Aiex R.M., Resende M.G.C., Ribeiro C.C.: Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8, 343–373 (2002)

    Article  Google Scholar 

  3. Angeline P.J.: Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Porto, V.W., Saravanan, N., Waagen, D., Eiben, A.E. (eds) Evolutionary programming, vol. 7, pp. 601–610. Springer-Verlang, Berlin (1998)

    Chapter  Google Scholar 

  4. Caponetto R., Fortuna L., Fazzino S., Xibilia M.G.: Chaotic sequences to improve the performance of evolutionary algorithms. IEEE Trans. Evolut. Comput. 7(3), 289–304 (2003)

    Article  Google Scholar 

  5. Cassioli, A., Di Lorenzo, D., Locatelli, M., Schoen, F., Sciandrone, M.: Machine Learning for Global Optimization. Comput. Optim. Appl. doi:10.1007/s10589-010-9330-x accepted August (2010)

  6. Chambers J.M., Cleveland W.S., Kleiner B., Tukey P.A.: Graphical Models for Data Analysis. Chapman & Hall, London (1983)

    Google Scholar 

  7. Chellapilla K.: Combining mutation operators in evolutionary programming. IEEE Trans. Evolut. Comput. 2, 91–96 (1998)

    Article  Google Scholar 

  8. Cutello, V., Narzisi, G., Nicosia, G., Pavone, M.: An immunological algorithm for global numerical optimization. In: Proceedings of the of the Seventh International Conference on Artificial Evolution (EA’05), vol. 3871, 284–295. LNCS (2005)

  9. Cutello, V., Narzisi, G., Nicosia, G., Pavone, M.: Clonal selection algorithms: a comparative case study using effective mutation potentials. In: Proceedings of the Fourth International Conference on Artificial Immune Systems (ICARIS’05), vol. 3627, pp. 13–28. LNCS (2005)

  10. Cutello, V., Nicosia, G., Pavone, M.: A hybrid immune algorithm with information gain for the graph coloring problem. In: Proceedings of Genetic and Evolutionary Computation COnference (GECCO’03), vol. 2723, pp. 171–182. LNCS (2003)

  11. Cutello, V., Nicosia, G., Pavone, M.: Exploring the capability of immune algorithms: a characterization of hypermutation operators. In: Proceedings of the Third International Conference on Artificial Immune Systems (ICARIS’04), vol. 3239, pp. 263–276. LNCS (2004)

  12. Cutello, V., Nicosia, G., Pavone, M.: An immune algorithm with hyper-macromutations for the Dill’s 2D hydrophobic–hydrophilic model. In: Proceedings of Congress on Evolutionary Computation (CEC’04), vol. 1, pp. 1074–1080. IEEE Press, New York (2004)

  13. Cutello V., Nicosia G., Pavone M.: An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem. J. Comb. Optim. 14(1), 9–33 (2007)

    Article  Google Scholar 

  14. Cutello, V., Nicosia, G., Pavone, M., Narzisi, G.: Real coded clonal selection algorithm for unconstrained global numerical optimization using a hybrid inversely proportional hypermutation operator. In: Proceedings of the 21st Annual ACM Symposium on Applied Computing (SAC’06), vol. 2, pp. 950–954 (2006)

  15. Cutello V., Nicosia G., Pavone M., Timmis J.: An immune algorithm for protein structure prediction on lattice models. IEEE Trans. Evolut. Comput. 11(1), 101–117 (2007)

    Article  Google Scholar 

  16. Dasgupta, D.: Advances in artificial immune systems. IEEE Comput. Intell. Mag. 40–49 (2006)

  17. Dasgupta D., Niño F.: Immunological Computation: Theory and Applications. CRC Press, Taylor & Francis Group, Boca Raton (2009)

    Google Scholar 

  18. Davies M., Secker A., Freitas A., Timmis J., Clark E., Flower D.: Alignment-independent techniques for protein classification. Curr. Proteomics 5(4), 217–223 (2008)

    Article  Google Scholar 

  19. De Castro L.N., Von Zuben F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. Evolut. Comput. 6(3), 239–251 (2002)

    Article  Google Scholar 

  20. Feo T.A., Resende M.G.C., Smith S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860–878 (1994)

    Article  Google Scholar 

  21. Finkel, D.E.: DIRECT optimization algorithm user guide. Technical report, CRSC N.C. State University. ftp://ftp.ncsu.edu/pub/ncsu/crsc/pdf/crsc-tr03-11.pdf (March 2003)

  22. Floudas, C.A., Pardalos, P.M. (eds): Encyclopedia of Optimization. Springer, Berlin (2009)

    Google Scholar 

  23. Garrett S.: How do we evaluate artificial immune systems?. Evolut. Comput. 13(2), 145–178 (2005)

    Article  Google Scholar 

  24. Goldberg D.E.: The Design of Innovation Lessons from and for Competent Genetic Algorithms, vol. 7. Kluwer Academic Publisher, Boston (2002)

    Google Scholar 

  25. Goldberg, D.E., Voessner, S.: Optimizing global-local search hybrids. In: Genetic and Evolutionary Computation Conference (GECCO’99), pp. 220–228 (1999)

  26. Hart W.E., Krasnogor N., Smith J.E.: Recent Advances in Memetic Algorithms, Series in Studies in Fuzziness and Soft Computing. Springer, Berlin (2005)

    Book  Google Scholar 

  27. http://www2.research.att.com/~mgcr/tttplots/

  28. Jones D.R., Perttunen C.D., Stuckman B.E.: Lipschitzian optimization without the Lipchitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)

    Article  Google Scholar 

  29. Karaboga D., Baturk B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Global Optim. 39, 459–471 (2007)

    Article  Google Scholar 

  30. Lozano M., Herrera F., Krasnogor N., Molina D.: Real-coded Memetic algorithms with crossover hill-climbing. Evolut. Comput. 12(3), 273–302 (2004)

    Article  Google Scholar 

  31. Mezura-Montes, E., Velázquez-Reyes, J., Coello Coello C.: A comparative study of differential evolution variants for global optimization. In: Genetic and Evolutionary Computation Conference (GECCO’06), vol. 1, pp. 485–492 (2006)

  32. Noman N., Iba H.: Enhancing differential evolution performance with local search for high dimensional function optimization. In: Genetic and Evolutionary Computation Conference (GECCO’05), pp. 967–974 (2005)

  33. Pardalos P.M., Resende M.: Handbook of Applied Optimization. Oxford University Press, Oxford (2002)

    Google Scholar 

  34. Price K.V., Storn M., Lampien J.A.: Differential Evolution: A Practical Approach to Global Optimization. Springer, Berlin (2005)

    Google Scholar 

  35. Smith S., Timmis J.: Immune network inspired evolutionary algorithm for the diagnosis of Parkinsons disease. Biosystems 94(1–2), 34–46 (2008)

    Article  Google Scholar 

  36. Storn R., Price K.V.: Differential evolution a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997)

    Article  Google Scholar 

  37. Timmis J.: Artificial immune systems—today and tomorrow. Nat. Comput. 6(1), 1–18 (2007)

    Article  Google Scholar 

  38. Timmis J., Hart E.: Application areas of AIS: the past, present and the future. J. Appl. Soft Comput. 8(1), 191–201 (2008)

    Article  Google Scholar 

  39. Timmis, J., Hart, E., Hone, A., Neal, M., Robins, A., Stepney, S., Tyrrell A.: Immuno-engineering. In: Proceedings of the international conference on Biologically Inspired Collaborative Computing (IFIP’09), vol. 268, pp. 3–17. IEEE Press, New York (2008)

  40. Timmis, J., Kelsey J.: Immune inspired somatic contiguous hypermutation for function optimization. In: Proceedings of Genetic and Evolutionary Computation Conference (GECCO’03), vol. 2723, pp. 207–218. LNCS (2003)

  41. Vaz A.I.F., Vicente L.N.: A particle swarm pattern search method for bound constrained global optimization. J. Global Optim. 39, 197–219 (2007)

    Article  Google Scholar 

  42. Versterstrøm, J., Thomsen, R.: A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems. In: Congress on Evolutionary Computing (CEC’04), vol. 1, pp. 1980–1987 (2004)

  43. Yao X., Liu Y., Lin G.M.: Evolutionary programming made faster. IEEE Trans. Evolut. Comput. 3(2), 82–102 (1999)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, University of Catania, Viale A. Doria 6, 95125, Catania, Italy

    Mario Pavone & Giuseppe Nicosia

  2. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, New York, NY, 10012, USA

    Giuseppe Narzisi

Authors
  1. Mario Pavone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giuseppe Narzisi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giuseppe Nicosia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giuseppe Nicosia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pavone, M., Narzisi, G. & Nicosia, G. Clonal selection: an immunological algorithm for global optimization over continuous spaces. J Glob Optim 53, 769–808 (2012). https://doi.org/10.1007/s10898-011-9736-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-011-9736-8

Keywords

Search

Navigation