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.     

Computing the Initial Temperature of Simulated Annealing

The classical version of simulated annealing is based on a cooling schedule. Generally, the initial temperature is set such that the acceptance ratio of bad moves is equal to a certain value ₀. In this paper, we first propose a simple algorithm to compute a temperature which is compatible with a given acceptance ratio. Then, we study the properties of the acceptance probability. It is shown that this function is convex for low temperatures and concave for high temperatures. We also provide a lower bound for the number of plateaux of a simulated annealing based on a geometric cooling schedule. Finally, many numerical experiments are reported.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

Convergence of the Simulated Annealing Algorithm for Continuous Global Optimization

A class of simulated annealing algorithms for continuous global optimization is considered in this paper. The global convergence property is analyzed with respect to the objective value sequence and the minimum objective value sequence induced by simulated annealing algorithms. The convergence analysis provides the appropriate conditions on both the generation probability density function and the temperature updating function. Different forms of temperature updating functions are obtained with respect to different kinds of generation probability density functions, leading to different types of simulated annealing algorithms which all guarantee the convergence to the global optimum.     

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

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

Scheduling problem using genetic algorithm,simulated annealing and the effects of parameter values on GA performance

Genetics algorithms have been designed as general purpose optimisation methods. Simulated annealing simulates the cooling process of solid materials-known as annealing. However this analogy is limited to the physical movement of the molecules without involving complex thermodynamic systems. Physical annealing refers to the process of cooling a solid material so that it reaches a low energy state. Initially the solid is heated up to the melting point. Then it is cooled very slowly, allowing it is to come to thermal equilibrium at each temperature. This process of slow cooling is called annealing. The goal is to find the best arrangement of molecules that minimises the energy of the system, which is referred to as the ground state of the solid material. If the cooling process is fast, the solid will not attain the ground state, but a locally optimal structure. In this paper presents a general purpose schedule optimiser for manufacturing shop scheduling using genetic algorithms and simulated annealing. Then, the ‘uniform order-based’ crossover and mutation operators and novel general effects of parameter values on minimised objective value are presented.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).     

Simulated annealing algorithm for finding periodic orbits of multi-electron atomic systems

We adapt the simulated annealing algorithm to the search of periodic orbits for classical multi-electron atomic systems. This is done by minimizing the nth return distance to the initial position on a Poincaré surface of section under an energy constraint. Here we give evidence of the feasibility of the method by applying it to the helium atom in the ground state for one to three spatial dimensions. We examine the structure of the dynamics and connect its organization to the periodic orbits we have found.     

The interacting-particle algorithm with dynamic heating and cooling

We consider an interacting-particle algorithm which is population-based like genetic algorithms and also has a temperature parameter analogous to simulated annealing. The temperature parameter of the interacting-particle algorithm has to cool down to zero in order to achieve convergence towards global optima. The way this temperature parameter is tuned affects the performance of the search process and we implement a meta-control methodology that adapts the temperature to the observed state of the samplings. The main idea is to solve an optimal control problem where the heating/cooling rate of the temperature parameter is the control variable. The criterion of the optimal control problem consists of user defined performance measures for the probability density function of the particles’ locations including expected objective function value of the particles and the spread of the particles’ locations. Our numerical results indicate that with this control methodology the temperature fluctuates (both heating and cooling) during the progress of the algorithm to meet our performance measures. In addition our numerical comparison of the meta-control methodology with classical cooling schedules demonstrate the benefits in employing the meta-control methodology.     

A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling

In this study, a general framework is proposed that combines the distinctive features of three well-known approaches: the adaptive memory programming, the simulated annealing, and the tabu search methods. Four variants of a heuristic based on this framework are developed and presented. The performance of the proposed methods is evaluated and compared with a conventional simulated annealing approach using benchmark problems for job shop scheduling. The unique feature of the proposed framework is the use of two short-term memories. The first memory temporarily prevents further changes in the configuration of a provisional solution by maintaining the presence of good elements of such solutions. The purpose of the second memory is to keep track of good solutions found during an iteration, so that the best of these can be used as the starting point in a subsequent iteration. Our computational results for the job shop scheduling problem clearly indicate that the proposed methods significantly outperform the conventional simulated annealing.     

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.     

