Investigating restricted tournament replacement in ECGA for non-stationary environments

ABSTRACT

This paper investigates the incorporation of restricted tournament replacement (RTR) in the extended compact genetic algorithm (ECGA) for solving problems with non-stationary optima. RTR is a simple yet efficient niching method used to maintain diversity in a population of individuals. While the original version of RTR uses Hamming distance to quantify similarity between individuals, we propose an alternative substructural distance to enforce the niches. The ECGA that restarts the search after a change of environment is compared with the approach of maintaining diversity, using both versions of RTR. Results on several dynamic decomposable test problems demonstrate the usefulness of maintaining diversity throughout the run over the approach of restarting the search from scratch at each change. Furthermore, by maintaining diversity no additional mechanisms are required to detect the change of environment, which is typically a problem-dependent and non-trivial task.

REFERENCES

• 1: H. A. Abbass, K. Sastry, and D. E. Goldberg. Oiling the wheels of change: The role of adaptive automatic problem decomposition in non-stationary environments. IlliGAL Report No. 2004029, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2004.
• 2: David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
• 3: Jurgen Branke, Evolutionary Optimization in Dynamic Environments, Kluwer Academic Publishers, Norwell, MA, 2001
• 4: K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms 2, pages 93--108, 1993.
• 5: Ashish Ghosh , Heinz Muehlenbein, Univariate marginal distribution algorithms for non-stationary optimization problems, International Journal of Knowledge-based and Intelligent Engineering Systems, v.8 n.3, p.129-138, August 2004
• 6: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 7: G. Harik, F. G. Lobo, and K. Sastry. Linkage learning via probabilistic modeling in the ECGA. In M. Pelikan, K. Sastry, and E. Cantu-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 39--61. Springer, 2006.
• 8: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 9: G. R. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 1999.
• 10: Y. Jin and J. Branke. Evolutionary optimization in uncertain environments-a survey. IEEE Transactions on Evolutionary Computation, 9(3):303--317, 2005.
• 11: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 12: C. F. Lima, C. Fernandes, and F. G. Lobo. Investigating restricted tournament replacement in ECGA for non-stationary environments. IlliGAL Report No. 2008007, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2008.
• 13: M. Pelikan. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms. Springer, 2005.
• 14: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 15: J. J. Rissanen. Modelling by shortest data description. Automatica, 14:465--471, 1978.
• 16: K. Sastry, H. A. Abbass, and D. E. Goldberg. Sub-structural niching in non--stationary environments. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, LNAI 3339, pages 873--885. Springer, 2004.
• 17: Kumara Sastry , Hussein A. Abbass , David E. Goldberg , D. D. Johnson, Sub-structural niching in estimation of distribution algorithms, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068123]
• 18: K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation. In Proceedings of the IEEE International Conference on Evolutionary Computation, pages 720--727, 2004.
• 19: D. H. Wolpert and W. G. Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997.
• 20: S. Yang. Constructing dynamic test environments for genetic algorithms based on problem difficulty. In Proceedings of the IEEE International Conference on Evolutionary Computation, pages 1262--1269. IEEE Press, 2004.
• 21: 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]
• 22: Shengxiang Yang , Jürgen Branke, Evolutionary algorithms for dynamic optimization problems: workshop preface, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102261]
• 23: 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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
diversity preservation, estimation of distribution algorithms, genetic algorithms, niching, non-stationary environments, restricted tournament replacement