Adaptation of expansion rate for real-coded crossovers

ABSTRACT

Premature convergence is one of the most notable obstacles that GAs face with. Once it happens, GAs cannot generate candidate solutions globally and the solutions are finally captured by local minima. To overcome it, we propose a mechanism that indirectly controls the variety of the population. It is realized by adapting the expansion rate parameter of crossovers, which determines the variance of the crossover distribution. The resulting algorithm is called adaptation of expansion rate (AER). The performance of the proposed methods is compared to an existing GA on several benchmark functions including functions whose landscape have ridge or multimodal structure. On these functions, existing GAs are likely to lead to premature convergence. The experimental result shows our approach outperforms the existing one on deceptive functions without disturbing the performance on comparatively easy problems.

REFERENCES

• 1: D. H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing, 1:170--204, 1987.
• 2: Y. Akimoto, R. Hasada, J. Sakuma, I. Ono, and S. Kobayashi. Generation alternation model for real-coded ga using multi-parent: Proposal and evaluation of just generation gap (JGG). In Proceedings of the 19th SICE Symposium on Decentralized Autonomous Systems, pages 341--346, 2007. In Japanese.
• 3: Youhei Akimoto , Jun Sakuma , Isao Ono , Shigenobu Kobayashi, Functionally specialized CMA-ES: a modification of CMA-ES based on the specialization of the functions of covariance matrix adaptation and step size adaptation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389188]
• 4: Kalyanmoy Deb , Ashish Anand , Dhiraj Joshi, A computationally efficient evolutionary algorithm for real-parameter optimization, Evolutionary Computation, v.10 n.4, p.371-395, December 2002 [doi>10.1162/106365602760972767]
• 5: L. Eshelman. Real-coded genetic algorithms and interval-schemata. Foundations of Genetic Algorithms, 2:187--202, 1993.
• 6: L. J. Eshelman. The chc adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination. Foundations of Genetic Algorithms, pages 265--283, 1991.
• 7: L. J. Eshelman, K. E. Mathias, and J. D. Schaffer. Crossover operator biases: Exploiting the population distribution. In Proceedings of the 7th International Conference on Genetic Algorithms, pages 354--361, 1997.
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: Jörn Grahl , Peter A.N. Bosman , Franz Rothlauf, The correlation-triggered adaptive variance scaling IDEA, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144071]
• 10: N. Hansen. The CMA evolution strategy: a comparing review. In Towards a new evolutionary computation. Advances on estimation of distribution algorithms, pages 75--102. Springer, 2006.
• 11: D. A. Harville. MATRIX ALGEBRA FROM A STATISTICIAN'S PERSPECTIVE. Springer-Verlag, 2008.
• 12: H. Kita, I. Ono, and S. Kobayashi. Theoretical analysis of the unimodal normal distribution crossover for real-coded genetic algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 529--534, 1998.
• 13: H. Kita, I. Ono, and S. Kobayashi. Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 1581--1587, 1999.
• 14: H. Kita and M. Yamamura. A function specialization hypothesis for designing genetic algorithms. In Proceedings of the IEEE Congress on Systems, Man and Cybernetics, pages 579--584, 1999.
• 15: S. Kobayashi. The frontiers of real-coded genetic algorithms. Transactions of the Japanese Society for Artificial intelligence, 24(1):147--162, 2009. In Japanese.
• 16: N. Mori, J. Yoshida, H. Tamaki, H. Kita, and Y. Nishikawa. A thermodynamical selection rule for the genetic algorithm. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 188--192, 1995.
• 17: I. Ono, H. Kita, and S. Kobayashi. A robust real-coded genetic algorithm using unimodal normal distribution crossover augmented by uniform crossover: Effects of self-adaptation of crossover probabilities. In Proceedings of the Genetic and Evolutionary Computation Conference(GECCO 1999), 13-17 July 1999, Orlando, Florida, USA, pages 496--503. Morgan Kaufmann, 1999.
• 18: I. Ono and S. Kobayashi. A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover. In Proceedings of the 7th International Conference on Genetic Algorithms, pages 246--253, 1997.
• 19: Andreas Ostermeier , Andreas Gawelczyk , Nikolaus Hansen, Step-Size Adaption Based on Non-Local Use of Selection Information, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.189-198, October 09-14, 1994
• 20: A. Irfan Oyman , Hans-georg Beyer , Hans-paul Schwefel, Analysis of the (1, λ) - ES on the Parabolic Ridge, Evolutionary Computation, v.8 n.3, p.249-265, September 2000 [doi>10.1162/106365600750078772]
• 21: A. Irfan Oyman , Hans-georg Beyer, Analysis of the (μ/μ, λ) - ES on the Parabolic Ridge, Evolutionary Computation, v.8 n.3, p.267-289, September 2000 [doi>10.1162/106365600750078781]
• 22: J. Sakuma and S. Kobayashi. Extrapolation-directed crossover for real-coded ga: Overcoming deceptive phenomena by extrapolative search. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 655--662, 2001.
• 23: Jun Sakuma , Shigenobu Kobayashi, Latent variable crossover for k-tablet structures and its application to lens design problems, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068226]
• 24: H. Satoh, M. Yamamura, and S. Kobayashi. Minimal generation gap model for GAs considering both exploration and exploitation. In Proceedings of IIZUKA'96, pages 494--497, 1996.
• 25: H. Someya. Theoretical parameter value for appropriate population variance of the distribution of children in real-coded ga. In Proceedings of the IEEE Congress on Evolutionary Computation: CEC 2008 (IEEE World Congress on Computational Intelligence: WCCI 2008), pages 2722-- 2729, 2008.
• 26: H. Someya , M. Yamamura, A robust real-coded evolutionary algorithm with toroidal search space conversion, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.9 n.4, p.254-269, April 2005 [doi>10.1007/s00500-004-0378-3]
• 27: G. Syswerda. A study of reproduction in generational and steady-state genetic algorithms. Foundations of Genetic Algorithms, pages 94--101, 1991.
• 28: O. Takahashi, H. Kita, and S. Kobayashi. A real-coded genetic algorithm using distance dependent alternation model for complex function optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2000, pages 219--226. Morgan Kaufmann, 2000.
• 29: D. Thirens and D. E. Goldberg. Elitist recombination: An integrated selection recombination ga. In Proceedings of the IEEE Congress on Evolutionary Computation, pages 508--512, 1994.
• 30: S. Tsutsui. Sampling bias and search space boundary extension in real coded genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2000, pages 211--218. Morgan Kaufmann, 2000.
• 31: S. Tsutsui, M. Yamamura, and T. Higuchi. Multi-parent recombination with simplex crossover in real coded genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 1999, pages 657--664. Morgan Kaufmann, 1999.
• 32: Andrew Tuson , Peter Ross, Cost Based Operator Rate Adaption: An Investigation, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.461-469, September 22-26, 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Experimentation, Performance

Keywords:
adaptation of expansion rate, function optimization, premature convergence, real-coded genetic algorithms