改进的遗传算法在异形件优化排样中的应用(包络矩形)

摘 要 :对于二维不规则图形零件在排样区域上的最优排列 ,也就是对二维不规则图形的计算机自动排样算法进行优化的问题 。采 用矩形包络算法 、遗传算法和模拟退火算法相结合 ,寻找排样件在排样时的最优次序及各自的旋转角度 ,再用基于“最低水平 线 ”策略的启发式排样算法实现二维不规则图形零件自动排样 ,从而得到满意的优化排样结果 。
第 3步 :在新 newpop1 ( k + 1)中计算适应函数 fi ( Tk ) = exp [ ( fm in - fi ) / Tk ] ,其中 fm in是 newpop1 ( k + 1 )中的最小值 ; 由适应函数决定的概率分布从 newpop1 ( k + 1)中随机选 max2 pop个染色体形成种群 newpop2 ( k + 1) 。
·62·
3 遗传模拟退火算法
排样件的排样次序和各自的旋转角度是影响布局效果至 关重要的因素 ,如何确定它们以产生最优的排样布局是一个 NP完全难题 。采用人工智能领域中的遗传模拟退火算法 ,通 过全局优化概率搜索来产生最佳的排样次序和每个排样件的 旋转角度 。 3. 1 遗传模拟退火算法的设计思想
遗传模拟退火算法 ,遗传模拟退火算法是将遗传算法与 模拟退火算法相结合而构成的一种优化算法 ,引入局部搜索 过程 。是以遗传算法运算流程为主体流程 ,将模拟退火机制 融入其中 ,进一步调整优化群体 。整个算法的执行过程由两 部分组成 :首先通过遗传算法部分的进化操作 (侧重全局搜 索 )产生较优良的一个群体 ,再利用模拟退火算法部分的退火 操作 (侧重局部搜索 ) 来进行进一步基因个体的优化调整 。 其中模拟退火操作设计是针对一定规模群体中的每个基因个 体 ,对每个基因个体实施一定演变而产生恶化解的设计引用 遗传算法中的变异和倒位的思想 。这种算法思想策略 ,从对 全局最优解的搜索角度和算法的进化速度来提高模拟退火遗 传算法的性能 ,运行过程反复迭代 ,直到满足某个终止条件为 止 。其流程如下 [4 ] :
式 ( 2)表示零件 j与零件 k互不重叠 ; xji和 yji为零件 j的 第 i个顶点的坐标 , L 为板材长 , W 为板材的宽 ; 式 ( 3 ) 和式
(4)表示零件不能排在板材之外 。
虽然 ,提出零件优化排样模型 ,但对其模型的求解很难 。
笔者采用将不规则零件根据零件的外轮廓特征 ,求取零件最
(1) 最小包络矩形的定义 [3 ] :几何图形的包络矩形是指 完全包含图形上所有的点 、线 ,且各边均与图形相接触的矩 形 ,如图 1 ( a)中的矩形是该图形的一个包络矩形 ,而图 1 ( b) 的矩形则不是 。一个图形的包络矩形随图形的摆放位置和方 向的不同而不断变化 。同一个图形的包络矩形有无穷多个 , 其中面积最者称为最小包络矩形 。
第 19卷 2006年
第 10月
5期
M
ECHAN
机械研究与应用 ICAL RESEARCH & A
PPL
ICA
T
ION
Vo
l
19 No 5 2006210
改进的遗传算法在异形件优化排样中的应用 3
翟红岩 ,冯美贵 ,史俊友
(青岛科技大学 机电工程学院 ,山东 青岛 266061)
2 模型分析
2. 1 数学模型 [1, 2 ]
由于零件都是刚体 ,一个零件在板材上的定位实际上只
需 3个参数就可完全确定 。这 3个参数是该零件的一个给定
点在板材上的坐标 (X, Y)和该零件的排放角度 α。当这 3个
参数确定后 ,该零件的其它各顶点坐标都可由这 3 个参数计
算出来 。设 Gj ( j∈J, J 为零件集合 )为零件 j的图形 , ( xj, yj ) 为该零件给定点的坐标 , 则该零件在板材上的定位可表示为
n
6 Sj
Emax
=
i =1
L ×W
(1)
Gj (Δxj,Δyj,αj ) ∩ Gk (Δxk ,Δyk ,αk ) =Φ, j ≠ k (2)
S. t.
0 ≤ xji (Δxj,Δyj,αj ) ≤L ji = 0, 1, …nj
( 3)
0 ≤ yji (Δxj,Δyj,αj ) ≤W ji = 0, 1, …nj (4)
·61·
Vol 19 No 2006210
5
机械研究与应用
第
M ECHAN ICAL RESEARCH & APPL ICATION
19卷 第 5期 2006年 10月
2. 2 零件预处理 采用求取零件最小包络矩形的方法简化预处理 ,并对一
些形状互补的零件进行组合 ,确定零件间的最佳组合 ,使零件 区域在最小包络矩形中所占比例尽可能大 ,对组合后的图形 再求取最小包络矩形 ,同时记录各个不规则零件在相应最佳 包络矩形中的具体位置和各自排放的角度 ,二维不规则零件 排样问题就转化为矩形件排样问题 。
( College of m echan ica l & electrica l eng ineering, Q ingdao un iversity of science & technology, Q ingdao S handong 266061, Ch ina) Abstract: For the irregular shapes nesting p roblem in the given nest region of two - dimensional irregular graphics, that is to op tim ize the computer automated nest algorithm of two dimensional irregular graphics. Rectangle enclosure algorithm , genetic algorithm and simulated annealing algorithm are integrated to look for the best sequence of the shaped parts and each part′s op2 timum rotation, and " the lowest horizontal algorithm " is used to comp lete the automatic layout of two dimensional irregular graphical parts in this paper, the satisfactory results of op timal layout have been obtained. Key words: genetic simulated annealing algorithm; rectangle enclosure; op timal layout
因此笔者在矩形包络算法的基础上利用遗传模拟退火思 想从迭代群体中产生种群 ,使种群与最优解的偏离程度不断 缩小 ,从而有效缩小可行解搜索区域 ,缓解 SGA 的选择压力 , 增强算法收敛性 ,保证算法收敛到全局最优解 ,并利用基于最 低水平线算法的解码方法求解异形件排样的最优化问题 ,提 高板材的利用率 。
关键词 :遗传模拟退火算法 ;矩形包络 ;优化排样 中图分类号 : TP 391. 7 文献标识码 : A 文章编号 : 1007 - 4414 (2006) 05 - 0061 - 03
Applica tion of genetic sim ula ted annea ling a lgor ithm in optima l layout for irregular part Zhai Hong - yan, Feng M ei - gui, Shi Jun - you
小包络矩形的方法 ,将其近似矩形来处理 ,从而将不规则零件
的排样转化为矩形正交排样问题 。
3 收稿日期 : 2006 - 07 - 31 作者简介 :翟红岩 (1979 - ) ,女 ,山东聊城人 ,助教 ,研究方向 : C IMS, PDM。
© 1994-2007 China Academic Journal Electronic Publishing House. All rights reserved.
下述过程
:先将该
零件
以该
定
点为
轴作
角பைடு நூலகம்
度
为
α j
旋
转
,
再
将
定点 ( xj, yj )在板材作位移 (Δxj ,Δyj ) 。这时零件 j在板材上
的方位可表示为 Gj (Δxj ,Δyj,αj ) 。设 S j 为零件 j的面积 , 则 L
为板材的长 , W 为板材的宽 ,定义排样布局的原材料的利用率
Emax , Emax越大板材的利用率越高 。则零件优化排样模型为 :
性 。若多边形走向是逆时针 ,则当 S ( Pi - 1 Pi Pi +1 ) ≥0 时 Pi点 就为凸 ,而当 S ( Pi - 1 Pi Pi + 1 ) < 0时 Pi点为凹 。
图 2 多边形的包络矩形示意图
已证明只有使多边形的 2个凸点之间的边或连线平行于 坐标轴时 ,才有可能产生最小包络矩形 ,据此性质 ,可减少求 多边形最小包络矩形的计算量 。所谓最小包络矩形就是在多 边形所有的包络矩中面积最小的包络矩形 。则求取最小包络 矩形步骤 : ①求出多边形的所有凸点 ,依次连接得到新的凸多 边形 。 ②求出新凸多边形每条边与坐标轴所成的角 。 ③以凸 多边形每条边为基准 ,对应角为旋转角对其进行旋转 ,得到新 的凸多边形 。 ④求出新凸多边形的包络矩 ,并求出包络矩的 面积 。 ⑤求出所有包络矩形面积的最小者 ,此最小面积所对 应的包络矩即为原多边形所对应的最小包络矩 。图 2为多边 形的包络矩形示意图 。