Simulated annealing applied to test generation: landscape characterization and stopping criteria

This paper investigates a measurement approach to support the implementation of Simulated Annealing (SA) applied to test generation. SA, like other metaheuristics, is a generic technique that must be tuned to the testing problem under consideration. Finding an adequate setting of SA parameters, that will offer good performance for the target problem, is known to be difficult. Our measurement approach is intended to guide the implementation choices to be made. It builds upon advanced research on how to characterize search problems and the dynamics of metaheuristic techniques applied to them. Central to this research is the concept of landscape. Existing measures of landscape have mainly been applied to combinatorial problems considered in complexity theory. We show that some of these measures can be useful for testing problems as well. The diameter and autocorrelation are retained to study the adequacy of alternative settings of SA parameters. A new measure, the Generation Rate of Better Solutions (GRBS), is introduced to monitor convergence of the search process and implement stopping criteria. The measurement approach is experimented on various case studies, and allows us to successfully revisit a problem issued from our previous work on testing control systems.     

蚁群模拟退火算法在测试用例约简中的应用

参数的成对组合覆盖测试技术是软件测试中有效的测试方法之一。该文将模拟退火思想引入蚁群算法,组成新的混合算法,即蚁群模拟退火混合算法(ASA),应用在组合测试用例的约简过程中。按照测试的特殊需求进行多种建模尝试,通过仿真实验对算法涉及的参数进行研究,实验验证了ASA 算法对测试用例集的约简作用是有效的。     

Simulated annealing with adaptive neighborhood: A case study in off-line robot path planning

Simulated annealing (SA) is an optimization technique that can process cost functions with degrees of nonlinearities, discontinuities and stochasticity. It can process arbitrary boundary conditions and constraints imposed on these cost functions. The SA technique is applied to the problem of robot path planning. Three situations are considered here: the path is represented as a polyline; as a Bézier curve; and as a spline interpolated curve. In the proposed SA algorithm, the sensitivity of each continuous parameter is evaluated at each iteration increasing the number of accepted solutions. The sensitivity of each parameter is associated to its probability distribution in the definition of the next candidate.     

一种求解圆形Packing问题的模拟退火算法?

为求解矩形区域内的圆形Packing问题,提出一种启发式模拟退火算法。寻求多个圆在一个矩形区域内的优良布局,使这些圆两两互不嵌入地放置。算法从任一初始构形出发,采用模拟退火(SA)算法进行全局寻优,在SA执行过程中,应用基于自适应步长的梯度法进行局部搜索,同时介绍一些启发式策略。对2组共20个算例进行实算测试,计算结果证明了该算法的有效性。     

Parallel Simulated Annealing Algorithms

Simulated annealing (SA) has been considered a good tool for complex nonlinear optimization problems. The technique has been widely applied to a variety of problems. However, a major disadvantage of the technique is that it is extremely slow and hence not suitable for complex optimization problems such as scheduling. There are many attempts to develop parallel versions of the algorithm. Many of these algorithms are problem dependent in nature. We present, in this paper, two general algorithms for SA. The algorithms have been applied to job shop scheduling problem (JSS) and the traveling salesman problem (TSP) and it has been observed that it is possible to achieve superlinear speedups using the algorithm.     

混合SPMD模拟退火算法及其应用

模拟退火算法由于有很好的数学特性－以概率1收敛于全局最优值,再加上其算法本身与特定的问题无关,因此被广泛地用于各种组合优化问题。但是,模拟退火算法又具有收敛速度慢,执行时间长,算法性能与初始值有关及参数敏感等特点,使得它在不少应用中成为一种低效甚至是不可行的算法。文中提出一种混合SPMD模拟退火算法,在克服经典模拟退火算法内在串行性的同时,进一步和下山法结合起来,并综合多种优化方法,在一定的处理机规模内取得了可扩展和并行效果,显著提高了算法的收敛速度,克服了算法性能对初始值和参数选择的过分依赖,在提高算法性能的同时,方便了算法的使用。该算法已在一个机群系统THNPSC－1上得以实现,并在材料科学的一个定量电子晶体学研究问题中得到应用,降低了该问题的求解时间,提高了求解质量。     

