A comparative study of immune system based genetic algorithms in dynamic environments

ABSTRACT

Diversity and memory are two major mechanisms used in biology to keep the adaptability of organisms in the ever-changing environment in nature. These mechanisms can be integrated into genetic algorithms to enhance their performance for problem optimization in dynamic environments. This paper investigates several GAs inspired by the ideas of biological immune system and transformation schemes for dynamic optimization problems. An aligned transformation operator is proposed and combined to the immune system based genetic algorithm to deal with dynamic environments. Using a series of systematically constructed dynamic test problems, experiments are carried out to compare several immune system based genetic algorithms, including the proposed one, and two standard genetic algorithms enhanced with memory and random immigrants respectively. The experimental results validate the efficiency of the proposed aligned transformation and corresponding immune system based genetic algorithm in dynamic environments.

REFERENCES

• 1: J. Branke. Memory enhanced evolutionary algorithms for changing optimization problems. Proc. of the 1999 Congr. on Evol. Comput., vol. 3, pp. 1875--1882, 1999.
• 2: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 1920
• 3: Helen G. Cobb , John J. Grefenstette, Genetic Algorithms for Tracking Changing Environments, Proceedings of the 5th International Conference on Genetic Algorithms, p.523-530, June 01, 1993
• 4: A. Gaspar and P. Collard. From GAs to artificial immune systems: Improving adaptation in time dependent optimization. Proc. of the 1999 Congr. on Evol. Comput., vol. 3, pp. 1859--1866, 1999.
• 5: A. Gaspar and P. Collard. Two models of immunization for time dependent optimization. Proc. of the 2000 IEEE Int. Conf. on SMC, 2000.
• 6: J. J. Grefenstette. Genetic algorithms for changing environments. Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pp. 137--144, 1992.
• 7: D. L. Hartl and E. W. Jones. Genetics: Principles and Analysis. Jones and Bartllet Publishers, Inc., 1998.
• 8: N. Mori, H. Kita and Y. Nishikawa. Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. Proc. of the 7th Int. Conf. on Genetic Algorithms, pp. 299--306, 1997.
• 9: R. W. Morrison and K. A. De Jong. Triggered hypermutation revisited. Proc. of the 2000 Congress on Evol. Comput., pp. 1025--1032, 2000.
• 10: A. Simões and E. Costa. On biologically inspired genetic operators: Using transformation in the standard genetic algorithm Proc. of the 2001 Genetic and Evol. Comput. Conf., pp. 584--591, 2001.
• 11: A. Simões and E. Costa. An immune system-based genetic algorithm to deal with dynamic environments: diversity and memory. Proc. of the 6th Int. Conf. on Neural Networks and Genetic Algs., pp. 168--174, 2003.
• 12: A. Simões and E. Costa. Improving the genetic algorithm's performance when using transformation. Proc. of the 6th Int. Conf. on Neural Networks and Genetic Algs., pp. 175--181, 2003.
• 13: K. Trojanowski and Z. Michalewicz. Searching for optima in non-stationary environments. Proc. of the 1999 Congress on Evol. Comput., pp. 1843--1850, 1999.
• 14: S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm. Proc. of the 2003 Congress on Evolutionary Computation, vol. 3, pp. 2246--2253, 2003.
• 15: Shengxiang Yang, Memory-based immigrants for genetic algorithms in dynamic environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068196]
• 16: Shengxiang Yang , Xin Yao, Experimental study on population-based incremental learning algorithms for dynamic optimization problems, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.11, p.815-834, November 2005 [doi>10.1007/s00500-004-0422-3]
• 17: Shengxiang Yang, Population-based incremental learning with memory scheme for changing environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068128]

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:
dynamic environments, immune system based genetic algorithms, memory, random immigrants, transformation