二维不规则零件优化排样系统的研究与开发

论文摘要

计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上,找出零件的最优布局,使得给定材料的利用率最高,以达到节约材料、提高效益的目的。从数学计算复杂性理论看,二维不规则样件的排样问题在理论上属于NP完全问题,因为存在实际形状的复杂性和计算上的复杂性,求解十分困难。传统的排样工作都是人工依靠经验进行的,时间长并且效果不理想。由于生产实际的需要,人们迫切需要利用现代科技来解决这一问题。目前研究较多的是规则零件（如矩形）的排样问题,对不规则件的研究较少。本文在分析国内外排样问题研究现状以及遗传算法局限性的基础上,针对传统遗传算法在求解排样问题时存在的不足,提出了基于最优保持的单亲遗传算法,用于求解二维不规则零件优化排样问题。单亲遗传算法取消了传统遗传算法的交叉算子,采取单亲繁殖方式。跟传统遗传算法相比,单亲遗传算法遗传操作简单,容易在遗传操作过程中处理约束条件,不要求初始群体具有多样性,不存在早熟收敛问题,计算效率高。通过两个实例验证,此方法所得结果在计算精度和计算时间上优于常用算法,表明此方法与传统方法相比具有更高的准确性、有效性以及可行性。本文利用单亲遗传算法固有的并行特性,将并行技术与单亲遗传算法相结合,在局域网中运行并行单亲遗传算法突破单台计算机计算能力的局限性,加快单亲遗传算法的运行速度。并行计算时所选用的模型为粗粒度的主/从模型,在计算过程中,将初始个体分别分配到各台slave机器上,然后slave机就开始计算,在slave机计算到一定的时间以后,依据一定的迁移策略,向master迁移个体,然后再从master机上取回其它机器的个体继续运算,直到满足中止条件为止。实验表明,分布式并行单亲遗传算法不但可以加快优化排样的速度,而且还可以提高解的质量。本文以Visual C++6.0作为开发平台,MFC作为工具库,开发具有实用价值的二维不规则零件优化排样系统。该系统具有良好的数据接口,可以和AutoCAD平台顺畅地交互数据;该系统具有友好的交互环境,用户可以方便地输入和调整参数;该系统具有快速的响应特性,可以在比较短的时间内得到排样结果;该系统具有优良的排样功能,可以得到比较好的排样结果;该系统易于维护,易于扩充。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 计算机辅助优化排样简介
• 1.2 排样问题的分类
• 1.2.1 一维排样问题
• 1.2.2 二维排样问题
• 1.2.3 三维排样问题
• 1.3 排样问题的研究背景和意义
• 1.4 排样问题的复杂性理论
• 1.4.1 排样问题难度简介
• 1.4.2 排样问题的计算复杂度
• 1.4.3 规则零件排样和不规则件排样难度分析
• 1.5 计算机辅助优化排样问题国内外研究现状及发展趋势
• 1.5.1 国外研究现状
• 1.5.2 国内研究现状
• 1.5.3 排样问题的发展趋势
• 1.6 论文背景及主要研究内容
• 1.6.1 论文背景
• 1.6.2 论文主要研究内容
• 第二章 常用优化算法简介
• 2.1 传统的寻优方法
• 2.1.1 处理完整解的算法
• 2.1.2 处理部分解或不完整解的算法
• 2.2 现代优化排样算法
• 2.2.1 禁忌搜索算法
• 2.2.2 模拟退火算法
• 2.2.3 人工神经网络算法
• 2.2.4 蚁群算法
• 2.2.5 遗传算法
• 2.2.6 粒子群算法
• 2.3 优化排样技术难点
• 2.4 本章小结
• 第三章 单亲遗传算法及其在二维不规则零件排样中的应用
• 3.1 遗传算法描述
• 3.1.1 遗传算法的原理
• 3.1.2 简单遗传算法模型
• 3.1.3 基本遗传算法的特点
• 3.1.4 遗传算法在排样中的应用
• 3.1.5 遗传算法解决二维不规则件排样问题的优越性
• 3.1.6 遗传算法在解决二维不规则件排样问题中的缺陷和改进
• 3.2 单亲遗传算法描述
• 3.2.1 单亲遗传算法概述
• 3.2.2 单亲遗传算法的基本概念
• 3.2.3 单亲遗传算法的实现步骤
• 3.2.4 单亲遗传算法的图式定理及隐含并行性
• 3.2.5 单亲遗传算法的收敛性
• 3.3 单亲遗传算法在二维不规则零件排样问题中的应用
• 3.3.1 染色体编码
• 3.3.2 个体适应度评价
• 3.3.3 初始种群的产生
• 3.3.4 遗传操作
• 3.3.5 实例分析
• 3.4 本章小结
• 第四章 并行单亲遗传算法及其在二维不规则零件排样中的应用
• 4.1 引入并行遗传算法的理由
• 4.1.1 遗传算法的并行性
• 4.1.2 并行遗传算法有利解决传统遗传算法的早熟现象
• 4.1.3 并行遗传算法可以提高运行速度
• 4.2 并行遗传算法的实现方案
• 4.2.1 主从式并行遗传算法
• 4.2.2 细粒度并行遗传算法
• 4.2.3 粗粒度并行遗传算法
• 4.3 迁移策略
• 4.4 并行遗传算法的性能与参数选取关系
• 4.4.1.遗传代数和群体规模
• 4.4.2 迁移策略
• 4.4.3 迁移率和迁移间隔
• 4.5 并行单亲遗传算法
• 4.6 分布式单亲遗传算法在排样中的应用
• 4.6.1 模型的实现环境
• 4.6.2 粗粒度模型的建立
• 4.6.3 粗粒度模型的实现方法
• 4.6.4 实例分析
• 4.7 本章小结
• 第五章 二维不规则排样系统的研究与开发
• 5.1 常见的系统分析方法
• 5.2 软件的开发平台
• 5.3 系统整体框架介绍
• 5.3.1 系统的主要功能
• 5.3.2 系统的功能模块
• 5.4 系统简介
• 5.4.1 排样系统界面
• 5.4.2 零件参数设置
• 5.4.3 板材参数设置
• 5.4.4 排样参数设置
• 5.4.5 排样结果与统计信息的显示
• 5.4.6 排样结果的保存
• 5.5 本章小结
• 第六章 总结与展望
• 参考文献
• 作者在攻读硕士学位期间的主要研究工作
• 致谢