提高资源利用效率和应用计算机技术是现代船舶制造工业实现“绿色造船”模式、增强造船企业的国际竞争力的主要方法和途径。排样优化技术则是工业产品设计、制造及使用中如何节约原材料、优化利用资源的重要手段。运用计算机技术实现排样自动化和智能化,将很大程度地提高劳动效率和资源利用率,因此对优化排样问题的研究具有重要经济意义和社会效益。优化排样问题就是将一系列形状各异的零件排放在给定的原材料上,在满足一定工艺要求或约束的条件下寻找出零件的最优布局,以达到原材料利用率最大的优化目标,具体到不同的行业以及切割、排样环境,表现为不同的约束形式。从数学计算复杂性理论看,优化排样问题属于组合优化问题和NP完全问题,它很难用单一的知识模型(如数学模型)来精确表达,对于二维不规则零件的排样优化,零件形状的复杂性将使得计算求解十分困难。特别的,大规模规则件排样和不规则件排样问题随着问题规模的增大,计算复杂度更是飞速增长。如何缩短排样时间同时提高板料利用率,是该问题研究的难点,也是本文讨论的重点。针对目前排样问题中存在的难点和关键问题,本文围绕排样图形预处理、图形入排控制、图形碰靠技术三个方面进行了深入的研究,提出了一系列解决方案和算法,并通过开发的船体建造板材智能排样系统进行了验算和分析,研究成果和创新点可概括如下:(1)图形入排控制算法优化1)由于一般的遗传算法存在早熟收敛问题,本文利用基于排挤机制的小生境技术对算法进行改进,同时根据排样编码的具体含义,给出了改进的免疫浓度定义,通过改进小生境免疫遗传算法从而散步解,避免陷入局部最优。并将其应用于计算机辅助排样领域,将改进的免疫因子和小生境遗传算法相结合,用于求解矩形件及不规则件的排样问题。2)针对圆形包络的二维不规则件排样问题,本文提出一种基于已入排圆形重心最低规则的圆弧搜索方法作为改进的解码方法(ASALC,Arc Search Algorithm based on the lowest center)。在使用改进遗传算法智能寻优的基础上,在优化计算过程中运用基于圆形包络的新解码算法ASALC将排样序列转化为排样图。3)排样优化问题中混合算法的改进研究及实现。(2)碰靠技术研究与改进。对于基于轮廓矢量信息图形的碰靠技术研究:根据船体建造板材套料系统开发过程中的需要和实例碰靠分析,提出判距-碰靠思路下的基于矩形包络的不规则件碰靠算法和不规则件最佳吻合碰靠定位算法;构建判交-分离思路下的一种碰靠方法——基于基础几何图元的不规则件碰靠技术。对于基于位图的碰靠技术:在对基于位图的图形表示特点进行分析的基础上,对比研究了基于位图的三种碰靠实现模型,给出了碰靠算法选择原则。(3)图形预处理技术的改进对二维不规则零件的包络矩形求取方法进行了改进,提出了一种改进的快速求取方法,可以有效地减少计算量,加快运算速度。在对船体零件不规则图形聚类分析的基础上,根据提取的零件图形聚类特征值筛选出同类或相似类零件参与优化排样过程,然后通过同类零件组合(拆分)、其他异类零件(如特殊形状或面积较小的零件)进行快速填充等方法进行图形的预处理。本课题与广州文冲船厂合作,以自动、交互排样为一体,设计开发出船体建造板材套料系统,并实现排样零件的数据信息管理。