基于遗传模拟退火算法的矩形件优化排样 被引量：24

1

作者 杨卫波 王万良 +1 位作者 张景玲 赵燕伟 《计算机工程与应用》 CSCD 北大核心 2016年第7期259-263,共5页

为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,... 为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。 展开更多

关键词 矩形件排样 启发式布局算法 临界多边形 模拟退火算法 自适应遗传算法

下载PDF 职称材料

求解矩形packing问题的贪心算法 被引量：15

2

作者 陈端兵 黄文奇 《计算机工程》 CAS CSCD 北大核心 2007年第4期160-162,共3页

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

关键词 矩形packing 贪心算法 占角动作

下载PDF 职称材料

基于改进最低水平线方法与遗传算法的矩形件排样优化算法 被引量：17

3

作者 刘海明 周炯 +1 位作者 吴忻生 罗家祥 《图学学报》 CSCD 北大核心 2015年第4期526-531,共6页

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理,提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采... 传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理,提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算法能够有效改善排样效果,提高材料利用率。 展开更多

关键词 矩形件排样 优化算法 最低水平线 遗传算法

下载PDF 职称材料

一种“一刀切”式矩形件优化排样混合算法 被引量：15

4

作者 陈仕军 曹炬 《锻压技术》 CAS CSCD 北大核心 2009年第4期143-147,共5页

对"一刀切"矩形件排样问题,提出一种将启发式递归与免疫克隆算法相结合的混合优化方法。首先,提出一种启发式递归算法,利用该算法逐次生成利用率最高的条料,直到所有矩形件均生成条料;然后利用免疫克隆算法全局搜索能力强的特... 对"一刀切"矩形件排样问题,提出一种将启发式递归与免疫克隆算法相结合的混合优化方法。首先,提出一种启发式递归算法,利用该算法逐次生成利用率最高的条料,直到所有矩形件均生成条料;然后利用免疫克隆算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少,即使总的板材利用率达到了最大。对两个典型算例进行计算,并与相关文献比较,表明了算法的有效性。 展开更多

关键词 矩形件排样 启发式递归算法 免疫克隆算法

下载PDF 职称材料

一种针对绝缘纸板排样的混合算法 被引量：12

5

作者 邓应波 祝胜兰 饶运清 《机械设计与制造》 北大核心 2013年第3期23-25,共3页

绝缘纸板排样属于"一刀切"的二维矩形排样问题,是一个NP难问题,在造纸、变压器制造等领域有着广泛的应用。提出了一种改进的剩余矩形填充算法和遗传算法相结合的混合算法,建立绝缘纸板排样的数学模型,在满足"一刀切"... 绝缘纸板排样属于"一刀切"的二维矩形排样问题,是一个NP难问题,在造纸、变压器制造等领域有着广泛的应用。提出了一种改进的剩余矩形填充算法和遗传算法相结合的混合算法,建立绝缘纸板排样的数学模型,在满足"一刀切"工艺的同时,能使同种类零件尽量排放在一起,方便加工。算法解决了多种类零件、多种类板材排样的组合优化问题,并结合工厂下料实例,得到了更优的排样方案,大大提高板材利用率。最后总结并分析了二维排样问题的前景。 展开更多

关键词 矩形排样 一刀切 改进的剩余矩形填充算法 遗传算法

下载PDF 职称材料

改进的双种群遗传算法在矩形件排样中的应用 被引量：10

6

作者 孙佳正 郭骏 《计算机工程与应用》 CSCD 北大核心 2018年第15期139-146,共8页

在矩形件排样问题中,按照面积大小的顺序排放通常比随机排放效果要好,因此在遗传算法的随机初始的种群中加入部分按照面积大小排序的个体以达到加速收敛的目的。然而在同一个种群中,这部分个体适应度高,迭代前期快速扩散,使得种群多样... 在矩形件排样问题中,按照面积大小的顺序排放通常比随机排放效果要好,因此在遗传算法的随机初始的种群中加入部分按照面积大小排序的个体以达到加速收敛的目的。然而在同一个种群中,这部分个体适应度高,迭代前期快速扩散,使得种群多样性降低,导致遗传算法过早熟。针对此缺陷把随机个体作为一个种群,按照面积大小排序的个体作为另一个种群并采用特定的交叉方式保证此种群子代个体大体上按面积大小排序局部乱序。此外,针对最低水平线搜索算法搜索频率低的缺陷,增多了搜索的发生时机,实现更频繁的调整排序提高遗传算法局部搜索能力。实验结果表明了改进后算法的有效性。 展开更多

