圆形件排样优化算法及其并行实现方法研究

摘要

排样优化问题广泛存在于国民经济生产中的机械制造、木材服装加工、印刷排版和交通运输等行业，采用排样优化技术实现对这些行业生产及运营各环节资源的优化利用，已成为企业降低生产运营成本，提高经济效益的重要手段之一。排样优化问题是具有极高计算复杂度的NPC类问题，研究其求解方法，不仅可以满足求解生产实践中排样优化问题需要，同时也为其他NPC类问题求解方法研究提供了重要的理论依据。因此，开展排样优化问题求解方法的深入研究，对促进实践生产发展和推动计算科学理论进步都具有极其重要的价值和意义。
　　 圆形件排样优化问题普遍存在于工业生产和人们生活中，但相比于其他类型排样优化问题研究情况，其求解方法研究仍然较少，并且由于其排样件形状相对不规则，排样规律难寻，更加大了问题求解难度。本文在总结分析国内外研究现状及发展趋势基础上，分别对矩形容器内及圆形容器内圆形件排样，提出了一系列新的求解方法，主要工作及研究内容有:
　　 (1)针对矩形容器内圆形件排样优化问题求解，本文提出一种以启发式多策略布局为基础，基于二分搜索和单亲遗传算法驱动的混合算法(PGA-BOFA)。算法基于一个嵌套双重迭代过程实现:内核OFA算法，通过定义紧凑度、可行度等优选参数，并引入优先占项角、贴边界等布局策略，能够求得定长矩形容器内圆形件排样布局;在OFA基础上，内环BOFA算法利用二分搜索自适应找到在指定布局策略下的矩形容器最小长度;外环通过单亲遗传算法迭代进化，动态改变BOFA算法运行的布局策略，驱动整个算法运行，以扩大搜索解空间，提高求解质量。
　　 (2)对于圆形容器内圆形件排样优化问题，根据排入容器和排样件特点，本文通过定义伪边、伪顶角等概念，提出了对圆形容器进行拟矩形划分的设计思想，并设计了适用于问题求解的布局策略，使得PGA-BOFA算法同样可以用于圆形容器内圆形件排样优化问题求解。
　　 (3)根据PGA-BOFA算法隐含的并行性特点，并结合HPC系统高速并行性，基于并行分而治之思想，本文设计实现适用于求解圆形件排样优化问题的并行PGA-BOFA算法。算法基于主从式-粗粒度并行模型，采用多种群不同控制参数同时进化方式，结合最优解收集协同处理及子种群个体整体迁移策略，不仅加强种群整体的多样性，同时避免盲目搜索，进一步提高算法搜索速度和质量。最后基于MPI技术在构建的HPC系统上实现了上述并行算法。
　　 通过大量算例的实验测试和仿真，对以上三种方法进行了验证和性能分析，结果表明其对圆形件排样优化问题求解是可行有效的。

目录

声明

学位论文数据集

摘要

第一章 绪论

1．1 排样优化问题概述

1．1．1 排样优化问题研究背景

1．1．2 排样优化问题分类

1．1．3 排样优化方案质量评价

1．2 排样优化问题研究的工程应用及理论意义

1．3 排样优化问题国内外研究现状及发展趋势

1．3．1 国内外研究历史与现状

1．3．2 求解方法的研究趋势

1．4 本文主要研究内容、章节安排及创新点

1．4．1 主要研究内容和章节安排

1．4．2 论文的主要创新点

第二章 圆形件排样优化问题及其复杂度分析和求解方法综述

2．1 问题描述及数学模型

2．2 复杂性分析及求解难点

2．3 圆形件排样优化算法研究

2．3．1 BLP、RBLP、ABLP和GA-BH算法

2．3．2 MHD及A1.0-5和B1.0-5

2．3．3 ASA及HGA-ASA

2．4 求解算法性能评价指标

2．5 小结

第三章 求解矩形容器内圆形件排样的PGA-BOFA算法

3．1 基于顺序定向填充排样优化算法

3．1．1 概念定义及符号说明

3．1．2 布局策略

3．1．3 OFA算法

3．1．4 算例实验

3．2 基于二分搜索驱动的BOFA算法

3．2．1 BS及BOFA算法

3．2．2 算例实验

3．3 基于单亲遗传算法的PGA-BOFA算法

3．3．1 遗传算法概述

3．3．2 单亲遗传算法概述

3．3．3 PGA-BOFA算法

3．4 算法实验仿真

3．4．1 实验算例

3．4．2 实验结果

3．5 算法性能分析

3．5．1 选取范围Ns对算法性能影响

3．5．2 可行度对排样结果的影响

3．5．3 占顶角放置对排样结果的影响

3．5．4 贴边界放置对排样结果的影响

3．6 小结

第四章 圆形容器内圆形件排样求解算法研究

4．1 圆形容器拟矩形划分

4．2 概念定义及布局策略

4．2．1 概念定义

4．2．2 布局策略

4．3 圆形容器内排样优化问题求解算法

4．3．1 圆形容器内圆形件排样的PGA-BOFA算法求解

4．3．2 算例实验仿真

4．3．3 拟矩形贴边放置对排样结果影响

4．4．小结

第五章 并行PGA-BOFA算法及其在HPC系统的设计实现

5．1 单亲遗传算法并行化的可行性与必要性分析

5．1．1 单亲遗传算法具有隐含的可并行性

5．1．2 实施单亲遗传算法并行化处理的必要性

5．2 单亲遗传算法并行实现模型

5．2．1 主从式模型

5．2．2 粗粒度模型

5．2．3 细粒度模型

5．3 并行PGA-BOFA设计方案

5．4 基于MPI的并行PGA-BOFA算法程序设计实现

5．4．1 MPI技术概述

5．4．2 基于MPI的并行PGA-BOFA算法程序设计

5．4．3 基于MPI的并行PGA-BOFA算法程序核心代码

5．5 并行HPC系统搭建及实验算例测试比较

5．5．1 基于Blade Server集群并行计算环境平台构建

5．5．2 实验算例测试及性能比较

5．6 小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

研究成果及发表的学术论文

作者和导师简介

硕士研究生学位论文答辩委员会决议书