Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Revisiting the Simulated Annealing Algorithm from a Teaching Perspective

  • Conference paper
  • First Online:
International Joint Conference SOCO’16-CISIS’16-ICEUTE’16 (SOCO 2016, CISIS 2016, ICEUTE 2016)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 527))

Abstract

Hill climbing and simulated annealing are two fundamental search techniques integrating most artificial intelligence and machine learning courses curricula. These techniques serve as introduction to stochastic and probabilistic based metaheuristics. Simulated annealing can be considered a hill-climbing variant with a probabilistic decision. While simulated annealing is conceptually a simple algorithm, in practice it can be difficult to parameterize. In order to promote a good simulated annealing algorithm perception by students, a simulation experiment is reported here. Key implementation issues are addressed, both for minimization and maximization problems. Simulation results are presented.

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

Similar content being viewed by others

References

  1. Russel, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Pearson Education, Upper Saddle River (2014)

    Google Scholar 

  2. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953)

    Article  MATH  Google Scholar 

  3. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  4. Nandhini, M., Kanmani, S.: A survey of simulated annealing methodology for university course timetabling. Int. J. Recent Trends Eng. 1(2), 177–178 (2009)

    Google Scholar 

  5. Wang, C., Mua, D., Zhao, F., Sutherland, J.W.: A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Comput. Ind. Eng. 83, 111–122 (2015)

    Article  Google Scholar 

  6. Wang, S., Zuo, X., Liu, X., Zhao, X., Li, J.: Solving dynamic double row layout problem via combining simulated annealing and mathematical programming. Appl. Soft Comput. 37, 303–310 (2015)

    Article  Google Scholar 

  7. Behnck, L.P., Doering, D., Pereira, C.P., Rettberg, A.: A modified simulated annealing algorithm for SUAVs path planning. IFAC-PapersOnLine 48(10), 63–68 (2015)

    Article  Google Scholar 

  8. Ingber, L.: Very fast simulated re-annealing. Mathl. Comput. Model. 2(8), 967–973 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ingber, L.: Practice versus theory. Mathl. Comput. Model. 18(11), 29–57 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  10. Mirhosseini, S.H., Yarmohamadi, H., Kabudian, J.: MiGSA: a new simulated annealing algorithm with mixture distribution as generating function. In: 4th International Conference on Computer and Knowledge Engineering, pp. 455–461. IEEE (2014)

    Google Scholar 

  11. Debudaj-Grabysz, A., Czech, Z.J.: Theoretical and practical issues of parallel simulated annealing. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) PPAM 2007. LNCS, vol. 4967, pp. 189–198. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  12. Misevičius, A.: A modified simulated annealing algorithm for the quadratic assignment problem. Informatica 14(4), 497–514 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ali, M.M., Törn, A., Viitanen, S.: A direct search variant of the simulated annealing algorithm for optimization involving continuous variables. Comput. Oper. Res. 29, 87–102 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Park, M.-W., Kim, Y.-D.: A systematic procedure for setting parameter in simulated annealing algorithms. Comput. Ops. Res. 25(3), 207–217 (1998). Elsevier

    Article  MATH  Google Scholar 

  15. Ameur, W.B.: Computing the initial temperature of simulated annealing. Comput. Optim. Appl. 29, 369–385 (2004). Kluwer Academic Publishers

    Article  MathSciNet  MATH  Google Scholar 

  16. Shakouri, H.G., Shojaee, K., Behnam, M.T.: Investigation on the choice of the initial temperature in the simulated annealing: a Mushy State SA for TSP. In: 17th IEEE Mediterranean Conference on Control & Automation, Thessaloniki, Greece, pp. 1050–1055, 24–26 June 2009

    Google Scholar 

  17. Nourani, Y., Andresen, B.: A comparison of simulated annealing cooling strategies. J. Phys. A: Math. Gen. 31, 8373–8385 (1998)

    Article  MATH  Google Scholar 

  18. Lee, C.-Y., Lee, D.: Determination of initial temperature in fast simulate annealing. Comput. Optim. Appl 58, 503–522 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering, School of Sciences and Technology, INESC TEC – INESC Technology and Science, 5001–801, Vila Real, Portugal

    Paulo B. de Moura Oliveira & Eduardo J. Solteiro Pires

  2. Centro ALGORITMI/Departamento de Informática, Universidade do Minho, Braga, Portugal

    Paulo Novais

Authors
  1. Paulo B. de Moura Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eduardo J. Solteiro Pires
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paulo Novais
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paulo B. de Moura Oliveira .

Editor information

Editors and Affiliations

  1. Computational Intelligence Group, University of the Basque Country (UPV/EHU), San Sebastian, Spain

    Manuel Graña

  2. University of the Basque Country, Vitoria, Spain

    José Manuel López-Guede

  3. Computational Intelligence Group, University of the Basque Country (UPV/EHU), San Sebastian, Spain

    Oier Etxaniz

  4. Department of Civil Engineering, University of Burgos, Burgos, Spain

    Álvaro Herrero

  5. University of Salamanca, Salamanca, Spain

    Héctor Quintián

  6. University of Salamanca, Salamanca, Spain

    Emilio Corchado

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

de Moura Oliveira, P.B., Pires, E.J.S., Novais, P. (2017). Revisiting the Simulated Annealing Algorithm from a Teaching Perspective. In: Graña, M., López-Guede, J.M., Etxaniz, O., Herrero, Á., Quintián, H., Corchado, E. (eds) International Joint Conference SOCO’16-CISIS’16-ICEUTE’16. SOCO CISIS ICEUTE 2016 2016 2016. Advances in Intelligent Systems and Computing, vol 527. Springer, Cham. https://doi.org/10.1007/978-3-319-47364-2_70

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-47364-2_70

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-47363-5

  • Online ISBN: 978-3-319-47364-2

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation