Improving genetic algorithms performance via deterministic population shrinkage

ABSTRACT

Despite the intuition that the same population size is not needed throughout the run of an Evolutionary Algorithm (EA), most EAs use a fixed population size. This paper presents an empirical study on the possible benefits of a Simple Variable Population Sizing (SVPS) scheme on the performance of Genetic Algorithms (GAs). It consists in decreasing the population for a GA run following a predetermined schedule, configured by a speed and a severity parameter. The method uses as initial population size an estimation of the minimum size needed to supply enough building blocks, using a fixed-size selectorecombinative GA converging within some confidence interval toward good solutions for a particular problem. Following this methodology, a scalability analysis is conducted on deceptive, quasi-deceptive, and non-deceptive trap functions in order to assess whether SVPS-GA improves performances compared to a fixed-size GA under different problem instances and difficulty levels. Results show several combinations of speed-severity where SVPS-GA preserves the solution quality while improving performances, by reducing the number of evaluations needed for success.

REFERENCES

• 1: David H. Ackley, A connectionist machine for genetic hillclimbing, Kluwer Academic Publishers, Norwell, MA, 1987
• 2: J. Arabas, Z. Michalewicz, and J. Mulawka. GAVaPS -- A genetic algorithm with varying population size. International Conference on Evolutionary Computation (IEEE-CEC 1994)}, pages 73--78 vol.1, Jun 1994.
• 3: Thomas Bäck , A. E. Eiben , N. A. L. van der Vaart, An Empirical Study on GAs "Without Parameters", Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.315-324, September 18-20, 2000
• 4: J. Costa, R. Tavares, and A. Rosa. An experimental study on dynamic random variation of population size. IEEE conference on Systems, Man, and Cybernetics (SMC 1999), 1:607---612 vol.1, 1999.
• 5: F. F. de Vega, E. Cantú-Paz, J. López, and T. Manzano. Saving resources with plagues in genetic algorithms. In Parallel Problem Solving from Nature (PPSN VIII), pages 272--281, 2004.
• 6: A. E. Eiben, R. Hinterding, and Z. Michalewicz. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation}, 3:124--141, 1999.
• 7: A. E. Eiben, E. Marchiori, and V.A. Valkó. Evolutionary algorithms with on-the-fly population size adjustment. In Parallel Problem Solving from Nature (PPSN VIII), pages 41--50, 2004.
• 8: A. E. Eiben , Marc Schoenauer , D. W. F. van Krevelen , M. C. Hobbelman , M. A. ten Hagen , R. C. van het Schip, Autonomous selection in evolutionary algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277235]
• 9: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 10: L. Eshelman. The CHC adaptive search algorithm: how to have safe search when engaging in non-traditional genetic recombination. In Foundations of Genetic Algorithms (FOGA 1991), pages 265--283, 1991.
• 11: C. Fernandes and A. Rosa. Self-regulated population size in evolutionary algorithms. In Parallel Problem Solving from Nature (PPSN IX), pages 920--929, 2006.
• 12: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 13: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 14: G. Harik, D. E. Goldberg, E. Cantú-paz, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. In IEEE Conference on Evolutionary Computation (IEEE-CEC 1997), pages 7--12, 1997.
• 15: V. Koumousis and C. Kats aras. A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Transactions on Evolutionary Computation, 10(1):19--28, Feb. 2006.
• 16: J. Laredo, P. Castillo, A. Mora, J. Merelo, and C. Fernandes. Resilience to churn of a peer-to-peer evolutionary algorithm. Int. J. High Performance Systems Architecture, 1(4):260--268, 2008.
• 17: Juan L. Laredo , Agoston E. Eiben , Maarten Steen , Juan J. Merelo, On the Run-Time Dynamics of a Peer-to-Peer Evolutionary Algorithm, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_24]
• 18: Fernando G. Lobo , Cláudio F. Lima, Revisiting evolutionary algorithms with on-the-fly population size adjustment, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144192]
• 19: F. G. Lobo and C. F. Lima. Adaptive population sizing schemes in genetic algorithms. In Parameter Setting in Evolutionary Algorithms, Studies in Computational Intelligence, pages 185--204. Springer Berlin/Heidelberg, 2007.
• 20: K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Technical Report 2002004, University of Illinois at Urbana-Champaign, Urbana, IL., 2001.
• 21: R. E. Smith and E. Smuda. Adaptively resizing populations: Algorithm, analysis, and first results. Complex Systems, 9:47--72, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms

Keywords:
adaptation, genetic algorithms, parameter tuning, performance analysis, self-adaptation