Skip to main content

2012 | OriginalPaper | Buchkapitel

Simulated Annealing

verfasst von : Kathryn A. Dowsland, Jonathan M. Thompson

Erschienen in: Handbook of Natural Computing

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Since its introduction as a generic heuristic for discrete optimization in 1983, simulated annealing (SA) has become a popular tool for tackling both discrete and continuous problems across a broad range of application areas. This chapter provides an overview of the technique with the emphasis being on the use of simulated annealing in the solution of practical problems. A detailed statement of the algorithm is given, together with an explanation of its inspiration from the field of statistical thermodynamics. This is followed by a brief overview of the theory with emphasis on those results that are important to the decisions that need to be made for a practical implementation. It then goes on to look at some of the ways in which the basic algorithm has been modified in order to improve its performance in the solution of a variety of problems. It also includes a brief section on application areas and concludes with general observations and pointers to other sources of information such as survey articles and websites offering downloadable simulated annealing code.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Aarts EHL, Korst JHM (1989) Simulated annealing and Boltzmann machines. Wiley, ChichesterMATH Aarts EHL, Korst JHM (1989) Simulated annealing and Boltzmann machines. Wiley, ChichesterMATH
Zurück zum Zitat Aarts EHL, Van Laarhoven PJM (1985) Statistical cooling: a general approach to combinatorial optimisation problems. Philips J Res 40:193–226MathSciNet Aarts EHL, Van Laarhoven PJM (1985) Statistical cooling: a general approach to combinatorial optimisation problems. Philips J Res 40:193–226MathSciNet
Zurück zum Zitat Aarts EHL, Korst JHM, Michiels W (2005) Simulated annealing. In: Burke EK, Kendall G (eds) Search methodologies. Springer, New York, pp 187–210 Aarts EHL, Korst JHM, Michiels W (2005) Simulated annealing. In: Burke EK, Kendall G (eds) Search methodologies. Springer, New York, pp 187–210
Zurück zum Zitat Abramson D (1991) Constructing school timetables using simulated annealing: sequential and parallel algorithms. Manag Sci 37:98–113 Abramson D (1991) Constructing school timetables using simulated annealing: sequential and parallel algorithms. Manag Sci 37:98–113
Zurück zum Zitat Alrefaei MH, Andradottir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimisation. Manag Sci 45:748–764MATH Alrefaei MH, Andradottir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimisation. Manag Sci 45:748–764MATH
Zurück zum Zitat Altiparmak F, Karaoglan I (2008) An adaptive tabu-simulated annealing for concave cost transportation problems. J Operational Res Soc 59:331–341MATH Altiparmak F, Karaoglan I (2008) An adaptive tabu-simulated annealing for concave cost transportation problems. J Operational Res Soc 59:331–341MATH
Zurück zum Zitat Anagnostopoulos A, Michel L, Van Hentenryck P, Vergados YA (2006) Simulated annealing approach to the traveling tournament problem. J Scheduling 9:177–193MATH Anagnostopoulos A, Michel L, Van Hentenryck P, Vergados YA (2006) Simulated annealing approach to the traveling tournament problem. J Scheduling 9:177–193MATH
Zurück zum Zitat Arai K, Sakakibara J (2006) Estimation of sea surface temperature, wind speed and water vapour with microwave radiometer data based on simulated annealing. Adv Space Res 37(12):2202–2207 Arai K, Sakakibara J (2006) Estimation of sea surface temperature, wind speed and water vapour with microwave radiometer data based on simulated annealing. Adv Space Res 37(12):2202–2207
Zurück zum Zitat Azizi N, Zolfaghari S (2004) Adaptive temperature control for simulated annealing: a comparative study. Comput Operations Res 31(4):2439–2451MathSciNetMATH Azizi N, Zolfaghari S (2004) Adaptive temperature control for simulated annealing: a comparative study. Comput Operations Res 31(4):2439–2451MathSciNetMATH
Zurück zum Zitat Bai R, Burke EK, Kendall G, McCollum B (2006) A simulated annealing hyper-heuristic for university course timetabling. In: Burke EK, Rudova H (eds) In: Proceedings of PATAT 2006, Brno, Czech Republic, August–September 2006. Lecture notes in computer science, vol 3867. Springer, Heidelberg Bai R, Burke EK, Kendall G, McCollum B (2006) A simulated annealing hyper-heuristic for university course timetabling. In: Burke EK, Rudova H (eds) In: Proceedings of PATAT 2006, Brno, Czech Republic, August–September 2006. Lecture notes in computer science, vol 3867. Springer, Heidelberg
Zurück zum Zitat Bianci L, Dorigo M, Gambardella LM, Gutjahr WJ (2008) A survey on metaheuristics for stochastic combinatorial optimisation. Nat Comput. DOI 101007, Online September 2008 Bianci L, Dorigo M, Gambardella LM, Gutjahr WJ (2008) A survey on metaheuristics for stochastic combinatorial optimisation. Nat Comput. DOI 101007, Online September 2008
Zurück zum Zitat Boese KD, Kahng AB (1994) Best-so-far vs. where-you-are: implications for optimal finite time annealing. Syst Control Lett 22:71–78MathSciNetMATH Boese KD, Kahng AB (1994) Best-so-far vs. where-you-are: implications for optimal finite time annealing. Syst Control Lett 22:71–78MathSciNetMATH
Zurück zum Zitat Bonomi E, Lutton JL (1984) The N-city travelling salesman problem: statistical mechanics and the Metropolis algorithm. SIAM Rev 26:551–568MathSciNetMATH Bonomi E, Lutton JL (1984) The N-city travelling salesman problem: statistical mechanics and the Metropolis algorithm. SIAM Rev 26:551–568MathSciNetMATH
Zurück zum Zitat Brandimarte P, Conterno R, Laface P (1987) FMS production scheduling by simulated annealing. In: Micheletti GF (ed) Proceedings of the 3rd international conference on simulation in manufacturing, Turin, Italy, November 1987. Springer, Berlin, pp 235–245 Brandimarte P, Conterno R, Laface P (1987) FMS production scheduling by simulated annealing. In: Micheletti GF (ed) Proceedings of the 3rd international conference on simulation in manufacturing, Turin, Italy, November 1987. Springer, Berlin, pp 235–245
Zurück zum Zitat Bulgak AA, Sanders JL (1988) Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimise buffer sizes in automatic assembly systems. In: Abrams M, Haigh P, Comfort J (eds) Proceedings of the 1988 winter simulation conference, San Diego, CA, December 1998. IEEE Press, Piscataway, NJ, pp 684–690 Bulgak AA, Sanders JL (1988) Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimise buffer sizes in automatic assembly systems. In: Abrams M, Haigh P, Comfort J (eds) Proceedings of the 1988 winter simulation conference, San Diego, CA, December 1998. IEEE Press, Piscataway, NJ, pp 684–690
Zurück zum Zitat Burke EK, Kendall G, Whitwell G (2008) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem. INFORMS J Comput 21(3):505–516 Burke EK, Kendall G, Whitwell G (2008) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem. INFORMS J Comput 21(3):505–516
Zurück zum Zitat Černy V (1985) A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. J Optimization Theory Appl 45:41–55MATH Černy V (1985) A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. J Optimization Theory Appl 45:41–55MATH
Zurück zum Zitat Chams M, Hertz A, De Werra D (1987) Some experiments with simulated annealing for colouring graphs. Eur J Operational Res 32:260–266MATH Chams M, Hertz A, De Werra D (1987) Some experiments with simulated annealing for colouring graphs. Eur J Operational Res 32:260–266MATH
Zurück zum Zitat Chandy JA, Banerjee P (1996) Parallel simulated annealing strategies for VLSI cell placement. In: Proceedings of the 9th conference on VLSI design, Bangalore, India, January 1996. IEEE Computer Society, Washington, pp 37–42 Chandy JA, Banerjee P (1996) Parallel simulated annealing strategies for VLSI cell placement. In: Proceedings of the 9th conference on VLSI design, Bangalore, India, January 1996. IEEE Computer Society, Washington, pp 37–42
Zurück zum Zitat Chen YL, Ke YL (2004) Multi-objective VAr planning for large-scale power systems using projection-based two-layer simulated annealing algorithms. IEE Proc Generation, Transm Distribution 151(4):555–560 Chen YL, Ke YL (2004) Multi-objective VAr planning for large-scale power systems using projection-based two-layer simulated annealing algorithms. IEE Proc Generation, Transm Distribution 151(4):555–560
Zurück zum Zitat Chen S-H, Yeh C-H (2001) Evolving traders and the business school with genetic programming: a new architecture of the agent based artificial stock market. J Econ Dyn Control 25 (3–4):363–393MATH Chen S-H, Yeh C-H (2001) Evolving traders and the business school with genetic programming: a new architecture of the agent based artificial stock market. J Econ Dyn Control 25 (3–4):363–393MATH
Zurück zum Zitat Chen C-H, Ting C-J, Chang P-C (2005) Applying a hybrid ant colony system to the vehicle routing problem. Lect Notes Comput Sci 3483:417–426 Chen C-H, Ting C-J, Chang P-C (2005) Applying a hybrid ant colony system to the vehicle routing problem. Lect Notes Comput Sci 3483:417–426
Zurück zum Zitat Choi K-S, Sun H, Heng P-A (2004) An efficient and scalable deformable model for virtual reality-based medical applications. Artif Intell Med 32(1):51–69 Choi K-S, Sun H, Heng P-A (2004) An efficient and scalable deformable model for virtual reality-based medical applications. Artif Intell Med 32(1):51–69
Zurück zum Zitat Connolly DT (1990) An improved annealing scheme for the QAP. Eur J Operational Res 46:93–100MathSciNetMATH Connolly DT (1990) An improved annealing scheme for the QAP. Eur J Operational Res 46:93–100MathSciNetMATH
Zurück zum Zitat Cook SA (1971) The complexity of theorem procedures. In: Proceedings of 3rd ACM symposium on the theory of computing, Shaker Heights, OH, 1971. ACM, New York, pp 151–158 Cook SA (1971) The complexity of theorem procedures. In: Proceedings of 3rd ACM symposium on the theory of computing, Shaker Heights, OH, 1971. ACM, New York, pp 151–158
Zurück zum Zitat Cook SA (1972) An overview of computational complexity. Commun ACM 26:400–408 Cook SA (1972) An overview of computational complexity. Commun ACM 26:400–408
Zurück zum Zitat Cornish NJ, Porter EK (2007) The search for massive black hole binaries with LISA. Classical Quantum Gravity 24(23):5729–5755MATH Cornish NJ, Porter EK (2007) The search for massive black hole binaries with LISA. Classical Quantum Gravity 24(23):5729–5755MATH
Zurück zum Zitat Crowe KA, Nelson JD (2005) An evaluation of the simulated annealing algorithm for solving the area-restricted harvest-scheduling model against optimal benchmarks. Can J Forest Res 35(10):2500–2509 Crowe KA, Nelson JD (2005) An evaluation of the simulated annealing algorithm for solving the area-restricted harvest-scheduling model against optimal benchmarks. Can J Forest Res 35(10):2500–2509
Zurück zum Zitat De Andrade MD, Nascimento MAC, Mundim KC, Sobrinho AMC, Malbouisson LAC (2008) Atomic basis sets optimization using the generalized simulated annealing approach: new basis sets for the first row elements. Int J Quantum Chem 108(13):2486–2498 De Andrade MD, Nascimento MAC, Mundim KC, Sobrinho AMC, Malbouisson LAC (2008) Atomic basis sets optimization using the generalized simulated annealing approach: new basis sets for the first row elements. Int J Quantum Chem 108(13):2486–2498
Zurück zum Zitat Degertekin SO (2007) A comparison of simulated annealing and genetic algorithm for optimum design of nonlinear steel space frames. Struct Multidisciplinary Optimization 34(4):347–359 Degertekin SO (2007) A comparison of simulated annealing and genetic algorithm for optimum design of nonlinear steel space frames. Struct Multidisciplinary Optimization 34(4):347–359
Zurück zum Zitat Dowsland KA (1993a) Some experiments with simulated annealing techniques for packing problems. Eur J Operational Res 68:389–399MATH Dowsland KA (1993a) Some experiments with simulated annealing techniques for packing problems. Eur J Operational Res 68:389–399MATH
Zurück zum Zitat Dowsland KA (1993b) Using simulated annealing for efficient allocation of students to practical classes. In: Vidal RVV (ed) Applied simulated annealing. Lecture notes in economics and mathematical systems, vol 396. Springer-Verlag, Berlin Dowsland KA (1993b) Using simulated annealing for efficient allocation of students to practical classes. In: Vidal RVV (ed) Applied simulated annealing. Lecture notes in economics and mathematical systems, vol 396. Springer-Verlag, Berlin
Zurück zum Zitat Dowsland KA, Thompson JM (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648 Dowsland KA, Thompson JM (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648
Zurück zum Zitat Dowsland KA, Soubeiga E, Burke EK (2007) A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. Eur J Oper Res 179(3):759–774MATH Dowsland KA, Soubeiga E, Burke EK (2007) A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation. Eur J Oper Res 179(3):759–774MATH
Zurück zum Zitat Dueck G, Sheuer T (1990) Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys 90:161–175MathSciNetMATH Dueck G, Sheuer T (1990) Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys 90:161–175MathSciNetMATH
Zurück zum Zitat Egeblad J, Pisinger D (2009) Heuristic approaches for the two and three dimensional knapsack packing problem. Comput Oper Res 36(4):1026–1049MathSciNetMATH Egeblad J, Pisinger D (2009) Heuristic approaches for the two and three dimensional knapsack packing problem. Comput Oper Res 36(4):1026–1049MathSciNetMATH
Zurück zum Zitat Eglese RW (1990) Simulated annealing: a general tool for operational research. Eur J Oper Res 46(3):271–281MathSciNetMATH Eglese RW (1990) Simulated annealing: a general tool for operational research. Eur J Oper Res 46(3):271–281MathSciNetMATH
Zurück zum Zitat Erdemir ET, Batta R, Spielman S, Rogerson PA, Blatt A, Flanigan M (2008) Location coverage models with demand originating from nodes and paths: application to cellular network design. Eur J Oper Res 190(3):610–632MathSciNetMATH Erdemir ET, Batta R, Spielman S, Rogerson PA, Blatt A, Flanigan M (2008) Location coverage models with demand originating from nodes and paths: application to cellular network design. Eur J Oper Res 190(3):610–632MathSciNetMATH
Zurück zum Zitat Feo TA, Resende MGC, Smith SH (1994) A greedy randomised adaptive search procedure for maximum independent set. Oper Res 42:860–878MATH Feo TA, Resende MGC, Smith SH (1994) A greedy randomised adaptive search procedure for maximum independent set. Oper Res 42:860–878MATH
Zurück zum Zitat Fleischer M, Jacobson SH (1999) Information theory and the finite time behavior of the simulated annealing algorithm: experimental results. INFORMS J Comput 11:35–43MathSciNetMATH Fleischer M, Jacobson SH (1999) Information theory and the finite time behavior of the simulated annealing algorithm: experimental results. INFORMS J Comput 11:35–43MathSciNetMATH
Zurück zum Zitat Franz A, Hoffmann KH (2003) Threshold accepting as limit case for a modified Tsallis statistics. Appl Math Lett 16:27–31MATH Franz A, Hoffmann KH (2003) Threshold accepting as limit case for a modified Tsallis statistics. Appl Math Lett 16:27–31MATH
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability. WH Freeman, San Francisco, CAMATH Garey MR, Johnson DS (1979) Computers and intractability. WH Freeman, San Francisco, CAMATH
Zurück zum Zitat Ge H, Du W, Qian F (2007) A hybrid algorithm based on particle swarm optimisation and simulated annealing for job shop scheduling. In: Proceedings of ICNC 2007. Third International Conference on Natural Computation, vol 3, Haikou, China, August 2007. IEEE Computer Society, Washington, pp 715–719 Ge H, Du W, Qian F (2007) A hybrid algorithm based on particle swarm optimisation and simulated annealing for job shop scheduling. In: Proceedings of ICNC 2007. Third International Conference on Natural Computation, vol 3, Haikou, China, August 2007. IEEE Computer Society, Washington, pp 715–719
Zurück zum Zitat Gelfand SB, Mitter SK (1989) Simulated annealing with noisy or imprecise measurements. J Opt Theory Appl 69:49–62MathSciNet Gelfand SB, Mitter SK (1989) Simulated annealing with noisy or imprecise measurements. J Opt Theory Appl 69:49–62MathSciNet
Zurück zum Zitat Gendreau M, Potvin JY (2005) Tabu search. In: EK Burke, G Kendall (eds) Introductory tutorials in optimisation, decision support and search methodology. Springer, New York, pp 165–186 Gendreau M, Potvin JY (2005) Tabu search. In: EK Burke, G Kendall (eds) Introductory tutorials in optimisation, decision support and search methodology. Springer, New York, pp 165–186
Zurück zum Zitat Glover F, Greenberg HJ (1989) New approaches for heuristic search: a bilateral link with artificial intelligence. Eur J Oper Res 39:119–130MathSciNetMATH Glover F, Greenberg HJ (1989) New approaches for heuristic search: a bilateral link with artificial intelligence. Eur J Oper Res 39:119–130MathSciNetMATH
Zurück zum Zitat Gogos C, Alefragis P, Housos E (2008) A multi-staged algorithmic process for the solution of the examination timetabling problem. In: Burke EK, Gendreau M (eds) The 7th international conference on the practice and theory of automated timetabling, Montreal, Canada, August 2008 Gogos C, Alefragis P, Housos E (2008) A multi-staged algorithmic process for the solution of the examination timetabling problem. In: Burke EK, Gendreau M (eds) The 7th international conference on the practice and theory of automated timetabling, Montreal, Canada, August 2008
Zurück zum Zitat Goldstein L, Waterman MS (1988) Neighbourhood size in the simulated annealing algorithm. Am J Math Manag Sci 8:409–423MathSciNetMATH Goldstein L, Waterman MS (1988) Neighbourhood size in the simulated annealing algorithm. Am J Math Manag Sci 8:409–423MathSciNetMATH
Zurück zum Zitat Gomes AM, Oliveira JF (2006) Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Oper Res 171(3):811–829MATH Gomes AM, Oliveira JF (2006) Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Oper Res 171(3):811–829MATH
Zurück zum Zitat Greene JW, Supowit KJ (1986) Simulated annealing without rejected moves. IEEE Trans Comput Aided Des CAD-5:221–228 Greene JW, Supowit KJ (1986) Simulated annealing without rejected moves. IEEE Trans Comput Aided Des CAD-5:221–228
Zurück zum Zitat Guo XP, Yang GK, Zhiming W, Huang ZH (2006) A hybrid fine-tuned multi-objective memetic algorithm. IEICE Trans Fundam Electron Commun Comput Sci E89A(3):790–797 Guo XP, Yang GK, Zhiming W, Huang ZH (2006) A hybrid fine-tuned multi-objective memetic algorithm. IEICE Trans Fundam Electron Commun Comput Sci E89A(3):790–797
Zurück zum Zitat Gutjahr WJ, Pflug GCh (1996) Simulated annealing for noisy cost functions. J Global Optimisation 8(1):1–13MathSciNetMATH Gutjahr WJ, Pflug GCh (1996) Simulated annealing for noisy cost functions. J Global Optimisation 8(1):1–13MathSciNetMATH
Zurück zum Zitat Hamacher K (2006) Adaptation in stochastic tunnelling global optimisation of complex potential energy landscapes. Europhys Lett 74:944–950 Hamacher K (2006) Adaptation in stochastic tunnelling global optimisation of complex potential energy landscapes. Europhys Lett 74:944–950
Zurück zum Zitat Hamacher K, Wenzel W (1999) Scaling behaviour of stochastic minimisation algorithms in a perfect funnel landscape. Phys Rev E 59:938–941 Hamacher K, Wenzel W (1999) Scaling behaviour of stochastic minimisation algorithms in a perfect funnel landscape. Phys Rev E 59:938–941
Zurück zum Zitat Hansen P, Mladenovic N (2005) Variable neighbourhood search. In: Burke EK, Kendall G (eds) Search methodologies. Springer, New York, pp 211–238 Hansen P, Mladenovic N (2005) Variable neighbourhood search. In: Burke EK, Kendall G (eds) Search methodologies. Springer, New York, pp 211–238
Zurück zum Zitat Henderson D, Jacobson SH, Johnson AW (2003) The theory and practice of simulated annealing. In: Glover F, Kochenberger GA (eds) The handbook of metaheuristics, International series in operations research and management science, vol 57. Springer, New York Henderson D, Jacobson SH, Johnson AW (2003) The theory and practice of simulated annealing. In: Glover F, Kochenberger GA (eds) The handbook of metaheuristics, International series in operations research and management science, vol 57. Springer, New York
Zurück zum Zitat Huang MD, Romeo F, Sangiovanni-Vincentelli AL (1986) An efficient general cooling schedule for simulated annealing. In: Proceedings of IEEE international conference on computer aided design, Santa Clara, CA, November 1986. IEEE Computer Society, Washington, pp 381–384 Huang MD, Romeo F, Sangiovanni-Vincentelli AL (1986) An efficient general cooling schedule for simulated annealing. In: Proceedings of IEEE international conference on computer aided design, Santa Clara, CA, November 1986. IEEE Computer Society, Washington, pp 381–384
Zurück zum Zitat Jacob D, Raben A, Sarkar A, Grimm J, Simpson L (2008) Anatomy-based inverse planning simulated annealing optimization in high-dose-rate prostrate brachytherapy significant dosimetric advantage over other optimization techniques. Int J Radiat Oncol Biol Phys 72(3):820–827 Jacob D, Raben A, Sarkar A, Grimm J, Simpson L (2008) Anatomy-based inverse planning simulated annealing optimization in high-dose-rate prostrate brachytherapy significant dosimetric advantage over other optimization techniques. Int J Radiat Oncol Biol Phys 72(3):820–827
Zurück zum Zitat Johnson DS, Aragon CR, McGeoch LA, Schevon C (1989) Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Oper Res 37:865–892MATH Johnson DS, Aragon CR, McGeoch LA, Schevon C (1989) Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Oper Res 37:865–892MATH
Zurück zum Zitat Johnson DS, Aragon CR, McGeoch LA, Schevon C (1991) Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Oper Res 39:378–406MATH Johnson DS, Aragon CR, McGeoch LA, Schevon C (1991) Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning. Oper Res 39:378–406MATH
Zurück zum Zitat Jwo W-S, Liu C-W, Liu C-C, Hsiao Y-Y (1995) Hybrid expert system and simulated annealing approach to optimal reactive power planning. IEE Proc Generation, Transm Distribution 142(4):381–385 Jwo W-S, Liu C-W, Liu C-C, Hsiao Y-Y (1995) Hybrid expert system and simulated annealing approach to optimal reactive power planning. IEE Proc Generation, Transm Distribution 142(4):381–385
Zurück zum Zitat Kalivas JH (1992) Optimization using variations of simulated annealing. Chemometrics Intell Lab Syst 15(1):1–12 Kalivas JH (1992) Optimization using variations of simulated annealing. Chemometrics Intell Lab Syst 15(1):1–12
Zurück zum Zitat Karp RM (1972) Reducibility amongst combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85–103 Karp RM (1972) Reducibility amongst combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85–103
Zurück zum Zitat Kern W (1986) On the depth of combinatorial optimisation problems. University of Koln Technical Report 8633 Kern W (1986) On the depth of combinatorial optimisation problems. University of Koln Technical Report 8633
Zurück zum Zitat Kirkpatrick CD, Gellat CD, Vecchi MP (1983) Optimisation by simulated annealing. Science 220:671–680MathSciNetMATH Kirkpatrick CD, Gellat CD, Vecchi MP (1983) Optimisation by simulated annealing. Science 220:671–680MathSciNetMATH
Zurück zum Zitat Kubicky CD, Yeh BM, Lessard E, Joe BN, Speight JL, Pouliot J, Hsu I-C (2008) Inverse planning simulated annealing for magnetic resonance imaging-based intracavitary high dose-rate brachytherapy for cervical cancer. Bracytherapy 7(3):242–247 Kubicky CD, Yeh BM, Lessard E, Joe BN, Speight JL, Pouliot J, Hsu I-C (2008) Inverse planning simulated annealing for magnetic resonance imaging-based intracavitary high dose-rate brachytherapy for cervical cancer. Bracytherapy 7(3):242–247
Zurück zum Zitat Kostuch PA (2004) The university course timetabling problem with a 3-phase method. In: Burke EK, Trick M (eds) The practice and theory of automated timetabling V. Lecture notes in computer science, vol 3616. Springer-Verlag, Berlin, pp 109–125 Kostuch PA (2004) The university course timetabling problem with a 3-phase method. In: Burke EK, Trick M (eds) The practice and theory of automated timetabling V. Lecture notes in computer science, vol 3616. Springer-Verlag, Berlin, pp 109–125
Zurück zum Zitat Lin S, Yu VF, Chou S-Y (2008) Solving the truck and trailer problem based on a simulated annealing heuristics. Comput Oper Res, Available online 17-4-2008 (corrected proof) Lin S, Yu VF, Chou S-Y (2008) Solving the truck and trailer problem based on a simulated annealing heuristics. Comput Oper Res, Available online 17-4-2008 (corrected proof)
Zurück zum Zitat Liu X, Pardalos PM, Rajasekaran S, Resende MGC (2000) A GRASP for frequency assignment in mobile radio networks. In: Badrinath BR, Hsu F, Pardalos PM, Rajasejaran S (eds) Mobile networks and computing. DIMACS series on discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence, RI, pp 195–201 Liu X, Pardalos PM, Rajasekaran S, Resende MGC (2000) A GRASP for frequency assignment in mobile radio networks. In: Badrinath BR, Hsu F, Pardalos PM, Rajasejaran S (eds) Mobile networks and computing. DIMACS series on discrete mathematics and theoretical computer science, vol 52. American Mathematical Society, Providence, RI, pp 195–201
Zurück zum Zitat Marsh RE, Riauka TA, McQuarrie SA (2007) Use of a simulated annealing algorithm to fit compartmental models with an application to fractal pharmacokinetics. J Pharm Pharm Sci 10(2):167–178 Marsh RE, Riauka TA, McQuarrie SA (2007) Use of a simulated annealing algorithm to fit compartmental models with an application to fractal pharmacokinetics. J Pharm Pharm Sci 10(2):167–178
Zurück zum Zitat Merlot LTG, Boland N, Hughes BD, Stuckey PJ (2003) A hybrid algorithm for the examination timetabling problem. Lect Notes Comput Sci 2740:207–231 Merlot LTG, Boland N, Hughes BD, Stuckey PJ (2003) A hybrid algorithm for the examination timetabling problem. Lect Notes Comput Sci 2740:207–231
Zurück zum Zitat Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculation by fast computing machines. J Chem Phys 21:1087–1091 Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculation by fast computing machines. J Chem Phys 21:1087–1091
Zurück zum Zitat Mitra D, Romeo F, Sangiovanni-Vincentelli AL (1986) Convergence and finite time behaviour of simulated annealing. Adv Appl Probability 18:747–771MathSciNetMATH Mitra D, Romeo F, Sangiovanni-Vincentelli AL (1986) Convergence and finite time behaviour of simulated annealing. Adv Appl Probability 18:747–771MathSciNetMATH
Zurück zum Zitat Monem MJ, Namdarian R (2005) Application of simulated annealing (SA) techniques for optimal water distribution in irrigation canals. Irrigation Drainage 54(4):365–373 Monem MJ, Namdarian R (2005) Application of simulated annealing (SA) techniques for optimal water distribution in irrigation canals. Irrigation Drainage 54(4):365–373
Zurück zum Zitat Morgenstern C, Shapiro H (1989) Chromatic number approximation using simulated annealing. Technical Report CS86-1, Department of Computer Science, University of New Mexico Morgenstern C, Shapiro H (1989) Chromatic number approximation using simulated annealing. Technical Report CS86-1, Department of Computer Science, University of New Mexico
Zurück zum Zitat Morton GC, Sangreacha R, Halina P, Loblaw A (2008) A comparison of anatomy-based inverse planning with simulated annealing and graphical optimization for high-dose-rate prostrate brachytherapy. Brachytherapy 7(1):12–16 Morton GC, Sangreacha R, Halina P, Loblaw A (2008) A comparison of anatomy-based inverse planning with simulated annealing and graphical optimization for high-dose-rate prostrate brachytherapy. Brachytherapy 7(1):12–16
Zurück zum Zitat Moscato P, Fontanari JF (1990) Stochastic versus deterministic update in simulated annealing. Phys Lett A 146:204–208 Moscato P, Fontanari JF (1990) Stochastic versus deterministic update in simulated annealing. Phys Lett A 146:204–208
Zurück zum Zitat Nissen V (1995) An overview of evolutionary algorithms in management applications. In: Biethahn J, Nissen V (eds) Evolutionary algorithms in management applications. Springer Verlag, New York, pp 44–97 Nissen V (1995) An overview of evolutionary algorithms in management applications. In: Biethahn J, Nissen V (eds) Evolutionary algorithms in management applications. Springer Verlag, New York, pp 44–97
Zurück zum Zitat Ogbu FA, Smith DK (1990) The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Comput Oper Res 17:243–253MathSciNetMATH Ogbu FA, Smith DK (1990) The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Comput Oper Res 17:243–253MathSciNetMATH
Zurück zum Zitat Osman IH (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Oper Res 41:421–451MATH Osman IH (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Oper Res 41:421–451MATH
Zurück zum Zitat Outeiro MT, Chibante R, Carvalho AS, de Almeida AT (2008) A parameter optimized model of a proton exchange membrane fuel cell including temperature effects. J Power Sources 185(2):952–960 Outeiro MT, Chibante R, Carvalho AS, de Almeida AT (2008) A parameter optimized model of a proton exchange membrane fuel cell including temperature effects. J Power Sources 185(2):952–960
Zurück zum Zitat Pakhira MK (2003) A hybrid genetic algorithm using probabilistic selection. J Inst Eng (India) 84:23–30 Pakhira MK (2003) A hybrid genetic algorithm using probabilistic selection. J Inst Eng (India) 84:23–30
Zurück zum Zitat Paya I, Yepes V, Gonzalez-Vidosa F, Hospitaler A (2008) Multiobjective optimization of concrete frames by simulated annealing. Comput Aided Civil Infrastructure Eng 23(8):596–610 Paya I, Yepes V, Gonzalez-Vidosa F, Hospitaler A (2008) Multiobjective optimization of concrete frames by simulated annealing. Comput Aided Civil Infrastructure Eng 23(8):596–610
Zurück zum Zitat Pedamallu CS, Ozdamar L (2008) Comparison of simulated annealing, interval partitioning and hybrid algorithms in constrained global optimisation. In: Siarry P, Michalewicz Z (eds) Advances in metaheuristics for hard optimization 2008. Natural computing series. Springer, Berlin, pp 1–22 Pedamallu CS, Ozdamar L (2008) Comparison of simulated annealing, interval partitioning and hybrid algorithms in constrained global optimisation. In: Siarry P, Michalewicz Z (eds) Advances in metaheuristics for hard optimization 2008. Natural computing series. Springer, Berlin, pp 1–22
Zurück zum Zitat Penna TJP (2008) Travelling salesman problem and Tsallis statistics. Phys Rev E 51:R1–R3 Penna TJP (2008) Travelling salesman problem and Tsallis statistics. Phys Rev E 51:R1–R3
Zurück zum Zitat Perea C, Alcaca J, Yepes V, Gonzalez-Vidosa F, Hospitaler A (2008) Design of reinforced concrete bridge frames by heuristic optimization. Adv Eng Software 39(8):676–688 Perea C, Alcaca J, Yepes V, Gonzalez-Vidosa F, Hospitaler A (2008) Design of reinforced concrete bridge frames by heuristic optimization. Adv Eng Software 39(8):676–688
Zurück zum Zitat Rodriguez-Tello E, Hao J-K, Torres-Jimenez J (2008) An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput Oper Res 35:3331–3346MATH Rodriguez-Tello E, Hao J-K, Torres-Jimenez J (2008) An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput Oper Res 35:3331–3346MATH
Zurück zum Zitat Ropke S, Pisinger D (2006) An adaptive large neighbourhood search heuristics for the pickup and delivery problem with time windows. Transportation Sci 40:455–472 Ropke S, Pisinger D (2006) An adaptive large neighbourhood search heuristics for the pickup and delivery problem with time windows. Transportation Sci 40:455–472
Zurück zum Zitat Salamon P, Suibani P, Frost R (2002) Facts, conjectures and improvements for simulated annealing. SIAM Monographs on Mathematical Modeling and Computation 7, Society for Industrial and Applied Mathematics Salamon P, Suibani P, Frost R (2002) Facts, conjectures and improvements for simulated annealing. SIAM Monographs on Mathematical Modeling and Computation 7, Society for Industrial and Applied Mathematics
Zurück zum Zitat Santé-Riveira I, Boullón-Magán M, Crecente-Maseda R, Miranda-Barrós D (2008) Algorithm based on simulated annealing for land-use allocation. Comput Geosci 34(3):259–268 Santé-Riveira I, Boullón-Magán M, Crecente-Maseda R, Miranda-Barrós D (2008) Algorithm based on simulated annealing for land-use allocation. Comput Geosci 34(3):259–268
Zurück zum Zitat Sechen D, Braun D, Sangiovanni-Vincetelli A (1988) Thunderbird: a complete standard cell layout package. IEEE J Solid State Circuits 23:410–420 Sechen D, Braun D, Sangiovanni-Vincetelli A (1988) Thunderbird: a complete standard cell layout package. IEEE J Solid State Circuits 23:410–420
Zurück zum Zitat Seçkiner SU, Kurt M (2007) A simulated annealing approach to the solution of job rotation scheduling problems. Appl Math Comput 188(1):31–45MATH Seçkiner SU, Kurt M (2007) A simulated annealing approach to the solution of job rotation scheduling problems. Appl Math Comput 188(1):31–45MATH
Zurück zum Zitat Szu H, Hartley R (1987) Fast simulated annealing. Phys Lett A 122:157–162 Szu H, Hartley R (1987) Fast simulated annealing. Phys Lett A 122:157–162
Zurück zum Zitat Tavakkoli-Moghaddam R, Safaei N, Kah MMO, Rabbani M (2007) A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. J Franklin Inst 344(5):406–425MathSciNet Tavakkoli-Moghaddam R, Safaei N, Kah MMO, Rabbani M (2007) A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing. J Franklin Inst 344(5):406–425MathSciNet
Zurück zum Zitat Teitz MB, Bart P (1968) Heuristics methods for estimating the generalised vertex median of a weighted graph. Oper Res 16:955–961MATH Teitz MB, Bart P (1968) Heuristics methods for estimating the generalised vertex median of a weighted graph. Oper Res 16:955–961MATH
Zurück zum Zitat Tewari S, Arnold J, Bhandarkar SM (2008) Likelihood of a particular order of genetic markers and the construction of genetic maps. J Bioinform Comput Biol 6(1):125–162 Tewari S, Arnold J, Bhandarkar SM (2008) Likelihood of a particular order of genetic markers and the construction of genetic maps. J Bioinform Comput Biol 6(1):125–162
Zurück zum Zitat Thompson JM, Dowsland KA (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648MATH Thompson JM, Dowsland KA (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648MATH
Zurück zum Zitat Thompson JM, Dowsland KA (1996) General cooling schedules for a simulated annealing based timetabling system. In: Burke EK, Ross P (eds) Practice and theory of automated timetabling. Lecture notes in computer science, vol 1153. Springer-Verlag, Berlin Thompson JM, Dowsland KA (1996) General cooling schedules for a simulated annealing based timetabling system. In: Burke EK, Ross P (eds) Practice and theory of automated timetabling. Lecture notes in computer science, vol 1153. Springer-Verlag, Berlin
Zurück zum Zitat Tiourine S, Hurkens C, Lenstra JK (1995) An overview of algorithmic approaches to frequency assignment problems. Technical report, EUCLID CALMA project, Eindhoven University of Technology Tiourine S, Hurkens C, Lenstra JK (1995) An overview of algorithmic approaches to frequency assignment problems. Technical report, EUCLID CALMA project, Eindhoven University of Technology
Zurück zum Zitat Triki E, Collette Y, Siarry P (2005) A theoretical study on the behavior of simulated annealing leading to a new cooling schedule. Eur J OR 166:77–92MathSciNetMATH Triki E, Collette Y, Siarry P (2005) A theoretical study on the behavior of simulated annealing leading to a new cooling schedule. Eur J OR 166:77–92MathSciNetMATH
Zurück zum Zitat Tsallis C, Stariolo DA (1996) Generalized simulated annealing. Phys A 233:395–406 Tsallis C, Stariolo DA (1996) Generalized simulated annealing. Phys A 233:395–406
Zurück zum Zitat Tuga M, Berretta R, Mendes A (2007) A hybrid simulated annealing with Kempe chain neighbourhood for the university timetabling problem. In: Lee R, Chowdhury M, Ray S, Lee T (eds) 6th IEEE/ACIS Conference Proceedings Computer and Information Science 2007, Melbourne, Australia, July 2007. IEEE Computer Society, Washington, pp 400–405 Tuga M, Berretta R, Mendes A (2007) A hybrid simulated annealing with Kempe chain neighbourhood for the university timetabling problem. In: Lee R, Chowdhury M, Ray S, Lee T (eds) 6th IEEE/ACIS Conference Proceedings Computer and Information Science 2007, Melbourne, Australia, July 2007. IEEE Computer Society, Washington, pp 400–405
Zurück zum Zitat Vakharia AJ, Chang Y-L (1990) A simulated annealing approach to scheduling a manufacturing cell. Naval Res Logistics 37:559–577MathSciNetMATH Vakharia AJ, Chang Y-L (1990) A simulated annealing approach to scheduling a manufacturing cell. Naval Res Logistics 37:559–577MathSciNetMATH
Zurück zum Zitat Van Breedam A (1995) Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur J Operational Res 86(3):480–490MATH Van Breedam A (1995) Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur J Operational Res 86(3):480–490MATH
Zurück zum Zitat Van Hentenryck P, Vergados Y (2007) Population-based simulated annealing for traveling tournaments. Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Vancouver, Canada, AAAI Press, pp 267–271 Van Hentenryck P, Vergados Y (2007) Population-based simulated annealing for traveling tournaments. Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Vancouver, Canada, AAAI Press, pp 267–271
Zurück zum Zitat Van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. Kluwer, Dordrecht, The NetherlandsMATH Van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. Kluwer, Dordrecht, The NetherlandsMATH
Zurück zum Zitat Wales DJ, Scheraga HA (1999) Chemistry: global optimisation of clusters, crystals and biomolecules. Science 285:1368–1372 Wales DJ, Scheraga HA (1999) Chemistry: global optimisation of clusters, crystals and biomolecules. Science 285:1368–1372
Zurück zum Zitat Wishart JD, Dong Z, Secanell MM (2006) Optimization of a PEM fuel cell system for low-speed hybrid electric vehicles. In: Proceedings of the ASME Design Engineering Technical Conference 2006, Philadelphia, PA, September 2006 Wishart JD, Dong Z, Secanell MM (2006) Optimization of a PEM fuel cell system for low-speed hybrid electric vehicles. In: Proceedings of the ASME Design Engineering Technical Conference 2006, Philadelphia, PA, September 2006
Zurück zum Zitat Wong, DF, Leong HW, Liu HW (1998) Simulated annealing for VLSI design. The Springer International Series in Engineering and Computer Science, vol 42. Springer, Berlin Wong, DF, Leong HW, Liu HW (1998) Simulated annealing for VLSI design. The Springer International Series in Engineering and Computer Science, vol 42. Springer, Berlin
Zurück zum Zitat Wright M (1991) Scheduling English cricket umpires. J OR Soc 42:447–452 Wright M (1991) Scheduling English cricket umpires. J OR Soc 42:447–452
Zurück zum Zitat Wright M (1996) School timetabling using heuristic search. J OR Soc 47:347–357 Wright M (1996) School timetabling using heuristic search. J OR Soc 47:347–357
Zurück zum Zitat Wright M (2001) Subcost-guided search – experiments with timetabling problems. J Heuristics 7:251–260MATH Wright M (2001) Subcost-guided search – experiments with timetabling problems. J Heuristics 7:251–260MATH
Zurück zum Zitat Yu P, Dai M-G, Wang J-L, Wu J-S (2008) Joint inversion of gravity and seismic data based on common gridded model with random density and velocity distributions. Chinese J Geophys 51(3):845–852 Yu P, Dai M-G, Wang J-L, Wu J-S (2008) Joint inversion of gravity and seismic data based on common gridded model with random density and velocity distributions. Chinese J Geophys 51(3):845–852
Zurück zum Zitat Zolfaghari S, Liang M (2002) Comparative study of simulated annealing, genetic algorithms and tabu search for solving binary and comprehensive machine-grouping problems. Int J Prod Res 40:2141–2158MATH Zolfaghari S, Liang M (2002) Comparative study of simulated annealing, genetic algorithms and tabu search for solving binary and comprehensive machine-grouping problems. Int J Prod Res 40:2141–2158MATH
Metadaten
Titel
Simulated Annealing
verfasst von
Kathryn A. Dowsland
Jonathan M. Thompson
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-540-92910-9_49