三维装箱问题的组合启发式算法

通过组合拟人启发式和模拟退火算法,提出了三维装箱问题的组合启发式算法.拟人启发式算法的主要思想来源于日常砌墙中的策略.利用找点法以及水平和垂直参考线规则来控制装填过程.用模拟退火算法改进拟人启发式.经过一些数据的测试,实验结果表明,该算法能够同文献中的优秀算法竞争.     

求解SAT问题的改进粒子群优化算法

利用限制哆公式的相关理论将可满足性问题（SAT）等价转换为定义在{0，1}^n上的多项式函数优化问题，并将二进制粒子群优化算法（BPSO）与局部爬山搜索策略相结合，给出了一种求解SAT问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法（简称IBPSO）．数值实验表明，对于随机产生的3-SAT问题测试实例，该算法的计算结果均优于著名的WalkSAT算法和SATI．3算法．     

基于遗传和模拟退火算法求解3-SAT问题

命题逻辑公式的CNF范式的可满足性问题（sAT）是计算机科学的非常重要的核心问题,能否快速求解SAT问题是目前的研究热点之一。介绍Johnson算法、遗传算法和模拟退火算法,比较三种算法的特性,提出综合GA、SA算法优点的一种混舍遗传和模拟退火算法的思想。数值计算结果表明,相对于Johnson算法,采用启发式（SA、GA）算法可以显著地提高3-SAT问题解的质量和求解速度。     

求解SAT问题的退火遗传算法

提出一种将遗传算法与模拟退火算法相结合的SAT问题求解算法SAT-SAGA.该算法以遗传算法流程为主体,并把模拟退火机制融入其中,用以调整优化群体,防止陷入局部最优和出现早熟;在进化过程中算法采用了最优染色体保存策略,防止进化过程的发散.实验表明:该算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.     

一种神经网络参数扰动算法及其在机械手控制中的应用

基于Ｈｏｐｆｉｅｌｄ型网络的收敛特性和Ｋｉｒｐａｔｒｉｃｋ等的模拟退火算法的思想，提出了一种克服Ｈｏｐｆｉｅｌｄ网络的局部极值问题的网络参数扰动算法，它具有类似ＳＡ算法的随机退火的特性。文中通过大量数字模拟分析了该算法的退火性能。     

求解可满足问题的改进的蚁群算法

可满足问题（SAT）是一个NP-hard问题,将SAT问题转换为无约束的离散优化（最小值）问题。并根据M Dorigo提出的蚁群算法,给出了一种求解SAT问题的新方法：改进的最大最小蚁群系统（MMAS-SAT）。在改进的算法中,给出了SAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整。测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法。     

基于改进的遗传模拟退火混合算法求解TSP问题

本文针对遗传算法（GA）早熟收敛问题就GA的交叉算予进行改进,针对模拟退火算法易陷入局部最小值的缺点．使用HFC—ADM（自适应输入阂值的分等级搜索）的SA（模拟退火算法）和改进后的GA相结合,提出了一种求解TSP问题的遗传模拟退火混合算法,并应用于求解TSP（旅行商问题）问题。实验结果表明,该算法具有比传统的GA以及基于HFC—ADM的SA具有更强的全局搜索能力和更快的收敛速度。     

F1ow—shop调度问题的自适应模拟退火算法

为求得一个强NP-难问题——flow-shop调度问题的最优解或近优解，提出一种自适应模拟退火算法．本算法采用一种基于区段特性的特殊邻域结构、简便的目标函数计算方法和自适应退火策略．通过Flow-shop调度问题的基准测试问题的实验，数值结果证实了该方法的有效性．     

文化基因算法求解TSP问题的研究

TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。     

一种新型模拟退火神经网络及其应用

针对训练神经网络权值的BP算法容易陷于局部最小值点的问题，提出了带自适应冷却进度表的模拟退火算法与lowell算法构成新型混合算法，用该算法训练网络的权值。冷却进度表中主要参数是模拟退火算法的控制参数T的初值T0和T的衰减函数。把整个迭代过程划分为若干阶段，在每个阶段结束时，依据网络模型误差自适应地修正下阶段的T0（回火温度）、T的衰减函数中的参数和迭代步长初值。仿真结果表明，上述混合算法具有很强的全局和局部搜索能力，其性能优于BP算法；该算法在油田系统建模问题中的成功应用也表明了该方案的有效性。     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

基于加强概率控制策略的SAT局部搜索算法

局部搜索算法是目前求解SAT问题比较有效的方法,而Sattime算法是在SAT国际大赛中获得大奖的一种典型局部搜索算法。在Sattime算法的求解过程中,记录变元翻转事件流数据库,通过数据分析与模式挖掘,发现Sattime算法的局部搜索行为中会出现相邻搜索步选择同一个变元的现象,即所谓的回环现象,从而降低了求解效率。为解决此问题,提出两种概率控制策略：加强子句选择策略和加强变元选择策略,并将这两种策略应用到Sattime算法中,形成新的局部搜索算法Sattime-P。实验结果表明,与Sattime算法相比,改进后的Sattime-P算法求解效率有显著的提升。该方法也对其他局部搜索算法的改进具有参考价值。     