关键词 矩形件排样 优化算法 遗传算法 最低水平线 双种群

下载PDF 职称材料

基于并行遗传算法的矩形件排样优化 被引量：9

7

作者 隗平平 刘斌 《组合机床与自动化加工技术》 北大核心 2011年第3期78-82,共5页

利用遗传算法对待排零件进行编码,将矩形件正交排样问题转化为排列问题。然后采用一种新的解码排样算法——基于最低水平线的改进算法,将每一个体编码转化为排样图,进行适应度评价,以驱动遗传进化,最终寻找出最优排样图。对遗传算法进... 利用遗传算法对待排零件进行编码,将矩形件正交排样问题转化为排列问题。然后采用一种新的解码排样算法——基于最低水平线的改进算法,将每一个体编码转化为排样图,进行适应度评价,以驱动遗传进化,最终寻找出最优排样图。对遗传算法进行了并行性改进,较好地维持了种群的多样性,增强了算法的搜索效率。对文献中的两个算例进行了求解,结果表明该算法是有效的。 展开更多

关键词 矩形件 排样优化 并行遗传算法

下载PDF 职称材料

基于遗传模拟退火混合算法的矩形包络求解 被引量：9

8

作者 薛迎春 须文波 孙俊 《计算机工程与设计》 CSCD 北大核心 2007年第22期5457-5460,共4页

介绍了一种利用遗传模拟退火混合算法求解矩形包络的方法,该算法在优化搜索中能自适应地控制变异率,使得优化高效地逼近全局最优。矩形包络是将不规则多边形用它们的最小外接矩形来代替,就是求解该多边形的最佳包络矩形。实验结果表明,... 介绍了一种利用遗传模拟退火混合算法求解矩形包络的方法,该算法在优化搜索中能自适应地控制变异率,使得优化高效地逼近全局最优。矩形包络是将不规则多边形用它们的最小外接矩形来代替,就是求解该多边形的最佳包络矩形。实验结果表明,在解决矩形包络问题中,遗传模拟退火混合算法是一种高效的、可靠的优化算法,具有一定的实用价值。 展开更多

关键词 矩形包络 几何计算 二维几何 遗传算法 模拟退火 量子行为粒子群算法

下载PDF 职称材料

矩形件和任意多边形排样问题的算法及应用 被引量：6

9

作者 李满江 孟祥旭 王志强 《贵州工业大学学报（自然科学版）》 CAS 2002年第4期126-130,141,共6页

探讨了矩形件和任意形状图案的排样优化问题的遗传算法求解 ,提出了剩余矩形表示法和条形图表示法。对于矩形排样 ,剩余矩形表示法提高了板材利用率 ,更容易得到较优解。对于任意形状图案排样 ,条形图表示法直接利用位图排样 ,不对图案... 探讨了矩形件和任意形状图案的排样优化问题的遗传算法求解 ,提出了剩余矩形表示法和条形图表示法。对于矩形排样 ,剩余矩形表示法提高了板材利用率 ,更容易得到较优解。对于任意形状图案排样 ,条形图表示法直接利用位图排样 ,不对图案作任何限制 (允许有孔洞 ) ,排样速度很快。该算法已应用于智能印花分色系统中。 展开更多

关键词 任意多边形 矩形件 排样 遗传算法 排样优化 剩余矩形表示法 条形图表示法 智能印花分色系统

下载PDF 职称材料

矩形件优化排样的混合启发式方法 被引量：8

10

作者 许继影 《计算机工程与应用》 CSCD 2012年第13期234-239,共6页

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对... 提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。 展开更多

关键词 矩形件排样 启发式递归算法 遗传算法

下载PDF 职称材料

基于两阶段排放算法的矩形件排样优化方法 被引量：5

11

作者 许继影 陈仕军 郑晴 《计算机时代》 2020年第5期13-15,19,共4页

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

关键词 矩形排样 排放算法 两阶段 邻域搜索

下载PDF 职称材料

基于改进蚁群算法和剩余矩形法的二维矩形件优化排样 被引量：4

12

作者 郭蕴华 许昆仑 +1 位作者 常万里 牟军敏 《武汉理工大学学报》 CAS 北大核心 2018年第2期95-100,共6页

二维矩形件优化排样是一类具有NP完全难度的组合优化问题。提出了一种基于改进蚁群算法和剩余矩形法的新型混合算法对其进行求解。通过针对最优个体的变异策略和具有随机选择机制的路径选择规则,提高了算法的全局寻优能力。在每一代的... 二维矩形件优化排样是一类具有NP完全难度的组合优化问题。提出了一种基于改进蚁群算法和剩余矩形法的新型混合算法对其进行求解。通过针对最优个体的变异策略和具有随机选择机制的路径选择规则,提高了算法的全局寻优能力。在每一代的寻优过程中采用剩余矩形法完成矩形件排样,以改善算法的局部寻优能力。将该文算法与已有算法通过两个仿真实例进行了对比分析,仿真结果表明该算法具有明显的优势。 展开更多

关键词 矩形件排样 蚁群算法 剩余矩形算法

原文传递

矩形件优化排样算法研究 被引量：5

13

作者 郭文文 计明军 邓文浩 《现代制造工程》 CSCD 北大核心 2020年第6期86-93,共8页

矩形件排样的合理性直接影响着板材的利用率。考虑到板材下料中纤维方向和一刀切等工艺约束,结合实际作业中切割机器的刀缝限制,建立了板材原料利用率最大的矩形件优化排样模型,同时设计了不同切割方式下的规则算法进行求解。算例结果表... 矩形件排样的合理性直接影响着板材的利用率。考虑到板材下料中纤维方向和一刀切等工艺约束,结合实际作业中切割机器的刀缝限制,建立了板材原料利用率最大的矩形件优化排样模型,同时设计了不同切割方式下的规则算法进行求解。算例结果表明,不同切割方式下的规则算法能够得到板材利用率不同的矩形件排样图,且都能较快地得到最优解,为实际作业提供决策支持。 展开更多

关键词 矩形件排样 工艺约束 切割方式 规则算法

下载PDF 职称材料

基于自适应遗传算法和多条带策略的排样方法研究 被引量：5

14

作者 许华杰 檀洪森 胡小明 《计算机科学》 CSCD 北大核心 2016年第4期274-278,317,共6页

针对现代工业工艺生产中普遍存在的矩形件排样优化问题,在遗传算法的主要环节应用性能较优的算子对矩形件排样序列进行了求解,并运用交叉概率和变异概率能自适应调整的方法来提高遗传算法的收敛速度及稳定性。提出了满足工艺生产切割要... 针对现代工业工艺生产中普遍存在的矩形件排样优化问题,在遗传算法的主要环节应用性能较优的算子对矩形件排样序列进行了求解,并运用交叉概率和变异概率能自适应调整的方法来提高遗传算法的收敛速度及稳定性。提出了满足工艺生产切割要求的多条带策略,辅以最低水平线算法的择优插入策略对矩形件序列进行解码。实验结果表明,与分层策略相比,所提出的排样方法不仅能得到更高、更稳定的板材利用率,而且还能提高工艺生产的效率并降低生产的时间成本,具有重要的现实意义。 展开更多

关键词 自适应遗传算法 矩形件排样 多条带策略 最低水平线算法 板材利用率

下载PDF 职称材料

面向利用率的矩形排样分级进化遗传算法优化 被引量：4

15

作者 冯建云 刘祎 《机械设计与制造》 北大核心 2022年第11期11-16,共6页

为了提高矩形排样的板材使用率,提出了基于分级进化遗传算法的排样优化方法。以板材利用率最高为目标建立了矩形排样的目标模型,将排样问题分为定位和排序两个步骤实现。在定位方面,将最低水平线法和填充算法进行优势融合,得到了混合定... 为了提高矩形排样的板材使用率,提出了基于分级进化遗传算法的排样优化方法。以板材利用率最高为目标建立了矩形排样的目标模型,将排样问题分为定位和排序两个步骤实现。在定位方面,将最低水平线法和填充算法进行优势融合,得到了混合定位方法。在排序方面,以遗传算法为基础,将染色体分为保留层级、交叉层级和变异层级等3个层级,每个层级制定相适应的进化操作方法,从而提高算法的搜索能力和收敛速度。使用文献[13]和文献[14]中的两组实验数据进行验证,结果表明这里提供的排样方案可以得到最佳的排样结果,且排样耗时最少。验证了这里分级进化遗传算法排样方法的有效性和高效性。 展开更多

关键词 矩形件排样 分级进化遗传算法 混合定位方法 板材利用率

下载PDF 职称材料

基于蚁群算法的矩形件优化排样问题 被引量：4

16

作者 冯琳 史俊友 《青岛科技大学学报（自然科学版）》 CAS 2011年第1期90-94,共5页

由于蚁群算法具有正反馈并行自催化机制和较强的鲁棒性等优点,逐渐成为一种应用广泛的元启发式算法。针对矩形毛坯在定宽无限长的板材上排样这个NP难问题,提出采用蚁群算法进行求解。采用1种2步法:第1步利用蚁群算法寻找最优底部毛坯排... 由于蚁群算法具有正反馈并行自催化机制和较强的鲁棒性等优点,逐渐成为一种应用广泛的元启发式算法。针对矩形毛坯在定宽无限长的板材上排样这个NP难问题,提出采用蚁群算法进行求解。采用1种2步法:第1步利用蚁群算法寻找最优底部毛坯排放顺序得到条形料排放顺序,第2步采用一种宽度方向最大填充排放算法来排放每个条形料。并将得到的结果与以往算法的结果进行比较,进一步验证了蚁群算法的优越性及处理矩形件排样问题的有效性。 展开更多

关键词 蚁群算法 矩形件排样 剪切下料 条形料排样

下载PDF 职称材料

基于模拟退火剩余矩形算法的矩形件排样 被引量：3

17

作者 全雪峰 沈继涛 《软件》 2016年第3期27-29,共3页

针对矩形件优化排样问题,讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型,然后给出了模拟退火剩余矩形算法求解问题的步骤和方法,最后用实例进行了算法验证。实例分析表明,采用模拟退火剩余矩形算法... 针对矩形件优化排样问题,讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型,然后给出了模拟退火剩余矩形算法求解问题的步骤和方法,最后用实例进行了算法验证。实例分析表明,采用模拟退火剩余矩形算法求解矩形件排样问题是适合的。 展开更多

关键词 矩形件 排样 模拟退火算法 剩余矩形法

下载PDF 职称材料

结合批量问题的多目标矩形件优化排样 被引量：4

18

作者 郑明月 刘林 +1 位作者 阚方 方昶 《计算机工程与应用》 CSCD 2014年第22期260-264,共5页

设计多目标启发式进化算法,研究了一种考虑批量问题的二维矩形件排样问题,建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式,再用改进的快速非支配排序算法进行优化求解,确定下料方案。... 设计多目标启发式进化算法,研究了一种考虑批量问题的二维矩形件排样问题,建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式,再用改进的快速非支配排序算法进行优化求解,确定下料方案。通过实验结果以及与其他算法的对比表明,在中等规模的矩形件排样问题中,该算法能够在较快的时间内既保证较高的原料利用率,又能降低该问题的总成本,证明了该算法的有效性。 展开更多

关键词 矩形件排样 批量问题 多目标优化 启发式 进化算法

下载PDF 职称材料

定序列矩形件优化排样的二维搜索算法 被引量：3

19

作者 杨传华 吴锦文 +3 位作者 李亚芹 郭士清 康金波 姜东华 《佳木斯大学学报（自然科学版）》 CAS 2010年第3期354-356,359,共4页

为了提高矩形件排样时材料的利用率,针对定序列矩形件优化排样问题,本文在"基于最低水平线的搜索算法"的基础上,提出了一种改进的矩形件优化排样算法——基于最低水平线的二维搜索算法.此改进算法在"基于最低水平线的搜... 为了提高矩形件排样时材料的利用率,针对定序列矩形件优化排样问题,本文在"基于最低水平线的搜索算法"的基础上,提出了一种改进的矩形件优化排样算法——基于最低水平线的二维搜索算法.此改进算法在"基于最低水平线的搜索算法"基础上,进行了排样宽度的二维搜索,并将该改进算法与其他算法进行实例排样比较,排样结果表明,改进后的排样算法能有效地利用排样时产生的空白区域,在提高材料利用率上具有可行性和有效性. 展开更多

关键词 矩形排样 最低水平线算法 优化排样 二维搜索

下载PDF 职称材料

利用可行域的矩形布局求解方法 被引量：3

20

作者 张鹏程 郗艳梅 +1 位作者 李国顺 茹江燕 《现代制造工程》 CSCD 北大核心 2010年第3期90-93,共4页

针对矩形布局求解问题,研究和分析矩形在布局空间中的可行域,提出一种以矩形可行域为依据的布局求解方法,其内容包括矩形可行域的确定、布局空间的分割和确定以及布局子空间的选择等算法。算例表明,该方法可以获得良好的布局方案,是一... 针对矩形布局求解问题,研究和分析矩形在布局空间中的可行域,提出一种以矩形可行域为依据的布局求解方法,其内容包括矩形可行域的确定、布局空间的分割和确定以及布局子空间的选择等算法。算例表明,该方法可以获得良好的布局方案,是一种行之有效的布局求解方法,具有广泛的实用性。 展开更多

关键词 矩形布局 可行域 布局空间 定位函数

下载PDF 职称材料