Large-scale optimization using immune algorithm

ABSTRACT

Immune-inspired optimization algorithms encoded the parameters into individuals where each individual represents a search point in the space of potential solutions. A large number of parameters would result in a large search space. Nowadays, there is little report about immune algorithms effectively solving numerical optimization problems with more than 100 parameters. In this paper, we introduce an improved immune algorithm, termed as Dual-Population Immune Algorithm (DPIA), to solve large-scale optimization problems. DPIA adopts two side-by-side populations, antibody population and memory population. The antibody population employs the cloning, affinity maturation, and selection operators, which emphasizes the global search. The memory population stores current representative antibodies and the update of the memory population pay more attention to maintain the population diversity. Normalized decimal-string representation makes DPIA more suitable for solving large-scale optimization problems. Special mutation and recombination methods are adopted to simulate the somatic mutation and receptor editing process. Experimental results on eight benchmark problems show that DPIA is effective to solve large-scale numerical optimization problems.

REFERENCES

• 1: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 2: Y. Ishida. Fully Distributed Diagnosis by PDP Learning Algorithm: Towards Immune Network PDP Model. In: Proceedings of International Joint Conference on Neural Networks, San Diego, (1990) 777--782.
• 3: Stephanie Forrest , Alan S. Perelson , Lawrence Allen , Rajesh Cherukuri, Self-Nonself Discrimination in a Computer, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.202, May 16-18, 1994
• 4: A. Tarakanov, D. Dasgupta. A formal model of an artificial immune system. BioSystems, 55(1/3) (2000) 151--158.
• 5: F. Gonzalez, D. Dasgupta, R. Kozma. Combining Negative Selection and Classification Techniques for Anomaly Detection. In: Proceedings of the special sessions on artificial immune systems in Congress on Evolutionary Computation, Honolulu, Hawaii, 2002.
• 6: J.H. Carter. The Immune System as a model for Pattern Recognition and classification. Journal of the American Medical Informatics Association, 7(3) (2000) 28--41.
• 7: J. Timmis, M. Neal, J. Hunt. An artificial immune system for data analysis. Biosystems, 55(1/3) (2000) 143--150.
• 8: U. Garain, M. P. Chakraborty, D. Dasgupta. Recognition of Handwritten Indic Script using Clonal Selection Algorithm. In: Proceedings of Fifth International Conference on Artificial Immune Systems. Oeiras, Portugal: September, 2006. 256--266.
• 9: L.N. de Castro, F.J. Von Zuben. Learning and Optimization Using the Clonal Selection Principle. IEEE Transactions on Evolutionary Computation, 6(3) (2002) 239--251.
• 10: L. N. de Castro, J. Timmis. An Artificial Immune Network for Multimodal Function Optimization. In: Proceedings of the 2002 IEEE Congress on Evolutionary Computation, Vol. 1, (2002) 699--704.
• 11: J. Kelsey, J. Timmis. Immune inspired somatic contiguous hypermutation for function optimisation. In: Genetic and Evolutionary Computation Conference, volume 2723 of Lecture Notes in Computer Science, (2003) 207--218.
• 12: S.M. Garrett. Parameter-free, Adaptive Clonal Selection. In: Proceedings of the 2004 IEEE Congress on Evolutionary Computing, Portland, Oregon, (2004) 1052--1058.
• 13: V. Cutello, G. Nicosia, M. Pavone. Exploring the Capability of Immune Algorithms: A Characterization of Hypemutation Operators. In: Proceedings of Third International Conference on Artificial Immune Systems, Lecture Notes in Computer Science, 3239 (2004) 263--276.
• 14: V. Cutello, G.Narzisi, G. Nicosia, M. Pavone. Clonal Selection Algorithms: A Comparative Case Study Using Effective Mutation Potentials. In: Proceedings of 4th International Conference on Artificial Immune Systems, Lecture Notes in Computer Science, 3627 (2005) 13--28.
• 15: Maoguo Gong, Licheng Jiao, Wenping Ma, Shuiping Gou. Solving Multidimensional Knapsack Problems by an Immune-inspired Algorithm. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore, (2007) 3385--3391.
• 16: T. Fukuda, K Mori, M. Tsukiyama. Immune networks using genetic algorithm for adaptive production scheduling. In 15th IFAC World Congress, Vol. 3 (1993) 57--60.
• 17: Maoguo Gong, Licheng Jiao, Fang Liu, Haifeng Du. The Quaternion Model of Artificial Immune Response. In: Proceedings of the fourth international conference on Artificial Immune Systems, Banff, Canada (2005) 207--219.
• 18: C. Berek, M. Ziegner. The maturation of the immune response. Immunology Today, Vol. 14, No. 8 (1993) 400--402.
• 19: A. J. T. George, D. Gray. Receptor editing during affinity maturation. Immunology Today. Vol. 20, No. 4 (1999) 196.
• 20: S.Y. Ho, L.S. Shu, J.H. Chen. Intelligent Evolutionary Algorithms for large Parameter Optimization Problems. IEEE Transactions on Evolutionary Computation. Vol. 8, No. 6 (2004) 522--540.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
evolutionary algorithm, immune algorithm, large-scale optimization