Population-based incremental learning with memory scheme for changing environments

ABSTRACT

In recent years there has been a growing interest in studying evolutionary algorithms for dynamic optimization problems due to its importance in real world applications. Several approaches have been developed, such as the memory scheme. This paper investigates the application of the memory scheme for population-based incremental learning (PBIL) algorithms, a class of evolutionary algorithms, for dynamic optimization problems. A PBIL-specific memory scheme is proposed to improve its adaptability in dynamic environments. In this memory scheme the working probability vector is stored together with the best sample it creates in the memory and is used to reactivate old environments when change occurs. Experimental study based on a series of dynamic environments shows the efficiency of the memory scheme for PBILs in dynamic environments. In this paper, the relationship between the memory scheme and the multi-population scheme for PBILs in dynamic environments is also investigated. The experimental results indicate a negative interaction of the multi-population scheme on the memory scheme for PBILs in the dynamic test environments.

REFERENCES

• 1: T. Bäck. On the behaviour of evolutionary algorithms in dynamic fitness landscape. In Proc. of the 1998 IEEE Int. Conf. on Evolutionary Computation, pages 446--451, 1998.
• 2: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 3: S. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. In Proc. of the 12th Int. Conf. on Machine Learning, pages 38--46, 1995.
• 4: C. N. Bendtsen and T. Krink. Dynamic memory model for non-stationary optimization. In Proc. of the 2002 Congress on Evolutionary Computation, pages 145--150, 2002.
• 5: 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.
• 6: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 1920
• 7: D. Dasgupta and D. McGregor. Nonstationary function optimization using the structured genetic algorithm. In Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pages 145--154, 1992.
• 8: 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
• 9: P. Larrañaga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.
• 10: 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
• 11: 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.
• 12: N. Mori, H. Kita 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.
• 13: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 14: 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
• 15: 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
• 16: 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.
• 17: S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm. In Proc. of the 2003 Congress on Evolutionary Computation, volume 3, pages 2246--2253, 2003.
• 18: 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 problem, memory scheme, multi-population scheme, population-based incremental learning