详情

原文传递船体板材排样优化算法研究与智能系统的设计

论文题名：	船体板材排样优化算法研究与智能系统的设计
关键词：	船体;板材排样优化;算法研究;智能系统;不规则零件;碰靠算法;排样问题;计算机技术;动态匹配;矩形;智能优化;遗传算法;最优布局;群集智能;排放;原材料;类零件;自动排样;优化问题;优化方法
摘要：	提高资源利用效率和应用计算机技术是现代船舶制造工业实现“绿色造船”模式、增强造船企业的国际竞争力的主要方法和途径。排样优化技术则是工业产品设计、制造及使用中如何节约原材料、优化利用资源的重要手段。运用计算机技术实现排样自动化和智能化，将很大程度地提高劳动效率和资源利用率，因此对优化排样问题的研究具有重要经济意义和社会效益。　　优化排样问题就是将一系列形状各异的零件排放在给定的原材料上，在满足一定工艺要求或约束的条件下寻找出零件的最优布局，以达到原材料利用率最大的优化目标。从数学计算复杂性理论看，优化排样问题属于组合优化问题和NP完全问题，它很难用单一的知识模型（如数学模型）来精确表达，特别对于二维不规则零件的排样优化，零件形状的复杂性将使得计算求解十分困难。针对目前排样问题中存在的难点和关键问题，本文从排样的优化理论、算法分析以及智能优化等方面进行了深入的研究，提出了一系列解决方案和算法，并通过开发的船体零件的智能排样系统进行了验算和分析，研究成果和创新点可概括如下：　　（1）基于启发式搜索策略，提出了一种改进的排样算法--剩余矩形的动态匹配法来求解不规则零件的矩形化排样。首先将同类零件进行最小包络矩的组合及组合零件的填充操作（基于零件互补组合的对称性特征）的预处理过程，将不规则件排样问题转化为（类）矩形件排样，然后依次对入排零件与未排放的剩余矩形区域进行宽度匹配计算和排样高度的调整，并以其匹配度最佳及最低排样高度作为排样布局的评估准则来实现了排样过程中的实时动态寻优。该算法通过搜索所有的剩余矩形空间与待排零件进行动态匹配，改进了现有的启发式算法（如最低水平线法等）在排样定位中只限于排样高度轮廓上的排放规则，使其进一步提高板材的使用效率，并基于匹配的原则对零件的入排序列进行了局部优化，在一定程度上实现了排样中定位与定序的协同思路。　　（2）基于不规则零件碰靠算法的思想，提出不规则零件的最佳吻合碰靠算法。将碰靠定位的参考区域限定在入排零件当前排样高度最低的未排空间内，零件以不同入排角度进行正交靠接排放和定位，碰靠的吻合度以零件定位后的最小静矩（或重心）以及排样高度作为排样定位的评估规则。该算法降低了自由碰靠算法及NFP（临界多边形）方法中零件平移碰靠计算的盲目性和复杂度，而且碰靠区域的设定有利于保证整体排样布局的最优。最小静矩的计算则减少了零件与板材边界的靠接中产生的无效区域，利于板材利用率的提高。通过交互排样中的点对点自动碰靠算法，实现零件以任意碰靠方向进行最优布局调整，为完善自动排样提供了有效的辅助作用。　　（3）针对待排零件图形的多样性，本文采用了零件的分类操作，建立阶段性排样优化策略：以设定的零件图形属性阈值筛选出同类或相似类零件参与优化排样过程，然后对其他异类零件（如特殊形状或面积较小的零件）进行快速填充处理。这一过程对于大小差异较大的入排零件，可有效调整排样布局和提高优化速度；针对遗传算法的易陷入局部最优而过早收敛的缺点，采用了基于免疫优化机制的混合遗传算法，通过免疫选择和接种疫苗操作来改善种群进化的多样性。　　（4）在对群集智能优化方法的收敛性、参数选择等算法特性分析的基础上，采用蚁群算法求解排样优化问题，并对算法的选择策略、局部搜索和信息素更新提出了有效的改进；以零件的排放次序和角度变异序列作为粒子运动速度重新构造粒子群算法，通过搜索零件的最佳定位来寻找最优排样布局。运用两种群集优化方法结合剩余矩形动态匹配的解码方法和碰靠算法实现不规则件的自动排样。相对于遗传算法的均匀进化过程，群集智能优化算法的信息反馈机制和分布式计算使得收敛速度更快且趋于全局最优。通过排样结果的比较和实算分析，证明了算法的有效性和可行性。　　（5）依据以上核心算法，以自动、交互排样为一体，设计开发船体零件二维智能排样系统，并实现排样零件的数据信息管理。
作者：	梁利东
专业：	船舶与海洋结构物设计制造
导师：	叶家玮
授予学位：	博士
授予学位单位：	华南理工大学
学位年度：	2009
正文语种：	中文