Elsevier

Computer Physics Communications

Applications of critical temperature in minimizing functions of continuous variables with simulated annealing algorithm

Abstract

The simulated annealing (SA) algorithm has been recognized as a powerful technique for minimizing complicated functions. However, a critical disadvantage of the SA algorithm is its high computational cost. Therefore, it is the goal of this paper to investigate the use of the critical temperature in SA to reduce its computational cost. This paper presents a systematic study of the critical temperature and its applications in the minimization of functions of continuous variables with the SA algorithm. Based on this study, a new algorithm was developed to exploit the unique feature of the critical temperature in SA. The new algorithm combines SA and local search to determine global minimum effectively. Extensive tests on a variety of functions demonstrated that the new algorithm provides comparable performance to well-established SA techniques. Furthermore, the new algorithm also improves the determination of the starting temperature for the SA algorithm. The results obtained in this study are expected to be useful for improving the efficiency of SA algorithms, and for facilitating the development of temperature parallel SA algorithms.

Introduction

The simulated annealing (SA) algorithm, initially invented for minimizing discrete problems [1], has been extensively demonstrated as an effective technique for problems with continuous variables as well [2], [3], [4]. The SA algorithm enables several key advantages when applied to complicated problems, where a large number of interfering local minima exist and the global minimum is difficult to find [5]. These advantages include the ability to discriminate between confusing local minima to locate the global minimum, the insensitivity to the initial guess, and the relative simplicity of implementation.

It has been well recognized that a critical disadvantage of the SA technique is its high computational cost [2], quantified by the number of evaluations of the objective function. The SA algorithm usually requires at least 103 more evaluations of the objective function than algorithms based on the derivative (or gradient). The computational cost is proportional to the number of variables in various versions of the implementations of the SA algorithm [2], [5], [6]. Therefore, when the objective function is complicated (such that each evaluation of the function becomes expensive) or the number of variables in the function increases, there is a strong incentive to develop more efficient implementation of the SA algorithm to keep the computational cost at a manageable level.

This paper focuses on the application of the critical temperature ( T C ) in the SA algorithm to achieve such a goal. The critical temperature is an important concept in the SA algorithm for multiple reasons. For instance, the SA algorithm searches for the global minimum with optimal efficiency at T C [7], [8], [9], and T C provides critical information about the starting and ending temperatures of the SA algorithm, which are two of the most crucial parameters for the SA technique [2], [10], [11]. Therefore, the efficient determination of T C and its application in SA have been the subject of extensive investigation [7], [8], [9], [10], [11], [12]. However, past studies of T C mainly focused on discrete (combinatorial) problems [7], [8], [9], [10], [11], and little attention has been paid to problems with continuous variables. Therefore, this paper aims at providing a systematic study of T C for continuous problems.

The remainder of the paper is organized as follows. Section 2 provides a summary of the simulated annealing algorithm for the ease of reference. Section 3 introduces the concept of T C in the SA algorithm, followed by its applications and results in Section 4. These results demonstrated that the proper use of T C resulted in enhanced performance of the SA algorithm, enabled accurate determination of the starting and ending temperature, and reduced the computational cost. Based on these results, a new SA method is proposed based on the use of T C , which provides comparable performance to previously developed SA techniques with reduced computational cost. Finally, Section 5 summarizes the paper with conclusions.

Section snippets

Simulated annealing algorithm

A certain amount of in-depth knowledge of the SA algorithm is desired for the rest of the discussion in this paper. Therefore, an introduction of the SA algorithm is provided here for the ease of reference, and more elaborated discussions can found in [2] and [5].

The SA algorithm roots from an analogy with the way liquids are annealed, i.e., cooled slowly to arrive at a low energy and crystallize. During the annealing process, the energy of the liquid is lowered gradually such that the system

Critical temperature

