基于序列对和模拟退火算法的布局问题研究

结合布局问题的具体特点,采用序列对来间接描述布局问题的解结构,并且在模拟退火算法的基础上对布局问题的优化算法进行了研究,综合构成了一种有效求解布局问题的模拟退火算法。还将传统模拟退火算法和加回火策略的模拟退火算法的测试结果进行了比较。通过测试模块验证,传统算法取得了很优的结果,加回火策略的算法略微优于传统优化算法但却大大增加了时间复杂度。     

布局问题的模拟退火算法

布局问题属于ＮＰ－完全问题已被研究多年，模拟退火法是一种新的通用启发式优化算法，现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组成优化问题，本语文通过对布局问题及模拟退火算法的分析，将它们综合起来构成了求解布局问题的模拟退火算法，计算结果表明，本文算法得到的解优于传统优化方法所得到的解；本文还通过实验对算法中各参数所起作用进行了论述。     

求解矩形件优化排样的自适应模拟退火遗传算法

矩形件优化排样是一个NPC问题,在工业界有着广泛的应用.针对该问题,提出一种自适应模拟退火遗传算法.采用一种基于环形交叉算子和环形变异算子的自适应遗传算法来自动调整交叉和变异概率;同时引入模拟退火算法对个体适应度大于平均适应度的个体进行退火处理.自适应模拟退火遗传算法充分发挥了自适应遗传算法与模拟退火算法各自的全局搜索能力与局部搜索能力.对比实验表明,该算法结合改进的最左最下布局算法解决矩形件优化排样问题更加有效.     

改进型模拟退火算法在设备布局设计中的应用

由于设备布局问题是NP完全问题，它在有限合理的时间内难以求得最优解，因此问题的求解只能依赖于各种启发式方法。文章针对传统的模拟退火算法经常出现迂回搜索，导致搜索效率低，解的质量差这一现象，通过在传统模拟退火算法搜索过程中增加记忆功能，来避免迂回搜索，将改进的模拟退火算法应用于设备布局的研究中，通过实例证明改进的模拟退火算法解的质量有了很大提高。     

基于遗传算法和模拟退火算法的布局问题研究

文章在介绍遗传算法和模拟退火算法的基本理论及主要特点的基础上,提出了一个基于遗传算法和模拟退火算法的求解布局问题(矩形件排样优化)算法,并通过算例验证了该算法的有效性。     

一种混合全局寻优算法及其在布局中的应用

布局问题是NP完全问题,传统的优化算法很难求得全局最优欠解,遗传算法和模拟退火算法等的随机搜索算法的求解精度和效率不能令人满意,文中将启发式随机搜索策略的局部优化算法相结合,构造混合全局寻优算法,以旋转卫星舱布局问题的简化模型为背景,建立了多目标优化的数学模型,通过一已在最优解的布局算例与遗传算法和乘子法的计算结果比较,该算法求解的质量和效率更优,表明此算法在布局优化中具有应用潜力。     

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

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

基于量子模型的快速FPGA布局算法

为能在全局范围内快速搜索到优化的布局结果,提出一种基于量子模型的布局算法,并结合传统模拟退火算法实现FPGA布局。测试结果表明,相比VPR布局算法,该算法的布局运行速度平均提高了2倍以上,时序性能提升了2%,且随着FPGA芯片和电路规模的不断增大,能有效提高FPGA的软件运行效率。     

基于模拟退火离散粒子群算法的芯片堆叠热布局优化

针对芯片堆叠的热布局优化问题,使用热叠加模型,结合热传导公式,以所有芯片温度的最高值作为评价指标,确定出三维芯片堆叠热布局优化的适应度函数;然后采用模拟退火离散粒子群算法对芯片热布局进行优化。得到优化后的芯片堆叠布局方案,并用Icepak软件对优化后的布局进行仿真验证。仿真结果表明：采用模拟退火离散粒子群算法对三维芯片堆叠进行热布局优化可以使温度分布更加均匀,最高温度明显降低。     

量子行为粒子群优化算法的布局问题研究

基于多边形扫描转换的启发式底左（HBL）算法，将量子行为的粒子群算法（QPSO）应用于布局问题——二维不规则多边形优化排样，给出了该问题的粒子构造方法及其布局优化过程。通过与模拟退火遗传算法（SAGA）进行布局优化比较，验证了该算法求解布局优化问题的有效性。     

基于改进初始解的遗传算法的布局设计方法

带性能约束的三维布局问题属于具有很强应用背景的组合优化问题,进行了基于全局的布局求解方法的探索。由于NP完全问题的计算复杂性,使得遗传算法求解问题的全局最优解时效率较低。改进了遗传算法的初始解,对提高算法的效率进行了研究。并以旋转卫星舱布局的简化模型为背景,建立了多目标优化数学模型。实例结果与传统遗传算法以及乘子法的计算结果比较,表明该算法具有较好的求解效率。     

基于自适应遗传模拟退火算法的矩形件排样

研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。     

A simple simulated annealing algorithm for the maximum clique problem

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.     

有卸货顺序约束的集装箱装载问题及算法研究

对有卸货顺序约束的三维集装箱问题进行了描述.基于禁忌规则,采用了求解该问题的模拟退火算法,设计了货物的摆放规则和序列生成方式.采用3种邻域,根据邻域的不同,构造了2种禁忌表.根据问题的特点,在模拟退火算法抽样过程中加入了禁忌规则.介绍了算法的原理,给出了具有代表性算例试验结果并且进行了分析.试验结果表明,提出的混合算法对有卸货顺序约束的集装箱三维装载问题的有效性.     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

带有一刀切约束的二维非规则装箱算法

针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法。该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的NFP(Not-Fit-Polygon)预判交方法,极大地缩短了排样的整体时间,最后使用模拟退火算法对下料流程进行了优化,改善了排样结果。     

利用改进的差分进化算法求解等圆Packing问题

等圆Packing问题属于强约束的复杂组合优化问题之一,针对其强约束特点及难点,通过改进传统的差分进化算法,提出一种等圆Packing问题的求解方法。该改进算法特点是将有效解空间加入差分进化的变异约束中,并采用随机排序机制改进差分进化的选择机制。通过多次实验,表明此算法在求解小规模等圆Packing问题上取得的效果与目前所能找到的最优值相差不到0.6%,从而验证了演化计算在求解等圆Packing问题的可行性;与此同时,演化算法具有很好的收敛性,因此在其他强约束的复杂优化问题上将有很好的应用。     

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

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