Article

Population implosion in genetic programming

Authors:

Gabriel Catalin Balan,

Liviu PanaitAuthors Info & Claims

GECCO'03: Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartII

Pages 1729 - 1739

Published: 12 July 2003 Publication History

Abstract

With the exception of a small body of adaptive-parameter literature, evolutionary computation has traditionally favored keeping the population size constant through the course of the run. Unfortunately, genetic programming has an aging problem: for various reasons, late in the run the technique become less effective at optimization. Given a fixed number of evaluations, allocating many of them late in the run may thus not be a good strategy. In this paper we experiment with gradually decreasing the population size throughout a genetic programming run, in order to reallocate more evaluations to early generations. Our results show that over four problem domains and three different numbers of evaluations, decreasing the population size is always as good as, and frequently better than, various fixed-sized population strategies.

References

[1]

Streeter, M.J., Keane, M.A., Koza, J.R.: Iterative refinement of computational circuits using Genetic Programming. In Langdon, W.B., Cantú-Paz, E., Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Honavar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M.A., Schultz, A.C., Miller, J.F., Burke, E., Jonoska, N., eds.: GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, Morgan Kaufmann Publishers (2002) 877-884.

Digital Library

[2]

Koza, J.R., Keane, M.A., Yu, J., Mydlowec, W.: Automatic synthesis of electrical circuits containing a free variable using Genetic Programming. In Whitley, D., Goldberg, D., Cantu-Paz, E., Spector, L., Parmee, I., Beyer, H.G., eds.: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), Las Vegas, Nevada, USA, Morgan Kaufmann (2000) 477-484.

[3]

Koza, J.: Genetic Programming: on the Programming of Computers by Means of Natural Selection. MIT Press (1992).

Digital Library

[4]

Luke, S.: When short runs beat long runs. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2001, Morgan Kaufmann Publishers (2001) 74-80.

[5]

De Jong, K.: An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan, Ann Arbor, MI (1975).

Digital Library

[6]

Grefenstette, J.J.: Optimization of control parameters for Genetic Algorithms. IEEE Transactions on Systems Man and Cybernetics 16 (1986) 122-128.

Digital Library

[7]

Schaffer, J.D., Caruana, R.A., Eshelman, L.J., Das, R.: A study of control parameters affecting online performance of Genetic Algorithms for function optimization. In: Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Inc. (1989) 51-60.

Digital Library

[8]

De Jong, K., Spears, W.M.: An analysis of the interacting roles of population size and crossover in Genetic Algorithms. In Schwefel, H.P., Männer, R., eds.: Parallel Problem Solving from Nature - Proceedings of 1st Workshop, PPSN 1. Volume 496., Dortmund, Germany, Springer-Verlag, Berlin, Germany (1991) 38-47.

Digital Library

[9]

Goldberg, D.E., Deb, K., Clark, J.H.: Genetic Algorithms, noise, and the sizing of populations. Complex Systems 6 (1992) 333-362.

[10]

Giguère, P., Goldberg, D.E.: Population sizing for optimum sampling with Genetic Algorithms: A case study of the onemax problem. In Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H., Riolo, R., eds.: Genetic Programming 1998: Proceedings of the Third Annual Conference, University of Wisconsin, Madison, Wisconsin, USA, Morgan Kaufmann (1998) 496-503.

[11]

Federman, F., Dorchak, S.F.: A study of classifier length and population size. In Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H., Riolo, R., eds.: Genetic Programming 1998: Proceedings of the Third Annual Conference, University of Wisconsin, Madison, Wisconsin, USA, Morgan Kaufmann (1998) 629-634.

[12]

Arabas, J., Michalewicz, Z., Mulawka, J.J.: GAVaPS - A Genetic Algorithm with varying population size. In: Proceedings of IEEE Conference on Evolutionary Computation. Volume 1. (1994) 73-78.

[13]

13. Balazs, M.E., Richter, D.L.: A Genetic Algorithm with dynamic population: Experimental results. In Brave, S., Wu, A.S., eds.: Late Breaking Papers at the 1999 Genetic and Evolutionary Computation Conference, Orlando, Florida, USA (1999) 25-30.

[14]

Fuchs, M.: Large populations are not always the best choice in Genetic Programming. In Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M.H., Honavar, V., Jakiela, M., Smith, R.E., eds.: Proceedings of the Genetic and Evolutionary Computation Conference. Volume 2., Orlando, Florida, USA, Morgan Kaufmann (1999) 1033- 1038.

