An adaptive simulated annealing algorithm for global optimization over continuous variables

A method is presented for attempting global minimization for a function of continuous variables subject to constraints. The method, calledAdaptive Simulated Annealing (ASA), is distinguished by the fact that the fixed temperature schedules and step generation routines that characterize other implementations are here replaced by heuristic-based methods that effectively eliminate the dependence of the algorithm's overall performance on user-specified control parameters. A parallelprocessing version of ASA that gives increased efficiency is presented and applied to two standard problems for illustration and comparison.This research was supported by the University Research Initiative of the U.S. Army Research Office.     

Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

Robust optimization with simulated annealing

Complex systems can be optimized to improve the performance with respect to desired functionalities. An optimized solution, however, can become suboptimal or even infeasible, when errors in implementation or input data are encountered. We report on a robust simulated annealing algorithm that does not require any knowledge of the problems structure. This is necessary in many engineering applications where solutions are often not explicitly known and have to be obtained by numerical simulations. While this nonconvex and global optimization method improves the performance as well as the robustness, it also warrants for a global optimum which is robust against data and implementation uncertainties. We demonstrate it on a polynomial optimization problem and on a high-dimensional and complex nanophotonic engineering problem and show significant improvements in efficiency as well as in actual optimality.     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

A simulated annealing technique for multi-objective simulation optimization

In this paper, we present a simulated annealing algorithm for solving multi-objective simulation optimization problems. The algorithm is based on the idea of simulated annealing with constant temperature, and uses a rule for accepting a candidate solution that depends on the individual estimated objective function values. The algorithm is shown to converge almost surely to an optimal solution. It is applied to a multi-objective inventory problem; the numerical results show that the algorithm converges rapidly.     

A simulated annealing algorithm for transient optimization in gas networks

In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.     

A combined procedure for discrete simulation–optimization problems based on the simulated annealing framework

This paper addresses the problem of optimizing a function over a finite or countable infinite set of alternatives, whenever the objective function cannot be evaluated exactly, but has to be estimated via simulation. We present an iterative method, based on the simulated annealing framework, for solving such discrete stochastic optimization problems. In the proposed method, we combine the robustness of this metaheuristic method with a statistical procedure for comparing the solutions that are generated. The focus of our work is on devising an effective procedure rather than addressing theoretical issues. In fact, in our opinion, although significant progresses have been made in studying the convergence of a number of simulation–optimization algorithms, at present there is no procedure able to consistently provide good results in a reasonable amount of time. In addition, we present a parallelization strategy for allocating simulation runs on computing resources.     

Derivative-free simulated annealing and deflecting function technique for global optimization

A hybrid descent method based on simulated annealing (SA) algorithm and one modifying function technique, named deflecting function method, for global optimization is proposed. Unlike some previously proposed algorithms, the designed SA algorithm is executed repeatedly on the transformed function with respect to one prior-obtained local minimum instead of on the original objective function. Meanwhile, large scale searches at the beginning stages and small scale detections in the last stages are adopted. The global convergence is proved. Simulation demonstrates that the new method utilizes the obtained information effectively, so the convergence is significantly sped up and the success rate is greatly improved, compared with other existing methods. As an experimental result, how to combine SA and the deflecting function technique can make the new method more effective is discussed.     

Continuous optimization by a variant of simulated annealing

A variant of the simulated annealing algorithm, based on the generalized method of Bohachevsky et al., is proposed for continuous optimization problems. The algorithm automatically adjusts the step sizes to reflect the local slopes and function values, and it controls the random directions to point favorably toward potential improvements. Computational results on some well known functions show substantial improvements both in solution quality and efficiency.     

A simulated annealing algorithm for resource constrained project scheduling problems

This paper presents a simulated annealing algorithm for resource constrained project scheduling problems with the objective of minimising makespan. In the search algorithm, a solution is represented with a priority list, a vector of numbers each of which denotes the priority of each activity. In the algorithm, a priority scheduling method is used for making a complete schedule from a given priority list (and hence a project schedule is defined by a priority list). The search algorithm is applied to find a priority list which corresponds to a good project schedule. Unlike most of priority scheduling methods, in the suggested algorithm some activities are delayed on purpose so as to extend search space. Solutions can be further improved by delaying certain activities, since non-delay schedules are not dominant in the problem (the set of non-delay schedules does not always include an optimal solution). The suggested algorithm is flexible in that it can be easily applied to problems with an objective function of a general form and/or complex constraints. The performance of the simulated annealing algorithm is compared with existing heuristics on problems prepared by Patterson and randomly generated test problems. Computational results showed that the suggested algorithm outperformed existing ones.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.     

Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem

Modern very large scale integration technology is based on fixed-outline floorplan constraints, mostly with an objective of minimizing area and wirelength between the modules. The aim of this work is to minimize the unused area, that is, dead space in the floorplan, in addition to these objectives. In this work, a Simulated Annealing Algorithm (SAA) based heuristic, namely Simulated Spheroidizing Annealing Algorithm (SSAA) has been developed and improvements in the proposed heuristic algorithm is also suggested to improve its performance. Exploration capability of the proposed algorithm is due to the mechanism of reducing the uphill moves made during the initial stage of the algorithm, extended search at each temperature and the improved neighborhood search procedure. The proposed algorithm has been tested using two kinds of benchmarks: Microelectronics Center of North Carolina (MCNC) and Gigascale Systems Research Center (GSRC). The performance of the proposed algorithm is compared with that of other stochastic algorithms reported in the literature and is found to be efficient in producing floorplans with very minimal dead space. The proposed SSAA algorithm is also found more efficient for problems of larger sizes.     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

A survey of simulated annealing as a tool for single and multiobjective optimization

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.     

Applying simulated annealing using different methods for the neighborhood search in forest planning problems

Adjacency constraints along with even flow harvest constraints are important in long term forest planning. Simulated annealing (SA) is previously successfully applied when addressing such constraints. The objective of this paper was to assess the performance of SA under three new methods of introducing biased probabilities in the management unit (MU) selection and compare them to the conventional method that assumes uniform probabilities. The new methods were implemented as a search vector approach based on the number of treatment schedules describing sequences of silvicultural treatments over time and standard deviation of net present value within MUs (Methods 2 and 3, respectively), and by combining the two approaches (Method 4). We constructed three hundred hypothetical forests (datasets) for three different landscapes characterized by different initial age class distributions (young, normal and old). Each dataset encompassed 1600 management units. The evaluation of the methods was done by means of objective function values, first feasible iteration and time consumption. Introducing a bias in the MU selection improves solutions compared to the conventional method (Method 1). However, an increase of computational time is in general needed for the new methods. Method 4 is the best alternative because, for large parts of the datasets, produced the best average and maximum objective function values and had lower time consumption than Methods 2 and 3. Although Method 4 performed very well, Methods 2 and 3 should not be neglected because for a considerable number of datasets the maximum objective function values were obtained by these methods.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

Parallel simulated annealing

This article introduces the notion of restricted parallelism for networks, a generalization of the unlimited parallelism for Boltzmann machines. The convergence of the annealing algorithm in the restricted parallel form is established, for an arbitrary network.     

Optimal acceptance probability for simulated annealing

The objective of this note is two-fold: first, to prescribe a rather general form for the acceptance probability which will attain the Gibbs distribution for a stationary Markov chain; second, to find the particular one that will maximize the rate at which equilibrium is reached.     

A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.