最佳吻合矩形件排样算法

LFB矩形零件排放算法具有很高的效率,文章在LFB算法的基础上,针对该算法在排放中产生的浪费矩形块问题,提出最佳吻合算法,待排零件优先从浪费矩形块中选择最佳排放位置,得到了较原LFB算法更优的排样结果,并为其它排样算法的改进提供了一种思路。     

矩形件排样问题的遗传算法求解

本文研究了求解矩形件正交排样优化问题的遗传算法。同时，将矩形件正交排样问题转化为一个排列问题，提出了求一个排列所对应的排样图的下台阶算法（改进的ＢＬ算法）将下台阶算法与遗传算法相结合，用于矩形件排样问题的求解，给出了该算法的实现。用该算法对文献中的两个算例进行了求解，结果表明该算法获得了比ＢＬ算法更好的解，是一种较为行之有效的方法。     

基于最优子段的矩形优化排样

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究, 给出基于最优子段的矩形优化排样算法,有效解决了企业实际生产中的长板矩形优化排样问题。 首先基于动态规划算法求出所有小于剪床刀刃长度的最优子段的最佳排样方式,然后以所求的最 优子段作为可用子段在长板上进行优化排样,并将矩形优化排样问题转化为完全背包问题。最后 基于分支定界技术的整数规划算法对其进行求解。企业应用实例表明该算法在解决长板矩形优化 问题方面优于其他算法。     

板材排样问题中不规则多边形优化组合策略研究

板材排样问题是从一组给定的矩形（或非矩形）板材上切割出一批规则的和不规则形状的零件，且使板材的耗费最低。本文研究不规则多边形优化组合策略，提出一种相同零件受限递归组合算法。     

矩形件优化排样问题的混合遗传算法求解

利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过遗传算法将矩形件正交排样问题转化为一个排列问题，并引人剩余矩形排样算法来惟一确定每一个排列所对应的排样图（即排样方案），两者结合用于求解矩形件排样问题。最后用此混合遗传算法对文献[1]中的两个算例进行了验证，表明了其有效性。     

基于离散粒子群优化算法求解矩形件排样问题

改进了一种近似排样算法,并将改进的近似排样算法与离散粒子群优化算法结合求解矩形件排样问题.设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作和定义,给出了离散粒子群优化算法求解矩形件排样问题的详细步骤,最后通过实验测试,验证了算法的有效性.     

矩形件排样优化的一种近似算法

本文对理论上属于ＮＰ－完备问题的二维矩形件优化排样问题，构造了一个效率高、速度快、可令人满意的一种近似算法，该算法的主要思想是在排样过程中根据一种局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一些已排过的矩形区域，直至所有的矩形件被排完，根据本文算法我们开发了一个矩形件排样系统。     

基于两阶段的分段单一矩形优化排样

为有效解决分段单一矩形优化排样问题,给出一个求解分段单一矩形优化排样问题的两阶段方法。第一阶段完成标准子段最佳排样方式求解,并将二维排样问题转化为一维下料问题,第二阶段使用适合于一维下料问题求解的算法完成板材最佳排样方式求解。使用该方法开发了一个单一矩形优化排样系统,该系统既可以解决分段单一矩形排样问题也可以解决其他类型的单一矩形优化排样问题。企业应用实例表明该方法是求解分段单一矩形优化排样问题的一个较为有效的方法。     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

基于排样矩形的直角边零件下料算法

针对实际操作中直角边零件下料利用率不高的问题,导入排样矩形的概念,将直角边零件下料问题分解为若干优化子问题,在此基础上,基于动态规划思想通过求解子问题构建全局最优解.实验表明,与传统的直角边零件板材切割相比,使用本文算法能够使板材的利用率提高30％-50％;与其他几种典型算法相比,本算法板材利用率提高显著,并且排样方案简单,更适用于实际操作.     

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

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

基于AGA和集中剩余矩形区域策略的排样方法研究

针对目前工业生产中存在的矩形件排样优化问题,采用交叉概率和变异概率自适应改变的自适应遗传算法(AGA),并在遗传算法主要环节中采用改进的、性能较优的算子对排样序列进行求解,提出一种基于集中剩余矩形区域策略的解码方法并将其运用到求解过程中,以提高排样的板材利用率。经实验结果分析,所提出的排样方法在寻优能力和求解的稳定性方面均有较明显的提高,可获得较高的板材利用率,适于在生产实践中应用。     

基于遗传算法的不规则件优化排样研究