A direct search variant of the simulated annealing algorithm for optimization involving continuous variables

A memory-based simulated annealing algorithm is proposed which fundamentally differs from the previously developed simulated annealing algorithms for continuous variables by the fact that a set of points rather than a single working point is used. The implementation of the new method does not need differentiability properties of the function being optimized. The method is well tested on a range of problems classified as easy, moderately difficult and difficult. The new algorithm is compared with other simulated annealing methods on both test problems and practical problems. Results showing an improved performance in finding the global minimum are given.Scope and purposeThe inherent difficulty of global optimization problems lies in finding the very best optimum (maximum or minimum) from a multitude of local optima. Many practical global optimization problems of continuous variables are non-differentiable and noisy and even the function evaluation may involve simulation of some process. For such optimization problems direct search approaches are the methods of choice. Simulated annealing is a stochastic global optimization algorithm, initially designed for combinatorial (discrete) optimization problems. The algorithm that we propose here is a simulated annealing algorithm for optimization problems involving continuous variables. It is a direct search method. The strengths of the new algorithm are: it does not require differentiability or any other properties of the function being optimized and it is memory-based. Therefore, the algorithm can be applied to noisy and/or not exactly known functions. Although the algorithm is stochastic in nature, it can memorise the best solution. The new simulated annealing algorithm has been shown to be reliable, fast, general purpose and efficient for solving some difficult global optimization problems.     

基于融合算法的测试优化选择问题研究

测试优化选择是个集覆盖问题,而启发式算法是求解集覆盖问题的有效方法。文中将遗传算法、BP神经网络和模拟退火算法进行融合,提出了一种融合算法,该算法充分利用遗传算法全局搜索能力强、BP神经网络训练能力强和模拟退火算法搜索速度快的优点,既避免陷入局部最优的现象,又提高了搜索的效率和精度。该算法已应用于求解测试优化问题。实例证明,该算法能够快速有效地求得测试优化问题的最优解。     

求解TSP的改进模拟退火算法

利用模拟退火算法给出了求解旅行商问题的一种新方法.在模拟退火算法的基本原理基础上,针对解变换只交换两个城市而容易落入局部最优解的缺点,提出了在解变换产生新解的过程中,采用逆转操作的改进方法.这使得迭代过程突破局部最优圈,然后跳到另一个搜索空间.这样能够使其更具多样性,改善了模拟退火算法的局部搜索能力.并将其应用于求解旅行商问题,显著改善了它局部寻优的能力.在几个公共测试数据集上的结果表明,算法稳定可行,在求解组合优化问题方面,具有良好的性能.     

Simulated annealing for the design of structures with time-varying constraints

The optimal design of structural systems with conventional members or systems with conventional as well as passive or active members is presented. The optimal sizes of the conventional members of structural systems are obtained for dynamic loads. A modified simulated annealing algorithm is presented which is used to solve the optimization problem with dynamic constraints. The present algorithm differs from existing simulated annealing algorithms in two respects; first, an automatic reduction of the search range is performed, and second, a sensitivity analysis of the design variables is utilized. The present method converges to the minimum in less iterations when compared to existing simulated annealing algorithms. The algorithm is advantageous over classical methods for optimization of structural systems with constraints arising from dynamic loads. For certain initial values of the design variables, classical optimization methods either fail to converge or produce designs which are local minima; the present algorithm seems to be successful in yielding the global minimum design.     

Flexible job-shop scheduling with tolerated time interval and limited starting time interval based on hybrid discrete PSO-SA: An application from a casting workshop

In this paper, we addressed two significant characteristics in practical casting production, namely tolerated time interval (TTI) and limited starting time interval (LimSTI). With the consideration of TTI and LimSTI, a multi-objective flexible job-shop scheduling model is constructed to minimize total overtime of TTI, total tardiness and maximum completion time. To solve this model, we present a hybrid discrete particle swarm optimization integrated with simulated annealing (HDPSO-SA) algorithm which is decomposed into global and local search phases. The global search engine based on discrete particle swarm optimization includes two enhancements: a new initialization method to improve the quality of initial population and a novel gBest selection approach based on extreme difference to speed up the convergence of algorithm. The local search engine is based on simulated annealing algorithm, where four neighborhood structures are designed under two different local search strategies to help the proposed algorithm jump over the trap of local optimal solution. Finally, computational results of a real-world case and simulation data expanded from benchmark problems indicate that our proposed algorithm is significant in terms of the quality of non-dominated solutions compared to other algorithms.     

MAX-SAT问题一种改进的局部搜索算法

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的。本文提出了用单纯形法产生“初始概率”（每个变量取1的概率）,用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度。通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.