research-article

Idealized dynamic population sizing for uniformly scaled problems

Author:

Fernando G. LoboAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 917 - 924

https://doi.org/10.1145/2001576.2001702

Published: 12 July 2011 Publication History

Abstract

This paper explores an idealized dynamic population sizing strategy for solving additive decomposable problems of uniform scale. The method is designed on top of the foundations of existing population sizing theory for this class of problems, and is carefully compared with an optimal fixed population sized genetic algorithm. The resulting strategy should be close to a lower bound in terms of what can be achieved, performance-wise, by self-adjusting population sizing algorithms for this class of problems.

References

[1]

J. Arabas, Z. Michalewicz, and J. Mulawka. GAVaPS -- a genetic algorithm with varying population size. In Proc. of the First IEEE Conf. on Evolutionary Computation, pages 73--78, Piscataway, NJ, 1994. IEEE Press.

[2]

T. Bäck, A. E. Eiben, and N. A. L. van der Vaart. An empirical study on GAs without parameters. In Parallel Problem Solving from Nature, PPSN VI, LNCS 1917, pages 315--324. Springer, 2000.

Digital Library

[3]

J. E. Cook and D. R. Tauritz. An exploration into dynamic population sizing. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2010, pages 807--814. ACM, 2010.

Digital Library

[4]

A. E. Eiben, E. Marchiori, and V. A. Valko. Evolutionary algorithms with on-the-fly population size adjustment. In X. Yao et al., editors, Parallel Problem Solving from Nature PPSN VIII, LNCS 3242, pages 41--50. Springer, 2004.

[5]

A. E. Eiben, Z. Michalewicz, M. Schoenauer, and J. E. Smith. Parameter control in evolutionary algorithms. In F. G. Lobo, C. F. Lima, and Z. Michalewicz, editors, Parameter Setting in Evolutionary Algorithms, pages 19--46. Springer, 2007.

[6]

W. Feller. An introduction to probability theory and its applications, volume 1. John Wiley and Sons, New York, NY, 2nd edition, 1966.

[7]

C. Fernandes and A. Rosa. A study on non-random mating and varying population size in genetic algorithms using a royal road function. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 60--66. IEEE Press, 2001.

[8]

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

[9]

G. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Evolutionary Computation, 7(3):231--253, 1999.

Digital Library

[10]

G. R. Harik and F. G. Lobo. A parameter-less genetic algorithm. In W. Banzhaf et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, pages 258--265, San Francisco, CA, 1999. Morgan Kaufmann.

Digital Library

[11]

F. G. Lobo and C. F. Lima. Adaptive population sizing schemes in genetic algorithms. In F. G. Lobo, C. F. Lima, and Z. Michalewicz, editors, Parameter Setting in Evolutionary Algorithms, pages 185--204. Springer, 2007.

[12]

H. Mühlenbein and T. Mahning. FDA - A scalable evolutionary algorithm for the optimization of additively decomposed functions. Evolutionary Computation, 7(4):353--376, 1999.

Digital Library

[13]

M. Pelikan. Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms. Springer, 2005.

[14]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2001.

[15]

R. E. Smith and E. Smuda. Adaptively resizing populations: Algorithm, analysis, and first results. Complex Systems, 9:47--72, 1995.

[16]

E. Smorodkina and D. R. Tauritz. Greedy population sizing for evolutionary algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2007, pages 2181--2187. IEEE, 2007.

[17]

T.-L. Yu, K. Sastry, and D. E. Goldberg. Online population size adjusting using noise and substructural measurements. In Proceedings of the IEEE International Conference on Evolutionary Computation, pages 2491--2498, 2005.

Cited By

Goldman BPunch W(2015)Fast and efficient black box optimization using the parameter-less population pyramidEvolutionary Computation10.1162/EVCO_a_0014823:3(451-479)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00148
Karafotias GHoogendoorn MEiben A(2015)Parameter Control in Evolutionary Algorithms: Trends and ChallengesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.230829419:2(167-187)Online publication date: Apr-2015
https://doi.org/10.1109/TEVC.2014.2308294
Aleti AGrunske L(2015)Test data generation with a Kalman filter-based adaptive genetic algorithmJournal of Systems and Software10.1016/j.jss.2014.11.035103:C(343-352)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.jss.2014.11.035
Show More Cited By

Index Terms

Idealized dynamic population sizing for uniformly scaled problems
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

An exploration into dynamic population sizing
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Traditional evolutionary algorithms are powerful problem solvers that have several fixed parameters which require prior specification. Determining good values for any of these parameters can be difficult, as these parameters are generally very sensitive,...
Empirical analysis of ideal recombination on random decomposable problems
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

This paper analyzes the behavior of a selectorecombinative genetic algorithm (GA) with an ideal crossover on a class of random additively decomposable problems (rADPs). Specifically, additively decomposable problems of order k whose subsolution ...
To explore or to exploit: An entropy-driven approach for evolutionary algorithms

An evolutionary algorithm is an optimization process comprising two important aspects: exploration discovers potential offspring in new search regions; and exploitation utilizes promising solutions already identified. Intelligent balance between these ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
123
Total Downloads

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

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Goldman BPunch W(2015)Fast and efficient black box optimization using the parameter-less population pyramidEvolutionary Computation10.1162/EVCO_a_0014823:3(451-479)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00148
Karafotias GHoogendoorn MEiben A(2015)Parameter Control in Evolutionary Algorithms: Trends and ChallengesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2014.230829419:2(167-187)Online publication date: Apr-2015
https://doi.org/10.1109/TEVC.2014.2308294
Aleti AGrunske L(2015)Test data generation with a Kalman filter-based adaptive genetic algorithmJournal of Systems and Software10.1016/j.jss.2014.11.035103:C(343-352)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.jss.2014.11.035
Aleti AMoser IMeedeniya IGrunske L(2014)Choosing the appropriate forecasting model for predictive parameter controlEvolutionary Computation10.1162/EVCO_a_0011322:2(319-349)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1162/EVCO_a_00113
Aleti AMoser IAlba E(2013)Entropy-based adaptive range parameter control for evolutionary algorithmsProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463560(1501-1508)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463560
Karafotias GHoogendoorn MEiben A(2013)Why parameter control mechanisms should be benchmarked against random variation2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557590(349-355)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557590

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents