A Hybrid Descent Method for Global Optimization

In this paper, a hybrid descent method, consisting of a simulated annealing algorithm and a gradient-based method, is proposed. The simulated annealing algorithm is used to locate descent points for previously converged local minima. The combined method has the descent property and the convergence is monotonic. To demonstrate the effectiveness of the proposed hybrid descent method, several multi-dimensional non-convex optimization problems are solved. Numerical examples show that global minimum can be sought via this hybrid descent method.     

一类非线性两级整数规划问题的全局优化方法

本文研究了整数规划连续化的途径,对一类非线性两级整数规划问题的上级规划连续化以后采用模拟退火算法;其对应的下级规划问题采用离散搜索法求解,从而给出了求解一类非线性两级整数规划问题的一种全局优化算法,并通过算例验证了该算法是有效的.     

基于模拟退火地震反演技术——以X油田某区为例

为了提高地震反演预测的分辨率和可信度,提出了线性反演与非线性反演二者相结合的反演方法——以稀疏脉冲反演结果为约束背景的基于模拟退火的反演方法,阐述了基于模拟退火法的反演机理,并以X油田某区为例,开展了基于模拟退火地球物理反演预测,从反演分辨率、可信度和误差三个方面进行分析和定量研究.结果表明,非线性的随机反演与线性反演相结合有效地提高了反演分辨率,纵向上能够精细到单砂体级,反演结果多个概率的实现最大程度上降低反演的多解性,并且,反演结果的精度较高,2m以上砂岩反演符合率均在90%以上.     

Solving Location-allocation Problems with Rectilinear Distances by Simulated Annealing

The objective of this study is to use the simulated annealing method to solve minisum location-allocation problems with rectilinear distances. The major advantage of the simulated annealing method is that it is a very general and efficient algorithm for solving combinatorial optimization problems with know objective functions. In this study, a simulated annealing algorithm was developed to solve the location-allocation problems, and its performance was compared with two other popular methods for solving location-allocation problems. The results show that simulated annealing is a good alternative to the two methods, as measured by both the solution quality and the computational time.     

混合模拟退火-进化策略在非线性参数估计中的应用

提出了一种混合模拟退火-进化策略算法应用在非线性参数估计中,方法克服了传统优化方法估计参数精度不高且容易陷入局部极小值等缺点,并且将模拟退火算法和进化策略算法相结合,充分发挥各自算法优点.最后通过给出非线性参数估计算例,结果表明,算法具有参数估计精度较高,收敛速度快,自适应性强,在实际工程中有较大的应用价值.     

A reduction method for semi-infinite programming by means of a global stochastic approach†

We describe a reduction algorithm for solving semi-infinite programming problems. The proposed algorithm uses the simulated annealing method equipped with a function stretching as a multi-local procedure, and a penalty technique for the finite optimization process. An exponential penalty merit function is reduced along each search direction to ensure convergence from any starting point. Our preliminary numerical results seem to show that the algorithm is very promising in practice.     

DESA: a new hybrid global optimization method and its application to analog integrated circuit sizing

This paper presents a new hybrid global optimization method referred to as DESA. The algorithm exploits random sampling and the metropolis criterion from simulated annealing to perform global search. The population of points and efficient search strategy of differential evolution are used to speed up the convergence. The algorithm is easy to implement and has only a few parameters. The theoretical global convergence is established for the hybrid method. Numerical experiments on 23 mathematical test functions have shown promising results. The method was also integrated into SPICE OPUS circuit simulator to evaluate its practical applicability in the area of analog integrated circuit sizing. Comparison was made with basic simulated annealing, differential evolution, and a multistart version of the constrained simplex method. The latter was already a part of SPICE OPUS and produced good results in past research.     

Applying Stochastic Algorithms to a Locomotive Scheduling Problem

This paper addresses a problem common to all railway networks. Given a fixed train timetable and locomotives (or other forms of traction) of various types, each train must be allocated a locomotive. This paper examines the use of stochastic algorithms for such a problem. Two types of algorithm are used—a simple ‘local improvement’ method, performed successively from randomly chosen starting points, and a ‘simulated annealing’ approach. Both are found to give considerably better results than a deterministic method in current use, and the annealing approach is probably the better stochastic method.     

Generalized speculative computation of parallel simulated annealing

Simulated annealing is known to be highly sequential due to dependences between iterations. While the conventional speculative computation with a binary tree has been found effective for parallel simulated annealing, its performance is limited to (logp)-fold speedup due to parallel execution of logp iterations onp processors. This report presents a new approach to parallel simulated annealing, calledgeneralized speculative computation (GSC). The GSC is synchronous, maintaining the same decision sequence as sequential simulated annealing. The use of two loop indices encoded in a single integer eliminates broadcasting of central data structure to all processors. The master-slave parallel programming paradigm simplifies controlling the activities ofp iterations which are executed in parallel onp processors. To verify the performance of GSC, we implemented 100-city to 500-city Traveling Salesman Problems on the AP1000 massively parallel multiprocessor. Execution results on the AP1000 demonstrate that the GSC approach can indeed be an effective method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors.     

