矩形件排样问题广泛存在于机械、家具、服装等国民经济行业,解决好该问题可以节省原材料,简化生产工艺,降低生产成本,增加企业效益。对于许多不规则零件的排样问题,也可通过计算机的图形处理技术将其转化为矩形件排样问题。矩形件带排样问题(RSPP)是指将给定的一定数量的矩形件P1 , P2 ,…, Pn排放在定宽无限高的板材Q中,使所占据板材的高度最小。它是计算机辅助排样的一个重要分支。但RSPP在理论上是属于高计算复杂性的NP完全问题,在问题规模较大时,很难用精确算法求得最优解。因此,研究RSPP具有重要的实用和理论价值。遗传算法是基于生物进化和随机选择的全局搜索优化计算技术,它模拟生物进化的基本过程,用数码基因串来类比生物中的染色体,通过选择、交叉、变异等遗传算子来仿真生物的基本进化过程,进化若干代以后,使最优异染色体所代表的问题解逼近问题的全局最优解或近优解。多种群遗传算法采用多个种群代替单一种群,其中每个子种群按各自不同的进化策略和遗传操作并行独立进化。进化过程中可以选取和保留每个子种群的优秀染色体,就可以在保持优秀染色体进化的稳定性的同时加快进化速度,避免单一种群进化过程中出现的过早收敛现象。基于上述考虑,本文以多种群遗传算法为基础,提出了一种基于遗传算法求解RSPP的新算法。通过大量的实例测试,验证了该算法的有效性。本文的主要工作和创新点如下:首先,改进了一种矩形件近似排样算法。对中外学者提出的四种近似排样算法进行比较和分析,在总结其优缺点的基础上,针对递减排序的矩形序列,对基于最低水平线的搜索算法进行了改进,称为基于最低水平线的择优插入算法。改进算法在零件排放过程中,将最低水平线的长度先与当前待排放矩形件的长度(本文定义矩形件平行X轴的方向称为长度,另一边称为宽度)比较,若最低水平线的长度大于矩形件的长度,将矩形件排放在此位置;否则将最低水平线的长度与当前矩形的宽度比较,若最低水平线的长度大于矩形件的宽度,将矩形件旋转90度排放在此位置。若最低水平线的长度均小于当前矩形件的长度和宽度,即说明当前矩形件不能放到最低水平线上,则在排样序列的当前位置向后搜索,选择一个满足排放条件并且长度或者宽度与最低水平线的长度最接近的矩形件(称为最优零件)进行合理排放;否则,更新最低水平线。将搜索到的最优零件直接插入到当前排放位置,不更改后续矩形的序列。算法可以使得零件之间排放紧凑,降低排样高度,在一定程度上提高材料利用率。其次,将基于最低水平线的择优插入算法和简化的多种群遗传算法结合,设计了一种采用两个种群并行进化的遗传算法求解RSPP的新算法。矩形件排样问题中如何产生排样序列是一个关键的问题,许多学者应用遗传算法,模拟退火算法等算法产生排样序列,再将产生的排样序列与某种矩形件近似排样算法结合求解矩形件排样问题,取得了较好的排样效果。多种群遗传算法是在基本遗传算法基础上改进的一种算法。本文分析了多种群遗传算法,应用两个规模相当的子种群进行并行进化,其中两个子种群采用不同的初始策略。产生两种不同性质的矩形零件递减序列,并设计了求解RSPP的相关操作,定义了求解RSPP的适应度函数。将遗传算法产生矩形件的递减序列,按照本文的基于最低水平线的择优插入算法和本文的适应度函数得到序列的适应度值,并生成排样图。通过矩形零件序列的适应度值的比较,从而得到一个较优的排样方案。然后,规划和设计了排样系统的基本功能模块,开发了一个基于遗传算法的矩形件优化排样系统。通过大量实验测试,并将实验结果与应用遗传算法、模拟退火算法、随机算法求解矩形件排样问题的实验结果进行了比较和分析,验证了该系统的算法的有效性。最后,论文对己完成的工作进行了总结,提出了需要进一步改进的工作。