[15]

Wagner, N., Michalewicz, Z.: Genetic Programming with efficient population control for financial time series prediction. In Goodman, E.D., ed.: 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, San Francisco, California, USA (2001) 458-462.

[16]

Luke, S. ECJ 9: A Java EC research system. http://www.cs.umd.edu/projects/plus/ec/ecj/ (2002).

[17]

Cervone, G., Michalski, R., Kaufman, K., Panait, L.: Combining Machine Learning with Evolutionary Computation: Recent results on LEM. In: Proceedings of the Fifth International Workshop on Multistrategy Learning. (2000) 41-58.

Cited By

Burlacu BAffenzeller MKommenda MWinkler SKronberger GAlba E(2013)Visualization of genetic lineages and inheritance information in genetic programmingProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482714(1351-1358)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482714
Silva SDignum SVanneschi L(2012)Operator equalisation for bloat free genetic programming and a survey of bloat control methodsGenetic Programming and Evolvable Machines10.1007/s10710-011-9150-513:2(197-238)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9150-5
Lombraña González DFernández de Vega FCasanova H(2010)Characterizing fault tolerance in genetic programmingFuture Generation Computer Systems10.1016/j.future.2010.02.00626:6(847-856)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.future.2010.02.006
Show More Cited By

Population implosion in genetic programming
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

A dual-population genetic algorithm for adaptive diversity control

A variety of previous works exist on maintaining population diversity of genetic algorithms (GAs). Dual-population GA (DPGA) is a type of multipopulation GA (MPGA) that uses an additional population as a reservoir of diversity. The main population is ...
Adjusting population distance for the dual-population genetic algorithm
AI'07: Proceedings of the 20th Australian joint conference on Advances in artificial intelligence

A dual-population genetic algorithm (DPGA) is a new multipopulation genetic algorithm that solves problems using two populations with different evolutionary objectives. The main population is similar to that of an ordinary genetic algorithm, and it ...
Advanced Population Diversity Measures in Genetic Programming
PPSN VII: Proceedings of the 7th International Conference on Parallel Problem Solving from Nature

This paper presents a survey and comparison of significant diversity measures in the genetic programming literature. This study builds on previous work by the authors to gain a deeper understanding of the conditions under which genetic programming ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

GECCO'03: Proceedings of the 2003 international conference on Genetic and evolutionary computation: PartII

July 2003

2520 pages

ISBN:3540406034

Editor:
Erick Cantú-Paz
Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 July 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burlacu BAffenzeller MKommenda MWinkler SKronberger GAlba E(2013)Visualization of genetic lineages and inheritance information in genetic programmingProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482714(1351-1358)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482714
Silva SDignum SVanneschi L(2012)Operator equalisation for bloat free genetic programming and a survey of bloat control methodsGenetic Programming and Evolvable Machines10.1007/s10710-011-9150-513:2(197-238)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s10710-011-9150-5
Lombraña González DFernández de Vega FCasanova H(2010)Characterizing fault tolerance in genetic programmingFuture Generation Computer Systems10.1016/j.future.2010.02.00626:6(847-856)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.future.2010.02.006
Silva SCosta E(2009)Dynamic limits for bloat control in genetic programming and a review of past and current bloat theoriesGenetic Programming and Evolvable Machines10.1007/s10710-008-9075-910:2(141-179)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1007/s10710-008-9075-9
Fillon CBartoli A(2006)A divide & conquer strategy for improving efficiency and probability of success in genetic programmingProceedings of the 9th European conference on Genetic Programming10.1007/11729976_2(13-23)Online publication date: 10-Apr-2006
https://dl.acm.org/doi/10.1007/11729976_2
Silva SCosta EO'Reilly U(2005)Resource-limited genetic programmingProceedings of the 7th annual conference on Genetic and evolutionary computation10.1145/1068009.1068290(1673-1680)Online publication date: 25-Jun-2005
https://dl.acm.org/doi/10.1145/1068009.1068290
Daida JO'Reilly U(2005)Towards identifying populations that increase the likelihood of success in genetic programmingProceedings of the 7th annual conference on Genetic and evolutionary computation10.1145/1068009.1068284(1627-1634)Online publication date: 25-Jun-2005
https://dl.acm.org/doi/10.1145/1068009.1068284

View Options

View options

Figures

Tables

Media

View Table of Conten