提出了一种基于遗传算法的不规则件优化排样的求解方法,通过剩余矩形匹配算法实现解码和局部寻优,并结合正交靠接算法实现自动排样。实例证明,该方法是有效的。     

多值图像的直接NAM表示模型

尽管基于分层数据结构的图像表示有许多优点,但是它们过于强调分割的对称性,因此不是最优的表示方法.借助于布局问题的思想,提出一个基于非对称逆布局模型(NAM)的模式表示方法.通过描述NAM模型,给出多值图像直接NAM表示方法的编码和解码算法,并对算法的复杂性和存储的数据量进行了分析.理论分析和实验结果均表明:与传统的四元树和行程码等图像表示方法相比,直接NAM表示方法在图像数据压缩和重建质量等方面具有明显的优势,是多值图像模式表示的一种良好方法.     

基于两阶段排放算法的矩形件排样优化方法

针对矩形件排样问题,经典的最下左填充(BLF)算法易于出现区域浪费、原材料利用率低的缺点。对此,提出一种改进的两阶段排放算法。第一阶段利用BLF算法,第二阶段设计一个改进BLF排放算法以减小区域的浪费。再以矩形件排放顺序进行编码,利用两阶段排放算法解码,设计邻域搜索算法寻找最优解。通过已有文献的多个案例,对改进的算法进行实验验证,结果与BLF算法相比,原材料利用率能提高14%,证实了改进算法的有效性。     

矩形件优化排样问题的混合遗传算法求解

利用遗传算法结合剩余矩形排样法求解矩形件正交排样问题。通过遗传算法将矩形件正交排样问题转化为一个排列问题,并引入剩余矩形排样算法来惟一确定每一个排列所对应的排样图(即排样方案),两者结合用于求解矩形件排样问题。最后用此混合遗传算法对文献[1]中的两个算例进行了验证,表明了其有效性。     

The improved adaptive link adjustment evolutionary algorithm for the multiple container packing problem

In this paper, we propose a new version of Adaptive Link Adjustment Evolutionary Algorithm (ALA-EA) for the network optimization problems, and apply it to the multiple container packing problem (MCPP). Because the proposed algorithm uses a different encoding method from that of the original ALA-EA, we also need different decoding methods for the new algorithm. In addition, to improve the performance of the proposed algorithm, we incorporate heuristic local improvement approaches into it. To verify the effectiveness of the proposed algorithm we compare it with the existing evolutionary approaches for several instances, which are known to be extremely difficult to them. Computational tests show that the algorithm is superior to the existing evolutionary approaches and the original ALA-EA in both of the solution quality and the computational time. Moreover, the performance seems to be not affected by an instance property.     

An iterative merging algorithm for soft rectangle packing and its extension for application of fixed-outline floorplanning of soft modules

We address an important variant of the rectangle packing problem, the soft rectangle packing problem, and explore its problem extension for the fixed-outline floorplanning with soft modules. For the soft rectangle packing problem with zero deadspace, we present an iterative merging packing algorithm that merges all the rectangles into a final composite rectangle in a bottom-up order by iteratively merging two rectangles with the least areas into a composite rectangle, and then shapes and places each pair of sibling rectangles based on the dimensions and position of their composite rectangle in an up-bottom order. We prove that the proposed algorithm can guarantee feasible layout under some conditions, which are weaker as compared with a well-known zero-dead-space packing algorithm. We then provide a deadspace distribution strategy, which can systematically assign deadspace to modules, to extend the iterative merging packing algorithm to deal with soft packing problem with deadspace. For the fixed-outline floorplanning with soft modules problem, we propose an iterative merging packing based hierarchical partitioning algorithm, which adopts a general hierarchical partitioning framework as proposed in the popular PATOMA floorplanner. The framework uses a recursive bipartitioning method to partition the original problem into a set of subproblems, where each subproblem is a soft rectangle packing problem and how to solve the subproblem plays a key role in the final efficiency of the floorplanner. Different from the PATOMA that adopts the zero-dead-space packing algorithm, we adopt our proposed iterative merging packing algorithm for the subproblems. Experiments on the IBM-HB benchmarks show that the proposed packing algorithm is more effective than the zero-dead-space packing algorithm, and experiments on the GSRC benchmarks show that our floorplanning algorithm outperforms three state-of-the-art floorplanners PATOMA, DeFer and UFO, reducing wirelength by 0.2%, 4.0% and 2.3%, respectively.