学位论文 > 优秀研究生学位论文题录展示
圆形件排样优化算法及其并行实现方法研究
作 者: 赵政宝
导 师: 楚纪正
学 校: 北京化工大学
专 业: 控制科学与工程
关键词: 圆形件排样 NP问题 启发式方法 单亲遗传算法 并行计算
分类号: TP301.6
类 型: 硕士论文
年 份: 2012年
下 载: 81次
引 用: 0次
阅 读: 论文下载
内容摘要
排样优化问题广泛存在于国民经济生产中的机械制造、木材服装加工、印刷排版和交通运输等行业,采用排样优化技术实现对这些行业生产及运营各环节资源的优化利用,已成为企业降低生产运营成本,提高经济效益的重要手段之一。排样优化问题是具有极高计算复杂度的NPC类问题,研究其求解方法,不仅可以满足求解生产实践中排样优化问题需要,同时也为其他NPC类问题求解方法研究提供了重要的理论依据。因此,开展排样优化问题求解方法的深入研究,对促进实践生产发展和推动计算科学理论进步都具有极其重要的价值和意义。圆形件排样优化问题普遍存在于工业生产和人们生活中,但相比于其他类型排样优化问题研究情况,其求解方法研究仍然较少,并且由于其排样件形状相对不规则,排样规律难寻,更加大了问题求解难度。本文在总结分析国内外研究现状及发展趋势基础上,分别对矩形容器内及圆形容器内圆形件排样,提出了一系列新的求解方法,主要工作及研究内容有:(1)针对矩形容器内圆形件排样优化问题求解,本文提出一种以启发式多策略布局为基础,基于二分搜索和单亲遗传算法驱动的混合算法(PGA-BOFA)。算法基于一个嵌套双重迭代过程实现:内核OFA算法,通过定义紧凑度、可行度等优选参数,并引入优先占顶角、贴边界等布局策略,能够求得定长矩形容器内圆形件排样布局;在OFA基础上,内环BOFA算法利用二分搜索自适应找到在指定布局策略下的矩形容器最小长度;外环通过单亲遗传算法迭代进化,动态改变BOFA算法运行的布局策略,驱动整个算法运行,以扩大搜索解空间,提高求解质量。(2)对于圆形容器内圆形件排样优化问题,根据排入容器和排样件特点,本文通过定义伪边、伪顶角等概念,提出了对圆形容器进行拟矩形划分的设计思想,并设计了适用于问题求解的布局策略,使得PGA-BOFA算法同样可以用于圆形容器内圆形件排样优化问题求解。(3)根据PGA-BOFA算法隐含的并行性特点,并结合HPC系统高速并行性,基于并行分而治之思想,本文设计实现适用于求解圆形件排样优化问题的并行PGA-BOFA算法。算法基于主从式-粗粒度并行模型,采用多种群不同控制参数同时进化方式,结合最优解收集协同处理及子种群个体整体迁移策略,不仅加强种群整体的多样性,同时避免盲目搜索,进一步提高算法搜索速度和质量。最后基于MPI技术在构建的HPC系统上实现了上述并行算法。通过大量算例的实验测试和仿真,对以上三种方法进行了验证和性能分析,结果表明其对圆形件排样优化问题求解是可行有效的。
|
全文目录
摘要 4-6 ABSTRACT 6-14 第一章 绪论 14-26 1.1 排样优化问题概述 14-18 1.1.1 排样优化问题研究背景 14-15 1.1.2 排样优化问题分类 15-18 1.1.3 排样优化方案质量评价 18 1.2 排样优化问题研究的工程应用及理论意义 18-20 1.3 排样优化问题国内外研究现状及发展趋势 20-23 1.3.1 国内外研究历史与现状 20-23 1.3.2 求解方法的研究趋势 23 1.4 本文主要研究内容、章节安排及创新点 23-26 1.4.1 主要研究内容和章节安排 23-24 1.4.2 论文的主要创新点 24-26 第二章 圆形件排样优化问题及其复杂度分析和求解方法综述 26-34 2.1 问题描述及数学模型 26-28 2.2 复杂性分析及求解难点 28-29 2.3 圆形件排样优化算法研究 29-33 2.3.1 BLP、RBLP、ABLP 和 GA-BH 算法 29-31 2.3.2 MHD 及 A1.0-5 和 B1.0-5 31-32 2.3.3 ASA 及 HGA-ASA 32-33 2.4 求解算法性能评价指标 33 2.5 小结 33-34 第三章 求解矩形容器内圆形件排样的 PGA-BOFA 算法 34-66 3.1 基于顺序定向填充排样优化算法 34-41 3.1.1 概念定义及符号说明 34-39 3.1.2 布局策略 39 3.1.3 OFA 算法 39-40 3.1.4 算例实验 40-41 3.2 基于二分搜索驱动的 BOFA 算法 41-44 3.2.1 BS 及 BOFA 算法 41-43 3.2.2 算例实验 43-44 3.3 基于单亲遗传算法的 PGA-BOFA 算法 44-54 3.3.1 遗传算法概述 45-47 3.3.2 单亲遗传算法概述 47-50 3.3.3 PGA-BOFA 算法 50-54 3.4 算法实验仿真 54-57 3.4.1 实验算例 54-55 3.4.2 实验结果 55-57 3.5 算法性能分析 57-65 3.5.1 选取范围 NS对算法性能影响 58-59 3.5.2 可行度对排样结果的影响 59-60 3.5.3 占顶角放置对排样结果的影响 60-62 3.5.4 贴边界放置对排样结果的影响 62-65 3.6 小结 65-66 第四章 圆形容器内圆形件排样求解算法研究 66-74 4.1 圆形容器拟矩形划分 66 4.2 概念定义及布局策略 66-68 4.2.1 概念定义 67-68 4.2.2 布局策略 68 4.3 圆形容器内排样优化问题求解算法 68-73 4.3.1 圆形容器内圆形件排样的 PGA-BOFA 算法求解 68-69 4.3.2 算例实验仿真 69-72 4.3.3 拟矩形贴边放置对排样结果影响 72-73 4.4 小结 73-74 第五章 并行 PGA-BOFA 算法及其在 HPC 系统的设计实现 74-92 5.1 单亲遗传算法并行化的可行性与必要性分析 74-75 5.1.1 单亲遗传算法具有隐含的可并行性 74-75 5.1.2 实施单亲遗传算法并行化处理的必要性 75 5.2 单亲遗传算法并行实现模型 75-77 5.2.1 主从式模型 75-76 5.2.2 粗粒度模型 76-77 5.2.3 细粒度模型 77 5.3 并行 PGA-BOFA 设计方案 77-80 5.4 基于 MPI 的并行 PGA-BOFA 算法程序设计实现 80-86 5.4.1 MPI 技术概述 81-82 5.4.2 基于 MPI 的并行 PGA-BOFA 算法程序设计 82-83 5.4.3 基于 MPI 的并行 PGA-BOFA 算法程序核心代码 83-86 5.5 并行 HPC 系统搭建及实验算例测试比较 86-91 5.5.1 基于 Blade Server 集群并行计算环境平台构建 86-87 5.5.2 实验算例测试及性能比较 87-91 5.6 小结 91-92 第六章 总结与展望 92-94 6.1 总结 92-93 6.2 展望 93-94 参考文献 94-98 致谢 98-99 研究成果及发表的学术论文 99-100 作者和导师简介 100-101 硕士研究生学位论文答辩委员会决议书 101-102
|
相似论文
- 基于CUDA的图像数字水印技术的研究,TP309.7
- 基于MPI的三维地层建模和可视化方法研究,TP391.41
- 基于并行计算的医学超声成像技术研究,TP391.41
- 遥感影像并行计算策略研究,TP751
- 基于GPU加速FDTD计算速度的研究与仿真,TN011
- 军事物流车辆管理信息平台的设计与实现,TP311.52
- 遗传算法在多核系统上的性能分析和优化,TP18
- 图像检索的并行计算方法与系统,TP391.3
- GPU加速的粒子滤波PET图像重建算法,TP391.41
- 基于MPI和OpenMP的三维FDTD并行算法的研究,TN011
- 基于单亲遗传算法的RoboCup机器人足球比赛策略研究,TP242.6
- 自适应火灾应急预案调整研究,X928.7
- 分布式文件存储与检索平台的设计与实现,TP333
- 多核模式下地震勘探并行计算研究,TP338.6
- 基于多核环境下受限Voronoi图的研究与实现,TP391.41
- 基于置信度传播的立体匹配算法研究,TP391.41
- 基于NCES框架的网络中心企业应用服务体系结构与关键技术研究,TP393.09
- 基于.NET的高压电网继电保护整定计算系统的研究,TM774
- 复杂事故树定性与定量分析算法研究与应用,X913.4
- 军用物流中心选址研究,E234
- 多重幻方的构造与若干问题研究,O157
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|