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.     

A hybrid glowworm swarm optimization algorithm to solve constrained multimodal functions optimization

In this paper, a novel hybrid glowworm swarm optimization (HGSO) algorithm is proposed. The HGSO algorithm embeds predatory behaviour of artificial fish swarm algorithm (AFSA) into glowworm swarm optimization (GSO) algorithm and combines the GSO with differential evolution on the basis of a two-population co-evolution mechanism. In addition, to overcome the premature convergence, the local search strategy based on simulated annealing is applied to make the search of GSO approach the true optimum solution gradually. Finally, several benchmark functions show that HGSO has faster convergence efficiency and higher computational precision, and is more effective for solving constrained multi-modal function optimization problems.     

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

基于混合果蝇优化算法的选址-库存-配送集成优化研究

本文面向企业运营管理实践,构建了一种基于联合补货策略的选址-库存-配送集成优化新模型。作为典型的NP-hard问题,传统算法难以高效稳定地求解,故本文设计了一种新的混合果蝇优化算法(Fruit Fly Optimization Algorithm, FOA),通过引入进化算法的信息交换、变异、选择操作来增强算法局部寻优能力,采取概率性飞行策略来平衡算法的全局寻优与局部寻优。算例结果表明,新混合FOA算法的准确性和稳定性较标准FOA有了明显的改善,与差分进化、自适应混合差分进化、粒子群优化相比也具有比较优势。     

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.     

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.     

Analyzing the Performance of Generalized Hill Climbing Algorithms

Generalized hill climbing algorithms provide a framework to describe and analyze metaheuristics for addressing intractable discrete optimization problems. The performance of such algorithms can be assessed asymptotically, either through convergence results or by comparison to other algorithms. This paper presents necessary and sufficient convergence conditions for generalized hill climbing algorithms. These conditions are shown to be equivalent to necessary and sufficient convergence conditions for simulated annealing when the generalized hill climbing algorithm is restricted to simulated annealing. Performance measures are also introduced that permit generalized hill climbing algorithms to be compared using random restart local search. These results identify a solution landscape parameter based on the basins of attraction for local optima that determines whether simulated annealing or random restart local search is more effective in visiting a global optimum. The implications and limitations of these results 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 Trigonometric Mutation Operation to Differential Evolution

Previous studies have shown that differential evolution is an efficient, effective and robust evolutionary optimization method. However, the convergence rate of differential evolution in optimizing a computationally expensive objective function still does not meet all our requirements, and attempting to speed up DE is considered necessary. In this paper, a new local search operation, trigonometric mutation, is proposed and embedded into the differential evolution algorithm. This modification enables the algorithm to get a better trade-off between the convergence rate and the robustness. Thus it can be possible to increase the convergence velocity of the differential evolution algorithm and thereby obtain an acceptable solution with a lower number of objective function evaluations. Such an improvement can be advantageous in many real-world problems where the evaluation of a candidate solution is a computationally expensive operation and consequently finding the global optimum or a good sub-optimal solution with the original differential evolution algorithm is too time-consuming, or even impossible within the time available. In this article, the mechanism of the trigonometric mutation operation is presented and analyzed. The modified differential evolution algorithm is demonstrated in cases of two well-known test functions, and is further examined with two practical training problems of neural networks. The obtained numerical simulation results are providing empirical evidences on the efficiency and effectiveness of the proposed modified differential evolution algorithm.     

Parallelizing simulated annealing algorithms based on high-performance computer

We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance computers and applied them to a set of standard function optimization problems in order to test their performances. According to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely, parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great time cost if the random search space was considerably expanded. The most effective way we found in identifying the global optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success rate and solution quality.     

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.     

Approximation of the distribution of convergence times for stochastic global optimisation

How long should we run a stochastic global optimisation algorithm such as simulated annealing? How should we tune such an algorithm? This paper proposes an approach to the study of these questions through successive approximation of a generic stochastic global optimisation algorithm with a sequence of stochastic processes, culminating in a backtracking adaptive search process. Our emerging understanding of backtracking adaptive search can thus be used to study the original algorithm. The first approximation, the averaged range process, has the same expected number of iterations to convergence as the original process.     

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.     

基于精英区域学习的多种群自适应的差分进化算法

为了进一步提高差分进化算法的收敛速度、算法精度和稳定性,采用多种群技术来增加算法收敛速度和降低复杂度;利用精英区域学习策略来对算法的全局搜索能力和算法精度进一步提升,引进自适应免疫搜索策略,以实现自适应修正差分算法的变异因子和交叉因子。通过五个测试函数,把本文算法与最新文献中的算法进行对比,表明算法在收敛速度、精度和高维问题寻优能力方面的优越性。     

蚁群遗传混合算法

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

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.     

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.     

变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。