设 Gj ( j∈J, J 为零件集合 )为零件 j的图形 , ( X Y ( xj, yj )为该零件的给定点的坐标 , 则该零件在板材上的 定位可以表示为下述过程 :先将该零件以该定点为
轴作角度为
பைடு நூலகம்
α j
的旋转
, 然后再将定点
( xj ,
yj )在板材
作位移 (Δxj,Δyj ) 。这时零件 j在板材上的方位可
为此本文主要探讨采用求取零件最小包络矩形 的方法简化预处理 ,并且对一些形状互补的零件构 造矩形排样单元进行优化组合 ,使零件区域在最小 包络矩形中所占的比例尽可能大 ,对组合后的图形 再求取最小包络矩形 ,同时对多边形的外轮廓与包 络矩形之间产生的空白区域进行填充的预处理方 法 ;并从遗传模拟退火算法优化策略的构造出发 ,融 合小生境技术的思想 ,提出一种基于小生境技术的 遗传模拟退火算法 ( niching genetic simulated annea2 ling algorithm , GSA ) ,通过使用一种新的选择和变异 机制 ,从而提高遗传算法的稳定性和收敛速度 ,并在 此基础上开发了不规则件优化排样系统 。
件姿态时的材料利用率 ,求得材料利用率最高时的
Abstract: Firstly, we fully consider the shapes of irregular parts and convert the two2dim ensional irregular parts packing p roblem into rectangular parts packing p roblem using the com bined rectangle enclosure algorithm. W e overcome the blank area when m inimum enclosed rectangle was simp ly used to rep lace the parts packing, which re2 sults in too low utilization ratio of materials. Secondly, genetic simulated annealing algorithm and niche technique are integrated to search for the best sequence of the packed parts and each part′s angle of rotation. Finally, the lowest horizontal algorithm and filling algorithm are combined to comp lete the automatic layout. Examp les indicate that our algorithm is effective and p ractical. Key words: niche technique; genetic sim ulated annealing algorithm; combined rectangle enclosure algorithm; ir2 regular part; op tim al layout
942
机械科学与技术
第 26卷
降低 。因此充分考虑不规则形状零件自身的形状特
征 ,合理构造矩形排样单元 ,对于提高材料的利用
率 ,具有至关重要的作用 。为此针对在多边形的外
轮廓与矩形包络之间容易产生一些空白块 ,及最小
矩形包络算法效率很低的情况 ,本文对不规则形状
零件的矩形排样单元构造过程中的关键技术提出以
1 小生境遗传模拟退火算法 自然界中“物以类聚 ,人以群分 ”是一种司空见
惯的现象 ,生物总是倾向于与自己特征 、性状相类似 的生物生活在一起 ,一般总是与同类交配繁衍后代 。 在生物学中 ,把某种特定环境及其在此环境中生存 的组织称为小生境 [ 2 ] ,而把有共同特性的一些组织 称作物种 。基本遗传算法是模拟生物界适者生存原 理的技术 ,它在进行种群中个体的交配时采用的是 一种随机方式 ,这虽然增加了对问题解空间的搜索 能力 ,但由于缺乏对可能交配效果方面的考虑 ,也带 来了交配的有效性 、优化效率不太理想 ,以及其容易 产生熟现象 、局部寻优能力较差和随机漫游现象 ,从 而导致算法的收敛性能力较差等多方面的问题 。而 模拟退火算法则通过赋予搜索过程一种时变且最终 趋于零的概率突跳性 ,从而可有效避免陷入局部极 小并最终趋于全局最优 ,但模拟退火算法为寻找到 最优解需要合理选择冷却进度表 ,算法通常要求较 高的初温 、较慢的降温速率 、较低的终止温度以及各 温度下足够多次的抽样 ,因而 SA 算法往往优化过 程较长 。为解决这些问题 ,将基本遗传算法和模拟 退火算法相融合构成混合优化策略再引入小生境技 术 。例如在进行个体间的交配时需要考虑一定的条 件 ,即个体交配不完全是随机的 ,已证明其不仅能够 有效地保证群体中解的多样性 ,而且在问题求解的 收敛速度 、计算精度 、全局搜索能力等方面表现出明
2007年 7月 第 26卷 第 7期
机械科学与技术 M echanical Science and Technology for Aerospace Engineering
July 2007 Vol. 26 No. 7
不规则件优化排样的小生境遗传模拟退火算法
史俊友 ,冯美贵 ,苏传生 ,张 莹
(青岛科技大学 机电工程学院 ,青岛 266061)
宽 , H 为零件排样后在板材上达到的最大高度 ;式
(4)和式 (5)表示零件不能排在板材之外 。式 ( 1) 、
式 (2)表示该问题为多目标问题 ,而式 ( 3) ～式 ( 5)
表明该问题为多约束问题 ,因此可以采用小生境技
术求解该 NP完全问题 。
3 排样关键技术 311 零件预处理
由于材料利用率受不规则零件形状的影响 ,直 接将二维不规则零件作为排样对象 ,问题将变得十 分复杂 。通常不规则形状零件的优化排样一般采用 近似法即把不规则形状零件近似为矩形件来处理 , 从而简化为矩形件排样问题 。这种方法实现起来简 单方便 ,而且系统运行时间短 ,但如果在近似过程中 未充分考虑零件的形状特征 ,把不规则形状零件简 单地当成矩形件来处理 ,有可能导致材料利用率的
n
∑S j
Em ax
=
j=1
H ×W
(1)
m axz1 = L ×W - H ×W
(2)
Gj Δ( xj,Δyj,αj )∩Gk (Δxk ,Δyk ,αk ) =Φ, j≠k ( 3)
s. t. 0≤xji (Δxj,Δyj,αj ) ≤H ≤L, ji =0, 1, …, nj ( 4)
0 ≤ yji (Δxj,Δyj,αj ) ≤W , ji = 0, 1, …, nj ( 5) 式 (3)表示零件 j与零件 k互不重叠 ; xji和 yji为零件 j的第 i个顶点的坐标 , L 为板材的长 , W 为板材的
摘 要 :提出一种基于小生境遗传模拟退火算法求解不规则件排样问题的方法 。该方法首先充分 考虑不规则形状零件自身的形状特征 ,采用组合矩形包络算法将二维不规则零件的排样问题转化 为矩形件的排样问题 ,克服了以往简单采用最小包络矩形代替零件排样存在空白区域 ,从而导致材 料可能发生的利用率过低问题 ;然后利用遗传模拟退火算法及小生境技术相结合 ,寻找排样件在排 样时的最优次序及各自的旋转角度 ;最后用“最低水平线与填充算法相结合 ”策略的启发式排样算 法实现自动排样 。实例表明了该算法的有效性和实用性 。 关 键 词 :小生境技术 ;遗传模拟退火算法 ;组合矩形包络算法 ;不规则件 ;优化排样 中图分类号 : TP39117 文献标识码 : A 文章编号 : 100328728 (2007) 0720940205
图 1 空白区域填充
白区域的定位和
零件在空白区域的包含性问题 ,如图 1所示 。
(2) 在确定零件的外包围矩形定位位置后 ,以
被排零件代替矩形包络 ,对排样的零件拓扑关系不
作调整 ,只改变零件之间的位置和零件的姿态 。用
状态搜索法进行局部优化 ,即右边的零件依次作旋
转 ,以不同的姿态去接近左下角的零件 ,比较各种零
收稿日期 : 2006 08 04 作者简介 :史俊友 (1970 - ) ,男 (汉 ) ,山东 ,教授 ,博士 , qingdaoshijunyou@163. com
第 7期
史俊友等 :不规则件优化排样的小生境遗传模拟退火算法
941
解 ,通过研究解和邻域结构从理论上保证算法以概 率 1收敛到全局最优解的特点 ,因此具有较强的局 部搜索能力 ,并能使搜索过程避免陷入局部最优解 。 但模拟退火算法把握搜索过程的能力不强 ,从而使 得模拟退火算法的运行效率不高 。近年来 ,许多研 究人员把不规则零件当成转化为矩形排样来处理 , 这种方法简单易行 ,但由于没有充分考虑零件具体 的外形特征 ,会导致材料利用率的降低 。
表示为
Gj
(Δxj
,
Δyj
,
α j
)
。设
宽度
为
W ,长度为
L的
板材上排放给定的排样件 。零件种类数为 N; 第 j
个零件的长度为 L j,宽度为 W j,数量为 M j, Sj 为零件 j的最小包络矩形面积 。零件沿板材宽度方向进行
排放 ,零件排样后在板材上所达到的最大高度为 H。
定义排样布局的原材料利用率为 Emax , Emax越 大板材的利用率越高 , 板材余料为 maxz1 。则零件 优化排样的模型为
显的效果 ,是一种较有效的方法 [ 3～6 ] 。
2 排样模型
由于零件都是刚体 ,一个零件在板材上的定位
实际上只需 3个参数 [ 7 ]就可完全确定了 。这 3个参