Abstract
This paper presents a comprehensive review of simulated annealing (SA)-based optimization algorithms. SA-based algorithms solve single and multiobjective optimization problems, where a desired global minimum/maximum is hidden among many local minima/maxima. Three single objective optimization algorithms (SA, SA with tabu search and CSA) and five multiobjective optimization algorithms (SMOSA, UMOSA, PSA, WDMOSA and PDMOSA) based on SA have been presented. The algorithms are briefly discussed and are compared. The key step of SA is probability calculation, which involves building the annealing schedule. Annealing schedule is discussed briefly. Computational results and suggestions to improve the performance of SA-based multiobjective algorithms are presented. Finally, future research in the area of SA is suggested.
Similar content being viewed by others
References
Aarts EHL and van Laarhoven PJM (1985). Statistical cooling: a general approach to combinatorial optimization problems. Philips J Res 40: 193–226.
Aarts EHL and Korst JHM (1989). Simulated Annealing and Boltzmann Machine. Wiley: Chichester.
Alspector J and Allen RB (1987). A neuromorphic VLSI learning system. In: Losleben P (ed). Advanced Research in VLSI. MIT Press, Cambridge, MA, pp 313–349.
Anily S and Federguen A (1987). Simulated Annealing method with general acceptance probablisties. J App Prob 24: 657–667.
Azencott R (1992). Sequential simulated annealing: speed of convergence and acceleration techniques. In: Simulated Annealing: Penalization Techniques. Wiley, New York, p 1.
Azizi N and Zolfaghari S (2004). Adaptive temperature control for simulated annealing: a comparative study. Comput Opns Res 31: 2439–2451.
Bell DA, McErlean FJ, Stewart PM and McClean S (1987). Application of simulated annealing to clustering tuples in database. J Am Soc Inform Sci 41: 98–110.
Bentley PJ and Wakefield JP (1997). Finding acceptable solutions in the pareto-optimal range using multiobjective genetic algorithms. In: Chawdhry PK, Roy R and Pant RK (eds). Proceedings of the 2nd On-Line World Conference on Soft Computing in Engineering Design and Manufacturing (WSC2), pp 23–27.
Bland JA and Dawson GP (1989). Tabu Search Applied to Layout Optimization. Report, Department of Maths, Stats and OR, Trent Polytechnic, UK. Presented at CO89, Leeds.
Casotto A, Romeo F and Sangiovanni-Vincentelli AL (1987). A parallel simulated annealing algorithm for the placement of macro-cells. IEEE Trans Computer-Aided Design 6: 838–847.
Černy V (1985). Thermodynamics approach to the traveling salesman problem: an efficient simulation algorithm. J Optimization Theory Appl 45: 41–51.
Chams M, Hertz A and de Werra D (1987). Some experiments with simulated annealing for coloring graphs. Eur J Opl Res 32: 260–266.
Chattopadhyay A and Seeley CE (1994). A simulated annealing technique for multiobjective optimization of intelligent structures. Smart Mater Struct 3: 98–106.
Chen J, Zhang YF and Nee AYC (1988). Setup planning using Hopfield net and simulated annealing. Int J Product Res 36: 981–1000.
Chen S and Luk BL (1999). Adaptive simulated annealing for optimization in signal processing applications. Signal Process 79: 117–128.
Cho J-H and Kim Y-D (1997). A simulated annealing algorithm for resource constrained project scheduling problems. J Opl Res Soc 48: 736–744.
Chu KW, Deng Y and Reinitz J (1996). Parallel simulated annealing by mixing of states. J Comput Phys 148: 646–662.
Coello Coello CA (1996). An empirical study of evolutionary techniques for multiobjective optimization in engineering design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA.
Coello Coello CA (1999). A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge Inform Sys 1: 269–308.
Collins NE, Eglese RW and Golden BL (1988). Simulated annealing—an annotated bibliography. Am J Math Mngt Sci 8: 209–307.
Connolly DT (1987). Combinatorial optimization using simulated annealing. Report, London School of Economics, London, WC2A 2AE. Presented at the Martin Beale Memorial Symposium, London, July, 1987.
Connolly DT (1988). An improved annealing scheme for the QAP. Eur J Opl Res 46: 93–100.
Czyżak P, Hapke M and Jaszkiewicz A (1994). Application of the Pareto-simulated annealing to the multiple criteria shortest path problem. Technical Report, Politechnika Poznanska Instytut Informatyki, Poland.
Czyżak P and Jaszkiewicz A (1996). A multiobjective metaheuristic approach to the localization of a chain of petrol stations by the capital budgeting model. Control Cybernet 25: 177–187.
Czyżak P and Jaszkiewicz A (1997a). Pareto simulated annealing. In: Fandel G, Gal T (eds). Multiple Criteria Decision Making. Proceedings of the XIIth International Conference, Hagen (Germany). Springer-Verlag, Berlin-Heidelberg, pp 297–307.
Czyżak P and Jaszkiewicz A (1997b). The multiobjective metheuristic approach for optimization of complex manufacturing systems. In: Fandel G, Gal T (eds). Multiple Criteria Decision Making. Proceedings of the XIIth International Conference, Hagen (Germany). Springer-Verlag, Berlin-Heidelberg, pp 591–592.
Czyżak P and Jaszkiewicz A (1998). Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. J Multi-Criteria Decision Anal 7: 34–47.
Eglese RW (1990). Simulated annealing: a tool for operational research. Eur J Opl Res. 46: 271–281.
Eglese RW and Rand GK (1987). Conference seminar timetabling. J Opl Res Soc 38: 591–598.
Faigle U and Schrader R (1988). On the convergence of stationary distributions in simulated annealing algorithms. Inform Process Lett 27: 189–194.
Farhat NH (1987). Optoelectric analogs of self-programming neural nets: architecture and methodologies for implementing fast stochastic learning by simulated annealing. Appl Optics 26: 5093–5103.
Fonseca MC and Fleming PJ (1995). Multiobjective optimization and multiple constraints handling with evolutionary algorithms II: application example. Technical Report 565, University of Sheffeld, Sheffeld, UK.
Geman S and Geman D (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans Pattern Anal Mach Intell 6: 721.
Girard T, Staraj R, Cambiaggio E and Muller F (2001). A simulated annealing algorithm for planner or conformal antenna array synthesis with optimized polarization. Microwave Opt Technol Lett 28: 86–89.
Golenko-Ginzburg D and Sims JA (1992). Using permutation spaces in job-shop scheduling. Asia Pacific J Opn Res 9: 183–193.
Gong G, Lin Y and Qian M (2001). An adaptive simulated annealing algorithm. Stoch Process Appl 94: 95–103.
Glover F and Greenberg HJ (1989). New approaches for heuristic search: a bilateral linkage with artificial intelligence. Eur J Opl Res 39: 119–130.
Greene JW and Supowit KJ (1986). Simulated annealing without rejected move. IEEE Trans Comput Aided Design 5: 221–228.
Grover LK (1986). A new simulated annealing algorithm for standard cell placement. Proceedings of IEEE International Conference on Computer-Aided Design. Santa Clara, pp 378–380.
Hanke M and Li P (2000). Simulated annealing for the optimization of batch distillation process. Comput Chem Engin 24: 1–8.
Hapke M, Jaszkiewicz A and Słowiński R (1996). Interactive analysis of multiple-criteria project scheduling problems. Proceedings of the Fifth International Workshop on Project Management and Scheduling—EURO PMS'96. Poznań, Poland, 11–13.04.96, pp 107–110.
Hapke M, Jaszkiewicz A and Słowiński R (1997). Fuzzy project scheduling with multiple criteria. Proceedings of Sixth IEEE International Conference on Fuzzy Systems, FUZZ-IEEE'97, July 1–5, Barcelona: Spain, pp 1277–1282.
Hapke M, Jaszkiewicz A and Słowiński R (1998a). Fuzzy multi-mode resource-constrained project scheduling with multiple objectives. In: Wêglarz J (ed). Recent Advances in Project Scheduling, Chapter 16. Kluwer Academic Publishers, Dordrecht, pp 355–382.
Hapke M, Jaszkiewicz A and Słowiński R (1998b). Interactive analysis of multiple-criteria project scheduling problems. Eur J Opl Res 107: 315–324.
Hejak B (1988). Cooling schedule for optimal annealing. Math Opns Res 13: 311–329.
Hertz A and de Werra D (1987). Using tabu search techniques for graph coloring. Computing 39: 345–351.
Ingber L (1989). Very fast simulated annealing. Math Comput Model 12: 967.
Ingber L and Rosen B (1992). Genetic algorithms and very fast simulated annealing: a comparison. Math Comput Model 16: 87–100.
Jaszkiewicz A (1997). A metaheuristic approach to multiple objective nurses scheduling. Foundations of Comput Decision Sci 22: 169–184.
Jaszkiewicz A and Ferhat AB (1999). Solving multiple criteria choice problems by interactive trichotomy segmentation. Eur J Opl Res 113: 271–280.
Jeon YJ and Kim JC (2004). Application of simulated annealing and tabu search for loss minimization in distributed systems. Int J Electrical Power Energy Sys 26: 9–18.
Jerrum M and Sinclair A (1988). Approximating the permanent. Internal Report CSR-275-88, Department of Computer Science, University of Edinburgh.
Johnson DS, Aragon CR, Mcgeogh LA and Schevon C (1989). Optimization by simulated annealing: An experimental evolution part I (graph partitioning). Opns Res 37: 865–892.
Johnson DS, Aragon CR, Mcgeogh LA and Schevon C (1991). Optimization by simulated annealing: An experimental evolution part II (graph coloring and number partitioning). Opns Res 39: 378–406.
Kim JU, Kim YD and Shim SO (2002). Heuristic algorithms for a multi-period multi-stop transportation planning problem. J Opl Res Soc 53: 1027–1037.
Kirkpatrick S, Gelatt Jr CD and Vecchi MP (1983). Optimization by simulated annealing. Science 220: 671–680.
Kouvelis P and Chiang W (1992). A simulated annealing procedure for single row layout problems in flexible manufacturing systems. Int J Product Res 30: 717–732.
Kumral M (2003). Application of chance-constrained programming based on multiobjective simulated annealing to solve a mineral blending problem. Engin Optimi 35: 661–673.
Kunha AG, Oliveira P and Covas JA (1997). Use of genetic algorithms in multicriteria optimization to solve industrial problems. In: Back T (ed). Proceedings of the Seventh International Conference on Genetic Algorithms. pp 682–688.
Lam J and Delosme JM (1988a). An efficient simulated annealing schedule: derivation. Technical Report 8816, Electrical Engineering Department, Yale, New Havan, CT, September.
Lam J and Delosme JM (1988b). An efficient simulated annealing schedule: implementation and evaluation. Technical Report 8817, Electrical Engineering Department, Yale, New Havan, CT, September.
Liu HC and Huang JS (1998). Pattern recognition using evolution algorithms with fast simulated annealing. Pattern Recognition Lett 19: 403–413.
Lucic P and Teodorovic D (1999). Simulated annealing for the multiobjective aircrew roistering problem. Transportation Res Part A 33: 19–45.
Lundy M and Mees A (1986). Convergence of an annealing algorithm. Mathematical Programming 34: 111–124.
Maffioli F (1987). Randomized heuristic for NP-hard problem. In: Andreatta G, Mason F and Serafini P (eds). Advanced School on Stochastic in Combinatorial Optimization. World Scientific, Singapore, pp 760–793.
Matsuo H, Suh CJ and Sullivan RS (1988). A controlled search simulated annealing method for the general jobshop scheduling problem. Working paper # 03-04-88, Department of Management, The University of Texas at Austin, Austin.
McCormick G and Powell RS (2004). Derivation of near-optimal pump schedules for water distribution by simulated annealing. J Opl Res Soc 55: 728–736.
Meller RD and Bozer YA (1996). A new simulated annealing algorithm facility layout problem. Int J Product Res 34: 1675–1692.
Metropolis N et al (1953). Equations of state calculations by fast computing machines. J Chem Phys 21: 1087–1092.
Mingjun J and Huanwen T (2004). Application of chaos in simulated annealing. Chaos, Solitons Fractals 21: 933–944.
Mitra D, Romeo F and Sangiovanni-Vincentelli AL (1986). Convergence of finite-time behavior of simulated annealing. Adv Appl Prob 18: 747–771.
Mukhopadhyay SK, Singh MK and Srivastava R (1998). FMS machine loading: a simulated annealing approach. Int J Product Res 36: 1529–1547.
Nwana V, Darby Dowman K and Mitra G (2004). A co-operative parallel heuristic for mixed zero-one linear programming: combining simulated annealing with branch and bound. Eur J Opl Res 164: 12–23.
Otten RHJM and van Ginneken LPPP (1984). Floorpan design using simulated annealing. In: Proceedings of the IEEE International Conference in Computer-Aided Design. Santa Clara, pp 96–98.
Pareto V (1896). Cours D'Economie Politique, Vol. I and II. F. Rouge: Lausanne.
Pirlot M (1996). General local search methods. Eur J Opl Res 92: 493–511.
Romeo F and Sangiovanni-Vincentelli AL (1985). Probablistic hill climbing algorithms: properties and applications. Proceedings of Chapel Hill Conference on VLSI, Chapel Hill, NC, pp 393–403.
Rosen LS and Harmonosky MC (2003). An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Comput Opns Res 32: 343–358.
Rutenbar RA (1989). Simulated annealing algorithms: an overview. IEEE Circuits Devices Mag 5: 1989.
Sait SM and Youssef H (1999). Iterative Computer Algorithms with Applications in Engineering. Press of IEEE Computer Society: Silver Spring MD.
Sasaki GH and Hajek B (1988). The time complexity of maximum matching by simulated annealing. J ACM 35: 387–403.
Serafini P (1985). Mathematics of Multiobjective Optimization, Vol. 289, CISM Courses and Lectures. Springer-Verlag: Berlin.
Serafini P (1992). Simulated annealing for multiple objective optimization problems. In: Proceedings of the Tenth International Conference on Multiple Criteria Decision Making. Taipei, 19–24 July 1, pp 87–96.
Serafini P (1994). Simulated annealing for multiple objective optimization problems. In: Tzeng GH, Wang HF, Wen VP and Yu PL (eds). Multiple Criteria Decision Making. Expand and Enrich the Domains of Thinking and Application. Springer-Verlag, Berlin, pp 283–292.
Shutler PME (2003). A priority list based heuristic for the job shop problem. J Opl Res Soc 54: 571–584.
Sridhar J and Rajendran C (1993). Scheduling in a cellular manufacturing system: a simulated annealing approach. Int J Product Res 31: 2927–2945.
Srinivas N and Deb K (1994). Multiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2: 221.
Starink JPP and Backer E (1995). Finding point correspondences using simulated annealing. Pattern Recog 28: 231–240.
Suman B (2002). Multiobjective simulated annealing—a metaheuristic technique for multiobjective optimization of a constrained problem. Foundations of Comput Decision Sci 27: 171–191.
Suman B (2003). Simulated annealing based multiobjective algorithm and their application for system reliability. Engin Optim 35: 391–416.
Suman B (2004a). Study of Simulated annealing based multiobjective algorithm for multiobjective optimization of a constrained problem. Comput Chem Engin 28: 1849–1871.
Suman B (2004b). On-line multiobjective optimization algorithmic parameter estimation. Applied Soft Computing, submitted.
Suman B (2005). Self-stopping PDMOSA and performance measure in simulated annealing based multiobjective optimization algorithms. Comput Chem Engin 29: 1131–1147.
Suman B, Jha S and Hoda N (2005). Novel orthogonal simulated annealing for multiobjective optimization. IEEE Trans Evol Opti, submitted.
Suppapitnarm A and Parks T (1999). Simulated annealing: an alternative approach to true multiobjective optimization. In: Genetic and Evolutionary Computation Conference. Conference Workshop Program, Orlando, Florida, pp 406–407.
Suppapitnarm A, Seffen KA, Parks GT and Clarkson PJ (2000). Simulated annealing: an alternative approach to true multiobjective optimization. Engin Optim 33: 59.
Suresh G and Sahu S (1994). Stochastic assembly line balancing using simulated annealing. Int J Product Res 32: 1801–1810.
Surry PD and Mudge T (1995). A multiobjective approach to constrained optimization of gas supply networks: The COMOGA method. In: Fogarty TG (ed). Evolutionary Computing. AISB Workshop. Selected papers, Lecture Notes in Computer Science. Springer-Verlag, Sheffield, UK, pp 166–180.
Swarnkar R and Tiwari MK (2004). Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach. Robot Computer-Integrated Manufac 20: 199–209.
Szu H and Hartley R (1987). Fast simulated annealing. Phys Lett A 122: 157–162.
Teghem J, Tuyttens D and Ulungu EL (2000). An intractive heuristic method for multiobjective combinatorial optimization. Comput Opns Res 27: 621–634.
Terzi E, Vikiali A and Angelis L (2004). A simulated annealing approach for multimedia data placement. J Sys Software 73: 467–480.
Tiwari MK and Roy D (2003). Solving a part classification problem using simulated annealing-like hybrid algorithm. Robot Computer-Integrated Manufac 19: 415–424.
Tovey CA (1988). Simulated Annealing. Am J Math Mngt Sci 8: 389–407.
Triki E, Collette Y and Siarry P (2004). A theoretical study on the behavior of simulated annealing leading to a new cooling schedule. Eur J Opl Res 166: 77–92.
Tuyttens D, Teghem J, Fortemps PH and Nieuwenhuyze KV (2000). Performance of the MOSA method for the bicriteria assignment problem. J Heuristics 6: 295.
Ulungu LE and Teghem J (1994). Multiobjective combinatorial optimization problems: a survey. J Multicriteria Decision Anal 3: 83–104.
Ulungu LE, Teghem J and Fortemps P (1995). Heuristics for multiobjective combinatorial optimization problems by simulated annealing. In: Gu J, Chen G, Wei Q, and Wang S (eds). MCDM: Theory and Applications. Sci-Tech, Windsor, UK, pp 269–278.
Ulungu LE, Teghem J and Ost C (1998). Interactive simulated annealing in a multiobjective framework: application to an industrial problem. J Opl Res Soc 49: 1044–1050.
Ulungu LE, Teghem J, Fortemps PH and Tuyttens D (1999). MOSA Method: a tool for solving multiobjective combinatorial optimization problems. J Multicriteria Decision Anal 8: 221–236.
van Laarhoven PJM and Aarts EHL (1987). Simulated Annealing: Theory and Practice. Kluwer Academic Publishers: Dordrecht.
van Laarhoven PJM (1988). Theoretical and computational aspects of simulated annealing. PhD thesis, Erasmus University: Rotterdam.
van Laarhoven PJM, Aarts EHL, van Lint JH and Willie LT (1988). New upper bounds for the football pool problem for 6, 7 and 8 matches. J Combinat Theory A 52: 304–312.
van Laarhoven PJM, Aarts EHL and Lenstra JK (1992). Jobshop scheduling by simulated annealing. Opns Res 40: 113–125.
van Veldhuizen DA and Lamont GB (1998a). Multiobjective evolutionary algorithm research: a history and analysis. Technical Report TR-98-03, Department of Electrical and Computer Engineering. Graduate School of Engineering. Air Force Institute of Technology, Wright-Ptterson, AFB, Ohio.
van Veldhuizen DA and Lamont GB (1998b). Evolutionary computing conference to a Pareto front. In: Koza JR (ed). Late Breaking Papers at the Genetic Programming. Conference, Stanford University, California, July 1998, Stanford University Bookstore, Stanford, California, pp 221–228.
Wille LT (1987). The football pool problem for 6 matches: a new upper bound obtained by simulated annealing. J Combinat Theory A 45: 171–177.
Wright MB (1989). Applying stochastic algorithms to a locomotive scheduling problem. J Opl Res Soc 40: 187–192.
Yip PPC and Pao YH (1995). Combinatorial optimization with use of guided evolutionary simulated annealing. IEEE Trans 6: 290–295.
Youssef H, Sait SM and Adiche H (2003). Evolutionary algorithm simulated annealing and tabu search: a comparative study. Eng Appl Artif Intel 14: 167–181.
Zitzler E and Thiele L (1998). Multiobjective optimization using evolutionary algorithms: a comperative case study. In: Eiben AE, Back T, Schoenauer M and Schwefel HP (eds). Parallel Problem Solving from Nature V. Springer, Berlin, Germany, pp 292–301.
Zolfaghari S and Liang M (1999). Jointly solving the group scheduling and machine speed selection problems. Int J Product Res 37: 2377–2397.
Acknowledgements
The correspondence of Balram Suman with Kiran Mishra, graduate student, The State University of New Jersey, Rutgers and her valuable suggestions are gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Acronyms
- ASA:
-
Adaptive Simulated Annealing
- GA:
-
Genetic Algorithm
- PDMOSA:
-
Pareto Dominant based Multiobjective Simulated Annealing
- PSA:
-
Pareto Simulated Annealing
- SA:
-
Simulated Annealing
- CSA:
-
Chaotic Simulated Annealing
- SMOSA:
-
Suppapitnarm Multiobjective Simulated Annealing
- UMOSA:
-
Ulungu Multiobjective Simulated Annealing
- WMOSA:
-
Weight based Multiobjective Simulated Annealing
Notation
- a, b :
-
decision vector
- B, C, C 1, C 2 :
-
constant
- ΔE :
-
change in energy
- F :
-
objective function vector
- f :
-
objective function value
- f max :
-
estimated maximum value of the objective function
- Δf :
-
multidimensional criteria space
- Δf 0 :
-
range of change in the value of the objective function
- g :
-
inequality constraint violation
- h :
-
equality constraint violation
- I :
-
a column vector with all elements equal to 1.
- i, j :
-
index
- J :
-
number of constraints on the solution vector
- K :
-
a constant
- K B :
-
Boltzmann's constant
- L :
-
set of uniform random weight vectors
- L ∞ :
-
Chebysev norm
- l :
-
number of equality constraint
- m :
-
no of inequality constraint
- M k :
-
objective function at eqilibrium
- N :
-
number of objective functions
- n :
-
number of decision variables
- Prob :
-
probability
- S(A):
-
spacing of a Pareto set A
- ΔS′:
-
change in fitness value
- Δs :
-
one-dimensional space
- T :
-
annealing temperature (controlling parameter in the algorithm)
- W :
-
weight vector
- X :
-
current solution vector
- Y :
-
generated solution vector
- Z :
-
vector whose elements are objective function value ie z i after applying the penalty function approach
- Z k :
-
Chaotic variable
Greek symbols
- α :
-
a constant
- β :
-
a constant
- δ :
-
parameter for probability calculation
- λ :
-
weight vector
- σ 2 :
-
variance of the objective function at equilibrium
- μ :
-
bifurcation parameter of the system
- χ 0 :
-
defined as the number of accepted bad moves divided by the number of attempted bad moves
Rights and permissions
About this article
Cite this article
Suman, B., Kumar, P. A survey of simulated annealing as a tool for single and multiobjective optimization. J Oper Res Soc 57, 1143–1160 (2006). https://doi.org/10.1057/palgrave.jors.2602068
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2602068