Self-Adapting Evolutionary Parameters: Encoding Aspects for Combinatorial Optimization Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

Self-Adapting Evolutionary Parameters: Encoding Aspects for Combinatorial Optimization Problems

  • Conference paper
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3448))

Abstract

Evolutionary algorithms are powerful tools in search and optimization tasks with several applications in complex engineering problems. However, setting all associated parameters is not an easy task and the adaptation seems to be an interesting alternative. This paper aims to analyze the effect of self-adaptation of some evolutionary parameters of genetic algorithms (GAs). Here we intend to propose a flexible GA-based algorithm where only few parameters have to be defined by the user. Benchmark problems of combinatorial optimization were used to test the performance of the proposed approach.

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. Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3(2) (1999)

    Google Scholar 

  2. Rojas, I., Gonzalez, J., Pomares, H., Merelo, J., Castillo, P., Romero, G.: Statistical analysis of the main parameters involved in the design of a genetic algorithm. IEEE Transactions on Systems Man and Cybernetics 32, 31–37 (2002)

    Article  Google Scholar 

  3. Angeline, P.J.: Adaptive and self-adaptive evolutionary computation. In: Attikiouzel, Y., Marks, R., Fukuda, T. (eds.) Computational Intelligence, A Dynamic System Perspective, pp. 152–161. IEEE Press, Los Alamitos (1995)

    Google Scholar 

  4. Hinterding, R., Michalewicz, Z., Eiben, A.E.: Adaptation in evolutionary computation: A survey. In: Proceedings of the 4th IEEE International Conference on Evolutionary Computation, pp. 65–69 (1997)

    Google Scholar 

  5. Smith, J., Fogarty, T.C.: Operator and parameter adaptation in genetic algorithms. Soft Computing 1, 81–87 (1997)

    Article  Google Scholar 

  6. Eiben, A.E., Smith, J.E. (eds.): Introduction to Evolutionary Computing. Springer, Heidelberg (2003)

    MATH  Google Scholar 

  7. Davis, L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)

    Google Scholar 

  8. Spears, W.M.: Adapting crossover in evolutionary algorithms. In: Proceedings of the Fourth Annual Conference on Evolutionary Programming, San Diego, CA (1995)

    Google Scholar 

  9. De Jong, K.: The Analysis of the behaviour of a Class of Genetic Adaptive systems. PhD thesis, Department of Computer Science, University of Michigan (1975)

    Google Scholar 

  10. Grefenstette, J.J.: Optimization of control parameters for genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics 16, 122–128 (1986)

    Article  Google Scholar 

  11. Schaffer, J.D., Morishima, A.: An adaptive crossover distribution mechanism for genetic algorithms. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, Cambridge, Massachusetts, United States, pp. 36–40. Lawrence Erlbaum Associates, Inc, Mahwah (1987)

    Google Scholar 

  12. Bremermann, H.J., Rogson, M., Salaff, S.: Global properties of evolution processes. In: Pattee, H.H., Edlsack, E.A., Fein, L., Callahan, A.B. (eds.) Natural Automata and Useful Simulations, pp. 3–41. Spartan Books, Washington D.C (1966)

    Google Scholar 

  13. Smith, J., Fogarty, T.C.: Self-adaptation of mutation rates in a steady-state genetic algorithm. In: Proceedings of IEEE International Conference on Evolutionary Computation, pp. 318–323 (1996)

    Google Scholar 

  14. Bäck, T.: Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Oxford (1996)

    MATH  Google Scholar 

  15. Fogarty, T.C.: Varying the probability of mutation in the genetic algorithm. In: Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 104–109. Morgan Kaufmann Publishers Inc, San Francisco (1989)

    Google Scholar 

  16. Bäck, T.: Self-adaptation in genetic algorithms. In: Varela, F.J., Bourgine, P. (eds.) Proc. of the 1st European Conf. on Artificial Life, pp. 227–235. MIT Press, Cambridge (1992)

    Google Scholar 

  17. Thierens, D., Goldberg, D.E.: Mixing in genetic algorithms. In: Proceedings of the 5th International Conference on Genetic Algorithms, pp. 38–47. Morgan Kaufmann Publishers Inc, San Francisco (1993)

    Google Scholar 

  18. Schaffer, J.D., Eshelman, L.J.: On crossover as an evolutionary viable strategy. In: Belew, R., Booker, L. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 61–68 (1991)

    Google Scholar 

  19. Eshelman, L.J., Caruana, R., Schaffer, J.D.: Biases in the crossover landscape. In: Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 10–19. Morgan Kaufmann Publishers Inc, San Francisco (1989)

    Google Scholar 

  20. Sywerda, G.: Uniform crossover in genetic algorithms. In: Proceedings of the third international conference on Genetic algorithms, pp. 2–9. Morgan Kaufmann Publishers Inc, San Francisco (1989)

    Google Scholar 

  21. Spears, W.M., De Jong, K.: On the virtues of parameterized uniform crossover. In: Belew, R.K., Booker, L.B. (eds.) Proc. of the Fourth Int. Conf. on Genetic Algorithms, San Mateo, CA, pp. 230–236. Morgan Kaufmann, San Francisco (1991)

    Google Scholar 

  22. De Jong, K., Spears, W.M.: A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence 5, 1–26 (1992)

    Article  MATH  Google Scholar 

  23. Spears, W.M.: Crossover or mutation? In: Whitley, L.D. (ed.) Foundations of Genetic Algorithms 2, pp. 221–237. Morgan Kaufmann, San Mateo (1993)

    Google Scholar 

  24. 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, Dortmund, Germany, 1-3 1991, vol. 496, pp. 38–47. Springer, Heidelberg (1991)

    Google Scholar 

  25. Spears, W.M., Anand, V.: A study of crossover operators in genetic programming. In: Raś, Z.W., Zemankova, M. (eds.) ISMIS 1991. LNCS, vol. 542, pp. 409–418. Springer, Heidelberg (1991)

    Google Scholar 

  26. Eiben, A.E.: 3.7. Multi-parent Recombination. IOP Publishing Ltd and Oxford University Press (1995)

    Google Scholar 

  27. Eiben, A.E.: Multiparent recombination in evolutionary computing. Advances in evolutionary computing: theory and applications, 175–192 (2003)

    Google Scholar 

  28. Mumford, C.L.: Comparing representations and recombination operators for the multi-objective 0/1 knapsack problem. In: CEC 2003: Proceedings of The IEEE Conference on Evolutionary Computation, pp. 854–861. IEEE, Los Alamitos (2003)

    Chapter  Google Scholar 

  29. Thierens, D.: Adaptive mutation rate control schemes in genetic algorithms. In: CEC 2002: Proceedings of The IEEE Conference on Evolutionary Computation, pp. 980–985. IEEE, Los Alamitos (2002)

    Google Scholar 

  30. Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, Cambridge (1992)

    Google Scholar 

  31. Khuri, S., Bäck, T., Heitkötter, J.: SAC 94: suite of 0/1 multiple knapsack problem instances (1994), http://elib.zib.de/pub/packages/mp-testdata/ip/sac94-suite

  32. Kimbrough, S.O., Lu, M., Wood, D.H., Wu, D.-J.: Exploring a two-market genetic algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 415–422. Morgan Kaufmann Publishers Inc, San Francisco (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centro Federal de Educação Tecnológica do Paraná-CEFET/PR, Av. Sete de Setembro, 3165, 80230-901, Curitiba, Brazil

    Marcos H. Maruo, Heitor S. Lopes & Myriam R. Delgado

Authors
  1. Marcos H. Maruo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Heitor S. Lopes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Myriam R. Delgado
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/1861, 1040, Vienna, Austria

    Günther R. Raidl

  2. SAP AG, Neurottstr. 16, P.O. Box, Walldorf, Germany

    Jens Gottlieb

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Maruo, M.H., Lopes, H.S., Delgado, M.R. (2005). Self-Adapting Evolutionary Parameters: Encoding Aspects for Combinatorial Optimization Problems. In: Raidl, G.R., Gottlieb, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2005. Lecture Notes in Computer Science, vol 3448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31996-2_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-31996-2_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-25337-2

  • Online ISBN: 978-3-540-31996-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics