Singular perturbed Markov chains and exact behaviors of simulated annealing processes

We study asymptotic properties of discrete and continuous time generalized simulated annealing processesX(·) by considering a class of singular perturbed Markov chains which are closely related to the large deviation of perturbed diffusion processes. Convergence ofX(t) in probability to a setS ₀ of desired states, e.g., the set of global minima, and in distribution to a probability concentrated onS ₀ are studied. The corresponding two critical constants denoted byd and withd are given explicitly. When the cooling schedule is of the formc/logt, X(t) converges weakly forc>0. Whether the weak limit depends onX(0) or concentrates onS ₀ is determined by the relation betweenc, d, and . Whenc>, the expression for the rate of convergence for each state is also derived.     

Investigation of temperature parallel simulated annealing for optimizing continuous functions with application to hyperspectral tomography

The simulated annealing (SA) algorithm is a well-established optimization technique which has found applications in many research areas. However, the SA algorithm is limited in its application due to the high computational cost and the difficulties in determining the annealing schedule. This paper demonstrates that the temperature parallel simulated annealing (TPSA) algorithm, a parallel implementation of the SA algorithm, shows great promise to overcome these limitations when applied to continuous functions. The TPSA algorithm greatly reduces the computational time due to its parallel nature, and avoids the determination of the annealing schedule by fixing the temperatures during the annealing process. The main contributions of this paper are threefold. First, this paper explains a simple and effective way to determine the temperatures by applying the concept of critical temperature (T_C). Second, this paper presents systematic tests of the TPSA algorithm on various continuous functions, demonstrating comparable performance as well-established sequential SA algorithms. Third, this paper demonstrates the application of the TPSA algorithm on a difficult practical inverse problem, namely the hyperspectral tomography problem. The results and conclusions presented in this work provide are expected to be useful for the further development and expanded applications of the TPSA algorithm.     

Finite-Time Performance Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces -acceptable solutions, where is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying -acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using these measures. S²A uses a fixed cooling schedule during the algorithm's execution. Though S²A is provably nonconvergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying -acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a -acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S²A algorithm.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

We report about a study of a simulated annealing algorithm for the airline crew pairing problem based on a run-cutting formulation. Computational results are reported for some real-world short- to medium-haul test problems with up to 4600 flights per month. Furthermore we find that run time can be saved and solution quality can be improved by using a problem specific initial solution, by relaxing constraints as far as possible, by combining simulated annealing with a problem specific local improvement heuristic and by multiple independent runs.     

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 magnetic resonance device designed via global optimization techniques

In this paper we are concerned with the design of a small low-cost, low-field multipolar magnet for Magnetic Resonance Imaging with a high field uniformity. By introducing appropriate variables, the considered design problem is converted into a global optimization one. This latter problem is solved by means of a new derivative free global optimization method which is a distributed multi-start type algorithm controlled by means of a simulated annealing criterion. In particular, the proposed method employs, as local search engine, a derivative free procedure. Under reasonable assumptions, we prove that this local algorithm is attracted by global minimum points. Additionally, we show that the simulated annealing strategy is able to produce a suitable starting point in a finite number of steps with probability one.This work was supported by CNR/MIUR Research Program Metodi e sistemi di supporto alle decisioni, Rome, Italy.Mathematics Subject Classification (1991):65K05, 62K05, 90C56     

Parametric bounds for LPT scheduling on uniform processors

The nonpreemptive assignment of independent tasks to a system ofm uniform processors is examined with the objective of minimizing the makespan. Using _m , the ratio of the fastest speed to the slowest speed of the system, as a parameter, we assess the performance of LPT (largest processing time) schedule with respect to optimal schedules. It is shown that the worst-case bound for the ratio of the two schedule lengths is between      

Improving simulated annealing through derandomization

We propose and study a version of simulated annealing (SA) on continuous state spaces based on \((t,s)_R\)-sequences. The parameter \(R\in \bar{\mathbb {N}}\) regulates the degree of randomness of the input sequence, with the case \(R=0\) corresponding to IID uniform random numbers and the limiting case \(R=\infty \) to (t, s)-sequences. Our main result, obtained for rectangular domains, shows that the resulting optimization method, which we refer to as QMC-SA, converges almost surely to the global optimum of the objective function \(\varphi \) for any \(R\in \mathbb {N}\). When \(\varphi \) is univariate, we are in addition able to show that the completely deterministic version of QMC-SA is convergent. A key property of these results is that they do not require objective-dependent conditions on the cooling schedule. As a corollary of our theoretical analysis, we provide a new almost sure convergence result for SA which shares this property under minimal assumptions on \(\varphi \). We further explain how our results in fact apply to a broader class of optimization methods including for example threshold accepting, for which to our knowledge no convergence results currently exist. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study.     

Sequential Monte Carlo simulated annealing

In this paper, we propose a population-based optimization algorithm, Sequential Monte Carlo Simulated Annealing (SMC-SA), for continuous global optimization. SMC-SA incorporates the sequential Monte Carlo method to track the converging sequence of Boltzmann distributions in simulated annealing. We prove an upper bound on the difference between the empirical distribution yielded by SMC-SA and the Boltzmann distribution, which gives guidance on the choice of the temperature cooling schedule and the number of samples used at each iteration. We also prove that SMC-SA is more preferable than the multi-start simulated annealing method when the sample size is sufficiently large.     

Smoothness in Bayesian Non-parametric Regression with Wavelets

Consider the classical nonparametric regression problem y_i = f(t_i) + _ii = 1,...,n where t_i = i/n, and _i are i.i.d. zero mean normal with variance ². The aim is to estimate the true function f which is assumed to belong to the smoothness class described by the Besov space B _pq ^q . These are functions belonging to L_p with derivatives up to order s, in L_p sense. The parameter q controls a further finer degree of smoothness. In a Bayesian setting, a prior on B _pq ^q is chosen following Abramovich, Sapatinas and Silverman (1998). We show that the optimal Bayesian estimator of f is then also a.s. in B _pq ^q if the loss function is chosen to be the Besov norm of B _pq ^q . Because it is impossible to compute this optimal Bayesian estimator analytically, we propose a stochastic algorithm based on an approximation of the Bayesian risk and simulated annealing. Some simulations are presented to show that the algorithm performs well and that the new estimator is competitive when compared to the more standard posterior mean.     

Homogenization of the heat equation for a domain with a network of pipes with a well-mixed fluid

We consider the linear heat equation in a domain occupied by a solid material with a network of pipes in which a well-mixed fluid is circulating. The temperature of the fluid in the pipe is uniform and its time variation is determined by the thermal flux on the wall of the pipe, plus a given internal source; continuity of the temperature across the pipe is also assumed. We suppose that we deal with a periodic geometry, with cells of size with inclusions of size r_g; we study in detail in the case r, referring to a previous paper for the case r In the limit »0 we get a homogenized equation. The limit depends strongly on the ratio between the time variation of the temperature in the inclusions and the thermal flux through the interface. The homogenized equation has a new specific heat, which depends on the porosity and the constant of proportionality between the time variation of temperature and the flux on the boundary of the pipe. We also have a new thermal conductivity depending on the microstructure, and volume sources appear. The main tool is the energy method and we generalize the classical results for the more standard boundary conditions for parabolic equations. Finally, we consider the network of pipes forming a random ball structure. We prove convergence for this case. The homogenized equation is of the same form as in the periodic case but auxiliary problems are stochastic.     

Strength of polyethylene and capron as a function of stretch ratio

The relation between the strengths and stretch ratios of a capronmonofilament and a high-pressure polyethylene film has been investigated for various stretching temperatures and stretching rates. The strength, measured at –196°C (_–196), is directly proportional to the stretch ratio (). For a given , _-196 does not depend on stretching temperature and stretching rate. The breaking load at –196° C (for a given initial cross section of the starting unoriented specimen) does not vary with . A possible explanation is offered.Mekhanika Polimerov, Vol. 3, No. 4, pp. 591–595, 1967     

Temperature dependence of the strength of a woven composite in a plane state of stress

Conclusions On the basis of an analysis of test results obtained by typical patterns of simple momentary quasistatic loading at various temperatures within the 20–150°C range, we have found a family of strength surfaces for a woven organic plastic material in a plane state of stress in the reinforcement plane. These experimentally found strength surfaces can be approximated by the equation of a second-degree surface. It has been established that the range of safe states of stress in the stress space narrows nonuniformly with rising temperature; namely, this narrowing is accompanied by a shift of the center and a reorientation of the axes of the strength ellipsoid. We have revealed and described the temperature dependence of the components of the strength surface tensors involved in the strength criterion. The data can be used for predicting the strength of a composite material under consideration when the latter is subject to simple quasistatic loading patterns in the three-dimensional (₁₁, ₂₂, ₁₂) stress space in the reinforcement plane within a given test range of temperatures.Institute of Polymer Mechanics, Academy of Sciences of the Latvian SSR, Riga. Translated from Mekhanika Polimerov, No. 3, pp. 452–457, May–June, 1978.     

Approximating Scheduling Unrelated Parallel Machines in Parallel

We show how to approximate in NC the problem of scheduling unrelated parallel machines, for a fixed number of machines in which the makespan C _max is the objective function to minimize. We develop an approximate NC algorithm which finds a schedule whose length is at most (1+o(1))(C^* _max + 3 C^* _maxln(2n(n-1)/)), where C*_max denotes the optimal schedule, n the total number of jobs and a small positive constant. Our approach shows how to relate the linear program obtained by relaxing the integer programming formulation of the problem with a linear program formulation that is positive and in the packing/covering form. The established relationship enables us to transfer approximate fractional solutions from the later formulation that is known to be approximable in NC. Then, we show how to obtain an integer approximate solution, i.e. a schedule, from the fractional one, using the randomized rounding technique. We stress that our analysis assumes that the length of the schedule is (ln n) and that the min p _ij and max p _ij values are not too disparate (where p _ij is the time to run job j on machine i).Finally, we show that the same technique can be applied to the general assignment problem with a fixed number of machines and makespan T.     

A Range-Compaction Heuristic for Graph Coloring

This paper presents a novel heuristic for graph coloring that works on a range of colors and iteratively tries to make this range more compact. This range-compaction heuristic also has a pressure component and an annealing schedule for it. The value of this component is empirically quantified. This algorithm is evaluated on a wide range of DIMACS benchmark graphs, and found to be competitive with state-of-the-art algorithms in terms of solution quality and run time.     

An analytically derived cooling schedule for simulated annealing

We present an analytically derived cooling schedule for a simulated annealing algorithm applicable to both continuous and discrete global optimization problems. An adaptive search algorithm is used to model an idealized version of simulated annealing which is viewed as consisting of a series of Boltzmann distributed sample points. Our choice of cooling schedule ensures linearity in the expected number of sample points needed to become arbitrarily close to a global optimum.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.