The effect of genetic operator probabilities and selection strategies on the performance of a genetic algorithm | SpringerLink
Skip to main content
Springer Nature Link
Log in

The effect of genetic operator probabilities and selection strategies on the performance of a genetic algorithm

  • Genetic Algorithms
  • Conference paper
  • First Online:
Advances in Artificial Intelligence (Canadian AI 1998)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1418))

Abstract

This paper presents a comparison of two genetic algorithms (GAs) that use different selection strategies. The first GA uses the standard selection strategy of roulette wheel selection and generational replacement (STDS), while the second GA uses an intermediate selection strategy in addition to STDS. Our previous research has shown that this intermediate selection strategy, which we call “Keep-Best Reproduction (KBR)”, found solutions of lower cost for a variety of travelling salesman problems. In this paper, we study the effects of crossover and mutation probabilities on STDS as well as on KBR. We study the effect of recombination alone, mutation alone and both together. We compare the performance of the different selection strategies and discuss the environment that each selection strategy needs to flourish in. Overall, KBR is found to be the selection strategy of choice. We also present empirical evidence that suggests that KBR is more robust than STDS with regard to operator probabilities.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baeck, T., “Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms”, Oxford University Press, 1996.

    Google Scholar 

  2. Goldberg, D.E. and Lingle, R., Jr., “Alleles, Loci, and the Traveling Salesman Problem”, Proceedings of the 1st ICGA, pp. 154–159, 1985.

    Google Scholar 

  3. Grefenstette, J.J., Gopal, R., Rosmaita, R., and van Gucht, D., “Genetic Algorithms for the Traveling Salesman Problem”, Proceedings of the 1st ICGA, pp. 160–168, 1985.

    Google Scholar 

  4. Holland, J.H., Adaptation in Natural and Artificial Systems, Ann Arbor, MI, University of Michigan Press, 1975.

    Google Scholar 

  5. McGuire, K.M. and Sabin R.E., “Using a Genetic Algorithm to Find Good Linear Error-Correcting Codes”, Proceedings of the 1998 ACM Symposium on Applied Computing SAC'98”, pp. 332–337, 1998.

    Google Scholar 

  6. Oliver, I.M., Smith, D.J., and Holland, J.R.C., “A Study of Permutation Crossover Operators on the Traveling Salesman Problem”, Proceedings of the 2nd ICGA, pp. 224–230, 1987.

    Google Scholar 

  7. Sandalidis H.G., Stavroulakis P.P., Rodriguez-Tellez J., “A Combinatorial Evolution Strategy for Dynamic Channel Assignment in Cellular Radio”, Proceedings of the 1998 ACM Symposium on Applied Computing SAC'98”, pp. 303–307, 1998.

    Google Scholar 

  8. Starkweather, T., McDaniel, S., et. al, “A Comparison of Genetic Sequencing Operators”, Proceedings of the 4th ICGA, pp. 69–76, 1991.

    Google Scholar 

  9. Thierens, D. and Goldberg, D.E., "Elitist Recombination: An Integrated Selection Recombination GA”, Proceedings of the 1st IEEE World Congress on Computational Intelligence, pp. 508–512, 1994.

    Google Scholar 

  10. Thierens, D., “Selection Schemes, Elitist Recombination and Selection Intensity”, Proceedings of the 7th International Conference on Genetic Algorithms ICGA-97, pp. 152–159, 1997.

    Google Scholar 

  11. Wiese, K. and Goodwin, S.D., “Keep-Best Reproduction: A Selection Strategy for Genetic Algorithms”, Proceedings of the 1998 ACM Symposium on Applied Computing SAC'98, pp. 343–348, 1998.

    Google Scholar 

  12. Wiese K. and Goodwin, S.D., “Parallel Genetic Algorithms for Constrained Ordering Problems”, Proceedings of the 11th International Florida Artificial Intelligence Research Symposium, FLAIRS'98, to appear, 1998.

    Google Scholar 

  13. Whitley, D., Starkweather, T., and D'Ann Fuquay, “Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator”, Proceedings of the 3rd ICGA, pp. 133–140, 1989.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Regina, S4S 0A2, Regina, Saskatchewan, Canada

    Kay Wiese & Scott D. Goodwin

Authors
  1. Kay Wiese
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Scott D. Goodwin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Robert E. Mercer Eric Neufeld

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Wiese, K., Goodwin, S.D. (1998). The effect of genetic operator probabilities and selection strategies on the performance of a genetic algorithm. In: Mercer, R.E., Neufeld, E. (eds) Advances in Artificial Intelligence. Canadian AI 1998. Lecture Notes in Computer Science, vol 1418. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-64575-6_46

Download citation

  • DOI: https://doi.org/10.1007/3-540-64575-6_46

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64575-7

  • Online ISBN: 978-3-540-69349-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation