Memory-based immigrants for genetic algorithms in dynamic environments

ABSTRACT

Investigating and enhancing the performance of genetic algorithms in dynamic environments have attracted a growing interest from the community of genetic algorithms in recent years. This trend reflects the fact that many real world problems are actually dynamic, which poses serious challenge to traditional genetic algorithms. Several approaches have been developed into genetic algorithms for dynamic optimization problems. Among these approches, random immigrants and memory schemes have shown to be beneficial in many dynamic problems. This paper proposes a hybrid memory and random immigrants scheme for genetic algorithms in dynamic environments. In the hybrid scheme, the best solution in memory is retrieved and acts as the base to create random immigrants to replace the worst individuals in the population. In this way, not only can diversity be maintained but it is done more efficiently to adapt the genetic algorithm to the changing environment. The experimental results based on a series of systematically constructed dynamic problems show that the proposed memory-based immigrants scheme efficiently improves the performance of genetic algorithms in dynamic environments.

REFERENCES

• 1: C. N. Bendtsen and T. Krink. Dynamic memory model for non-stationary optimization. In Proc. of the 2002 Congress on Evol. Comput., pages 145--150, 2002.
• 2: J. Branke. Memory enhanced evolutionary algorithms for changing optimization problems. In Proc. of the 1999 Congress on Evolutionary Computation, volume 3, pages 1875--1882, 1999.
• 3: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 1920
• 4: J. Branke, T. Kauβler, C. Schmidth, and H. Schmeck. A multi-population approach to dynamic optimization problems. In Proc. of the Adaptive Computing in Design and Manufacturing, pages 299--308, 2000.
• 5: 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
• 6: D. Dasgupta and D. McGregor. Nonstationary function optimization using the structured genetic algorithm. In R. Männer and B. Manderick, editors, Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pages 145--154, 1992.
• 7: David E. Goldberg , Robert E. Smith, Nonstationary function optimization using genetic algorithm with dominance and diploidy, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.59-68, October 1987, Cambridge, Massachusetts, United States
• 8: J. J. Grefenstette. Genetic algorithms for changing environments. In R. Männer and B. Manderick, editors, Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pages 137--144, 1992.
• 9: Jonathan Lewis , Emma Hart , Graeme Ritchie, A Comparison of Dominance Mechanisms and Simple Mutation on Non-stationary Problems, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.139-148, September 27-30, 1998
• 10: S. J. Louis and Z. Xu. Genetic algorithms for open shop scheduling and re-scheduling. In Proc. of the 11th ISCA Int. Conf. on Computers and their Applications, pages 99--102, 1996.
• 11: H. K. N. Mori and Y. Nishikawa. Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In Proc. of the 7th Int. Conf. on Genetic Algorithms, pages 299--306. Morgan Kaufmann Publishers, 1997.
• 12: Khim Peow Ng , Kok Cheong Wong, A New Diploid Scheme and Dominance Change Mechanism for Non-Stationary Function Optimization, Proceedings of the 6th International Conference on Genetic Algorithms, p.159-166, July 15-19, 1995
• 13: Connie Loggia Ramsey , John J. Grefenstette, Case-Based Initialization of Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.84-91, June 01, 1993
• 14: K. Trojanowski and Z. Michalewicz. Searching for optima in non-stationary environments. In Proc. of the 1999 Congress on Evolutionary Computation, pages 1843--1850, 1999.
• 15: Frank Vavak , Terence C. Fogarty, A Comparative Study of Steady State and Generational Genetic Algorithms, Selected Papers from AISB Workshop on Evolutionary Computing, p.297-304, April 01-02, 1996
• 16: S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm, In Proc. of the 2003 Congress on Evol. Comput., Vol. 3, pages 2246--2253, 2003.
• 17: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
dynamic optimization problems, genetic algorithms, memory scheme, random immigrants scheme