文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 基于遗传模拟退火算法的不规则多边形排样
侵权投诉

基于遗传模拟退火算法的不规则多边形排样

5期陈勇等:基于遗传模拟退火算法的不规则多边形排样

599

平面最优布局的优化问题,广泛应用于服装、制鞋、船舶、钣金等工业生产中,以提高材料利用率,降低生产成本.矩形排样问题由于其广泛的应用和比较简单的几何特征,研究工作开展得比较早,并且可使

[l][2]

用一些数学规划技术,如线性规划、动态规划、[3][4-5]整数规划、整数线性规划等.但是,由于这些

直方向的移动直至无法再向左或者向下移动.启发式思想的本质是模拟人的智能行为,而排样对象的几何表达方式则是算法实现的关键.2.1

排样对象的几何表达

不规则形状的排样件及板料的几何轮廓由直线段和曲线段组成,因为曲线段可以按一定的精度离散成直线段,所以排样对象最终为可能带有内孔特征或者无效区域的多边形.

设G()为排样件G旋转角度后的图形,

数学规划技术的计算量大,因此不能处理不规则形

[6]

状的排样问题.自Adamowicz第一次提出对不规则排样问题的启发式算法的思想之后,许多学者在

这方面做了大量的研究工作.Yanasse等[7]

提出了基于某种优先级规则的顺序启发式算法,该算法只考虑一种确定的排样顺序,没有多种结果的相互比较,所以其给出的往往只是准优解.基于这种局限性,一些学者尝试用人工神经网络、模拟退火、遗传算法等人工智能方法结合启发式算法求解,并且取

得了很好的效果.Jakobs[8]将遗传算法和启发式算法应用于单张矩形板料上的多边形排样问题中,其

中遗传算法负责给出一个最佳的排样顺序样,启发式算法负责排样的实现.RemeshBabu等[9]

同样利用遗传算法和启发式算法给出了多张矩形板料上的矩形件排样.Han和Na[l0]

将神经网络和模拟退火技术应用于不规则形状的排样件在单张矩形板料上的排样,他们首先利用神经网络技术初始生成一个认为好的布局,然后用模拟退火技术通过平移、旋转等动作逐步改善这个布局.

本文的排样问题是若干个不规则排样件在板料上的排样,问题具有一般性,即排样对象的形状和角度等没有任何限制,而且还可能具有内孔特征或者无效区域.在处理这些极度不规则的排样对象时,使得本来就属于NP完全难题的排样问题变得更加复杂.目前,已有学者提出了一些几何表达方式来

降低问题的复杂性[ll-l3].在本文中,

我们在设计启发式排样算法的同时也提出了一种离散的几何表达方式,可以完全忽略高度不规则形状带来的复杂性影响,以提高启发式算法的效率.

2基于BL策略的启发式排样算法

我们采用遗传模拟退火算法,通过全局优化概率

搜索来产生最佳的排样次序和每个排样件的旋转角度,然后用启发式排样算法进行定位,实现自动排样.

启发式算法采用众所周知的左下角(Bottom-Left-condition,BL)

策略[l4]

,每一个排样件从板料的右上角开始向板料的左下角平移,重复水平和垂

!!G(!)

最大和最小的x,y坐标值分别为Xmax,Xmin,Ymax,Ymin.以间距为lmm的水平扫描线顺序扫描G(!)的多边形区域,经过G(!)的扫描线条数N=int(Ymax-Ymin).计算扫描线与多边形的相交区间,对于一条扫描线,可以分为4个步骤实现:

Stepl.求交.计算扫描线与多边形各边的交点.Step2.交点取舍.交点中,

如果是多边形的局部最高点或者局部最低点的顶点(极值点),交点算作零个或者两个交点;如果是顶点但不是极值点,交点只算一个.

Step3.排序.把所有交点按递增顺序进行排序.Step4.交点配对.第一个与第二个,

第三个与第四个……每对交点代表扫描线与多边形区域的一个相交区间.

这样,排样件可以看作是由一系列水平线段区间组成.如图l所示

基于遗传模拟退火算法的不规则多边形排样

.

a

基于遗传模拟退火算法的不规则多边形排样

若干扫描线与多边形的相交区间

b多边形的扫描区间表示示意

图l通过扫描线相交多边形来构造扫描区间

对于板料的扫描区间表示,我们增加一个脏位标志(DirtyFiag,DF),板料多边形有效区域内的扫描区

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email