基于智能算法的二维下料问题的研究

论文摘要

下料问题就是将一系列形状各异的小零件在大的原材料上进行合理的几何组合,切割下料,确定下料方案,使得给定原材料的利用率最高,以达到节约材料,提高效益的目的。从数学计算复杂性理论看,优化下料问题是具有很高计算复杂性的NP完全问题,对于大规模的下料问题,不但人工排样无法做到真正的优化,即使采用计算机也必须开发高效的算法,才能达到较高的材料利用率。根据空间划分,下料问题分为一维、二维、三维,其中二维下料的应用最为广泛,目前研究最多的是矩形件的下料,并且与各种智能算法相结合,进一步对算法进行优化,已经提出了许多成熟的算法。针对矩形下料问题,本文研究的问题是在宽度确定、长度无限的矩形板材上切割出所需的三角形,使所消耗的板材长度尽可能小。本文利用图形扫描转换技术把三角形转化为零件的离散化几何表达,从而避免利用最小包络矩形排样的低利用率和三角形判交的复杂性,接着将基于这种扫描技术的启发式扫描算法作为底层算法,粒子群优化算法作为顶层算法,用底层算法接受顶层算法传递过来的优化参数,为下料的高效处理奠定基础。通过对三角形的优化下料进行仿真,实验结果证明本文提出的启发式粒子群优化算法具有较强的全局搜索能力,与将三角形拟合成最小包络矩形后进行下料相比,材料的利用率得到很大的提高。总之,启发式粒子群优化算法是一种高效、快速、准确的智能算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 选题的目的和意义
• 1.3 国内外研究的现状
• 1.3.1 国外研究现状
• 1.3.2 国内研究
• 1.4 论文的主要内容
• 1.5 论文组织结构
• 第二章 二维下料问题
• 2.1 二维规则形状下料
• 2.1.1 矩形下料数学模型
• 2.1.2 优化下料算法分析
• 2.1.3 矩形件定位策略
• 2.2 启发式算法
• 2.2.1 启发式算法简介
• 2.2.2 启发式算法分类
• 2.2.3 矩形件下料的启发式算法
• 2.3 二维不规则零件下料
• 2.3.1 不规则零件的特点
• 2.3.2 不规则零件的处理方法
• 第三章 正直角三角形下料的贪心算法
• 3.1 问题描述
• 3.2 基本概念
• 3.3 贪心算法
• 3.3.1 定义
• 3.3.2 贪心算法基本思想
• 3.3.3 贪心算法的三个准则
• 3.4 正直角三角形下料的贪心算法
• 3.4.1 算法的实现过程
• 3.4.2 实验结果
• 第四章 三角形下料的粒子群算法
• 4.1 启发式扫描算法
• 4.1.1 三角形几何离散化
• 4.1.2 三角形零件边表的建立
• 4.1.3 零件的扫描区间
• 4.1.4 板材的扫描区间
• 4.1.5 算法设计
• 4.2 粒子群算法
• 4.2.1 PSO算法简介
• 4.2.2 PSO参数控制
• 4.2.3 PSO的特点
• 4.3 启发式PSO优化算法
• 4.3.1 三角形下料参数的确定
• 4.3.2 粒子的构造
• 4.3.3 下料优化算法
• 4.3.4 仿真实验
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 攻读学位期间的研究成果
• 致谢