求解矩形Packing问题的砌墙式启发式算法

为求解正交矩形Packing问题提出了一个新颖而有效的砌墙式启发式算法.该算法主要基于砌墙式启发式策略,其思想主要来源于砖匠在砌墙过程中所积累的经验:基于基准砖的砌墙规则.对国际上公认的大量的Bench-mark问题例的计算结果表明,该算法的计算速度不仅比著名的现代启发式算法快,而且获得更优的高度.

基于动作空间求解二维矩形Packing问题的高效算法

对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。

一种求解矩形packing问题的智能枚举算法

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明:该算法对求解矩形packing问题是行之有效的。

基于矩形Packing问题求解的页面自动排版方法

为了较好地实现页面的自动排版,本文提出了基于矩形Packing问题求解的页面自动排版方法。该方法采用结构化描述语言来分析描述版面的图文内容及排版样式,通过构建页面模型把页面自动排版问题抽象为关于图文混排矩形块的版面布局自动规划问题,根据矩形块面积排序,判断约束信息,定位步骤和回溯步骤,得到最终的页面自动排版效果。通过页面数据排版实验进行测试,实验验证该方法能较好地符合条件要求。

一种求解二维矩形Packing问题的拟人型全局优化算法

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。

一种求解Packing问题概率控制搜索行为的启发式算法

研究一种求解圆形和圆形与矩形混合Packing问题的启发式算法.借鉴Agent概念,赋予待布物具有跳跃、交换、旋转、移动和容器缩放等5种搜索行为,在寻优过程中以概率机制控制上述各搜索行为,并给出寻优过程中启用该搜索行为的时机及其操作顺序,该概率控制机制的适应性控制参数由待布物之间干涉信息决定.该法纯用上述搜索行为寻优,不辅以其他优化方法.该Packing问题数值实验结果表明,算法是可行和有效的.

一种实用的铁制工艺品排料方案的设计与实现

根据铁制工艺品企业的需求,结合前人提出的求解矩形Packing问题的贪心算法和矩形排料的十字线法,本文设计实现了一种实用的铁制工艺品排料方法。实验结果表明,本文所实现的排料方法运行速度较快,具有较强的可用性和实用性。系统已在有关企业投入试用。