基于遗传算法和模拟退火算法的TDOA定位技术

提出一种基于遗传算法与模拟退火算法的TDOA定位估计算法,该算法通过对求解定位坐标计算时的最大似然函数进行求解,实现了利用所有TDOA测量值对移动台的定位估计。该算法采用实数编码,自适应交叉率和变异率实现遗传算法的全局搜索,引入模拟退火的Boltzmann机制,解决遗传算法容易陷入局部最优的问题。实验结果表明,该算法定位精度高、收敛速度快。     

一个基于确定性退火的时延驱动标准单元布局算法

提出了一个基于确定性模拟退火技术的时延驱动标准单元布局算法,实现在满足时延约束和宽高比约束的前提下优化版图面积,与基于一般的随机模拟退火技术的标准单元布局算法相比,该算法的运行速度快、布局效果较好。     

基于遗传模拟退火算法的门阵列布局方法

为实现门阵列模式布局,将遗传算法与模拟退火算法相结合,提出一种新的遗传模拟退火算法,利用遗传算法进行全局搜索,利用模拟退火法进行局部搜索,在进化过程中采用精英保留策略,对进化结果进行有选择的模拟退火操作,既加强了局部搜索能力又防止陷入局部最优。实验结果表明,与传统遗传算法相比,该算法能够有效提高全局搜索能力。     

求解蛋白质结构问题的改进模拟退火算法