基于拟线性化方法的非线性系统闭环反馈控制保辛算法

提出了一种求解非线性系统闭环反馈控制问题的保辛算法．首先,通过拟线性化方法将非线性系统最优控制问题转化为线性非齐次Hamilton系统两端边值问题的迭代格式求解．然后,通过作用量变分原理与生成函数构造了保辛的数值算法,且该算法保持了原Hamilton系统的辛几何性质．最后,通过时间步的递进完成状态与控制变量的更新,进而达到闭环控制的目的．数值算例表明:保辛算法具有较高的计算精度和较快的收敛速度．此外,将闭环反馈控制与开环控制分别应用于驱动小车上的倒立摆控制系统中,结果表明:在存在初始偏差的情况下,开环控制会导致稳定控制任务的失败,而闭环反馈控制能够在一段时间后消除初始偏差的影响,并使系统达到稳定状态．     

On a bilateral birth-death process with alternating rates

We consider a bilateral birth-death process characterized by a constant transition rate ?? from even states and a possibly different transition rate??? from odd states. We determine the probability generating functions of the even and odd states, the transition probabilities, mean and variance of the process for arbitrary initial state. Some features of the birth-death process confined to the non-negative integers by a reflecting boundary in the zero-state are also analyzed. In particular, making use of a Laplace transform approach we obtain a series form of the transition probability from state 1 to the zero-state.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

A stochastic probing algorithm for global optimization

Recently, simulated annealing methods have proven to be a valuable tool for global optimization. We propose a new stochastic method for locating the global optimum of a function. The proposed method begins with the subjective specification of a probing distribution. The objective function is evaluated at a few points sampled from this distribution, which is then updated using the collected information. The updating mechanism is based on the entropy of a move selecting distribution and is loosely connected to some notions in statistical thermodynamics. Examples of the use of the proposed method are presented. These indicate its superior performance as compared with simulated annealing. Preliminary considerations in applying the method to discrete problems are discussed.     

求解整数规划问题的混合遗传算法及收敛性

1引言 科学和工程领域中的许多优化问题最终可以归结为求解一个带有约束条件的整数规划问题.其形式为: {maxx∈In f(x) s.t.gi(x)=0,j=1,…,me; gi(x)≥0,i=me+1,…m, x∈nΠi=1 Ai, 式中I表示整数集,x=(x1,…,xn)T,Ai(i∈{1,…,n})为有限整数集. 遗传算法作为一种优化技术,是一种近似算法,一般不能保证一定能得到优化问题的精确解.     

A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs

In this paper, we present an approach for finding a minimum cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relationships among the elements are satisfied, based on the concept of simulated annealing. Simulated annealing is generally applicable, and can be used to obtain solutions arbitrarily close to an optimum. However, the standard simulated annealing approach with a conventional neighbourhood structure does not yield good solutions for this problem, since this is a multiple partitioning problem and the number of subsets is not fixed. For this problem, we develop an effective neighbourhood structure and a new acceptance criterion. We also assess the effectiveness of the developed algorithm. The results show that this proposed algorithm outperforms, in terms of solution quality, any other algorithm using tabu search. The computational time of the procedure is proportional to the number of nodes in the graph.     

A GRASP for Coloring Sparse Graphs

We first present a literature review of heuristics and metaheuristics developed for the problem of coloring graphs. We then present a Greedy Randomized Adaptive Search Procedure (GRASP) for coloring sparse graphs. The procedure is tested on graphs of known chromatic number, as well as random graphs with edge probability 0.1 having from 50 to 500 vertices. Empirical results indicate that the proposed GRASP implementation compares favorably to classical heuristics and implementations of simulated annealing and tabu search. GRASP is also found to be competitive with a genetic algorithm that is considered one of the best currently available for graph coloring.     

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.