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.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

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.     

A new hybrid method for solving global optimization problem

In this paper we present a new hybrid method, called the SASP method. The purpose of this method is the hybridization of the simulated annealing (SA) with the descent method, where we estimate the gradient using simultaneous perturbation. Firstly, the new hybrid method finds a local minimum using the descent method, then SA is executed in order to escape from the currently discovered local minimum to a better one, from which the descent method restarts a new local search, and so on until convergence.The new hybrid method can be widely applied to a class of global optimization problems for continuous functions with constraints. Experiments on 30 benchmark functions, including high dimensional functions, show that the new method is able to find near optimal solutions efficiently. In addition, its performance as a viable optimization method is demonstrated by comparing it with other existing algorithms. Numerical results improve the robustness and efficiency of the method presented.     

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.     

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

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 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.     

A hybrid simulated annealing and column generation approach for capacitated multicommodity network design

This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.     

Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs

Local search heuristics are developed for a problem of scheduling jobs on a single machine. Jobs are partitioned into families, and a set-up time is necessary when there is a switch in processing jobs from one family to jobs of another family. The objective is to minimize the number of late jobs. Four alternative local search methods are proposed: multi-start descent, simulated annealing, tabu search and a genetic algorithm. The performance of these heuristics is evaluated on a large set of test problems. The best results are obtained with the genetic algorithm; multi-start descent also performs quite well.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

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

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

一类凸优化的加速混合下降算法

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术,结合邻近点算法和近似邻近点算法的思想,构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想,利用已有近似规则信息改善了混合下降算法的下降方向,得到了一类凸优化问题的加速混合下降算法.随后利用Markov不等式、凸函数性质和投影的基本性质等,实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

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.     

基于SA-GA混合算法的动车组车辆轮重分配优化

针对动车组车辆出厂前存在的轮重偏差问题,建立动车组车辆轮重调节力学模型,利用模拟退火算法（SA）的机制和遗传算法（GA）非均匀变异思想,提出了一种模拟退火遗传（SA-GA）混合算法,并利用该混合算法对车辆轮重调节力学模型进行数值求解, 结果显示: 轮重偏差降低到1.2%以下,符合GB/T 3317—2006的规定.同时使用SIMPACK软件仿真,将该仿真结果与数值计算结果对比分析,结果显示:基于SA GA混合算法的计算结果是正确的,这为快速优化轮重分配结果提供了一种有效的计算方法.     

A hybrid descent method for solving a convex constrained optimization problem with applications

The purpose of this paper is to introduce a hybrid descent algorithm for finding a common point in fixed‐point sets of quasi‐nonexpansive mappings and solution sets of variational inequality problems. In the framework of Hilbert spaces, the strong convergence of the hybrid descent algorithm is established. Numerical experiments for the bandwidth allocation, which demonstrate the effectiveness, performance, and convergence of the proposed algorithm, are provided.     

Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification

The hybrid algorithm that combined particle swarm optimization with simulated annealing behavior (SA-PSO) is proposed in this paper. The SA-PSO algorithm takes both of the advantages of good solution quality in simulated annealing and fast searching ability in particle swarm optimization. As stochastic optimization algorithms are sensitive to their parameters, proper procedure for parameters selection is introduced in this paper to improve solution quality. To verify the usability and effectiveness of the proposed algorithm, simulations are performed using 20 different mathematical optimization functions with different dimensions. The comparative works have also been conducted among different algorithms under the criteria of quality of the solution, the efficiency of searching for the solution and the convergence characteristics. According to the results, the SA-PSO could have higher efficiency, better quality and faster convergence speed than compared algorithms.     

蚁群遗传混合算法

将蚁群遗传混合算法分别求解离散空间的和连续空间优化问题.求解旅行商问题的混合算法是以遗传算法为整个算法的框架,利用了蚁群算法中的信息素特性的进行交叉操作;根据旅行商问题的特点,给出了4种变异策略;针对遗传算法存在的过早收敛问题,加入2-0pt方法对问题求解进行了局部优化.与模拟退火算法、标准遗传算法和标准蚁群算法进行比较,4种混合算法效果都比较好,策略D的混合算法效果最好.求解连续空间优化问题是以蚁群算法为整个算法的框架,加入遗传算法的交叉操作和变异操作,用测试函数验证了混合蚁群算法的正确性.     

Design method using hybrid of line-type and circular-type routes for transit network system optimization

Transit network design is a very important problem. In particular, it has a great influence on passenger satisfaction with the whole transit network system. The present research proposes a simulated annealing (SA) method for optimizing a transit network design. In the algorithm, the strategy to search for neighborhood solutions provides the chance to find the best hybrid of line-type and circular-type routes. The proposed SA method is also compared with other methods. The results show that the proposed SA model is a good alternative for transit network design, particularly as it provides the scope to design hybrids of line-type and circular-type routes.     

Using pattern matching for tiling and packing problems

This paper describes a new placement method based on pattern matching for 2D tiling problems. Tiling problem can be considered as a special case of bin packing. In the proposed method, the representation of the figures and the board is based on directional chain codes. Contrary to other works that the area has been used for the board and the figures, the proposed method is based on usage of their boundaries instead. With this representation, consideration of the area has been replaced with that of the exact string matching. With the proposed knowledge representation, rotation and reflection of the figures can be considered easily. The results of a hybrid approach of genetic algorithm and simulated annealing have been shown. This new method, introduces a novel approach for handling and solving a variety of 2D-packing problems.