将模拟退火(SA）思想用于求解蛋白质结构预测问题,并在此基础上提出了两个提高解的质量和加快收敛速度的改进策略,计算结果表明改进后的SA算法的计算效率优于目前常用的遗传算法和Monte Carlo方法。     

融合模拟退火的遗传算法在文档聚类中的应用

为了准确高效地对网上获取的文档进行聚类,在布尔逻辑模型的基础上提出了一种改进的最优相似度搜索方法。该方法将模拟退火的思想融入到遗传算法当中,通过“撒种”操作将模拟退火算法的局部搜索能力以及遗传算法的全局搜索能力结合起来。实验表明,使用该混合算法对文档进行聚类,不仅搜索效率得到了提高,而且准确度优于使用传统的遗传算法。     

Simulated annealing for the quadratic assignment problem: A further study

Concentrating on the generating mode of random permutation solutions and the corresponding theory and evaluation problems, this paper carries out a further study on the Simulated Annealing (SA) algorithm for the Quadratic Assignment Problem (QAP) which has many applications in practice. The paper introduces and analyzes the six different kinds of interchanges of facility locations for generating random permutations. The theoretical analyses prove that the relevant generation probabilities satisfy the asymptotical convergence conditions. The results of experimental evaluations reveal the relations between the random sampling modes, and show that adopting the proper generating mode the SA algorithm can produce better quality solutions of the QAP. At the same time, the conclusions reached in the paper are available for many extensive heuristics to solve combinatorial optimization problems.     

基于改进遗传与模拟退火融合的RISP软硬件划分

软硬件划分是可重构指令集处理器在软硬件协同设计中的关键问题,通过对比遗传算法和经典模拟退火算法的优缺点,提出改进遗传算法的适应度函数,同时将Tsallis接受准则引入到经典模拟退火当中;其思路是用遗传算法的结果来制约模拟退火算法产生的随机状态,然后由模拟退火的接受准则以及产生的随机状态函数对遗传算法的种群进行更新,从而找到全局近似最优解;实验结果证明,改进算法与单一遗传算法以及经典模拟退火算法相比,其收敛速度和适应度更好,找到全局近似最优解的概率更大。     

供应链订单分配优化模型及其模拟退火算法

受4M1E(人、机、料、法、环)因素的随机波动影响,产品的制造过程通常是不完美的,从而产生不良产品.针对已有研究多忽略不良产品的特点,建立了更加符合实际需求的订单分配多目标混合整数规划模型,其优化目标为最小化交易成本、采购成本、不良产品数量、产品延迟交付数量,以及最大化供应商信誉评价.考虑到模型求解的复杂度,设计了一种模拟退火算法,并结合启发式规则避免了大量非法初始解与邻点解的出现.实验算例表明所建立的模型能够反映订单分配过程中的产品缺陷现象,其算法能够在允许的运算时间内获得稳定的满意解,并且随着算例规模的增大,其计算时间与优化结果均优于LINGO软件.     

基于PSO和变异模拟退火的QoS单播路由算法

为了研发更高性能的QoS单播路由算法,提出变异退火粒子群优化（MSAPSO）算法。MSAPSO算法中使用一种新的。算子,将粒子群优化（PSO）的迭代公式简化成一个公式。通过设计变异退火算子,将遗传算法的变异操作和模拟退火的Meuopofis概率接受准则融入PSO,以改善粒子群的多样性和算法的收敛性。仿真结果表明MSAPSO在搜索成功率和收敛性上优于纯PSO算法和蚁群算法。     

基于离散和声搜索与模拟退火的混合算法

和声搜索是一种启发式优化算法,对和声搜索算法进行离散化,使其能够适用于组合优化问题,就离散和声搜索算法进行两点改进,针对离散和声搜索算法容易陷入局部最优的缺陷,提出一种离散和声搜索与模拟退火算法的混合策略。实验结果表明,基于改进离散和声搜索与模拟退火的混合算法具有较高的求解质量。     

模拟退火多级VQ编码方案及实现

在查阅和分析多级矢量量化和模拟退火技术有关文献资料的基础上,阐述了矢量量化最优码书的形成条件,并以多级矢量量化和模拟退火技术为基础,提出了一种基于模拟退火技术的多级矢量量化编码方案,该方案充分弥补了多级矢量量化和模拟退火技术在图象编码中应用的各自不足,并且发挥了多级矢量量化和模拟火技术在图象编码中应用的各自优点,理论和实验都证明,该算法不仅能 码书存储量,而且图象恢复效果较好。     

A comparative analysis of meta-heuristic approaches for facility layout design problem: a case study for an elevator manufacturer

In this study, a facility layout problem having NP-hard problem characteristic is attempted to be solved by using two different meta-heuristic approaches—Genetic Algorithm (GA) and Simulated Annealing (SA)—and a hybrid approach—Genetic Algorithm/Simulated Annealing (HGASA). The case study is completed for a company which can be seen as a small or a medium size enterprise. First, parameter values of GA and SA are determined by testing for various combinations of them. Then, the algorithms are run for one hundred times. The results of the algorithms are compared based on their fitness values and calculation time requirements using the paired-t test, mean and standard values. The results show that SA performs better than the others in terms of the fitness values and the time requirements. In this study, we also test the performance of our GA, SA and HGASA methodologies using some of the well-known test problems from the literature. We obtain very close results to those in literature.     

Estimation of the minimum machining performance in the abrasive waterjet machining using integrated ANN-SA

In this study, Artificial Neural Network (ANN) and Simulated Annealing (SA) techniques were integrated labeled as integrated ANN-SA to estimate optimal process parameters in abrasive waterjet (AWJ) machining operation. The considered process parameters include traverse speed, waterjet pressure, standoff distance, abrasive grit size and abrasive flow rate. The quality of the cutting of machined-material is assessed by looking to the roughness average value (R_a). The optimal values of the process parameters are targeted for giving a minimum value of R_a. It was evidence that integrated ANN-SA is capable of giving much lower value of R_a at the recommended optimal process parameters compared to the result of experimental and ANN single-based modeling. The number of iterations for the optimal solutions is also decreased compared to the result of SA single-based optimization.