Molecular conformation on the CM-5 by parallel two-level simulated annealing

In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.Also a researcher at the Army High Performance Computing Research Center, University of Minnesota, Minneapolis, MN 55415     

A novel characterization method of piezoelectric composite material based on particle swarm optimization algorithm

This paper presents a novel characterization method for high-loss piezoelectric composite material based on particle swarm optimization algorithm. This proposed method was applied to determine the properties parameters of 1–3 PZT5A/epoxy composite piezoelectric material with the thickness vibration mode. The analysis results show that this method has more accurate reconstructed values, faster convergence speed compared to the method using simulated annealing algorithm published in the literature under the same condition. Good agreement between the measured electrical impedance curve and the fitting one also verifies that this method can determine precise materials parameters. This is very useful for the accurate characterization of piezoelectric materials with the unknown parameters.     

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.     

A statistical analysis of simulated annealing applied to the p-median problem

We present a statistical analysis of simulated annealing applied to the p-median problem. The algorithm we use combines elements of the vertex substitution method of Teitz and Bart with the general methodology of simulated annealing. The cooling schedule adopted incorporates the notion of temperature adjustments rather than just temperature reductions. Computational results are given for test problems ranging from 100 to 900 vertices, retrieved from Beasley's OR-Library for combinatorial problems. Each problem was run for a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the optimal solution was 1.62%, after all runs for each of the test problems were computed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem

This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

Monte Carlo hyper-heuristics for examination timetabling

Automating the neighbourhood selection process in an iterative approach that uses multiple heuristics is not a trivial task. Hyper-heuristics are search methodologies that not only aim to provide a general framework for solving problem instances at different difficulty levels in a given domain, but a key goal is also to extend the level of generality so that different problems from different domains can also be solved. Indeed, a major challenge is to explore how the heuristic design process might be automated. Almost all existing iterative selection hyper-heuristics performing single point search contain two successive stages; heuristic selection and move acceptance. Different operators can be used in either of the stages. Recent studies explore ways of introducing learning mechanisms into the search process for improving the performance of hyper-heuristics. In this study, a broad empirical analysis is performed comparing Monte Carlo based hyper-heuristics for solving capacitated examination timetabling problems. One of these hyper-heuristics is an approach that overlaps two stages and presents them in a single algorithmic body. A learning heuristic selection method (L) operates in harmony with a simulated annealing move acceptance method using reheating (SA) based on some shared variables. Yet, the heuristic selection and move acceptance methods can be separated as the proposed approach respects the common selection hyper-heuristic framework. The experimental results show that simulated annealing with reheating as a hyper-heuristic move acceptance method has significant potential. On the other hand, the learning hyper-heuristic using simulated annealing with reheating move acceptance (L?CSA) performs poorly due to certain weaknesses, such as the choice of rewarding mechanism and the evaluation of utility values for heuristic selection as compared to some other hyper-heuristics in examination timetabling. Trials with other heuristic selection methods confirm that the best alternative for the simulated annealing with reheating move acceptance for examination timetabling is a previously proposed strategy known as the choice function.     

利用模拟退火算法进行油井流入动态研究

油井流入动态是油井举升优化设计的基础 ,目前国内外研究油井流入动态的方法有多种 ,但是各有其不足和局限性 .为此利用模拟退火方法进行油井流入动态方法研究 .与以往的近似算法相比 ,该方法不需要将单相流和多相流分开讨论 ,且无任何假设条件 ,适用范围广 ;通过实例 ,把模拟退火的预测的产量结果与利用 Vogel方程所预测的产量结果进行比较和误差分析 ,结果表明 ,该算法的误差是非常小的 .因此 ,利用该算法研究油井流入动态非常可行 .     

Evaluation of Spatial Scan Statistics for Irregularly Shaped Clusters

Spatial scan statistics are commonly used for geographic disease cluster detection and evaluation. We propose and implement a modified version of the simulated annealing spatial scan statistic that incorporates the concept of “non-compactness” in order to penalize clusters that are very irregular in shape. We evaluate its power for the simulated annealing scan and compare it with the circular and elliptic spatial scan statistics. We observe that, with the non-compactness penalty, the simulated annealing method is competitive with the circular and elliptic scan statistic, and both have good power performance. The elliptic scan statistic is computationally faster and is well suited for mildly irregular clusters, but the simulated annealing method deals better with highly irregular cluster shapes. The new method is applied to breast cancer mortality data from northeastern United States.     

Determination of lockbox collection points via simulated annealing

This research presents a heuristic to solve the lockbox location problem via a search-based technique known as simulated annealing. In the past, more traditional mathematical programming techniques have been used to address this problem, but with limited success due to its combinatorial nature. Because simulated annealing is a search-based technique, an optimal solution is not guaranteed, but past research has demonstrated that search-based heuristics can provide reasonable solutions without the difficulties associated with the more traditional formulations. In this paper, the simulated annealing methodology is used to solve a large lockbox location problem at several differing levels of cost. The results compare favourably to solutions obtained from a K-means clustering heuristic.