The concept of T C in SA is analogous to the freezing point of a liquid, i.e., the temperature at which the liquid undergoes a phase change to form a solid. Previous studies have found that the SA algorithm searches the global minimum with higher efficiency at T C than at other temperatures [8], [9], [11], [12]. Such enhanced efficiency can be explained intuitively by the discussions at the end of Section 2 and the analogy with the annealing of liquid. When the temperature is higher than T C (the

Application of critical temperature

As mentioned in the above section, the critical temperature offers attractive features for the SA technique. This section details an alternative SA algorithm based on the use of T C , compares this algorithm with another well-established SA algorithm, and discusses the advantages of the new method.

The algorithm based on T C will be compared with a well-established SA algorithm detailed in [2]. To facilitate the discussion, we refer to the algorithm described in [2] Algorithm I and our algorithm

Summary

To summarize, this paper presents a systematic study of the critical temperature and its applications to the minimization of functions of continuous variables with the SA algorithm. The paper shows that the SA algorithm searches the global minimum efficiently at the critical temperature. A new algorithm was developed to exploit this special feature of the critical temperature. This algorithm first determines the critical temperature, then performs a local search on the solutions obtained at the

References (14)

  • Math. Comput. Model.

    (1989)
  • L. Ingber

    Math. Comput. Model.

    (1993)
  • S. Kirkpatrick et al.

    Science

    (1983)
  • A. Corana et al.

    ACM Trans. Math. Software

    (1987)
  • S.P. Brooks et al.

    Statistician

    (1995)
  • W.H. Press et al.

    Numerical Recipes in FORTRAN: The Art of Scientific Computing

    (1992)
  • S.R. White

    AIP Conf. Proc.

    (1984)

There are more references available in the full text version of this article.

Cited by (34)

  • Reconstruction for limited-data nonlinear tomographic absorption spectroscopy via deep learning

    2018, Journal of Quantitative Spectroscopy and Radiative Transfer

    This may be due to the small amount of LOS measurements and the inherent lack of spatial resolution. In order to validate the reconstructions of CNN, we compared it against the SA algorithm, which currently is the most widely adopted inversion method for the NTAS problems [31,41]. As noise prevails in practical applications, artificial Gaussian noise was added to the LOS measurements.

  • Tomographic absorption spectroscopy for the study of gas dynamics and reactive flows

    2017, Progress in Energy and Combustion Science

    Thus, a robust global optimization algorithm is needed to escape local minima effectively and to land in the vicinity of the global minimum. It has been proven that heuristic algorithms such as the simulated annealing (SA) algorithm [294–298], genetic algorithm (GA) [299–301], and differential evolution (DE) algorithm [302–304] are efficient in solving large-scale optimization problems. So far, the SA algorithm has been favored for the solution of the nonlinear tomographic problems; it is briefly summarized here.

  • GACE: A meta-heuristic based in the hybridization of Genetic Algorithms and Cross Entropy methods for continuous optimization

    2016, Expert Systems with Applications

    In this category are algorithms like Particle Swarm Optimization (PSO) (Kennedy, 2010), Genetic Algorithm (GA) (Holland, 1975), Ant colony Optimization(ACO) (Dorigo & Gambardella, 1997), Differential Evolution (DE) (Neri & Tirronen, 2010), or Simulated Annealing (SA) (Van Laarhoven & Aarts, 1987). Since their formulation, these algorithms have been applied to optimization problems in Wang et al. (2011), Thakur (2014), Ciornei and Kyriakides (2012) and Cai and Ma (2010). Also, probabilistic techniques such as Cross Entropy (CE) (Rubinstein, 1999) or Covariance Matrix Adaptation (CMA) (Hansen & Ostermeier, 2001) have been applied to this kind of problem (Deb, Anand, & Joshi, 2002; Kroese, Porotsky, & Rubinstein, 2006).

Arrow Up and Right View all citing articles on Scopus
View full text

Copyright © 2009 Elsevier B.V. All rights reserved.