Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Preventing Premature Convergence to Local Optima in Genetic Algorithms via Random Offspring Generation

  • Conference paper

Abstract

TheGenetic Algorithms (GAs) paradigm is being used increasingly in search and optimization problems. The method has shown to be efficient and robust in a considerable number of scientific domains, where the complexity and cardinality of the problems considered elected themselves as key factors to be taken into account. However, there are still some insufficiencies; indeed, one of the major problems usually associated with the use ofGAs is the premature convergence to solutions coding local optima of the objective function. The problem is tightly related with the loss of genetic diversity of theGA’s population, being the cause of a decrease on the quality of the solutions found. Out of question, this fact has lead to the development of different techniques aiming to solve, or at least to minimize the problem; traditional methods usually work to maintain a certain degree of genetic diversity on the target populations, without affecting the convergence process of theGA. In one’s work, some of these techniques are compared and an innovative one, theRandom Offspring Generation, is presented and evaluated in its merits. TheTraveling Salesman Problem is used as a benchmark.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

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

    Google Scholar 

  2. DeJong, K.A.: An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Doctoral Dissertation. University of Michigan, Ann Arbor (1975)

    Google Scholar 

  3. Grenfenstette, J.J., Gopal, R., Rosmaita, B., van Gucht, D.: Genetic Algorithms for the Traveling Salesman Problem. In: Grenfenstette, J. (ed.) Proceedings of the Second International Conference on Genetic Algorithms and their Applications. MIT/Lawrence Erlbaum Associates, Cambridge/Hillsdale (1987)

    Google Scholar 

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

    Google Scholar 

  5. Kureichick, V., Melikhov, A.N., Miaghick, V.V., Savelev, O.V., Topchy, A.P.: Some New Features in the Genetic Solution of the Traveling Salesman Problem. In: Parmee, I., Denham, M.J. (eds.) Adaptive Computing in Engineering Design and Control 1996(ACEDC 1996), 2nd International Conference of the Integration of Genetic Algorithms and Neural Network Computing and Related Adaptive Computing with Current Engineering Practice, Plymouth, UK (March 1996)

    Google Scholar 

  6. Laporte, G.: The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms. European Journal of Operational Research 59, 231–247 (1992)

    Article MATH  Google Scholar 

  7. Muhlenbein, H.: Evolution in Time and Space - The Parallel Genetic Algorithm. In: Rawlins, G. (ed.) Foundations of Genetic Algorithms, San Mateo, pp. 316–337. Morgan-Kaufmann, San Francisco (1991)

    Google Scholar 

  8. Reinelt, G.: TSPLIB 1995. Universitat Heidelberg (1995)

    Google Scholar 

  9. Rocha, M., Neves, J.: An Analysis of Genetic Algorithms applied to the Traveling Salesman Problem. Technical Report, Universidade do Minho (1998)

    Google Scholar 

  10. Schleuter, M.G.: ASPARAGOS - An Asynchronous Parallel Genetic Optimization Strategy. In: Schafer, J.D. (ed.) Proceedings of the Third International Conference on Genetic Algorithms. George-Mason University, Morgan Kaufman (1989)

    Google Scholar 

  11. Starkweather, T., McDaniel, S., Mathias, K., Whitley, D., Whitley, C.: A Comparison of Genetic Sequencing Algorithms. In: Belew, R., Booker, L. (eds.) Proceedings ofthe Fourth International Conference on Genetic Algorithms. Morgan-Kaufmann, New York (1991)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Informática, Universidade do Minho, Largo do Paço, 4709, Braga Codex, Portugal

    Miguel Rocha & José Neves

Authors
  1. Miguel Rocha

    You can also search for this author inPubMed Google Scholar

  2. José Neves

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Thinking Machines Corporation, 16 New England Executive Park, 01803, Burlington, MA, USA

    Ibrahim Imam

  2. LRI, UMR CNRS 8623, Bât, 490, Université de Paris-Sud 11, 91405, Orsay, France

    Yves Kodratoff

  3.  ,  

    Ayman El-Dessouki

  4. Department of Computer Science, Texas State University-San Marcos, Nueces 247, 601 University Drive, 78666-4616, San Marcos, TX, USA

    Moonis Ali

Rights and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Rocha, M., Neves, J. (1999). Preventing Premature Convergence to Local Optima in Genetic Algorithms via Random Offspring Generation. In: Imam, I., Kodratoff, Y., El-Dessouki, A., Ali, M. (eds) Multiple Approaches to Intelligent Systems. IEA/AIE 1999. Lecture Notes in Computer Science(), vol 1611. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48765-4_16

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp