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

1

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

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

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

下载PDF 职称材料

基于轨迹计算的临界多边形求解算法 被引量：13

2

作者 刘胡瑶 何援军 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2006年第8期1123-1129,共7页

将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题.该算法的基本原理是:1)求解多边形顶点相对于另一多边形的轨迹线;2)求解轨迹线集合所形成的外包多边形... 将多边形滑动碰撞问题转化为顶点和边之间的轨迹线提取问题,从而降低了时间复杂度,并可统一处理边界空腔和内部靠接临界多边形问题.该算法的基本原理是:1)求解多边形顶点相对于另一多边形的轨迹线;2)求解轨迹线集合所形成的外包多边形和内部顺时针环,得到的多边形即为临界多边形.该算法采用基于网格的线段索引方法来加快线段之间的求交计算,进一步提高了临界多边形求解的计算速度. 展开更多

关键词 临界多边形 轨迹线 线段索引 排样

下载PDF 职称材料

基于临界多边形的不规则件启发式排样算法 被引量：16

3

作者 汤德佑 周子琳 《计算机应用》 CSCD 北大核心 2016年第9期2540-2544,共5页

为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP(GNFP)相结合的... 为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP(GNFP)相结合的排放策略以减少排样过程中可能产生的空隙面积;其次,给出了基于WeilerAtherton多边形裁剪算法的剩余原材料求解方法,重用排样过程中产生的孔洞,减少孔洞面积;最后,给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA,给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明,GEFHNA的耗时约为基于智能算法的排样方法的千分之一,同时在与两款商业软件Nest Lib和Sigma Nest的11个基准测试的对比中,GEFHNA获得了7/11个相对最优的排样面积利用率。 展开更多

关键词 二维不规则件 排样 临界多边形 启发式方法

下载PDF 职称材料

基于重心NFP的二维不规则形状排样算法 被引量：12

4

作者 刘胡瑶 何援军 《中国机械工程》 EI CAS CSCD 北大核心 2007年第6期723-726,731,共5页

提出了一种基于重心NFP的二维不规则多边形排样算法,算法主要包括临界多边形计算和排样定位选优等内容。该算法以多边形来表示板材和待排零件,通过求解临界多边形NFP来得到多边形之间的所有靠接(排放)位置。为了在NFP中进一步得到优化... 提出了一种基于重心NFP的二维不规则多边形排样算法,算法主要包括临界多边形计算和排样定位选优等内容。该算法以多边形来表示板材和待排零件,通过求解临界多边形NFP来得到多边形之间的所有靠接(排放)位置。为了在NFP中进一步得到优化的靠接位置,在NFP的基础上提出了重心NFP的概念,通过选择重心NFP中的最低重心位置来确定零件的排放位置。在零件的排样次序算法上,提出了顺序递归排样算法和遗传算法,以降低排样过程中形成的空腔所造成的浪费。该算法可处理板材和零件均为不规则形状的排样问题,允许零件在全角度范围内进行旋转,并可处理板材内部带孔洞或者边界形成空腔等特殊情况。 展开更多

关键词 不规则排样 临界多边形 重心NFP 递归排样 遗传算法

下载PDF 职称材料

用于二维不规则排样的离散临界多边形模型 被引量：11

5

作者 张德富 陈竞驰 +1 位作者 刘永凯 陈火旺 《软件学报》 EI CSCD 北大核心 2009年第6期1511-1520,共10页

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.... 提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的. 展开更多

关键词 不规则排样问题 禁止区 临界多边形 离散临界多边形

下载PDF 职称材料

改进临界多边形生成算法 被引量：8

6

作者 杨卫波 王万良 《计算机工程与应用》 CSCD 2013年第1期32-35,共4页

在Burke等人提出的用于求解临界多边形的移动碰撞算法基础之上,提出了一种更加高效的求取NFP的改进算法。该算法大大降低了问题的几何复杂性,简化了计算最小移动距离的方法,使许多启发式策略可以更加容易地与该算法结合来求解二维排样... 在Burke等人提出的用于求解临界多边形的移动碰撞算法基础之上,提出了一种更加高效的求取NFP的改进算法。该算法大大降低了问题的几何复杂性,简化了计算最小移动距离的方法,使许多启发式策略可以更加容易地与该算法结合来求解二维排样问题。实例验证了改进算法是有效且可行的,已应用于皮革自动排样软件中。 展开更多

关键词 临界多边形 不规则形状 排样 移动碰撞法

下载PDF 职称材料

应用临界多边形方法与小生境遗传算法求解不规则排样问题 被引量：8

7

作者 刘海明 周炯 吴忻生 《小型微型计算机系统》 CSCD 北大核心 2016年第5期1002-1007,共6页

针对现代制造业中广泛存在的不规则排样问题进行了研究,提出一种基于临界多边形排样策略和小生境遗传算法的排样优化算法.算法通过改进的移动碰撞法计算零件之间的临界多边形,以确定最佳的零件靠接排放位置;通过基于小生境策略的遗传算... 针对现代制造业中广泛存在的不规则排样问题进行了研究,提出一种基于临界多边形排样策略和小生境遗传算法的排样优化算法.算法通过改进的移动碰撞法计算零件之间的临界多边形,以确定最佳的零件靠接排放位置;通过基于小生境策略的遗传算法优化零件的排样顺序,确定最佳排样序列.对所提出的排样优化算法作了实验测试和算法评估,验证算法的可行性与有效性.排样实验结果表明,该算法能够用于求解不规则排样问题,且在一定程度上优于已有算法,能够提高材料利用率. 展开更多

关键词 不规则排样 临界多边形 遗传算法 小生境策略

下载PDF 职称材料

基于实数编码量子进化算法的不规则多边形排样 被引量：7

8

作者 杨卫波 王铮 +1 位作者 王万良 张景玲 《计算机集成制造系统》 EI CSCD 北大核心 2016年第5期1235-1243,共9页

为探索更高效的二维不规则多边形排样方法,提出一种改进的实数编码量子进化算法。设计了基于临界多边形的按照排样件最低形心位置进行布局的放置策略,并建立了以最大化材料利用率为优化目标的数学模型;设计了基于排样编号序列和旋转角... 为探索更高效的二维不规则多边形排样方法,提出一种改进的实数编码量子进化算法。设计了基于临界多边形的按照排样件最低形心位置进行布局的放置策略,并建立了以最大化材料利用率为优化目标的数学模型;设计了基于排样编号序列和旋转角索引序列的实数几率幅值编码方法及解生成方式,通过量子观测操作直接生成问题解,使其解码效率较高;算法通过自适应调节方式进行量子更新,采用启发式算法生成排样序列初始种群,以保证解在时间和质量上的可行性。通过基准算例仿真和算法对比实验,验证了所提算法的可行性和有效性。 展开更多

关键词 不规则排样问题 临界多边形 启发式算法 实数编码 量子进化算法

下载PDF 职称材料

基于改进免疫遗传算法的汽车零件排样 被引量：3

9

作者 闫嘉 李林峰 +1 位作者 林毓培 段书凯 《西南大学学报（自然科学版）》 CAS CSCD 北大核心 2023年第5期204-214,共11页

为提高汽车零件排样的板材利用率,对汽车零件的排样技术进行研究.汽车零件大多是不规则零件,因此其排样属于二维不规则排样问题范畴.在智能优化算法求解二维不规则排样领域,遗传算法容易产生早熟现象,并且局部寻优能力较差,而免疫算法... 为提高汽车零件排样的板材利用率,对汽车零件的排样技术进行研究.汽车零件大多是不规则零件,因此其排样属于二维不规则排样问题范畴.在智能优化算法求解二维不规则排样领域,遗传算法容易产生早熟现象,并且局部寻优能力较差,而免疫算法具有很强的局部寻优能力.结合遗传算法与免疫算法的全局与局部寻优能力,提出一种改进的免疫遗传算法.该算法的遗传选择操作加入个体浓度计算,操作步骤和变异概率可以自适应调整,从而有效避免早熟现象.自适应计算免疫选择个体数以及免疫克隆个体数以提高算法的收敛性能.分别使用ESICUP网站提供的公开数据和实际汽车零件专用数据对提出的免疫遗传算法的性能进行测试,实验结果表明,和现有的几种算法相比,本研究提出的免疫遗传算法能获得更高的材料利用率. 展开更多

关键词 二维不规则排样 临界多边形 汽车零件 智能优化算法

下载PDF 职称材料

临界多边形生成算法的改进 被引量：4

10

作者 刘嘉敏 佟德刚 黄有群 《沈阳工业大学学报》 EI CAS 2005年第5期567-570,共4页

二维不规则形状零件排样是将给定的若干不规则形状零件合理、较优地排放在给定的材料中,使得材料利用率最大.求解一个多边形相对于另一个多边形的临界多边形,是不规则形状零件自动排样算法中的关键技术,而且需要反复调用.探讨了斜率法... 二维不规则形状零件排样是将给定的若干不规则形状零件合理、较优地排放在给定的材料中,使得材料利用率最大.求解一个多边形相对于另一个多边形的临界多边形,是不规则形状零件自动排样算法中的关键技术,而且需要反复调用.探讨了斜率法求解临界多边形的优点,分析了该方法在任意两个多边形有多边重叠的情形时出现错误的原因,给出了对斜率法的改进方法,通过实例验证,该方法是有效可行的. 展开更多

关键词 临界多边形 排样 不规则形状 多边形 斜率法

下载PDF 职称材料

二维不规则图形排料CAD系统的设计 被引量：5

11

作者 顾振华 何援军 刘胡瑶 《工程图学学报》 CSCD 北大核心 2008年第2期17-22,共6页

采用轨迹线算法、自适应最低重心规则和遗传算法,解决了不规则图形的计算机辅助排料问题。提出采用轨迹线求解临界多边形实现快速的多边形靠接,根据自适应最低重心NFP的排样放置原则,配合改进后快速收敛的遗传算法,设计了一套自动并支... 采用轨迹线算法、自适应最低重心规则和遗传算法,解决了不规则图形的计算机辅助排料问题。提出采用轨迹线求解临界多边形实现快速的多边形靠接,根据自适应最低重心NFP的排样放置原则,配合改进后快速收敛的遗传算法,设计了一套自动并支持实时交互的排料CAD系统,给出了排料结果和对比,取得了良好的排料结果和应用。系统还提供零件及板材库的管理功能。 展开更多

关键词 计算机应用 排料CAD 临界多边形 轨迹线 遗传算法

下载PDF 职称材料

基于轨迹线改进的临界多边形算法

12

作者 韩志仁 韩子默 贾震 《航空制造技术》 CSCD 北大核心 2024年第9期83-88,共6页

在异形件的下料排样问题中,最为困难的就是求解裁片在板料中的位置以保证材料较高的利用率,算法复杂度随着料片数量和料片轮廓复杂度的增加迅速上升。临界多边形算法是计算异形件之间靠接位置和重叠关系的一种基础性几何工具,临界多边... 在异形件的下料排样问题中,最为困难的就是求解裁片在板料中的位置以保证材料较高的利用率,算法复杂度随着料片数量和料片轮廓复杂度的增加迅速上升。临界多边形算法是计算异形件之间靠接位置和重叠关系的一种基础性几何工具,临界多边形算法的性能与下料排样算法效率密切相关。本文在基于轨迹线的求解临界多边形算法基础上,提出一种求解临界多边形(NFP)的改进算法。该算法有效地将移动碰撞算法和轨迹线算法相结合,充分发挥两类算法各自的优点,提高了临界多边形求解的计算速度。仿真实例验证了改进方法的正确性和有效性。 展开更多

关键词 临界多边形 轨迹线 排样 移动碰撞法 不规则形状

下载PDF 职称材料

基于改进遗传禁忌搜索算法的二维不规则件排样优化

13

作者 梁金龙 毛文志 +1 位作者 栾显晔 徐金亭 《锻压技术》 CAS CSCD 北大核心 2024年第4期54-61,89,共9页

针对二维不规则钣金件排样问题,提出一种融合临界多边形(NFP)定位和改进遗传禁忌搜索算法的排样优化方法。首先,根据零件的几何特征对其进行分类编码,求解零件类间的NFP,避免NFP的重复计算,同时引入以排样高度最小化为目标的启发式规则... 针对二维不规则钣金件排样问题,提出一种融合临界多边形(NFP)定位和改进遗传禁忌搜索算法的排样优化方法。首先,根据零件的几何特征对其进行分类编码,求解零件类间的NFP,避免NFP的重复计算,同时引入以排样高度最小化为目标的启发式规则,给出零件定位策略的综合评价函数,以提高板材利用率。其次,在零件排序优化时,将遗传算法中的精英群体作为禁忌搜索算法的高质量初始解,减少计算资源消耗。最后,利用欧洲切割和包装特别兴趣小组ESICUP提供的标准算例对所提排样方法进行测试。结果表明:相比传统遗传禁忌搜索算法,所提排样方法的计算效率提升了28.32%~80.23%,并且在与两种现有算法的7个基准测试对比中,所提排样方法均取得了最优排样结果。 展开更多

关键词 二维不规则件 临界多边形 启发式规则 精英策略 遗传禁忌搜索算法

原文传递

求解带性能约束凸多边形布局的混合算法 被引量：5

14

作者 黄振东 肖人彬 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2014年第3期47-51,共5页

针对带性能约束的凸多边形布局问题,设计了一种波纹探测启发式定位算法(REHA),并将其与广义模拟退火算法(GSA)相结合,形成混合算法.波纹探测启发式算法模拟波纹的现象,以圆形容器的圆心为中心,构造同心圆,逐步增大同心圆半径向外探测,... 针对带性能约束的凸多边形布局问题,设计了一种波纹探测启发式定位算法(REHA),并将其与广义模拟退火算法(GSA)相结合,形成混合算法.波纹探测启发式算法模拟波纹的现象,以圆形容器的圆心为中心,构造同心圆,逐步增大同心圆半径向外探测,根据同心圆与质心临界多边形的交来确定布局物的放置位置.该算法同时兼顾布局问题的紧凑性和静平衡约束,是一种定位启发式方法,其解的质量受布局顺序的影响.利用广义模拟退火算法优化布局顺序,形成混合算法,并将其与经典的模拟退火算法作分析对比,数值试验验证了提出算法的有效性. 展开更多

关键词 约束布局问题 凸多边形 临界多边形 启发式方法 广义模拟退火算法

原文传递

一种基于Ghosh斜率图法的改进的临界多边形生成算法 被引量：2

15

作者 吴忻生 唐萍 袁鹏 《计算机应用研究》 CSCD 北大核心 2011年第3期1176-1179,共4页

在Ghosh的斜率图法(slope diagram)基础之上,对凹—凹这种情况进行了重点研究分析,提出了一种更加高效的求取NFP的改进算法。新的改进算法改进了边的遍历方式,简化了NFPList的构成,提高了求取外层NFP轮廓的效率。仿真实例验证了所提方... 在Ghosh的斜率图法(slope diagram)基础之上,对凹—凹这种情况进行了重点研究分析,提出了一种更加高效的求取NFP的改进算法。新的改进算法改进了边的遍历方式,简化了NFPList的构成,提高了求取外层NFP轮廓的效率。仿真实例验证了所提方法的正确性和有效性。 展开更多

关键词 临界多边形 排样 斜率图 临界多边形序列 分段 凹—凹多边形情况

下载PDF 职称材料

超边界约束条件下异形件排样问题的求解算法研究 被引量：1

16

作者 饶运清 彭灯 +2 位作者 杜冰 罗强 林信海 《计算机集成制造系统》 EI CSCD 北大核心 2023年第12期4063-4072,共10页

针对超边界约束条件,提出了板材动态边界搜索的处理策略,然后以临界多边形(NFP)为基础,同时引入无碰撞区域(CFR)的概念,以保证排样方案的可行性,在综合考虑零件之间的重合率和BL(bottom left)策略,以及CFR可能退化为点或线段的情况之后... 针对超边界约束条件,提出了板材动态边界搜索的处理策略,然后以临界多边形(NFP)为基础,同时引入无碰撞区域(CFR)的概念,以保证排样方案的可行性,在综合考虑零件之间的重合率和BL(bottom left)策略,以及CFR可能退化为点或线段的情况之后,提出基于CFR的混合启发式定位算法。在上述零件定位算法的基础上,采用遗传算法对零件排样顺序进行优化以解决超边界约束排样问题,并通过实例验证了所提算法的有效性。 展开更多

关键词 异形件排样 超边界约束 临界多边形 动态边界搜索

下载PDF 职称材料

不规则多边形优化组合的计算机自动排样 被引量：4

17

作者 王淑侠 廖达雄 王关峰 《航空制造技术》 2007年第7期73-74,91,共3页

针对计算机自动排样过程中图形求交和定位这一关键问题,通过对传统排样算法的分析,研究了不规则多边形优化组合的策略,提出了求凹多边形和凸多边形的临界多边形算法,并给出了最佳包络率的概念用来保证临界多边形算法的实现,从而使最小... 针对计算机自动排样过程中图形求交和定位这一关键问题,通过对传统排样算法的分析,研究了不规则多边形优化组合的策略,提出了求凹多边形和凸多边形的临界多边形算法,并给出了最佳包络率的概念用来保证临界多边形算法的实现,从而使最小包络矩的方法更加有效。 展开更多

关键词 自动排样 定位 临界多边形 最小包 络矩

下载PDF 职称材料

设计知识驱动的不规则多边形排样算法及应用 被引量：1

18

作者 冯毅雄 钟锐锐 +5 位作者 张志峰 黄城 李中凯 胡炳涛 洪兆溪 谭建荣 《计算机集成制造系统》 EI CSCD 北大核心 2023年第2期593-603,共11页

为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位... 为高效解决实际生产制造中的二维不规则多边形排样问题,提出一种设计知识驱动的启发式算法。利用临界多边形判定多边形之间的相对位置,并建立局部适应度数学模型用于衡量多边形的贴合程度;根据设计知识建立数学模型来评价多边形待摆放位置,利用基于局部搜索的贪心算法完成排样。通过对国际通用基准用例进行实验测试并与现有智能优化算法进行对比,证明了所提算法在排样质量与时间性能上不但具有一定优势,而且稳定性高。通过实际生产中样片数据的实验测试证明了所提算法的实用性。 展开更多

关键词 不规则排样问题 临界多边形 知识驱动 启发式算法

下载PDF 职称材料

工艺约束策略下的二维不规则零件排样算法 被引量：4

19

作者 葛志辉 王阳 +1 位作者 潘海鸿 李陶深 《广西大学学报（自然科学版）》 CAS 北大核心 2018年第2期580-588,共9页

针对已有排样算法在实际工业生产情况下缺乏对零件工艺约束等问题,提出一种基于工艺约束策略的二维不规则排样算法(PCTNA)。该算法结合临界多边形算法,通过对零件内含有的空洞进行填充,实现提高被加工板材材料的利用率;再通过引入等距... 针对已有排样算法在实际工业生产情况下缺乏对零件工艺约束等问题,提出一种基于工艺约束策略的二维不规则排样算法(PCTNA)。该算法结合临界多边形算法,通过对零件内含有的空洞进行填充,实现提高被加工板材材料的利用率;再通过引入等距偏移思想,解决实际生产时所需要的零件间的工艺间隙问题。通过对欧洲排样问题兴趣小组提供的测试算例进行实验测试,从12个测试算例的测试结果得到平均时间优化比率为10.33%,平均路径优化比率为11.06%,实验结果显示PCTNA可以降低排样的切割时间和减少路径,提高切割效率。 展开更多

关键词 工艺约束 多边形偏移 二维不规则排样 临界多边形

下载PDF 职称材料

复合材料铺层优化排样的研究 被引量：2

20

作者 邓冬梅 周来水 安鲁陵 《兵器材料科学与工程》 CAS CSCD 北大核心 2007年第6期17-21,共5页

根据复合材料的特点及其构件成形过程,总结复合材料铺层排样的特点,并拟定采用多边形排样算法实现复合材料自动排样的思路。重点研究简单多边形零件靠接时移动方向和移动距离的确定、多个可排放位置的状态评估、零件排放后多边形边界的... 根据复合材料的特点及其构件成形过程,总结复合材料铺层排样的特点,并拟定采用多边形排样算法实现复合材料自动排样的思路。重点研究简单多边形零件靠接时移动方向和移动距离的确定、多个可排放位置的状态评估、零件排放后多边形边界的合成等关键技术。利用模拟退火算法与以上多边形排放技术相结合,实现多边形零件的优化排放。 展开更多

关键词 多边形排样 BL策略 临界多边形 复合材料

下载PDF 职称材料